2022年10月自考02142数据结构导论试题及答案含解析

数据结构导论年月真题

02142202210

1、【单选题】下面几种算法时间复杂度中，阶数最小的是

O(log2n)

O(n)

A:

O(n2)

B:

O(2n)

C:

答D:案：A

2、【单选题】双向循环链表（非空表）中，头结点的prior指向

头指针head

第一个结点

A:

任意一个结点

B:

最后一个结点

C:

答D:案：D

3、【单选题】下列关于线性表的顺序实现和链接实现特点的描述，_错误_的是

顺序表不需要预先分配存储空间

单链表的指针域需要占用额外空间

A:

对于定位运算，顺序表和单链表上的实现算法的时间复杂度相同

B:

对于插入、删除运算，在顺序表和链表中，都需要进行定位

C:

答D:案：A

4、【单选题】线性表采用链表存储结构时，内存中可用存储单元的地址

必须是连续的

部分必须是连续的

A:

一定是不连续的

B:

连续不连续都可以

C:

答D:案：D

5、【单选题】循环队列满条件为

CQ.rear==CQ.front

CQ.rear=CQ.front

A:

(CQ.rear+1)%maxsize==CQ.front

B:

C:

(CQ.rear-1)%maxsize=CQ.front

答D:案：C

6、【单选题】一个数组的第一个元素的存储地址是100，每个元素占2存储单元.则第5个

元素的存储地址是

100

108

A:

110

B:

120

C:

答D:案：B

7、【单选题】二叉树的基本形态有

3种

4种

A:

5种

B:

6种

C:

答D:案：C

8、【单选题】在有n个叶子结点的哈夫曼树中，其结点总数为

2n

n-1

A:

2n-1

B:

2n+1

C:

答D:案：C

9、【单选题】若一棵非空二叉树的先序序列与后序序列相同，则该二叉树可能的形状是

树中没有度为2的结点

树中只有一个根结点

A:

树中非叶结点均只有左子树

B:

树中非叶结点均只有右子树

C:

答D:案：B

10、【单选题】一个具有n个顶点的有向完全图的弧数为

n(n-1)/2

n(n-1)

A:

n2/2

B:

C:

n2

答D:案：B

11、【单选题】设图G中有n个顶点，e条弧，采用邻接表存储，则拓扑排序算法的时间复

杂度为

O(n)

O(n+e)

A:

O(n2)

B:

O(n×e)

C:

答D:案：B

12、【单选题】在长度为n的带有岗哨的顺序表中，进行顺序查找，查找不成功时，与关键

字的比较次数为

1

n-1

A:

n

B:

n+1

C:

答D:案：D

13、【单选题】查找表的逻辑结构是

集合

链表

A:

树形结构

B:

图状结构

C:

答D:案：A

14、【单选题】用线性探测法解决冲突，可能要探测多个散列地址，这些位置上的键值

一定是同义词

一定都不是同义词

A:

都相同

B:

不一定都是同义词

C:

答D:案：D

15、【单选题】快速排序最坏时间复杂度为

O(n2)

O(nlog2n)

A:

B:

O(log2n)

O(n)

C:

答D:案：A

16、【问答题】题29-1图和题29-2图为两种形态的二叉树。(1)题29-1图、题29-2

图各属于何种类型的二叉树？(2)二叉树通常有哪两类存储结构？

答案：(1)题29-1图为满二叉树；题29-2图为完全二叉树。(2)顺序存储结构和链式存

储结构。

17、【问答题】无向图如题30图所示。(1)列出所有简单回路。(2)写出邻接矩阵。

答案：

18、【问答题】设待排序的键值为45386690881025_45_。利用冒泡排序算法进行排

序，已知第一趟排序后的键值为384566881025_45_90，请写出后续每趟排序的结果。

答案：第二趟排序后3845661025_45_8890第三趟排序后38451025_45_66

8890第四趟排序后38102545_45_668890第五趟排序后10253845_45_66

8890第六趟排序后10253845_45_668890第七趟排序后10253845_45_66

8890

19、【问答题】设序列{dcbaheifg}和{abchdiefg}分别是一棵二叉树的先序序列和中序序

列，请画出该二叉树。

答案：

20、【问答题】给定表(Jan,Feb,Mar,Apr,May,Jul)。散列表的地址空间为0~10.设散列函数

H(x)=[i/2],其中i为键值中第一个字母在英语字母表中的序号，要求画出以线性探测法解决

冲突的散列表。

答案：

21、【问答题】设计算法在整型数组A[n]中查找值为k的元素，若找到，则输出其位置

i(0≤i≤n-1),否则输出一1作为标志。

答案：

22、【问答题】设计算法按先序次序打印二叉树T中叶子结点的值。

答案：

23、【填空题】在顺序表上做插入运算平均要移动表中______的结点。

答案：一半

24、【填空题】在单链表中，指针p所指的结点为最后一个结点的条件是______。

答案：p->next==NULL

25、【填空题】在估算算法空间复杂度时，一般只需要分析______所占用的空间。

答案：辅助变量

26、【填空题】若一维数组中的数据元素又是一维数组结构，则该数组称为______。

答案：二维数组

27、【填空题】线性表中如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点

有且仅有______个直接前驱。

答案：1

28、【填空题】在树中，从根开始算起，根的层次为______。

答案：1

29、【填空题】一棵判定树描述了一种______方法。

答案：分类

30、【填空题】设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和

M3。与森林F对应的二叉树根结点的右子树上的结点个数是______。

答案：M2+M3

31、【填空题】设栈的输入序列为12.3，若输出的第一个元素为3，则第二个输出的元素为

______。

答案：2

32、【填空题】无向图的邻接