； ;
;
5n个结点无向 。

24、完全图的的边数为， n个结点的生成树的边数为。
6已知一有向无环图如下：BACDFEG任意写出二种拓扑排序序列： 、。
7已知二叉树的中序遍历序列为BCA ， 后序遍历序列为CBA ， 则该二叉树的先序遍历序列为， 层序遍历序列为 .三、 应用题1 设散列函数H(k)=k 13 ， 设关键字系列为22,12 ， 24 ， 6,45 ， 7,8 ， 13,21 ， 要求用线性探测法处理冲突.（6分）(1) 构造HASH表.(2） 分别求查找成功和不成功时的平均查找长度.2 给定表（19 ， 14 ， 22,15,20 ， 21 ， 56 ， 10).（8分）（1） 按元素在表中的次序 ， 建立一棵二叉排序树（2） 对（1）中所建立的二叉排序树进行中序 。

25、遍历 ， 写出遍历序列.（3） 画出对（2）中的遍历序列进行折半查找过程的判定树 。
3 已知二个稀疏矩阵A和B的压缩存储三元组表如下:A BijVijV13-5252246337252413421529529558写出A-B压缩存储的三元组表 。
(5分）4 已知一维数组中的数据为(18 ， 12 ， 25,53 ， 18）, 试写出插入排序（升序）过程 。
并指出具有n个元素的插入排序的时间复杂度是多少？(5分）5 已知一网络的邻接矩阵如下,求从顶点A开始的最小生成树.（8分 ， 要有过程）A B C D E F（1)求从顶点A开始的最小生成树 。
（2)分别画出以A为起点的DFS生成树和BFS生成树 。
6已知数据六个字母及在 。

26、通信中出现频率如下表：ABCDEF0.150 。
150 。
10.10 。
20 。
3把这些字母和频率作为叶子结点及权值,完成如下工作(7分 ， 要有过程） 。
（1） 画出对应的Huffman树 。
（2） 计算带权路径长度WPL 。
（3） 求A、B、C、D、E、F的Huffman编码 。
7 已知有如下的有向网:A2 5364 10 6 1 22 EBDC求顶点A到其它各顶点的最短路径（采用Dijkstra算法,要有过程） 。
（6分）四、 设计题(30分 ， 每题10分 ， 用C语言写出算法,做在答题纸上）1 已知线性表（a1 ， a2 ， an)以顺序存储结构为存储结构 ， 其类型定义如下：#define LIST_INIT_SIZE 1 。

27、00 /顺序表初始分配容量typedef struct Elemtype *elem； /顺序存储空间基址int length； /当前长度（存储元素个数）SqList;
设计一个算法 ， 删除其元素值为x的结点(假若x是唯一的).并求出其算法的平均时间复杂度 。
其算法函数头部如下：Status ListDelete（Sqlist L ， Elemtype x)ana2a12设顺序栈如左图所示 。
其中结点定义如下： toptypedef struct Elemtype *base;
/栈底指针Elemtype top;
/栈顶指针Stack；设计算法 ， 将栈顶元素出栈并存入e中 base3设二叉链树的类型定义 。

28、如下：typedef int Elemtype;
typedef struct nodeElemtype data；struct node lchild, *rchild； BinNode ，*BinTree;
试写出求该二叉树叶子结点数的算法：Status CountLeaves（BinTree root ， int n）/n is the number of leaves试题3答案一、 选择题（每题1分）1、 C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 二、 填空题1 设计、实现2 特殊、栈顶3 LOC（a1）+(i1)*L4 p-next=qnext；q-nex 。

29、t-prior=p;
qnext=p；pprior=q;
5 n（n1)/2、n16 ADCBFEG、ABCDEFFG7 ABC、ABC三、 应用题1 。
（1)Hash表（4分）地址0123456789101112关键安132164572282412探测次数171231311（2）查找成功的平均查找长度：（1分）（5*1+12+23+17）/9=20/9查找不成功的平均查找长度：(1分)（2+1+9+8+7+6+5+4+3+2+1）/13=2.（1)、构造(3分）1914 2210 15 20 5621(2）、10 14 15 19 20 21 22 56(2分)（3）、 (3分）3、（5分 ， 每 。

30、行0 。
5）ijv13524633741342-152185584、 初始关键字： 18 12 25 53 18第 一 趟: 12 18 25 53 18第 二 趟：12 18 25 53 18第 三 趟：12 18 25 53 18第 四 趟:12 18 18 25 53 （4分）O(n2）（1分） 。
5、7分(1)4分AB 1 C 3 25 D 4 E F（2）4分6、（1） 3分E FA B C D（2）WPL=0.13+0.1*3+0.22+0.153+0.15*3+0321= （1分)（3)A：010 B：011 C:110 D：111 E：00 F；10 （3分）7、A-B：(A、B) 。

31、 1分AC：(A、D、C) 2分A-D：(A、D) 1分AE：（A、D、E） 2分四、 设计题（30分)1、(10分)Status ListDelete(Sqlist L,ElemType x)int i ， j;
for（i=0；iL-length；i+）if(L-elemi=x) break;
if（i=L-length) return ERROR;
for(j=i;
jlengthi1；j+)L-elemj=L-elemj+1；Llength;
（8分）平均时间复杂度:（2分）设元素个数记为n ， 则平均时间复杂度为：2、（10分）void pop（Stack &S, Elemtype &e）if(S. 。

32、top=S 。
base） return ERROR;
S.top-；e=*s 。
top;
3、（10分)voidCountLeaves（BinTree T,int &n)if(T)if(!（Tlchild)&!（ Trchild)） n+;
CountLeaves （Tlchild ， n);
CountLeaves （T-rchild,n）；结尾处 ， 小编送给大家一段话 。

来源：(未知)

【学习资料】网址：/a/2021/0321/0021738320.html

标题：数据结构|(完整word版)2017《数据结构》期末考试试题及答案( 四 )