数据结构练习题及参考答案《数据结构》练习题一、解答题（共50分）1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算WPL。

2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为：DBEHGAFIC和DHGEBIFCA。

试画出这棵二叉树，并写出其先序遍历和层序遍历序列。

3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。

请画出其邻接表，并写出从顶点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) ，用堆（大根堆）排序方法进行排序，第一趟的排序结果是（）。

二、完善程序（共20分，每空2分）1.假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。

请填空完善程序。

int BinSearch(int r[ ], int low,int high,int k){ int l,h,m;l= low; h= high;while ( ⑴){m= ⑵;if (k < r[m]) ⑶;else if (k > r[m]) ⑷;else return m;}return 0;}2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。

请填空，完善程序。

int Partition(int r[ ], int first, int end){ int i,j,t;i=first; j=end; //初始化while ( ⑸){while (i<j && ⑹) j--；//右侧扫描if (i<j) {t=r[i]; r[i]=r[j]; r[j]=t; i++; //将较小记录交换到前面}while ( ⑺) i++；//左侧扫描if (i<j) {t=r[i]; r[i]=r[j]; r[j]=t; j--; //将较大记录交换到后面}}⑻//i为轴值记录的最终位置}3、以下程序是计算以rt所指向的结点为根结点的二叉树的深度算法，请填空，完善程序。

template<class T>int BiTree<T>::High(BiNode<T> *rt){ int lh,rh;if( ⑼) return 0;else{ lh=High(rt->lchild);rh=High(rt->rchild);return ⑽;}}三、编程题（共30分）1.（18分）假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾元素所在的结点，但不设头指针。

试设计相应的入队和出队算法。

template <class T>struct Node{ T data;Node<T> * next;};template <class T>class CirLinkQueue{ Node<T> * rear;public:CirLinkQueue(){ rear=NULL;}//构造函数void EnQueue(T x);//将元素x入队T DeQueue();//出队……};template<class T>void CirLinkQueue <T>::EnQueue(T x){……}template<class T>T CirLinkQueue <T>::DeQueue(){……}2.（12分）线性表存放在数组data[ArrSize]的前element个单元中，且递增有序。

编写算法，将元素x插入到线性表的适当位置上，并保持线性表的有序性。

const int ArrSize=100;template<class T >class SeqList{ T data[ArrSize];int element;public:void Insert(T x);……};template<class T >void SeqList<T>::Insert(T x){……}《数据结构》练习题参考答案及评分标准一、解答题（共50分） 1. （共8分） 哈夫曼树（5分） 1.00哈夫曼编码（2分）0 10.42 0.58 0 1 0 1 0.18 0.24 0.34 0.24 0 1 0 10.10 0.08 0.16 0.18 0 1 0.05 0.05 0 1 0.02 0.03WPL＝5*（0.02+0.03）+4*0.05+3*（0.16+0.08+0.18）+2*（0.24+0.24）＝2.67（1分）2．（共8分）二叉树原型：--6分AB CD E FG IH先序遍历序列为：ABDEGHCFI ----1分层序遍历序列为：ABCDEFGIH ----1分3（共16分）邻接表—4分从顶点f出发，深度优先遍历序列：f-d-b-a-c-h-g-e --4分从顶点f出发，广度优先遍历序列：f-d-e-g-b-c-g-h --4分用Prime方法从顶点c开始产生最小生成树的边的序列：--4分(c,a)3,(a,b)4,(c,h)5,(h,d)4,(d,g)5,(f,g)2,(f,e)3或(c,a)3,(a,b)4,(c,d)5,(h,d)4,(d,g)5,(f,g)2,(f,e)3或(c,a)3,(a,b)4,(b,d)5,(h,d)4,(d,g)5,(f,g)2,(f,e)34.（8分）键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，填充因子α=0.8元素个数n=16表长m=n/α=16/0.8=20 --1分取P=19 --1分散列函数为H(key)=key%19散列表如下：--6分⒌（5分）希尔排序第二趟结果为：12，7，15，37，31，45，81，60，67，88⒍（5分）堆排序第一趟结果为：60，81，37，45，67，15，7，31，12，88或6081 3745 67 15 731 12 88二、完善程序（共20分，每空2分）1.(8分)⑴l<=h ⑵(l+h)/2 ⑶l=m+1 ⑷h=m-12.（8分）⑸i<j ⑹r[j]>=r[i] ⑺i<j &&r[i]<=r[j] ⑻return i 或return j3.（4分）⑼!rt 或rt==NULL或rt==0⑽lh>rh?lh+1:rh+1三、编程题（共30分）1、（18分）（1）入队函数（9分）template<class T>void CirLinkQueue <T>::EnQueue(T x){ Node<T> *s=new Node<T>;s->data=x;if(!rear){ rear=s;rear->next=rear;}else{ s->next=rear->next;rear->next=s;rear=s;}}（2）出队函数（9分）template<class T>T CirLinkQueue <T>::DeQueue(){ if(!rear) throw”队空\n”;Node<T> *p=rear->next;T x=p->data;if(rear->next==rear) rear=NULL;else rear->next=p->next;delete p;return x;}2、（12分）template<class T >void SeqList<T>::Insert(T x){ if(element>=ArrSize) throw”表满，无法插入\n”;int i=element-1;while(i>=0&&x<data[i]){ data[i+1]=data[i];i- -;}data[i]=x;element++;}11。