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

数据结构导论年月真题

0214220194

1、【单选题】下列几种时间复杂度中,阶数最小的是

O(log2n)

O(n)

A:

O(n2)

B:

O(1)

C:

答D:案：D

2、【单选题】栈和队列的共同特点是

都是线性表

先进先出

A:

后进先出

B:

只能插入操作

C:

答D:案：A

解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。两

者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；

而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的

线性表。

3、【单选题】假设一个10×10的上三角矩阵A按照列优先顺序压缩存储在一维数组B中,则

B数组的大小应为

50

55

A:

100

B:

101

C:

答D:案：B

4、【单选题】一个栈的入序列是a,b,c,d,e,则栈可能的输出序列是

edcab

deabc

A:

abcde

B:

dceab

C:

D:

答案：C

5、【单选题】假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断对空的

条件为

f==MULL

f==r

A:

r+1==f

B:

f+1==r

C:

答D:案：B

6、【单选题】如果结点A有2个兄弟结点,结点B为A的双亲,则结点B的度为

2

3

A:

4

B:

5

C:

答D:案：B

7、【单选题】二叉树的中序遍历中,结点P排在结点Q之前的条件是在二叉树中

P在Q的左边

P在Q的右边

A:

p是Q的祖先

B:

P是Q的子孙

C:

答D:案：A

8、【单选题】二叉树的第k层的结点数最多为

2k-1

2k+1

A:

2k-1

B:

2k+1

C:

答D:案：C

9、【单选题】A是7×4的二维数组,按行优先方式顺序存储,元素A[0][0]的存储地址为

1000,若每个元素占2个字节,则元素A[3][3]的存储地址为

1026

1028

A:

1030

B:

1032

C:

D:

答案：C

10、【单选题】在表长为n的顺序表上做删除运算,其平均时间复杂度为

O(1)

O(n)

A:

O(nlog2n)

B:

O(n2)

C:

答D:案：B

11、【单选题】在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为

e

2e

A:

n2-e

B:

n2-2e

C:

答D:案：D

12、【单选题】设顺序表的长度为n,则插入算法的平均移动次数约为

n

n/2

A:

n-1

B:

(n-1)/2

C:

答D:案：B

13、【单选题】设一组初始记录关键字序列为（13,18,24,35,40,50,62,83,90,115,134）,

则利用二分查找算法查找关键字90需要比较的关键字个数为

1

2

A:

3

B:

4

C:

答D:案：B

14、【单选题】以下排序方法中,稳定的是

直接插入排序和快速排序

快速排序和冒泡排序

A:

直接选择排序和冒泡排序

B:

冒泡排序和直接插入排序

C:

D:

答案：D

15、【单选题】对n个记录的文件进行快速排序,所需要的辅助存储空间的空间复杂度为

O(1)

O(n)

A:

O(1og2n)

B:

O(n2)

C:

答D:案：A

16、【问答题】若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对

次序仍然保持不变,则称这种排序方法是▲的。

答案：稳定

17、【问答题】在最坏情况下,即对几乎已是排好序的输入序列,快速排序算法的效率较低,

此时其时间复杂度近似为▲。

答案：O(n2)

18、【问答题】有一个整数序列,其输入顺序为20,30,90,-10,45,78,试利用栈将其输出序列

改变为30,-10,45,90,78,20,写出该整数序列进栈和出栈的操作步骤。（用push（x）表示进

栈,pop（x）表示x出栈）

答案：push(20),push(30),(1分)pop(30),push(90)(1分)push(-10),pop(-10),(1

分),push(45),pop(45),(1分)pop(90),push(78),(1分)pop(78),pop(20)(1分)

19、【问答题】分别写出题30图所示的二叉树的先序遍历、中序遍历和后序遍历三种访

问方式的结点访问序列。

答案：先序顺序：ABDEGCF(2分)中序遍历:DBGEACF(2分)后序遍历:DGEBFCA(2分)

20、【问答题】设有字符集{,A,B,C,D,E,F},各字符使用频率对应为{2,4,5,13,9,18},试画

出哈夫曼树（要求任一结点的左孩子权值小于右孩子）。

答案：

21、【问答题】已知散列表的长度为11,散列函数H（key）=key%11,采用线性探测法解决冲

突,试用关键字值的序列:75,25,80,35,60,46,50,55建立散列表。

答案：

22、【问答题】试用冒泡法对数列（45,73,12,23,52,5,38）进行递增排序,写出第1、2、

3、4趟排序结果,并给出冒泡排序算法的时间复杂度。

答案：第1趟:45,12,23,52,5,38,73(1分)第2趟:12,2345,5,38,52,73(1分)第3

题:12,23,5,38,45,52,73(1分)第4趟:12,5,23,38,45,52,73(1分)冒泡排序算法的时间

复杂度为:O(n2)(2分)

23、【问答题】以二叉链表作存储结构,试写出二叉链表的结构类型定义,并编写求二叉树叶

子结点个数的算法。

答案：

24、【问答题】写出直接插入排序算法。

答案：

25、【填空题】1976年瑞士计算机科学家NiklausWirth曾提出一个著名公式:程序=数据

结构+

答案：算法

26、【填空题】简单地说,数据结构是计算机▲数据和存储数据的方式。

答案：组织

27、【填空题】线性表中结点个数n称为▲

答案：表长

28、【填空题】线性表上的插入和删除运算限定在表的某一端进行的数据结构是▲。

答案：栈

29、【填空题】对稀疏矩阵进行压缩存储的目的是节省▲

答案：存储空间

30、【填空题】一个具有n个顶点的有向完全图的弧数为P=▲

答案：n(n-1)

31、【填空题】构造最小生成树的算法有两种:Prim算法和▲算法。