考研计算机学科专业基础综合-42.doc

由天下分享时间：2025/1/5 17:58:33 加入收藏我要投稿点赞

考研计算机学科专业基础综合-42

(总分：149.96，做题时间：90分钟)

一、单项选择题(总题数：40，分数：80.00)

1.下列程序段的时间复杂度是 count=0;

for(k=1;k＜=n;k*=2) for(j=1;j＜=n;j++) count++;

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n)

（分数：2.00） A. B. C. D.

2.在具有n个结点的单链表中，下面的操作算法的时间复杂度为O(n)的是______。 A．遍历链表和求链表的第i个结点 B．在地址为P的结点之后插入一个结点 C．删除开始结点 D．删除地址为P的结点的后继结点

（分数：2.00） A. B. C. D.

3.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1=n，则Pi是______。 A．i B．n-i C．n-i+1 D．不确定

（分数：2.00） A. B. C. D.

4.已知一棵二叉树，它的第5层上最多含有结点数为______。 A．32 B．15 C．16 D．31

（分数：2.00） A. B. C. D.

5.在含有12个结点的平衡二叉树上，查找关键字为35(存在该结点)的结点，则依次比较的关键字有可能是______。

A．46，36，18，20，28，35 B．47，37，18，27，36 C．27，48，39，43，37 D．15，45，55，35

（分数：2.00） A.

答案见麦多课文库

B. C. D.

6.设二叉排序树中关键字由1～1000的整数构成，现要查找关键字为363的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是______。 A．2，252，401，398，330，344，397，363 B．924，220，911，244，898，258，362，363 C．925，202，911，240，912，245，363

D．2，399，387，219，266，382，381，278，363

（分数：2.00） A. B. C. D.

7.下列说法正确的是______。

A．任何有向网络(AOV网)拓扑排序的结果是唯一的 B．有回路的图不能进行拓扑排序 C．在AOE网中一定只有一条关键路径

D．一个正常的AOE网中只能有一个源点、一小汇点和一条关键路径

（分数：2.00） A. B. C. D.

8.下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度，可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是______。

（分数：2.00）

A. B. C. D.

9.当向一棵m阶的B-树作插入操作时，若一个结点中的关键字个数等于______，则必须分裂成两个结点，当向一棵m阶的B-树作删除操作时，若一个结点中的关键字个数等于______，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

A．m，m/2-2 B．m-1，m/2-1 C．m+1，m/2 D．m/2，m/2+1

（分数：2.00） A. B. C. D.