计算机专业(基础综合)模拟试卷107(题后含答案及解析) .pdfVIP

计算机专业（基础综合）模拟试卷107(题后含答案及解析)

题型有：1.单项选择题2.综合应用题

单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，

只有一个选项是最符合题目要求的。

1．下列叙述中，正确的是()。Ⅰ．非空循环单链表head的尾结点

p满足p→next=headⅡ．带头结点的循环单链表的头指针为head，如果head

→next→next→next=head成立，则该单链表的长度为3Ⅲ．静态链表中的指

针表示的是下一个元素在数组中的位置Ⅳ．将长度为n的单链表链接在长度

为m的单链表之后的算法时间复杂度为O(1)

A．仅Ⅰ、Ⅱ、Ⅲ

B．Ⅰ、Ⅱ、Ⅲ、Ⅳ

C．仅Ⅰ、Ⅲ

D．仅Ⅰ、Ⅲ、Ⅳ

正确答案：C

解析：Ⅰ：非空循环单链表的尾结点指针应该指向链表头，即p→next=head，

故Ⅰ正确。Ⅱ：head指向头结点，head→next就指向第一个结点。既然head

→next→next→next=head，说明此循环链表共有3个结点(包含头结点)，而单链

表中增加头结点仅仅是为了更方便地进行插入和删除操作，它并不存储线性表的

元素，故不能算为单链表结点，故此单链表的长度为2，故Ⅱ错误。Ⅲ：静

态链表中的指针所存储的不再是链表中的指针域，而是其下一个结点在数组中的

位置，即数组下标，故Ⅲ正确。Ⅳ：将链表连接起来只需O(1)的操作，但

找到具有m个结点链表的尾结点需遍历该链表，所以时间复杂度应该为O(m)，

故Ⅳ错误。

2．利用栈求表达式的值时，设立运算数栈S。假设栈S只有两个存储单元，

在下列表达式中，不发生溢出的是()。

A．A-B*(C-D)

B．(A-B)*C-D

C．(A-B*C)-D

D．(A-B)*(C-D)

正确答案：B

解析：利用栈求表达式的值时，需要设立运算符栈和运算数栈，下面仅举一

例。例如，求2×(5-3)+6／2的过程如表6-2所示。从上述的计算过程中，

考生可以自行对A、B、C、D选项进行练习，运算数栈S的大小分别至少为4、

2、3、3，只有B选项满足条件。

3．设有一个n阶三对角线矩阵A[n][n]，现把它的三条对角线上的非零元

素按行存放到一个一维数组B[]中，A[1][1]存放到B[1]中(假定不用0下标)，那

么B[k]存放的元素的行号是()。

A．[(k+1)／3]

B．[(k+1)／3]

C．[(k+2)／3]

D．[(k+2)／3]

正确答案：B

解析：这种题目最好采用特殊值法，推导过程可能比较繁琐，见表6-3。从

表6-3中的规律可得出答案。

4．已知一棵5阶B-树有53个关键字，并且每个结点的关键字都达到最少

状态，则它的深度是()。

A．3

B．4

C．5

D．6

正确答案：B

解析：根据B-树定义，m阶B-树除根结点之外，所有非终端结点至少有[m

／2]=3个子树，即至少有2个关键字。那么在每个结点的关键字最少的情况下，

根结点关键字个数为1，其他的结点关键字个数都为2。又第一层有1个结点，

第二层有2个结点，第三层有2×3个结点，第四层有2×3×3个结点。即：11+2

×2+2×3×2+2×3×3×2=53，根结点加非终端刚好四层，叶子结点那一层不算，

故树的深度为4。

5．下列说法中，正确的是()。Ⅰ．具有10个叶子结点的二叉树

中有9个度为2的结点Ⅱ．设高度为5的二叉树