2018年10月自考02142数据结构导论试题及答案含解析

数据结构导论年月真题

02142201810

1、【单选题】具有分支、层次特性，上层的结点可以和下层多个结点相邻接,但下层结点只

能和上层的一个结点相邻接，这种组织形式称为

集合

线性结构

A:

树形结构

B:

图结构

C:

答D:案：C

解析：本题考核的是数据结构中树形结构的定义。

2、【单选题】下面几种算法时间复杂度阶数中，最大的是

O(logn)

O(n)

A:₂

O(n²)

B:

O(nlogn)

C:

₂

答D:案：C

解析：算法时间复杂度阶数从小到大：O(logn)、O(n)、O(nlogn)、O(n²)。

₂₂

3、【单选题】设顺序表的表长为10,则执行插入算法的元素平均移动次数约为

4.

5

A:

6

B:

7

C:

答D:案：B

解析：在插入位置等概率情况下，平均移动元素的个数为：（n+（n-1）+（n-2）

+…+2+1+0）/（n+1）=n/2。当n=10时，n/2=5

4、【单选题】在带头结点的单链表L中，第一个数据元素结点的指针为

L->prior

L->next

A:

L

B:

C:

L->rear

答D:案：B

解析：在带头结点的单链表L中，头结点的指针为L,第一个数据元素结点的指针为L-

>next。

5、【单选题】栈初始化时一般将栈顶下标值top设置为

0

NULL

A:

1

B:

-1

C:

答D:案：A

解析：当栈顶下标值top==0时是栈空，栈初始化时一般将栈顶下标值top设置为0。

6、【单选题】设输入序列为ABC,输出为ABC,则经过的栈操作为

push,pop,push,push,pop,pop

push,push,pop,pop,push,pop

A:

push,pash,push,pop,pop,pop

B:

push,pop,push,pop,push,pop

C:

答D:案：D

解析：输入序列为ABC,输出为ABC，操作顺序只能是push,pop,push,pop,push,pop。

7、【单选题】设有一循环队列CQ，队列的长度为maxsize，则该循环队列满的条件为

(CQ.rear+l)%maxsize==CQ.front

CQ.rear==CQ.front

A:

(CQ.rear+l)%maxsize=CQ.rear

B:

CQ.rear==NULL

C:

答D:案：A

解析：循环队列队满的条件：(CQ.rear+1)%maxsize==CQ.front；，队空的条件是：CQ.

rear==CQ.front。

8、【单选题】树的相关术语中，兄弟指

祖先相同的结点

根相同的结点

A:

B:

度数相同的结点

父结点相同的结点

C:

答D:案：D

解析：树的相关术语中，兄弟指父结点相同的结点。

9、【单选题】执行进栈操作，在元素x进栈前需要进行的操作是

判断栈是否满，若栈未满，top值加1

判断栈是否空，若栈未空，top值加1

A:

判断栈是否满，若栈未满，top值减1

B:

判断栈是否空，若栈未空，top值减1

C:

答D:案：A

解析：执行进栈操作，在元素x进栈前需要判断栈是否满，若栈未满，top值加1。执行

出栈操作，出栈前判断栈是否空，若栈未空，top值减1。

10、【单选题】森林有两种遍历方法，分别是

先序遍历森林和中序遍历森林

先序遍历森林和后序遍历森林

A:

中序遍历森林和层次遍历森林

B:

后序遍历森林和层次遍历森林

C:

答D:案：A

解析：森林的遍历有先序遍历和中序遍历两种方式。先序遍历的定义为：（1）访问森林

中第一棵树的根结点；（2）前序遍历第一棵树的根结点的子树；（3）前序遍历去掉第一

棵树后的子森林。中序遍历的定义为：（1）中序遍历第一棵树的根结点的子树；（2）访

问森林中第一棵树的根结点；（3）中序遍历去掉第一棵树后的子森林。树遍历有三种方

法：先根遍历、后根遍历和层次遍历。

11、【单选题】有向图中某顶点v的入度为2,出度为3,则该顶点的度为

3

4

A:

5

B:

6

C:

答D:案：C

解析：有向图顶点的度等于其入度和出度之和。

12、【单选题】无向图的邻接矩阵为

对角矩阵

对称矩阵

A:

稀疏矩阵

B:

一般矩阵

C:

答D:案：B

解析：无向图的邻接矩阵为对称矩阵。有向图的矩阵一般为稀疏矩阵。

13、【单选题】对升序表进行二分査找，用给定值key与处在中间位置的数据元素

T.elem[mid]的键值T.elem[mid].key进行比较，当key<T.elem[mid].key时，说明

查找失败

查找成功，T.elem[mid]即为待查元素

A:

待查元素若在表中，则一定排在T.elem[mid]之前

B:

待查元素若在表中，则一定排在T.elem[mid]之后

C:

答D:案：C

解析：key=T.elem[mid].key，查找成功，T.elemEmid]即为待查元素；

key<t.elem[mid].key,说明若待查元素若在表中，则一定排在t.elem[mid]=""之前；

key>T.elem[mid].key,说明若待查元素若在表中，则一定排在T.elem[mid]之后。

14、【单选题】利用散列表进行査找的基本出发点是

减少査找过程中的比较次数

增加查找过程中的比较次数

A:

查找过程中不再需要比较操作

B:

节省存储空间

C:

答D:案：A

解析：利用散列表进行査找的基本出发点是减少査找过程中的比较次数。

15、【单选题】快速排序属于

插入排序

交换排序

A:

选择排序

B:

归并排序

C:

答D:案：B

解析：快速排序属于交换排序，快速排序方法的排序过程是一个递归过程。

16、【问答题】链式存储的特点是利用指针来表示数据元素之间的__________关系。

答案：逻辑

解析：链式存储的特点是利用指针来表示数据元素之间的逻辑关系，顺序存储的特点是利

用存储的位置来表示数据元素之间的逻辑关系

17、【问答题】单链表的每个结点包括__________和指针域。

答案：数据域

解析：单链表的每个结点包括数据域和指针域，数据域存储数据，指针域存储下一个结点

的地址。

18、【问答题】设有一个单链表，若结点的指针域为next，则指针P所指的结点为最后一个

结点的条件是__________.

答案：p->next==NULL

解析：单链表的最后一个结点的指针域存储的是空指针NULL。

19、【问答题】设栈的输入序列为1、2、3,若输出的第一个元素为3,则第二个输出的元素

为__________。

答案：2

解析：输出的第一个元素为3，一定是1、2、3都入栈后，第一个出栈的是3，第二个出

栈的是2。

20、【问答题】线性表中如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点

有且仅有__________个直接前驱。

答案：1

解析：线性表中如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有且仅

有1个直接前驱，则除终端结点没有直接后继外，其他每个结点有且仅有1个直接后继。

21、【问答题】由于链接实现需要__________，故链队列在一定范围内不会出现队列满的情

况。

答案：动态申请空间

解析：链接实现是动态申请空间，只要内存够用，链队列就不会出现队列满的情况。

22、【问答题】二叉树的__________存储结构可以用一维数组来实现。

答案：顺序

解析：二叉树的的顺序存储结构可以用一维数组来实现。

23、【问答题】含有10个叶子结点的哈夫曼树，其结点的总数为__________。

答案：19

解析：对于10个叶子结点的哈夫曼树，其10个权值分量，经过10-1次合并又产生10-1

个新结点，从而组成的10+10-1=2*10-1=19个结点的哈夫曼树。

24、【问答题】图的广度优先搜索遍历类似于树的按__________遍历的过程。

答案：层次

解析：图的广度优先搜索遍历类似于树的按层次遍历的过程，图的深度优先搜索遍历类

似于树的先根遍历的过程。

25、【问答题】如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶

点表示活动的有向图称为__________。

答案：AOV网

解析：本题考核AOV网的概念。

26、【问答题】用数据元素的__________通过散列函数获取存储位置的存储方式构造的存储

结构称为散列表。

答案：键值

解析：用数据元素的键值通过散列函数获取存储位置的存储方式构造的存储结构称为散列

表。

27、【问答题】静态查找表是以具有相同特性的数据元素集合为逻辑结构，包括建表、

__________、读表中元素三种基本运算。

答案：查找

解析：静态查找表的概念和基本运算

28、【问答题】若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相

对次序仍然保持不变，则称这种排序方法是__________的。

答案：稳定

解析：本题考核排序稳定性的概念。

29、【问答题】高度为h的满二叉树，如果按层次自上而下，同层从左到右的次序从1开始

编号，试问：（1）该树上有多少个结点？（2）编号为i的结点的左孩子和右孩子（若存

在）的编号分别是多少？

答案：（1）2h-1（2）左孩子的编号为2*i，右孩子的编号为2*i+1

30、【问答题】假设用于通讯的电文仅由6个字母A，B，C，D，E，F组成，各个字母在电

文中出现的频率分别为6，3,12,10,7,5,试为这6个字母设计哈夫曼树。（构建新二叉树

时，要求新二叉树的左子树根的权值小于等于右子树根的权值。）

答案：

解析：构造哈夫曼树的方法：①将给定的权值按照从小到大排列成｛W1，W2，…，

Wm｝，并且构造出树林F=｛Tl，T2，…，Tm｝。此时，其中的每棵树Ti(1≤i≤m）为

左、右子树均为空的二叉树，二叉树的根结点的权值为Wi。②把F中树根结点的权值最

小的两棵二叉树T1和T2合并为一棵新的二叉树T（T的左子树为T1，右子树为T2），并

令T的根结点的权值为T1和T2的根结点的权值之和，然后将T按其根结点的权值大小依

次加入到树林F中。同时，从F中删去T1和T2这两棵二叉树。③重复步骤②，直到构造

成一棵哈夫曼树。

31、【问答题】写出如题31图所示的有向图邻接矩阵表示和所有拓扑排序序列。

答案：

解析：本题考核有向图的邻接矩阵和拓扑排序。拓扑排序过程是：①从有向图中选择一

个入度为0的顶点；②从有向图中将该顶点以及由该顶点发出的所有弧全部删除；③重

复上述过程，直到剩余的网中不再存在入度为0的顶点。

32、【问答题】给定数据序列{46,25,78,62,12,80}，试按元素在序列中的次序将它

们依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。

答案：

解析：通常采用逐点插入结点的方法来构造二叉排序树，其方法表述如下：设K=｛kl，

k2，k3，…，kn｝为数据元素序列。从k1开始依次取序列中的元素，每取出一个数据元

素ki按下列原则建立二叉排序树的一个结点：①若二叉排序树为空，则ki就是该二叉排

序树的根结点。②若二叉排序树非空，则将ki与该二叉排序树的根结点的值进行比较。

若ki小于根结点的值，则将ki插入到根结点的左子树中，否则将ki插入到根结点的右

子树中。

33、【问答题】对键值序列（61，87，12，3，8，70）以位于最左位置的键值为基准进行由

小到大的快速排序，请写出第一趟排序后的结果，并给出快速排序算法在平均情况和最坏情

况下的时间复杂度。

答案：（1）第一趟排序后的结果:[8312]61[8770]（2）快速排序算法在平均情况下

的时间复杂度为O(nlog<>2n),在最坏情况下的时间复杂度为O(n<>2)。

解析：根据快速排序的算法，第一趟排序后的结果:[8312]61[8770]。快速排序方法

的排序过程是一个递归过程。快速排序方法是一种不稳定的排序方法，其时间复杂度为O

（nlog<>2n）。空间复杂度为O（log<>2n）。快速排序方法被认为是排序时间效率非常高

的一种方法，但是，当参加排序的原始序列已经是一个按值有序的序列时，快速排序方法

的时间效率将降到最低，这种情况下其时间复杂度为O（n<>2）

34、【问答题】假设线性表的数据元素的类型为DataType，顺序表的结构定义如下：

设计算法实现顺序表的插入运

算InsertSeqlist（SeqListL,DataTypex，inti）。该算法是指在顺序表的第i（l≤i

≤n+1）个元素之前，插入一个新元素x。使长度为n的线性表（a1，a2，…，ai-1，

ai，…，an）变为长度为n+1的线性表（a1，a2，…，ai