数据结构练习题及参考答案

《数据结构练习题及参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》练习题一、解答题（共50分）字符出现频率a0.05b0.03c0.24d0.16e0.08f0.24g0.18h0.021、（8分）假设用于通讯的电文字符集及其出现的频率如下表所示。请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算WPL。2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为：DBEHGAFIC和DHGEBIFCA。试画出这棵二叉树，并写出其先序遍历和层序遍历序列。3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并写出从顶

2、点f出发，分别进行深度和广度优先遍历的序列，写出用Prime方法从顶点c开始产生最小生成树的边的序列。4.（8分）已知键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（）。⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用堆（大根堆）排序方法进行排序，第一趟的排序

3、结果是（）。二、完善程序（共20分，每空2分）1.8假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。请填空完善程序。intBinSearch(intr[],intlow,inthigh,intk){intl,h,m;l=low;h=high;while(⑴){m=⑵;if(kr[m])⑷;elsereturnm;}return0;}2.以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。请填空，完善程序。intPartition(in

4、tr[],intfirst,intend){inti,j,t;i=first;j=end;//初始化while(⑸){while(iintBiTree::High(B

5、iNode*rt){intlh,rh;if(⑼)return0;else{lh=High(rt->lchild);rh=High(rt->rchild);return⑽;}}三、编程题（共30分）1.（18分）假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾元素所在的结点，但不设头指针。试设计相应的入队和出队算法。templatestructNode{Tdata;Node*next;};templateclassCirLinkQueue{Node*rear;public:CirLinkQueue(){rear=NUL

6、L;}//构造函数voidEnQueue(Tx);//将元素x入队TDeQueue();//出队……};templatevoidCirLinkQueue::EnQueue(Tx){……}templateTCirLinkQueue::DeQueue()8{……}2.（12分）线性表存放在数组data[ArrSize]的前element个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，并保持线性表的有序性。constintArrSize=100;templateclassSeqList{Tdata[ArrS

7、ize];intelement;public:voidInsert(Tx);……};templatevoidSeqList::Insert(Tx){……}8《数据结构》练习题参考答案及评分标准一、解答题（共50分）1.（共8分）哈夫曼树（5分）1.00哈夫曼编码（2分）010.420.58字符出现频率哈夫曼编码a0.050001b0.0300001c0.2401d0.16100e0.08001f0.2411g0.18101h0.020000001010.180.240.