2021年4月自考02331数据结构试题及答案含解析

数据结构年月真题

0233120214

1、【单选题】下列选项中，不属于线性结构的是

线性表

双向链表

A:

循环队列

B:

二叉树

C:

答D:案：D

解析：二叉树不属于线性结构。线性结构是指数据元素之间存在一对一的关系，即每个元

素只有一个直接前驱和一个直接后继。而二叉树是一种非线性结构，它的每个节点最多有

两个子节点，分别称为左子节点和右子节点。这种分支结构使得二叉树的数据元素之间存

在多对一的关系，因此二叉树不属于线性结构。

2、【单选题】某线性表L含有n个元素，采用单循环链表保存，仅有尾指针指向链表的终端

结点。在最后一个结点之后插入一个结点及删除第一个结点的时间复杂度分别是

O(1)和O(1)

O(1)和O(n)

A:

O(n)和O(1)

B:

O(n)和O(n)

C:

答D:案：A

3、【单选题】下列应用中会用到栈的是

计算后缀表达式的值

图的广度优先遍历

A:

对数组进行希尔排序

B:

对散列表进行查找

C:

答D:案：A

4、【单选题】设栈初始为空，入栈序列为1，2，3，4，5，下列选项中，不可能得到的出栈

序列是

1，2，3，4，5

3，1，4，2，5

A:

4，3，2，5，1

B:

5，4，3，2，1

C:

D:

答案：B

5、【单选题】已知广义表LS=(((c，(d))，(e，(f)))，(g，h)，(m，n)))，head(LS)是

c

(c)

A:

(c，(d))

B:

((c，(d))，(e，(f)))

C:

答D:案：D

6、【单选题】设线性表采用顺序存储方式保存，每个元素占8个存储单元。第1个元素的存

储地址为200，则第5个元素占用的最后一个存储单元的地址是

239

240

A:

247

B:

248

C:

答D:案：A

7、【单选题】一棵完全二叉树T的全部k个叶结点都在同一层中，每个分支结点都有两个孩

子结点。T中包含的结点数是

k

2k-1

A:

k²

B:

2k-1

C:

答D:案：B

8、【单选题】设字符集中有n个字符，对其进行哈夫曼编码，得到的哈夫曼树的结点总数是

2n-1

2n

A:

2n+1

B:

不确定

C:

答D:案：A

9、【单选题】设图G的邻接矩阵A如下所示。G的各顶点的度依次是

1，2，1，2

2，2，1，1

A:

3，4，2，3

B:

4，4，2，2

C:

答D:案：C

10、【单选题】对题10-11图进行深度优先遍历，下列选项中，正确的遍历序列是

1，2，3，4，5

A:

2，3，5，4，1

3，5，1，2，4

B:

4，3，5，1，2

C:

答D:案：A

11、【单选题】对题10-11图进行拓扑排序，下列选项中，正确的拓扑序列是

1，2，3，4，5

2，3，1，4，5

A:

3，5，1，2，4

B:

5，3，1，2，4

C:

答D:案：D

12、【单选题】下列排序方法中，不是稳定排序方法的是

直接插入排序

冒泡排序

A:

归并排序

B:

快速排序

C:

答D:案：D

解析：快速排序不是稳定的排序方法。稳定排序是指如果两个元素的值相等，排序后它们

的相对顺序保持不变。而快速排序在每一次分割过程中，会选择一个基准元素，将小于基

准元素的放在左边，大于基准元素的放在右边，这个过程会改变相等元素的相对顺序，因

此快速排序不是稳定的排序方法。

13、【单选题】已知数据序列(18，19，20，4，51，6，30，1，2)是某种排序算法第二趟排

序后得到的结果，则该算法可能是

选择排序

冒泡排序

A:

直接插入排序

B:

快速排序

C:

答D:案：C

14、【单选题】对有序表(1，3，9，12，32，41，45，62，75，77)进行二分查找，查找关

键字9时，进行比较的关键字依次是

1，3，9

32，3，9

A:

32，12，9

B:

C:

41，12，9

答D:案：B

15、【单选题】分别使用下列数据序列建立二叉排序树，能得到高度最高的二叉树的是

10，8，9，6，12，11，13

10，6，8，9，12，11，13

A:

10，12，11，13，8，6，9

B:

10，8，6，9，12，13，11

C:

答D:案：B

16、【问答题】请画出题26图所示的二叉树对应的树或森林。

答案：

17、【问答题】求题27图从顶点A到其余各顶点的最短路径，给出各条路径包含的顶点

序列及路径长度。

答案：

18、【问答题】有以下数据序列(20，84，19，14，23，01，68，27，55，11，10，79，

12)，使用二路归并排序算法将其排成升序序列。给出各趟排序结果。

答案：初始：20，84，19，14，23，01，68，27，55，11，10，79，12一趟归并：

20，84，14，19，01，23，27，68，11，55，10，79，12二趟归并：14，19，20，84，

01，23，27，68，10，11，55，79，12三趟归并：01，14，19，20，23，27，68，84，

10，11，12，55，79四趟归并：01，10，11，12，14，19，20，23，27，55，68，79，

84

19、【问答题】设有以下关键字：15，72，52，65，23，68，散列函数H(key)=key%7，散列

表空间为0~6，采用线性探查法解决冲突。请回答下列问题。(1)构造散列表。(2)计算等

概率情况下查找成功时的平均查找长度。

答案：

20、【问答题】顺序表类型定义如下。

答案：(1)30，2，10，9，5，3，(2)根据所给的数据建立顺序表，将偶数从表头插入，

奇数从表尾插入。

21、【问答题】阅读函数f31，并回答问题。

答案：(1)-38，-256，256，9，25，47，128，4，64(2)找到数组中第一个非负数的位

置。

22、【问答题】二叉排序树的存储结构类型定义如下。

答案：(1)1618253650(2)查找二叉排序树T中所有满足大于等于K1且小于等于K2

的元素，并按升序输出。

23、【问答题】待排序记录的数据类型定义如下。

答案：(1)j<=n(2)R[j].key＜R[k].key(3)k!=i

24、【问答题】已知单链表的存储结构类型定义如下。

答案：

25、【填空题】数据的运算，即对数据元素施加的操作，是定义在数据的_______结构上

的。

答案：逻辑

26、【填空题】在顺序表中，因为访问任一结点的方式是_______，所以访问每个结点的时

间复杂度均为O(1)。

答案：随机访问

27、【填空题】带头结点的链队列可以由一个头指针和一个尾指针唯一确定。当头指针和尾

指针相等时，表示队列_______。

答案：为空

28、【填空题】稀疏矩阵采用压缩存储，只保存非零元素，得到的顺序存储结构称为

_______。

答案：三元组表

29、【填空题】广义表((a)，(b，c)，(d，e，(f，g，h)))的表尾是_______。

答案：((b，c)，(d，e，(f，g，h)))

30、【填空题】中序线索化二叉树的过程，是在中序遍历过程中用线索取代_______。

答案：空指针

31、【填空题】在有n个顶点、e条边的无向连通图中，e的取值范围是_______。

答案：n-1