XXXX年硕士研究生入学考试试卷
科目：程序设计与算法语言（总分150分）时间：180分钟
一、填空题（每小题2分，共80分）
1.Anodeinatreethatdoesnothaveanychildreniscalled
(a)aleaf；(b)aninternalnode；(c)aroot；(d)anemptynode；
2.对于一棵深度为2的二叉树，它的总节点数：
(a)至多7个(b)至多2个(c)节点数不限(d)至多4个
3.下面的伪码是对二叉树操作算法的片段：
print(node)
{
if(thereisaleftchild)print(leftchild);
printdata;
if(thereisarightchild)print(rightchild);
}
这个算法是：
（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,42
5.递归函数可以调用自身多少次?
(a)只多1次;(b)任意次数;(c)0次;(d)至多2次;
6.分析下面函数：
intf(intn)
{
if(n==0)return0;
if((n&1)==0)returnf(n/2);
returnf(n/2) 1;
}
调用函数f(10)的返回值是：
(a)1；(b)3；(c)5；(d)2；
7.假如n,m>=0，那么下面函数的功能是：
intff(intn,intm)
{
if(n==0)returnm;
returnff(n-1,m*n);
}
(a)计算m*(n!)；(b)计算最大公约数；(c)计算最小公倍数；(d)计算(m n)!；
8.给定长度为10的数组，归并排序由于对站所需的额外空间是
(a)n 1；(b)n；(c)logn；(d)n2；
9.总的来说，哈希方法（hashing，也称散列方法）的主要问题在于：
(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)intp[]；(c)int&p；(d)int*p；
13.假设Thing是一个用户定义的类，B是Thing的一个实例，对于下面的代码段
ThingA=B
用到了类Thing中的哪一个成分：
(a)赋值操作符；(b)析构函数；(c)构造函数；(d)复制构造函数；
14.下面对类的部分描述用于说明一种用户定义的实数实现：
classRealNumber{
...
RealNumber(floatx);
RealNumber(floatx,floaty=0);
};
这段代码可能错在哪里?
(a)在构造函数中不允许时有缺省值；(b)没有错误；
(c)第二个构造函数与第一个不一致；(d)用两个实数参数无法创建一个实数；
15.面向对象的程序设计最适合下面哪一种开发要求:
(a)程序是一个完整的程序模块；(b)提供完善的代码复用；
(c)获得高效率；(d)对封装的需求；
16.下面哪一条关于继承的叙述是正确的:
(a)它是一种重要的面向对象程序设计思想,但是在程序语言中无法实现；
(b)它提供了由现有类构造新类的完善方法；
(c)提供数据成员保护，阻止非法存取；
(d)使得一种类型表现出多种类型的行为；
17.在面向对象方法中，多态机制的目的是:
(a)在现有的多个类的上层创建一个新类；(b)在运行时动态地确定一个对象的类型；
(c)保护数据成员，阻止非法存取；(d)根据类的数据成员确定类的方法；
18.对于有n个节点e条边的图，如果用邻接表表示，则计算全部入度的时间复杂度是:
(a)O(n e)；(b)O(n^2)；(c)O(n^3)；(d)O(n*e)；
19.结定结点的关键字序列（Ｆ、Ｂ、Ｊ、Ｇ、Ｅ、Ａ、Ｉ、Ｄ、Ｃ、Ｈ），对它按字母的字典顺序进行排列，快速排序的第一趟结果是：
(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.在高级程序设计语言中，参数传递方法有传值调用(CALLBYVALUE)、引用调用(CALLBYREFERENCE)、传名调用(CALLBYNAME)和宏扩展(MACROEXPANSION)，其中，引用调用是指把实在参数的___传递给相应的形式参数：
(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 树的叙述中，不正确的是
(a)B树和B 树都是平衡的多分树；（b）B树和B 树都是可用于文件的索引结构；
(c)B树和B 树都能有效地支持顺序检索；(d)B树和B 树都能有效地支持随机检索；
24.在数据结构中，从逻辑上可以把数据结构分成：
(a)动态结构和静态结构；(b)紧凑结构和非紧凑结构；
(c)线性结构和非线性结构；(d)内部结构和外部结构；
25.下面程序段的时间复杂度是
for(i=0;i<n;i )
for(j=0;j<m;j )
A[j]=0;
(a)O(m n)；(b)O(m/2 n/2)；(c)O(m/n)；(d)O(m*n)；
26.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn,那么p1=n；pi为：
(a)i；(b)n=i；(c)n-i 1；(d)不确定；
27.判断一个循环队列QU（最多元素m0）为空的条件是：
(a)QU->front==QU->rear；(b)QU->front!=QU->rear；
(c)QU->front==(QU->rear 1)%m0；(d)QU->front!=(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->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和5
32.计算机算法是指
(a)数值计算方法(b)对抽象数据结构的操作方法
(c)非数值计算方法(d)解决问题的有限运算序列
33.将递归算法转换成对应的非递归算法时，通常需要使用
(a)栈(b)对列
(c)链表(d)树
34.树最适合用来表示
(a)有序数据元素(b)无序数据元素
(c)元素之间具有分支层次关系的数据(d)元素之间相关联的数据
35.分析执行下面程序段后，变量a的值:
a←0
i←0
j←100
WHILEi<=jDO
BEGIN
a←a i j
i←i 1
j←j-1
END
(a)5100(b)5000
(c)4900(d)5101
36.要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是：
(a)分块查找(b)顺序查找
(c)二分查找(d)散列查找
37.下面哪种技术和分布式的软件体系结构无关
(a)CORBA规范(b)中间件
(c)客户／服务器结构(d)主程序／子程序结构
38.下面哪种说法是不合理的
(a)程序=算法 数据结构(b)软件=程序 文档
(c)对象=继承 封装(d)构件=接口 实现
39.被认为最有可能彻底解决“软件危机”的方法是：
(a)软件复用(b)对数据结构的标准化
(c)面向对象技术(d)原型开发模型
40.UML是指
(a)一种程序设计语言(b)一种通用的建模语言
(c)一种开发工具(d)一家著名的软件公司
二、在联欢会上，M个人围坐一圈，每人准备了一个节目。表演的顺序采用一种游戏的方法产生：从圈内选出1人记为1号，按顺时针方向每人的号数依次记为2号、3号…M号。由1号随机抽出一个号N（1<=N<=M），然后从1号开始顺时针方向1、2、3…顺序报数，每报到N时，这个人就出来表演节目，表演结束后，再从1开始继续向下报数，报到N的人就出来表演。凡是表演过的人，下一次报数时就跳过去，这样继续下去，直到M个人都表演完节目。请你编一个程序，用算法模拟这个过程，要求打印出表演节目人的顺序号。（15分）
三、有甲、乙、丙三个人和A、B、C三个不同的工作，每人一天只能干一个工作，且一个工作每天必须一个人干。下表表示的是甲、乙、丙三个人在A、B、C三个不同的工作岗位上工作一天所创造的价值：
A
B
C
甲
30
50
25
乙
35
30
20
丙
45
40
30
说明：甲在A岗位上干一天所创造的价值为30，在B岗位上干一天所创造的价值为50…
请编程确定如何分配工作（甲、乙、丙三人在什么工作岗位），三人一天共同创造的价值最多。（15分）
四、键盘输入一个高精度的正整数N（N不超过200位），去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数字最小。（20分）
五、设G=(V,E)是一无向连通图。如果去掉G的某顶点后，G就不是连通图，这样的顶点称为割点，试用深度优先搜索，编程确定一个无向连通图的所有割点。（20分）
