程序设计复试题

《程序设计复试题》由会员分享，可在线阅读，更多相关《程序设计复试题（6页珍藏版）》请在装配图网上搜索。

1、、填空题（每小题2分，共80分）1.A node in a tree that does not have any children is called 33(a) a leaf；(b) an internal node； (c) a root； (d) an empty node；2. 对于一棵深度为2的二叉树，它的总节点数：正门（a）至多7个（b）至多2个（c）节点数不限（d）至多4个3. 下面的伪码是对二叉树操作算法的片段:print( node )336HIif( there is a left child ) print( left child );print data;课if( t

2、here is a right child ) print( right child ); L 网这个算法是：（a）折半查找；（b）前序遍历；（c）中序遍历；（d）后序遍历;4. 下面哪个序列不是折半查找(二分查找)所访问的数值序列(a) 10, 20, 30, 40, 50；(b) 50, 40, 30, 20, 10；(c) 10, 20, 30, 15, 18；(d) 30, 50, 40, 45, 425. 递归函数可以调用自身多少次?（d）至多2 次;（a）只多1次；（b）任意次数；（c） 0次;6. 分析下面函数：int f( int n )if( n = = 0 ) return

3、 0;if( (n & 1) = = 0 ) return f(n/2); return f(n/2) + 1;调用函数f(10)的返回值是：(a) 1；(b) 3；(c) 5；(d) 2；int ff( int n, int m )if( n = 0 ) return m;return ff( n-1, m*n );(a)计算m * (n!)； (b)计算最大公约数；(c)计算最小公倍数；(d)计算(m + n)!；8. 给定长度为10的数组，归并排序由于对站所需的额外空间是(a) n+1；(b)n； (c)log n；(d)n2 ；9. 总的来说，哈希方法(hashing，也称散列方法)的

4、主要问题在于：(a)哈希函数难以计算；(b)哈希表的存取速度慢；(c)会发生冲突；(d)哈希表占很多内存；10. 对于一个大小为m含有n项的哈希表，它的负载(load)因子是：(a) m - n；(b) n + m；(c) m/n；(d) n/m ；11. 编译或执行下面C语言条件语句的结果是：if( x = expr );(a) expr的值赋给x,然后计算x的值作为if的条件；(b) 当且仅当expr的值为true(真)时，其值付给x;(c) 会出现编译错误；(d) 计算expr,然后与x的值相比较；12. 下面对p的声明，那一个是指向整数的指针：(a) int *p；(b) int p；

5、 (c) int &p；(d) int *p；13. 假设Thing是一个用户定义的类，B是Thing的一个实例，对于下面的代码段Thing A = B用到了类Thing中的哪一个成分：(a)赋值操作符；(b)析构函数；(c)构造函数；(d )复制构造函数；14. 下面对类的部分描述用于说明一种用户定义的实数实现：class RealNumber RealNumber( float x );RealNumber( float x, float y=0 );这段代码可能错在哪里？(a)在构造函数中不允许时有缺省值；(b)没有错误；(c)第二个构造函数与第一个不一致；(d)用两个实数参数无法创建一

6、个实数；(a)程序是一个完整的程序模块；(b)提供完善的代码复用；(c)获得高效率；(d)对封装的需求；16. 下面哪一条关于继承的叙述是正确的：(a) 它是一种重要的面向对象程序设计思想，但是在程序语言中无法实现；(b) 它提供了由现有类构造新类的完善方法；(c) 提供数据成员保护，阻止非法存取；(d) 使得一种类型表现出多种类型的行为；17. 在面向对象方法中，多态机制的目的是：(a)在现有的多个类的上层创建一个新类；(b)在运行时动态地确定一个对象的类型；(c)保护数据成员，阻止非法存取；(d)根据类的数据成员确定类的方法；18. 对于有n个节点e条边的图，如果用邻接表表示，则计算全部入

7、度的时间复杂度是:(a) O(n + e)；(b) O(nA2)；(c) O(nA3)；(d) O(n * e)；19. 结定结点的关键字序列(F、B、J、G、E、A、I、D、C、H),对它按字 母的字典顺序进行排列，快速排序的第一趟结果是：(a) (C、B、D、A、F、E、I、J、G、H)(b) (C、B、D、A、E、F、I、G、J、H)(c) (B、A、D、E、F、G、I、J、H、C)(d) (B、C、D、A、E、F、I、J、G、H)20. 在高级程序设计语言中，参数传递方法有传值调用(CALL BY VALUE)、引用调用 (CALL BY REFERENCE)、传名调用(CALL BY

8、 NAME)和宏扩展(MACRO EXPANSION),其 中，引用调用是指把实在参数的传递给相应的形式参数：(a)地址；(b)值；(c)地址和值；(d)名；21. 设W为一个二维数组，其每个数据元素Wij占用6个字节，行下标i从0到8,列 下标j从2到5,则二维数组W的数据元素共占用个字节。(a)480；(b)192；(c)216；(d)144；22. 堆是一种特殊的数据结构，下面哪一个是堆：(a)19,75,34,26,97,56； (b)97,26,34,75,19,56； (c)19,56,26,97,34,75； (d)19,34,26,97,56,75；23. 下面关于B树和B+树

9、的叙述中，不正确的是(a) B树和B+树都是平衡的多分树；(b) B树和B+树都是可用于文件的索引结构；(c) B树和B+树都能有效地支持顺序检索；(d) B树和B+树都能有效地支持随机检索；24. 在数据结构中，从逻辑上可以把数据结构分成：(a)动态结构和静态结构；(b)紧凑结构和非紧凑结构；(c)线性结构和非线性结构；(d)内部结构和外部结构；25. 下面程序段的时间复杂度是for (i=0;ivn;i+)for (j=0;jfront = = QU-rear；(b) QU-front! = QU-rear；(c) QU-front = = (QU-rear+1)%m0；(d) QU-fr

10、ont ! = (QU-rear+1)%m0；28. 表达式a*(b+c)-d的后缀表达式是(a)abcd*+-；(b)abc+*d-；(c)abc*+d-；(d)*-a+bc；29. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入 s结点，则执行：(a)s-next = p-next; p-next = s； (b)p -next = s-next; s-next = p；(c) q-next =s; s-next = p；(d) p-next =s; s-next = q；30. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是：(a) f-

11、next = s； f=s； (b) f-next = s； r=s； (c) s-next = r； r=s； (d) s-next = f； f=s；31. 将一个整数10002存到磁盘上，以ASCII码形式存储和以二进制形式存储，占用的 字节数分别是(a)2 和 2(b)2 和 5(c)5 和 2(d)5 和 532. 计算机算法是指(a)数值计算方法(b)对抽象数据结构的操作方法(c)非数值计算方法(d)解决问题的有限运算序列33. 将递归算法转换成对应的非递归算法时，通常需要使用(a)栈 (b)对列(c)链表 (d)树34. 树最适合用来表示(a)有序数据元素(b)无序数据元素(c)

12、元素之间具有分支层次关系的数据(d)元素之间相关联的数据35. 分析执行下面程序段后，变量a的值：a 0i 0j 100WHILE i = j DOBEGINa a + i + ji i + 1j j - 1END(a) 5100(b) 5000(c) 4900(d) 510136. 要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法 是：(a)分块查找(b)顺序查找(c)二分查找(d)散列查找37. 下面哪种技术和分布式的软件体系结构无关(a) CORBA规范 (b)中间件(c)客户/服务器结构(d)主程序/子程序结构38. 下面哪种说法是不合理的(a)程序=算法+数据

13、结构(b)软件=程序+文档(c)对象=继承+封装(d)构件=接口 +实现39. 被认为最有可能彻底解决“软件危机”的方法是：(a)软件复用 (b)对数据结构的标准化(c)面向对象技术(d)原型开发模型40. UML是指(a) 一种程序设计语言(b) 一种通用的建模语言(c) 一种开发工具(d) 家著名的软件公司二、在联欢会上，M个人围坐一圈，每人准备了一个节目。表演的顺序采用一种游戏的方 法产生：从圈内选出1人记为1号，按顺时针方向每人的号数依次记为2号、3号.M号。 由1号随机抽出一个号N (1v=Nv=M),然后从1号开始顺时针方向1、2、3顺序报数， 每报到N时，这个人就出来表演节目，表

14、演结束后，再从1开始继续向下报数，报到N的 人就出来表演。凡是表演过的人，下一次报数时就跳过去，这样继续下去，直到M个人都 表演完节目。请你编一个程序，用算法模拟这个过程，要求打印出表演节目人的顺序号。(15 分)三、有甲、乙、丙三个人和A、B、C三个不同的工作，每人一天只能干一个工作，且一个 工作每天必须一个人干。下表表示的是甲、乙、丙三个人在A、B、C三个不同的工作岗位 上工作一天所创造的价值：ABC甲305025乙353020丙454030说明：甲在A岗位上干一天所创造的价值为30,在B岗位上干一天所创造的价值为50请编程确定如何分配工作（甲、乙、丙三人在什么工作岗位），三人一天共同创造的价 值最多。（15分）四、键盘输入一个高精度的正整数N （N不超过200位），去掉其中任意S个数字后剩下的 数字按原左右次序组成一个新的正整数。编程对给定的N和S,寻找一种方案使得剩下的数 字组成的新数字最小。（20分）五、设G=（V,E）是一无向连通图。如果去掉G的某顶点后，G就不是连通图，这样的顶点 称为割点，试用深度优先搜索，编程确定一个无向连通图的所有割点。（20分）