自考02142《数据结构导论》真题(2022.4)_2.pdfVIP

自考02142《数据结构导论》真题及（2022.4）

自考02142《数据结构导论》真题及答案解析（2022.4）

1.[单选题]下列几种时间复杂度中，阶数最小的是（）

A.O(log2n)

B.O(n)

C.O(n2)

D.O(1)

2.[单选题]栈和队列的共同特点是（）

A.都是线性表

B.先进先出

C.后进先出

D.只能插入操作

3.[单选题]假设一个10x10的上三角矩阵A按照列优先顺序压缩在一

维数组B中，则B数组的大小应为（）

A.50

B.55

C.100

D.101

4.[单选题]一个栈的入栈序列是a，b，c，d，e，则栈可能的输出序

列是（）

A.edcab

1

B.deabc

C.abcde

D.dceab

5.[单选题]假定一个顺序存储的循环队列的队头和队尾指针分别为f

和r，则判断队空的条件为（）

A.f==NULL

B.f==r

C.r+1==f

D.f+1==r

6.[单选题]如果结点A有2个兄弟结点，结点B为A的双亲，则结点

B的度为（）

A.2

B.3

C.4

D.5

7.[单选题]二叉树的中序遍历中，结点P排在结点Q之前的条件是在

二叉树中（）

A.P在Q的左边

B.P在Q的右边

C.P是Q的祖先

D.P是Q的子孙

8.[单选题]二又树的第k层的结点数最多为（）

2

A.2k-1

B.2k+1

C.2k-1

D.2k+1

9.[单选题]A是7X4的二维数组，按行优先方式顺序存储元素A[0][0]

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

地址为（）

A.1026

B.1028

C.1030

D.1032

10.[单选题]在表长为n的顺序表上做删除运算，其平均时间复杂度

为（）

A.O(1)

B.O(n)

C.O(nlog2n)

D.O(n/2)

11.[单选题]在含n个顶点和e条边的无向图的邻接矩阵中，零元素

的个数为（）

A.e

B.2e

C.n2-e

3

D.n2-2e

12.[单选题]设顺序表的长度为n，则插入算法的平均移动次数约为（）

A.n

B.n/2

C.n-1

D.(n-1)/2

13.[单选题]设一组初始记录关键字序列为(13，18，24，35，47，50，

62，83，90，115，134)，则用二分查找算法查找关键字90需要比较

的关键字个数为（）

A.1

B.2

C.3

D.4

14.[单选题]以下排序方法中，稳定的是（）

A.直接插入排序和快速排序

B.快速排序和冒泡排序

C.直接选择排序和冒泡排序

D.冒泡排序和直接插入排序

15.[单选题]对n个记录的文件进行快速排序，所需要的辅助存储空

间的空间复杂度为（）

A.O(1)

B.O(n)

4

C.O(1og2n)

D.O(n2)

16.[填空题]1976年瑞士计算机科学家NiklausWirth曾提出一个著名

公式：程序=数据结构+____。

17.[填空题]简单地说，数据结构是计算机____数据和存储数据的方

式。

18.[填空题]线性表中结点个数n称为____。

19.[填空题]线性表上的插入和删除运算限定在表的某一端进行的数

损结构是____。

20.[填空题]对稀疏矩阵进行压缩存储的目的是节省____。

21.[填空题]一个具有n个顶点的有向完全图的弧数为=____.

22.[填空题]构造最小生成树的算法有两种:Prim算法和____算法。

23.[填空题]一棵树的结点个数最少为____。

24.[填空题]有K个叶子结点的哈夫曼树，其结点的总数为____。

25.[填空题]由二又树的后序序列和____序列，可以唯一确定一棵二

又树。

26.[填空题]二分查找算法的平均时间复杂度为____。

27.[填空题]若待排序的序列中存在多个记录具有相同的健值，经过

排序，这些记录的相对次序仍然保持不变，则称这种排序