郑州轻工业大学近几年数据结构试卷

近几年数据结构试卷：

链接：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( )

解析：