计算机专业（基础综合）模拟试卷95.pdf

计算机专业(基础综合)模拟试卷95

一、单选题(本题共40题，每题1.0分，共40分。)

1、下列叙述中，确的是()。I.非空循环单链表head的尾结点p满足

p—*next-headII.带头结点的循环单链表的头指针为head.如果

hcad—ncxt—ncxt—ncxt=hcad成立，则该单链表的长度为3HI.静态链表中的指针

表示的是下一个元素在数组中的位置IV.将长度为n的单链表链接在长度为m的

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

A、仅I、n、in

B、i、□、m、w

c、仅i、m

D、仅i、m、w

标准答案：c

知识点解析：i：非空循环单链表的尾结点指针应该指向链表头，即

p—next=hcad,故I确。□:head指向头结点，head-next就指向第一个结点。

既然head^-next—next-next=head,说明此循环链表共有3个结点(包含头结

点)，而单链表中增加头结点仅仅是为了更方便地进行插入和删除操作，它并不存

储线性表的元素，故不能算为单链表结点，故此单链表的长度为2,故II错误，

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

中的位置，即数组下标，故in确。IV：将链表连接起来只需0(1)的操作，但找

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

错误。

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

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

A、A—B*(C—D)

B、(A—B)*C—D

C、(A—B*C)—D

D、(A—B)*(C—D)

标准答案：B

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

例。例如，求2x(5—3)+6/2的过程如表6—2所示。

衰6-2

当前字符运算符栈运算数枝说明

22

X2

(•(2

5•(25

-•(-25

3253

)22---出栈

,+4

出枝

6+46

146

2462

+43*/*出栈

7

出栈

从上述的计算过程中，考生可以自行对

A、B、C、D选项进行练习，运算数栈S的大小分别至少为4、2、3、3,只有B

选项满足条件。

3、设有一个n阶三对角线矩阵A[n][n],现把它的三条对角线上的非零元素按行存

放到一个一维数组B口中，存放到B5中(假定不用0下标)，那么B[k]

存放的元素的行号是()c

A、|(k+l)/3]

B、[(k+l)/3]

C、[(k+2)/3]

D、[(k+2)/3]

标准答案：B

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

«6-3特殊值推导过程

k123456789

A(i)UlA[l](2]