数据结构期末考试试题及答案1
诺贝尔奖金-财务收支审计报告
一、填空题
1. 【答案】集合、线性结构、树形结构、图状结构或网状结构
【解析】相互之间存在一种或多种特定关系的数据元素的集合称为数据结构,根据数据元素
之间关系的
不同特性通常分出了以上四种逻辑结构。
2.【答案】插入和删除、后进现出(LIFO)
【解析】考查的栈的定义及性质,队列的定义及性质也需要牢固掌握。
3.
【答案】2-1
【解析】考查二叉树的性质2。
4. 【答案】图
【解析】根据图数据结构的特性。
5.【答案】有穷性、确定性、可行性、输入(0或多个)、输出(至少有1个)
【解析】算法是特定问题的求解步骤的一种描述,其五个基本性质如上。
6.【答案】串的长度相等且两串中对应位置的字符也相等
【解析】考查两个字符串相等的定义。
7.【答案】n
2
+1
【解析】考查二叉树的性质3。
8.【答案】树内各结点的度
【解析】考查树的度的定义。
9.【答案】入度、出度
【解析】考查有向图中顶点度的定义。
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. 【答案】图
【解析】根据图数据结构的特性。
5.【答案】有穷性、确定性、可行性、输入(0或多个)、输出(至少有1个)
【解析】算法是特定问题的求解步骤的一种描述,其五个基本性质如上。
6.【答案】串的长度相等且两串中对应位置的字符也相等
【解析】考查两个字符串相等的定义。
7.【答案】n
2
+1
【解析】考查二叉树的性质3。
8.【答案】树内各结点的度
【解析】考查树的度的定义。
9.【答案】入度、出度
【解析】考查有向图中顶点度的定义。
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分)
答: