数据结构期末考试试题及答案1
诺贝尔奖金-财务收支审计报告
一、填空题
1. 【答案】集合、线性结构、树形结构、图状结构或网状结构
【解析】相互之间存在一种或多种特定关系的数据元素的集合称为数据结构，根据数据元素
之间关系的
不同特性通常分出了以上四种逻辑结构。
2．【答案】插入和删除、后进现出（LIFO）
【解析】考查的栈的定义及性质，队列的定义及性质也需要牢固掌握。
3.
【答案】2-1
【解析】考查二叉树的性质2。
4. 【答案】图
【解析】根据图数据结构的特性。
５．【答案】有穷性、确定性、可行性、输入（0或多个）、输出（至少有1个）
【解析】算法是特定问题的求解步骤的一种描述，其五个基本性质如上。
６.【答案】串的长度相等且两串中对应位置的字符也相等
【解析】考查两个字符串相等的定义。
７．【答案】n
2
+1
【解析】考查二叉树的性质3。
８.【答案】树内各结点的度
【解析】考查树的度的定义。
９．【答案】入度、出度
【解析】考查有向图中顶点度的定义。
10. 【答案】顺序存储、有序
【解析】
因为折半查找需要拿表中第mid（其中mid=(low+high）2)个元素与查找的关键字
进行
比较，所以要求查找表需要能随机存取，因此，要求顺序存储；另外，实施折半查找的
前提必须是有序表
，顺序表不可以。
二、选择题
1. 【答案】B
【解析】根据具有n个顶点的无向完全图的边数为n(n-1)2，代入公式即可。
2.
【答案】B
【解析】在循环队列中队列满的条件是以牺牲一个存储空间为代价的，即当满足选项B时就
判断该队列已满。
3. 【答案】D
【解析】考查数据对象的定义。
4. 【答案】A、D
k
【解析】无论是循环链表还是单链表都属于
线性表的链式存储，所以选A、D。邻接多重表
属于图的存储结构，孩子链表属于树的存储结构。
5. 【答案】C
【解析】考查栈的基本性质，选项C中a先于b入栈，因此出栈顺序a应该在b的后面。
6.
【答案】B、C
【解析】考查完全二叉树的定义及二叉树的基本性质。
7. 【答案】A
【解析】该有序表中有8个元素，因此，折半查找时，查找第8个元素，根据判定树可以获
得需
先后与第4、6、7、8个元素进行比较4次，所以选A。
8. 【答案】A、B
【解析】
处理冲突的方法主要有四种：分别是开放定址法（包含线性探测再散列以及二次探
测再散列等）、再哈希
法、链地址法和建立一个公共溢出区。
9. 【答案】C
【解析】一个排序算法的时间复杂度主要与所需关键字的比较次数有关。
10. 【答案】B
【解析】考查数据元素的概念。
三、求解下列问题
1．答：根据树与二叉树的转换方法，得出转化为的二叉树如下图所示：
A
B
G
C
D
I
FE
J
L
M
K
H由此可得先序遍历序列为：ABCDFEGHIJKLM
中序遍历序列为：CFDEBGJILMKHA;
后序遍历序列为：FEDCJMLKIHGBA
2．答：根据克鲁斯卡尔算法思想画图表示最小生成树的生成过程如下：
0<
br>1
5
343
21
0
1
21
0
12
2
1
3
4
0
1
2
2
543
5
5
43
0
1
3
1
2
2
1
3
4
4
3
5
0
1
2
2
5
5
4
4
3
四、程序填空
1．答：low<=high;
mid=(low+high)2;
return(mid);
high=mid-1;
low=mid+1;
2．答：struct node
p=p->next;
Linklist或是LNode *
(
注意字母大小写与类型定义一致
)
s->next=p->next;
p->next=s
五、算法设计（本大题共1小题，共10分）
答：
一、填空题
1. 【答案】集合、线性结构、树形结构、图状结构或网状结构
【解析】相互之间存在一种
或多种特定关系的数据元素的集合称为数据结构，根据数据元素
之间关系的不同特性通常分出了以上四种
逻辑结构。
2．【答案】插入和删除、后进现出（LIFO）
【解析】考查的栈的定义及性质，队列的定义及性质也需要牢固掌握。
3.
【答案】2-1
【解析】考查二叉树的性质2。
4. 【答案】图
【解析】根据图数据结构的特性。
５．【答案】有穷性、确定性、可行性、输入（0或多个）、输出（至少有1个）
【解析】算法是特定问题的求解步骤的一种描述，其五个基本性质如上。
６.【答案】串的长度相等且两串中对应位置的字符也相等
【解析】考查两个字符串相等的定义。
７．【答案】n
2
+1
【解析】考查二叉树的性质3。
８.【答案】树内各结点的度
【解析】考查树的度的定义。
９．【答案】入度、出度
【解析】考查有向图中顶点度的定义。
10. 【答案】顺序存储、有序
【解析】
因为折半查找需要拿表中第mid（其中mid=(low+high）2)个元素与查找的关键字
进行
比较，所以要求查找表需要能随机存取，因此，要求顺序存储；另外，实施折半查找的
前提必须是有序表
，顺序表不可以。
二、选择题
1. 【答案】B
【解析】根据具有n个顶点的无向完全图的边数为n(n-1)2，代入公式即可。
2.
【答案】B
【解析】在循环队列中队列满的条件是以牺牲一个存储空间为代价的，即当满足选项B时就
判断该队列已满。
3. 【答案】D
【解析】考查数据对象的定义。
4. 【答案】A、D
k
【解析】无论是循环链表还是单链表都属于
线性表的链式存储，所以选A、D。邻接多重表
属于图的存储结构，孩子链表属于树的存储结构。
5. 【答案】C
【解析】考查栈的基本性质，选项C中a先于b入栈，因此出栈顺序a应该在b的后面。
6.
【答案】B、C
【解析】考查完全二叉树的定义及二叉树的基本性质。
7. 【答案】A
【解析】该有序表中有8个元素，因此，折半查找时，查找第8个元素，根据判定树可以获
得需
先后与第4、6、7、8个元素进行比较4次，所以选A。
8. 【答案】A、B
【解析】
处理冲突的方法主要有四种：分别是开放定址法（包含线性探测再散列以及二次探
测再散列等）、再哈希
法、链地址法和建立一个公共溢出区。
9. 【答案】C
【解析】一个排序算法的时间复杂度主要与所需关键字的比较次数有关。
10. 【答案】B
【解析】考查数据元素的概念。
三、求解下列问题
1．答：根据树与二叉树的转换方法，得出转化为的二叉树如下图所示：
A
B
G
C
D
I
FE
J
L
M
K
H由此可得先序遍历序列为：ABCDFEGHIJKLM
中序遍历序列为：CFDEBGJILMKHA;
后序遍历序列为：FEDCJMLKIHGBA
2．答：根据克鲁斯卡尔算法思想画图表示最小生成树的生成过程如下：
0<
br>1
5
343
21
0
1
21
0
12
2
1
3
4
0
1
2
2
543
5
5
43
0
1
3
1
2
2
1
3
4
4
3
5
0
1
2
2
5
5
4
4
3
四、程序填空
1．答：low<=high;
mid=(low+high)2;
return(mid);
high=mid-1;
low=mid+1;
2．答：struct node
p=p->next;
Linklist或是LNode *
(
注意字母大小写与类型定义一致
)
s->next=p->next;
p->next=s
五、算法设计（本大题共1小题，共10分）
答：