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

数据结构年月真题

02331201910

1、【单选题】下列选项中,不宜采用链式存储的是

无向图

单链表

A:

最优二叉树

B:

数组

C:

答D:案：D

2、【单选题】将10个数据元素保存在顺序栈S中,若栈顶元素的存储地址是100,栈中每个

元素占4个存储单元,进栈按Stop=S.top+1修改栈顶,则栈底元素的存储地址是

60

64

A:

136

B:

140

C:

答D:案：B

3、【单选题】设指针变量head指向循环链表的头结点,next是结点的指针域,则判断此链表

为空的条件是

head->next==NULL

head->next==head

A:

head->next!=NULL

B:

head->next!=head->next

C:

答D:案：B

4、【单选题】已知广义表LS=(((a,b,c)),((d,(e)),(f,(g))),(h,g),i),LS的深度是

4

3

A:

2

B:

1

C:

答D:案：A

5、【单选题】已知一棵完全二叉树T共有7个分支结点,则T中叶子结点个数最少是

7

A:

8

9

B:

10

C:

答D:案：A

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

左子树中的部分结点

右子树中的全部结点

A:

左右子树中的全部结点

B:

左右子树中的部分结点

C:

答D:案：C

解析：在一棵非空二叉树的后序遍历序列中，所有出现在根节点前面的元素都是左子树和

右子树中的全部节点。后序遍历是一种遍历二叉树的方式，它的遍历顺序是先遍历左子

树，再遍历右子树，最后访问根节点。因此，在后序遍历序列中，根节点的位置是在最后

的。假设后序遍历序列为[L1,L2,...,Ln,R1,R2,...,Rm,Root]，其中L1,

L2,...,Ln是左子树的节点，R1,R2,...,Rm是右子树的节点，Root是根节点。由于

后序遍历的特性，我们可以观察到，在序列中，所有出现在根节点前面的元素都是左子树

和右子树中的全部节点。也就是说，L1,L2,...,Ln,R1,R2,...,Rm都是左子树和右

子树中的节点，而Root是根节点。这个特性可以用来判断一个序列是否是一个合法的后

序遍历序列，以及还原二叉树的结构。

7、【单选题】用邻接表保存有n个顶点和e条边的无向图,邻接表中指针个数是

e

n-e

A:

n+e

B:

n+2e

C:

答D:案：D

解析：在邻接表中保存有n个顶点和e条边的无向图时，每个顶点对应一个链表，链表中

存储与该顶点相邻的其他顶点。对于每个顶点，我们需要一个指针来指向与之相邻的顶

点。由于无向图中的每条边都会连接两个顶点，所以每个顶点的链表中需要存储与之相邻

的顶点的信息。考虑到每条边都会在两个顶点之间建立连接，所以总共有2e个指针。而

每个顶点对应一个链表，所以需要n个指针来指向这些链表。因此，邻接表中指针的个

数是n+2e。其中n表示顶点的个数，2e表示边的个数乘以2，是因为每条边都会在两个

顶点之间建立连接。

8、【单选题】有向图G中某个顶点的出度和入度均为2,则G中的顶点个数最少是

2

3

A:

4

B:

5

C:

答D:案：B

9、【单选题】在带权图的最短路径问题中,路径长度是指

路径上边的数目

路径上结点的数目

A:

路径上边的权值之和

B:

到达终点的最短路径数目

C:

答D:案：C

解析：在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通，在有多条通

路的情况下，哪--条最近，哪一条花费最少，等等。交通网络可以用带权图表示，图中顶

点表示城镇，边表示两城镇之间的道路，边上的权值可表示两城镇间的距离、交通费用或

途中所需的时间等。上述这些问题就是在带权图中求最短路径的问题。此时的路径长度的

度量不再是路径上边的数目，而是路径上边的权值之和。P158

10、【单选题】对数据序列(15,10,8,12,15,8,10)按升序进行希尔排序,增量序列为5,3,两

趟排序后,得到的排序结果为

8,8,10,10,15,15,12

8,8,10,10,12,15,15

A:

8,10,8,10,15,15,12

B:

8,10,8,10,12,15,15

C:

答D:案：C

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

直接选择排序

归并排序

A:

直接插入排序

B:

基数排序

C:

答D:案：A

解析：直接选择排序是一种不稳定的排序方法。在直接选择排序中，每次从未排序的元素

中选择最小（或最大）的元素，然后将其放置在已排序序列的末尾。这个过程会破坏相同

元素之间的相对顺序，导致排序结果不稳定。

12、【单选题】一组记录的关键字为(35,58,24,13,44,19,10),利用堆排序算法进行降序排

序,要求空间复杂度为O(1),建立的初始堆为

10,13,19,58,44,35,24

10,13,35,58,44,19,24

A:

58,44,24,13,35,19,10

B:

58,35,24,13,44,19,10

C:

答D:案：A

13、【单选题】一棵二叉排序树中,关键字n所在结点的层数大于关键字m所在结点的层数,

则

n一定大于m

n一定小于m

A:

n一定等于m

B:

n与m的大小关系不确定

C:

答D:案：D

14、【单选题】设散列表长m=10,散列函数H(key)=key%9.表中已保存3个关键

字:H(13)=4,H(32)=5,H(15)=6,其余地址均为空。保存关键字23时存在冲突,采用线性探查法

来处理。则查找关键字23时的探查次数是

1

2

A:

3

B:

4

C:

答D:案：C

15、【单选题】下面关于m阶(m≥3)B树的叙述中,正确的是

终端结点可位于不同层

非终端结点至多有m+1棵子树

A:

若树非空,则根结点至少有2个关键字

B:

每个非根结点包含n个关键字,[m/2]-1≤n≤m-1

C:

答D:案：D

16、【问答题】设电文字符集是{e1,e2,e3,e4,e5,e6},它们出现的次数分别

为:38,12,17,26,14,20。现要为该字符集设计一种哈夫曼编码。请回答下列问题。(1)画出得

到的哈夫曼树。(2)给出各符号的哈夫曼编码。

答案：

17、【问答题】

答案：(1)ABDEFGCABDEGFC(2)ABCDEFGABCDEGFACBDEFG

18、【问答题】有以下关键字序列(15,20,24,32,15,7,14,23),使用快速排序方法将其按升

序排列。请回答下列问题。(1)若取第一个关键字为基准,写出第一趟快速排序的结果。(2)若

取最后一个关键字为基准,写出第一趟快速排序的结果

答案：(1)14,7,15,32,15,24,20,23(2)15,20,14,7,15,23,32,24

19、【问答题】

答案：

20、【问答题】

答案：(1)3,5,9,10,2,30,(2)用给定的整数建立顺序表,奇数从头插入,偶数从表尾插

入。

21、【问答题】

答案：

22、【问答题】。

答案：(1)R[mid].key==k(2)mid-1(3)mid+1

23、【问答题】

答案：(1)Q[front]!=NULL(2)rear%2(3)front++

24、【问答题】

答案：

25、【填空题】数据的四种基本存储方法是顺序存储、链接存储、____和散列存储。

答案：索引存储

26、【填空题】指针p和指针q分别指向单链表L中的两个结点,next为指针域,则判断这两

个结点是否相邻的条件是____

答案：p->next==q||q->next==p

27、【填空题】递归求解过程中的最小子问题称为____

答案：递归的终止条件(或递归出口)

28、【填空题】广义表(((a,b),(c,d,e)),(f,g),h)的表头是____

答案：((a,b),(c,d,e))

29、【填空题】3个结点的不同形状的二叉树有____棵。

答案：5

30、【填空题】若有向无环图G存在2个入度为0的结点,则G至少存在____个不同的拓扑

序列。

答案：2

31、【填空题】将一棵树T转换为一棵二叉树,则这棵二