数据结构导论自考题模拟7.pdf

数据结构导论自考题模拟7

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

一、单项选择题(总题数：15，分数：30.00)

1.若评价算法的时间复杂度，比较对数阶量级与线性阶量级，通常______

（分数：2.00）

A.对数阶量级复杂性大于线性阶量级

B.对数阶量级复杂性小于线性阶量级√

C.对数阶量级复杂性等于线性阶量级

D.两者之间无法比较

解析：

2.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则最节省运算时间的存

储方式是______

（分数：2.00）

A.单链表

B.双链表

C.单循环链表

D.带头结点的双循环链表√

解析：[考点]本题主要考查的知识点是双循环链表。

双循环链表结构是一种对称结构，既有前向链，又有后向链，这就使得插入和删除的操作都很方便。有头

结点的链表：一般链表中每个结点存储一个或者一组数据，但是有头结点的链表的第一个结点是头结点，

头结点不存储数据，它的主要作用是方便插入操作。

3.非空带头结点的单循环链表的尾结点*P满足______

（分数：2.00）

A.p-＞next=head√

B.p-＞next=NULL

C.p=NULL

D.p=head

解析：[考点]本题主要考查的知识点为单循环链表。

尾结点的指针域指向头结点。如果是空表则有head-＞next=head。

4.设有一个5阶上三角矩阵A[1..5，1..5]，现将其上三角中的元素按列优先顺序存放在一维数组B[1..15]

中。已知B[1]的地址为100，每个元素占用2个存储单元，则A[3]的地址为______

（分数：2.00）

A.116√

B.118

C.120

D.122

解析：

5.设有一顺序栈s，元素s，s，s，s，s，s依次进栈，如果6个元素出栈的顺序是s，

1234562

s，s，s，s，s，则栈的容量至少应该是______

34651

（分数：2.00）

A.2

B.3√

C.5

D.6

解析：[考点]本题主要考查的知识点是顺序栈。

栈的出入原则是后进先出。从出栈顺序可知，在s出栈前，栈中的元素应为s、s、s，此时需3

6651

个位置才能满足需要。所以栈的容量至少应该是3。

6.设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1则T中的叶子数为______

（分数：2.00）

A.5

B.6

C.7

D.8√

解析：[考点]本题主要考查的知识点是树中的叶子数。

由树的性质可知，任意一棵树的结点总数等于所有结点的出度之和加1。可求得此树的出度之和为：

1*4+2*2+3*1+4*1=15。设叶子结点的个数为x，可得x+4+2+1+1=15+1，求得x=8。

7.下列有关二叉树的说法中正确的是______

（分数：2.00）

A.二叉树的度为2

B.一棵二叉树的度可以小于2√

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

解析：[考点]本题主要考查的知识点是二叉树。

结点没有分叉的二叉树的度是0。如果二叉树中的结点最多只有一个分叉，则二叉树的度为1。如果二叉树

中某个结点有两个分叉，则二叉树的度为2。

8.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为______

（分数：2.00）

A.24√

B.25

C.98

D.99

解析：

9.若采用邻接表存储结构，则图的深度优先有哪些信誉好的足球投注网站类似于二叉树的______

（