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

数据结构年月真题

0233120194

1、【单选题】线性表是一种由n个数据元素组成的数据结构,n的取值是

0或者任意一个正整数或者∞

非负整数

A:

任意一个正整数或者∞

B:

某个正整数

C:

答D:案：B

解析：线性表是一种由n个数据元素组成的数据结构,n的取值是非负整数。

2、【单选题】在一个单链表中,已知q所指结点是p所指结点的后继结点,若在p和q之间插

入s所指结点,则正确的操作是

s->next=p->next;p->next=s;

s->next=q;p->next=s->next;

A:

q->next=s;s->next=p;

B:

p->next=s;s->next=p;

C:

答D:案：A

3、【单选题】下列选项中,不宜通过栈求解的问题是

判断字符串是否是回文

检验圆括号是否匹配

A:

不同数制之间进行转换

B:

图的广度优先搜索遍历

C:

答D:案：D

4、【单选题】设栈S的输入序列为1,2,3,4,5,则下列选项中不可能是S的输出序列的是

2,3,4,1,5

5,4,1,3,2

A:

2,3,1,4,5

B:

1,5,4,3,2

C:

答D:案：B

5、【单选题】使用一个大小为6的数组保存循环队列Q。若从Q中出队两个元素,并入队一

个元素,此时队尾rear和队头front的值分别为2和4。则在执行这三个操作之前rear和

front的值分别是

0和3

1和2

A:

2和5

B:

4和5

C:

答D:案：B

6、【单选题】设二维数组M有3行4列,按行优先的方式存储,每个元素占6个存储单元。第

1个元素的存储地址为100,则M[2][2]的存储地址为A

135

153

A:

160

B:

165

C:

答D:案：C

7、【单选题】设n阶方阵M是对称矩阵,采用压缩存储方式将M中的元素保存在一维数组B

中,则下列选项中,正确的是

保存M中的主对角线中的元素,B的元素个数是n

保存M中上三角部分的元素,B的元素个数是n(n-1)/2

A:

保存M中上三角部分的元素,B的元素个数是n(n+1)/2

B:

保存M中的全部元素,B的元素个数是n2

C:

答D:案：C

8、【单选题】已知完全二叉树T的第4层有5个叶结点,则T的结点个数最多是

12

20

A:

21

B:

36

C:

答D:案：C

9、【单选题】在一棵非空二叉树的后序遍历序列中,所有列在根结点前面的是

左子树中的部分结点

右子树中的全部结点

A:

左右子树中的部分结点

B:

左右子树中的全部结点

C:

D:

答案：D

10、【单选题】若对题10图所示的无向图进行深度优先搜索遍历,则下列选项中正确的遍

历序列是

h,c,a,b,d,e,g,f

e,a,f,g,b,h,c,d

A:

d,b,c,a,h,e,f,g

B:

a,b,c,d,h,e,f,g

C:

答D:案：D

11、【单选题】对题11图所示的有向图进行拓扑排序。下列选项中能够得到的拓扑序列

是

3,1,2,4,5,6

3,1,2,4,6,5

A:

3,1.4,2,5,6

B:

3,1,4,2,6,5

C:

答D:案：D

12、【单选题】已知数据序列(8,9.10,4,5.6,20,1,2)是某种排序算法第一趟排序后得到的

结果,则该算法可能是

选择排序

起泡排序

A:

直接插入排序

B:

快速排序

C:

答D:案：C

13、【单选题】下列选项中,每一趟都能选出一个元素放在其最终位置上,且不稳定的排序算

法是

起泡排序

希尔排序

A:

归并排序

B:

快速排序

C:

D:

答案：D

解析：对于每一趟都能选出一个元素放在其最终位置上的排序算法，我们可以考虑冒泡排

序和插入排序。这两种排序算法都是稳定的排序算法。快速排序是一种不稳定的排序算

法。在快速排序中，我们选择一个基准元素，将数组分成两个子数组，一个子数组中的元

素都小于基准元素，另一个子数组中的元素都大于基准元素。然后递归地对这两个子数组

进行排序。在快速排序的过程中，我们会通过交换元素的位置来实现元素的分区。这个过

程可能会导致相同元素之间的相对顺序发生改变，从而使快速排序成为不稳定的排序算

法。举个例子，考虑以下数组：[5,2,5,1,3]。在快速排序中，我们选择基准元素为

3，将数组分成[2,1]和[5,5]两个子数组。然后对这两个子数组进行排序，得到[1,2]和

[5,5]。最后将基准元素3放置在正确的位置上，得到[1,2,3,5,5]。可以看到，原

数组中的两个相同的5在排序后的结果中位置发生了变化，因此快速排序是不稳定的排序

算法。

14、【单选题】对有序表(1,9,12,41,62,77,82,95,100)采用二分查找方法查找值82,查找过

程中关键字的比较次数是

1

2

A:

4

B:

7

C:

答D:案：B

15、【单选题】将下列数据依次插入到初始为空的二叉排序树中能得到高度最小的二叉排序

树的序列是

2,4,7.5,8,10

5.1,2,6,3,4

A:

6,4,1,8,10,5

B:

9,7,2,1,4,0

C:

答D:案：C

16、【问答题】设细数矩阵M如下所示。矩阵的行列下标均从1开始，请画出M按行优先

存储的三元组表。

答案：

17、【问答题】已知二树T的前序遍历序列是A,B.C,D,E.L,M,O,N序遍历序列是

C,B,E,D,A,M,O,L,N请画出T。

答案：

18、【问答题】已知有向带权图G如题28图所示。请回答下列问题。(1)给出图G的

邻接矩阵。(2)求出G中从源点A到其余各顶点的最短路径。要求根据迪杰斯特拉算法

的求解过程依次给出各条路径,包括路径上经过的顶点及其长度。

答案：

19、【问答题】设有关键字序列(65,23,31,26,7,91,53,15,72,52),散列函数为

H(key)=key%11,将关键字依次放入表长为11的散列表H中,采用线性探测法处理冲突。请回

答下列问题。(1)画出构造的散列表,并给出查找每个关键字的探查次数。(2)求散列表的平均

查找长度ASL。

答案：

20、【问答题】

答案：

21、【问答题】

答案：

22、【问答题】

答案：(1)high=mid-1(2)mid(3)i>=inspace

23、【问答题】

答案：(1)R中的值是{30,14,-38,-9,52,256,128,258,64}(2)该算法选择第一个元素作

为基准,实现对数组的一次划分。(或实现快速排序的一次划分。)

24、【问答题】

答案：

25、【填空题】线性表的存储方式中，能够随机存取表中任一元素的存储结构是____。

答案：顺序存储结构

26、【填空题】用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到

1342的出栈顺序，相应的S、X操作串为____。

答案：SXSSXSXX

27、【填空题】若广义表L的深度是∞，则L一定是____。

答案：递归表

28、【填空题】广义表（（a,b）,（c,d）,e）的表尾是____。

答案：(（c,d),e）

29、【填空题】利用二叉树中的空指针域，使之指向结点在某种遍历次序下的前趋或后继结

点，此时域中的内容称为____。

答案：线索

30、【填空题】若用n个带权字符构造哈夫曼树T，则T中结点的总数是____。

答案：2n-1

31、【填空题】设连通带权图G中有n个顶点，使用普里姆算法构造G的最小生成树T，T

中含有的边数是____。

答案：n-1

32、【填空题】要使n个记录的关