近几年数据结构试卷：
链接：https://pan.baidu.com/s/1_ns6dbps8i6UyLN5RNJJiw?pwd=g3z2
提取码：g3z2
2019-2020（2）数据结构期末考试试卷
一、 简答题（共10题，100分）
1、已知某二叉树的先序序列和中序序列分别为ABDGEHCFI和DGBHEACIF，请画出这棵二叉树，并画出二叉树对应的森林。
正确答案：
二叉树正确得4分，森林正确得4分，满分8分。
解析：
2、依次把结点（50,75,80,35,40,28,63,51,8,21）插入初始状态为空的平衡二叉排序树，使得每次插入后该树仍然是平衡二叉树。请依次画出插入及平衡化过程。
正确答案：
每正确插入一个结点得1分，满分10分。
解析：
3、假设用于通讯的电文由字符a,b,c,d,e,f,g,h组成，字符在电文中出现的频率分别为3,8,12,21,17,19,4,16。
（1）画出你所建的赫夫曼树（画出构建过程）；
（2）给出每一字符的赫夫曼编码。
正确答案：
赫夫曼树答案不唯一。
构造过程为7步，每步1分。编码正确得3分。
解析：
4、已知带权无向图的邻接矩阵如下图所示，
（1）请画出该图，并画出该图的邻接表；
（2）从顶点A出发，写出该图的深度优先遍历序列和广度优先遍历序列；
（3）从顶点A出发，采用Prim算法求该图的最小生成树，画出求解过程。
正确答案：
（1）图正确得4分，邻接表正确得4分（邻接表不唯一）。
（1）图正确得4分，邻接表正确得4分（邻接表不唯一）。
（1）图正确得4分，邻接表正确得4分（邻接表不唯一）。
（2）每个序列正确得1分（遍历序列不唯一），共2分。
DFS序列：ABECFDG
BFS序列：ABCDEFG
（3）最小生成树每步1分，共6分。
解析：
5、AOE网是带权有向图，图中顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销。假设某项工程可以分解为若干个活动，下图给出了该工程各活动之间的优先关系和各活动所需的时间，请完成以下各题。
（1）写出2个拓扑排序序列；
（2）求出各事件、各活动的最早发生时间和最迟发生时间。
（3）求出关键路径，并指明完成该工程所需的最短时间。
正确答案：
（1）拓扑排序序列正确得2分（序列不唯一）
v1,v2,v4,v5,v3,v6,v7,v8
v1,v2,v3,v4,v5,v6,v7,v8
（3）求解正确得2分。
时间活动余量为0的活动：A,E,L,M；关键路径为v1,v2,v6,v7,v8
工程所需最短时间为11。
解析：
6、对下图所示的3阶B-树，依次执行下列操作，画出各步操作的结果。
（1）插入65 （2）插入25 （3）插入55 （4）删除100 （5）删除80
正确答案：
每一小问回答正确得2分。
解析：
7、给定一组查找关键字(32,15,7,11,4,28,56,61,79)，哈希表长为m=12，请按照除留余数法设计一个哈希函数，设每个记录的查找概率相等。
（1）画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算查找成功和查找失败时的平均查找长度各是多少。
（2）画出按照链地址法处理冲突得到的哈希表，并计算查找成功和查找失败时的平均查找长度各是多少。
正确答案：
每一小问为5分，其中哈希表构造正确得3分，每种平均查找长度计算正确得1分。哈希函数样例：H(key) = kye % 11。
（1）线性探测再散列
H(32) = 32 % 11 = 10
H(15) = 15 % 11 = 4
H(7) = 7 % 11 = 7
H(11) = 11 % 11 = 0
H(4) = 4 % 11 = 4 (4+1) % 12 = 5
H(28) = 28 % 11 = 6
H(56) = 56 % 11 = 1
H(61) = 61 % 11 = 6 (6+1) % 12 = 7; (6+2) % 12 = 8
H(79) = 79 % 11 = 2
查找成功时的平均查找长度： ASL = (7*1 + 1*2 + 1*3)/9 = 12/9 = 4/3;
查找失败时的平均查找长度： ASL = (4+3+2+1+6+5+4+3+2+1+2)/11 = 33/11 = 3。
（2）链地址法：
查找成功时的平均查找长度： ASL = (7*1 + 2*2)/9 = 11/9;
查找失败时的平均查找长度： ASL = (2*5 + 1*4 + 3*2)/11 = 20/11。
解析：
8、请尽可能多的列举你所知道的稳定排序方法和不稳定排序方法，对每种不稳定的排序方法各举一例来证明不稳定性。
正确答案：
稳定的排序方法有：直接插入排序、冒泡排序、归并排序、链式基数排序；（2分）
不稳定的排序方法有：希尔排序、快速排序、简单选择排序、堆排序。（2分）
举例：
序列 1 3 2 2，希尔排序后为 1 2 2 3； （1分）
序列 2 2 3 1，快速排序后为 1 2 2 3； （1分）
序列 2 3 2 1，堆排序后为1 2 2 3； （1分）
序列2 2 3 1，简单选择排序后为 1 2 2 3；（1分）
解析：
9、单链表结构定义如下：
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
给定一个带头结点的单链表L，表中结点元素值唯一，按递减次序输出单链表中各结点的元素值，并释放结点所占存储空间（要求：算法的空间复杂度为O(1)）。请采用C或者C++语言描述算法。
正确答案：
评分标准如下：
（1）能实现题目要求的功能，算法正确，表述清楚，代码规范，得8分
（2）能实现题目要求的功能，算法无逻辑错误，代码表述有少量语法错误（笔误性质），可得7-8分
（4）能实现题目要求的功能，算法有bug(对某个特殊输入，可能得不到正确结果），可得4-6分
（5）能表达出核心功能的实现方法，算法有逻辑错误，可得2-3分
（6）核心功能没有实现，算法有严重逻辑错误，可得0-2分
参考代码如下
void Delete(LinkList &L)
{
while(L->next != NULL){
pre = L;
p = pre->next;
while( p->next != NULL) {
if( p->next->data > pre->next->data)
pre = p;
p = p->next;
}
print( pre->next->data);
u = pre->next;
pre->next = u->next;
free(u);
}
free(L);
}
解析：
10、单链表结构定义如下：
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
给定一个带头结点的单链表L，表中结点元素值唯一，试采用直接插入排序法将L中的结点按值递减次序排列，并分析算法的时间复杂度。请采用C或者C++语言描述算法。
正确答案：
评分标准如下：
（1）能实现题目要求的功能，算法正确，表述清楚，代码规范，得8分
（2）能实现题目要求的功能，算法无逻辑错误，代码表述有少量语法错误（笔误性质），可得7-8分
（4）能实现题目要求的功能，算法有bug(对某个特殊输入，可能得不到正确结果），可得4-6分
（5）能表达出核心功能的实现方法，算法有逻辑错误，可得2-3分
（6）核心功能没有实现，算法有严重逻辑错误，可得0-2分
参考代码如下
void Sort(LinkList &L)
{
p = L->next->next;
L->next->next=NULL;
while( p!=NULL){
q = p->next;
pre = L;
while( pre->next!=NULL && pre->next->data > p-data){
pre = pre->data;
}
p->next = pre->next;
pre->next = p;
p=q;
}
}
时间复杂度为O( )
解析：
文章来源地址https://www.toymoban.com/news/detail-824162.html
文章来源：https://www.toymoban.com/news/detail-824162.html
到了这里，关于郑州轻工业大学近几年数据结构试卷的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
