计算机二级基础知识试题及答案

　　选择题-公共基础知识-数据结构与算法(共32题)

第1组

161) 下列叙述中正确的是

A)循环队列是线性结构

B)循环队列是线性逻辑结构

C)循环队列是链式存储结构

D)循环队列是非线性存储结构

答案：A

162) 设某棵树的度为3，其中度为3,2,1的结点个数分别为3,0,4。则该树中的叶子结点数为

A)7

B)8

C)6

D)不可能有这样的树

答案：A

163) 设有一个栈与一个队列的初始状态均为空。现有一个序A,B,C,D,E,F,G,H，先分别将序列中的前4个元素依次入栈，后4个元素依次入队;然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为

A)D,C,B,A,E,F,G,H

B)D,C,B,A,H,G,F,E

C)A,B,C,D,E,F,G,H

D)A,B,C,D,H,G,F,E

答案：A

164) 下列叙述中错误的是

A)具有两个以上指针域的链式结构一定属于非线性结构

B)具有两个以上叶子结点的数据结构一定属于非线性结构

C)具有两个根结点的数据结构一定属于非线性结构

D)具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构

答案：A

第2组

165) 下列结构中属于线性结构链式存储的是

A)双向链表

B)循环队列

C)二叉链表

D)二维数组

答案：A

166) 下列叙述中错误的是

A)循环链表的存储空间是连续的.

B)循环链表中有一个表头结点

C)循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点

D)循环链表实现了空表与非空表运算的统一

答案：A

167)度为3的一棵树共有30个结点，其中度为3,1的结点个数分别为3,4。 则该树中的叶子结点数为

A)15

B)16

C)14

D)不可能有这样的树

答案：A

168) 在长度为97的顺序有序表中作二分查找，最多需要的比较次数为

A)7

B)96

C)48

D)6

答案：A

第3组

169) 下列结构中属于非线性结构的是

A)二叉链表

B)二维数组

C)循环队列

D)双向链表

答案：A

【解析】二叉链表是二叉树的物理实现，是一种存储结构，不属于线性结构。故答案为A。

170) 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是

A)循环链表

B)双向链表

C)单向链表

D)二叉链表

答案：A

155) 在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为

A)0 或 1

B)0

C)1

D)队列满

答案：A

172) 设某棵树的度为3，其中度为3,1,0的结点个数分别为3,4,15。则该树中总结点数为

A)30

B)22

C)35

D)不可能有这样的树

答案：A

第4组

173) 下列叙述中正确的是

A)数组是长度固定的线性表

B)矩阵是非线性结构

C)对线性表只能作插入与删除运算

D)线性表中各元素的数据类型可以不同

答案：A

174) 在快速排序法中，每经过一次数据交换(或移动)后

A)能消除多个逆序

B)只能消除一个逆序

C)不会产生新的逆序

D)消除的逆序个数一定比新产生的逆序个数多

答案：A

175) 线性表的长度为n。在最坏情况下，比较次数为n-1的算法是

A)寻找最大项

B)同时寻找最大项与最小项

C)顺序查找

D)有序表的插入

答案：A

176) 设某棵树的度为3，其中度为2,1,0的结点个数分别为3,4,15。则该树中总结点数为

A)不可能有这样的树

B)30

C)22

D)35

答案：A

第5组

177) 下列叙述中错误的是

A)只有一个根结点和一个叶子结点的结构必定是线性结构

B)非空线性结构中只有一个结点没有前件

C)非空线性结构中只有一个结点没有后件

D)向量是线性结构

答案：A

178) 在希尔排序法中，每经过一次数据交换后

A)能消除多个逆序

B)只能消除一个逆序

C)不会产生新的逆序

D)消除的逆序个数一定比新产生的逆序个数多

答案：A

151) 带链栈空的条件是

A)top=bottom=NULL

B)top=-1 且 bottom=NULL

C)top=NULL 且 bottom=-1

D)top=bottom=-1

答案：A

180) 下列叙述中正确的是

A)所有的线性结构都可以采用顺序存储结构

B)能采用顺序存储的必定是线性结构

C)具有两个以上指针的链表必定是非线性结构

D)循环队列是队列的链式存储结构

答案：A

第6组

94) 设某二叉树中共有140个结点，其中有40个度为1的结点。则

A)该二叉树中有51个叶子结点

B)该二叉树中有50个叶子结点

C)该二叉树中有51个度为2的结点

D)该二叉树中有50个度为2的结点

E)不可能有这样的二叉树

答案：E

182) 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为

A)ABCDEFGHIJ

B)DGHEBIJFCA

C)JIHGFEDCBA

D)GHIJDEFBCA

答案：A

183) 设循环队列的存储空间为Q(1: 50)，初始状态为front=rear=50。经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为

A)48

B)49

C)1

D)0

答案：A

184) 设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为

A)780

B)820

C)40

D)41

答案：A

第7组

185) 设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是

A)希尔排序

B)循环链表中寻找最大项

C)有序链表查找

D)堆排序

答案：A

186) 设循环队列的存储空间为Q(1: 50)，初始状态为front=rear=50。经过一系列正常的操作后，front=rear-1。 为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为

A)0

B)1

C)49

D)50

答案：A

187) 设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为

A)DGHEBIJFCA

B)JIHGFEDCBA

C)GHIJDEFBCA

D)ABCDEFGHIJ

答案：A

188) 设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为

A)120

B)60

C)30

D)15

答案：A

第8组

189) 下列结构中为非线性结构的是

A)树

B)向量

C)二维表

D)矩阵

答案：A

190) 设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是

A)循环链表中寻找最大项

B)有序链表查找

C)堆排序

D)希尔排序

答案：A

159) 带链队列空的条件是

A)front=rear=NULL

B)front=-1 且 rear=NULL

C)front=NULL 且 rear=-1

D)front=rear=-1

答案：A

192) 设二叉树的后序序列为DGHEBIJFCA，中序序列为DBGEHACIFJ。则前序序列为

A)ABDEGHCFIJ

B)JIHGFEDCBA

C)GHIJDEFBCA

D)ABCDEFGHIJ

答案：A