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

数据结构年月真题

02331201710

1、【单选题】下列选项中，与数据存储结构直接相关的是

线性表

双向链表

A:

二叉树

B:

有向图

C:

答D:案：B

解析：双向链表的每个节点中储存有两个指针，这两个指针分别指向前一个节点的地址和

后一个节点的地址，这样无论通过那个节点都能够寻找到其他的节点。线性表、二叉树和

有向图需要查找某一个元素时，都必须从第一个元素开始进行查找。

2、【单选题】将12个数据元素保存在顺序表中，若第一个元素的存储地址是100，第二个

元素的存储地址是105，则该顺序表最后一个元素的存储地址是

111

144

A:

155

B:

156

C:

答D:案：C

解析：线性表的第i个元素ai的存储位置LOC(ai)=LOC(ai)+(i-1)*d,所以第12个元素

的地址=100+（12-1）*5=155

3、【单选题】设栈的初始状态为空,元素1,2,3,4,5,6依次入栈,栈的容量是3,能够得

到的出栈序列是

1,2,6,4,3,5

2,4,3,6,5,1

A:

3,1,2,5,4,6

B:

3,2,6,5,1,4

C:

答D:案：B

解析：栈的特点：后进先出，且容量为3.答案B的顺序为：1进，2进，2出，3进，4

进，4出，3出，5进，6进，6出，5出，1出。

4、【单选题】设指针变量head指向非空单循环链表的头结点,指针变量p指向终端结点,

next是结点的指针域,则下列逻辑表达式中,值为真的是

p->next->next==head

p->next==head

A:

p->next->next==NULL

B:

p->next==NULL

C:

答D:案：B

解析：循环单链表的特点就是最后一个结点的指针不为空，而是指向链表的头结点。

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

2

3

A:

4

B:

5

C:

答D:案：C

解析：一个表展开后所含括号的层数称为广义表的深度。即表中每个元素的括号匹配数加

1

6、【单选题】已知一棵高度为4的完全二叉树T共有5个叶结点,则T中结点个数最少是

9

10

A:

11

B:

12

C:

答D:案：A

解析：深度为4的二叉树，其前3层是一棵满二叉树，至少得有7个结点，而题目中结出

有5个是叶子结点，那么第三层的结点中得有一个得有左右子结点，这要T中结点个数至

少是9个。

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

左子树中的部分结点

左子树中的全部结点

A:

右子树中的部分结点

B:

右子树中的全部结点

C:

答D:案：B

解析：中序遍历二叉树的操作：1.中序遍历左子树2.访问根结点3.中序遍历右子树。

8、【单选题】用邻接矩阵表示有n个顶点和e条边的无向图，采用压缩方式存储，矩阵中零

元素的个数是

n(n+1)/2-e

n(n+1)/2—2e

A:

n×n-e

B:

n×n一2e

C:

答D:案：A

解析：有n个顶点的无向图的邻接矩阵一共有n*n个元素，由于是对称矩阵，采用压缩存

储，共存储n(n+1)/2个元素，其中只有e个元素是非零元素，其他都是零元素，共

n(n+1)/2-e个。

9、【单选题】无向图G中所有顶点的度数之和是20，则G中的边数是

10

20

A:

30

B:

40

C:

答D:案：A

解析：一条边是2度，20除以2等于10条边。

10、【单选题】设有向图G含有n个顶点、e条边，使用邻接表存储。对G进行广度优先遍

历的算法的时间复杂度是

O(n)

O(e)

A:

O(n+e)

B:

O(n×e)

C:

答D:案：C

解析：邻接表存储的有向图进行广度优先遍历的时间复杂度与图中的顶点个数以及边数都

相关

11、【单选题】对数据序列（25，15，7，18，10，0，4）采用直接插入排序进行升序排

序，两趟排序后，得到的排序结果为

0，4，7，18，10，25，15

A:

O，4，25，15，7，18，10

7，15，10，O，4，18，25

B:

7，15，25，18，10，O，4

C:

答D:案：D

解析：初始【25】【15，7，18，10，0，4】第一趟【15，25】【7，18，10，0，4】第二

趟【7，15，25】【18，10，0，4】

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

希尔排序

归并排序

A:

堆排序

B:

快速排序

C:

答D:案：B

解析：这个题考查各种排序方法的稳定性，教材190页内部排序方法的分析与比较中总结

到，直接插入、冒泡、归并、基数排序算法是稳定的，直接选择、希尔、快速、堆排序算

法是不稳定的

13、【单选题】一组记录的关键码为(45，68，57，13，24，89)，利用堆排序算法进行升序

排序，建立的初始堆为

68，45，57，13，24，89

89，68，57，13，24，45

A:

89，68，57，45，24，13

B:

89，57，68，24，45，13

C:

答D:案：B

解析：

根据教材183页堆排序定义，建堆过程如下：

14、【单选题】一棵二叉排序树中，关键字n所在结点是关键字m所在结点的祖先，则

n一定大于m

n一定小于m

A:

n一定等于m

B:

C:

n与m的大小关系不确定

答D:案：D

解析：由二叉排序树定义可知，其右子树上所有结点的值均大于根结点的值，则左子树上

所有结点的值均小于根结点的值，因为题目中m和n并没有给出是左子树还是右子树，所

以大小关系不确定。

15、【单选题】设散列表长m=14，散列函数H（key）=key％11。表中己保存4个关键字：

addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址均为空。保存关键字49时存

在冲突，采用线性探查法来处理。则查找关键字49时的探查次数是

1

2

A:

4

B:

8

C:

答D:案：C

解析：h(49)=5,散列地址5已经被占，因此探查h1=(5+1)%11=6,但散列地址6也已经被

占，再探查h2=(6+1)%11=7,散列地址7也被占了，再探查h3=(7+1)%11=8,此地址是开放

的，可将49插入。

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

10，16，8，12}。现要为该字符集设计哈夫曼编码。请回答下列问题。（1）画出得到的哈夫

曼树。（2）给出各符号的哈夫曼编码。

答案：

解析：

（1）哈夫曼树构造过程：（2）哈夫曼树左分支表示0，右分支表示1.以

根结点到叶结点路径上的分支字符组成的串作为该叶结点的字符编码。

17、【问答题】己知图G采用邻接矩阵存储，邻接矩阵如题27图所示。

（1）写出从顶点A开始图G

的3个不同的深度优先搜索遍历序列。（2）写出从顶点A开始图G的2个不同的广度优

先搜索遍历序列。

答案：(1)ABCEGDFACEGBDFADFGBCE(2)ABCDEFGADCBFEG

解析：

根据邻接矩阵可以画出这个有向图（因为不是对称矩阵），由深度优先遍历和广度优先遍

历的含义，可以写出出答案，答案不是唯一的。

18、【问答题】有以下数据序列（19,14,23,01,68,20,84,27,55,11,10,79,12),使用希尔排

序方法将其排成升序序列。请回答下列问题。（1）写出增量为4时对上述数据序列进行一趟

希尔排序的结果。（2）给出一个可行的希尔排序增量序列。

答案：（1）12，11，10，01，19，14，23，27，55，20，84，79，68（2）4，2，1

解析：教材171页希尔排序的思想，需要取一个小于n的整数做为第一个增量，因为增量

的不确定性，所以本题的答案也不唯一，如果增量序列是递减，且最后一个增量为1也是

正确的。

19、【问答题】设有二叉排序树如题29图所示。请回答下列问题。

（1）假定二叉排序树初始为

空，写出一个数据输入序列，按序插入时能得到题29图所示的二叉排序树。（2）能得到

题29图所示的二叉排序树的不同的输入数据序列有几个？

答案：（1）agebfdc；（2）4个

解析：从上到下遍历，有左右子树，则会有本同的序列。本题：遍历可以得到agebfdc。

以e为根的树有左右子树，其左右子树之间序列位置可以调换。遍历能得到题29图所示

的二叉排序树的不同的输入数据序列agebfdc；agebdfc；agebdcf；agefbdc；共四个。

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

阅读下列算法，并回答问题。

（1）若SL1-＞data中的数据

为｛25,4,256,9，-38,47,128,256,64},SL2-＞data中的数据为｛22,4，-

63,15,29,34,42,3}，则执行算法f30(&SL1,&SL2）后SL1-＞data和SL2-＞data中的数据

各是什么？（2）该算法的功能是什么？

答案：（1）SL1-＞data中的数据为｛25,4,256,15，29，47，128，256，64},SL2-＞data

中的数据为｛22,4，-63,9，-38，34，42，3}（2）该算法的功能是比较两个线性表中相

同下标位置的两个元素，较大者放到较长的线性表中，较小者放到较短的线性表中。

解析：该算法的功能是比较两个线性表中相同下标位置的两个元素，较大者放到较长的线

性表中，较小者放到较短的线性表中。

21、【问答题】二叉树的存储结构类型定义如下：

（1）设二叉树T如题31图所

示，给出执行A31（T）的输出结果。

（2）给出该算法的时间复杂

度。

答案：(1)ACCABB;(2)O(n),n是二叉树中所含结点个数。

解析：访问C时候也要执行两遍printf，访问完C还要在打印A本身一次再访问B，访问

B时候也要执行两遍printf。

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

下列算法实现自底向上、自顶

向下交替进行的双向扫描冒泡排序，请在空白处填上适当内容使算法完整。

答案：（1）j>=i+1;j--;(2)j=j+1;j<n-i+1;(3)i=i+1

解析：教材174页冒泡排序算法原题，第一个空是自底向上扫描，第二个空是自顶向下扫

描。

23、【问答题】二叉树的存储结构类型定义如下：

（1）设二叉排序树T如题33

图所示，bt是指向根结点的指针。给出执行A33(bt,6,100,0）的输出结果。

（2）给出该算法的功能。

答案：

解析：该算法的功能从是T中找出所有满足大于等于K1且小于等于k2的元素，并按升序

输出。这里K1是6，key是20，K2是100，那么就是把大于等6小于等于100的结点按升

序输出

24、【问答题】己知二叉树的存储结构类型定义如下：

编写递归算法，对于给定的一

棵二叉树T，将其修改为镜像二叉树。例如，题34图所示的两棵二叉树互为镜像二叉树。

函数的原型为：void

f34(BinTreeT);

答案：voidf34(BinTreeT){BinNode*s;If(BT){s=BT->lchild;BT->lchild=BT-

>rchild;BT->rchild=s;f34(BT->lchild);f34(BT->rchild);}}

解析：先设置一个中间变量s,用来存放左子树的值，然后把右子树的值交换给左子树，再

让右子树获得中间变量s值，这样做到左右子树结结点值互换，左右子树分别递归，最后

完成镜像。

25、【填空题】数据的逻辑结构是从逻辑关系上描述数据，它与数据元素的存储结构

______________。

答案：无关

解析：数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计

算机的

26、【填空题】指针P和指针q分别指向单链表L中的两个相邻结点，即q->next=p，且p

所指结点不是终端结点。若要删除P所指结点，则执行的语句是______________。

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

解析：q的下个结点是p，如果删除P，那么只能让P的下个结点当q的下个结点。

27、【填空题】一个直接或间接调用自己的函数称为______________。

答案：递归函数

解析：教材71页递归函数定义，一个直接或间接调用自己的函数称为递归函数。

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

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

解析：当表为非空时，称第一个元素是表头，其余元素组成的表称为表尾。本题中(a)是

表头，((b，c，d)，e，f，(g，h))为表尾。

29、【填空题】二叉树的前序遍历序列和后序遍历序列中，叶结点之间的相对次序

______________。

答案：不变

解析：根据三种遍历的次序和特点：前序是根左右、中序是左根右、后序是左右根,因此

相对次序发生变化的都是子树的根

30、【填空题】如果图G存在拓扑排序序列，则G必为______________。

答案：有向无环图

解析：教材163页：对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性

序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之

前。通常，这样的线性序列称为简称拓扑序列。

31、【填空题】将一棵树T转换为一棵二叉树T1，在Tl中结点A是结点B的父结点，则在

T中A可能是B的父结点或________