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

数据结构练习题一、解答题（共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的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并写出从顶点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 rm) ; 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 (ij & ) j-； /右侧扫描 if (ij) t=ri; ri=rj; rj=t; i+; /将较小记录交换到前面 while ( ) i+； /左侧扫描 if (ij) t=ri; ri=rj; rj=t; j-; /将较大记录交换到后面 /i为轴值记录的最终位置3、以下程序是计算以rt所指向的结点为根结点的二叉树的深度算法，请填空，完善程序。templateint BiTree:High(BiNode *rt)int lh,rh;if( ) return 0;elselh=High(rt-lchild);rh=High(rt-rchild);return ;三、编程题（共30分）1.（18分）假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾元素所在的结点，但不设头指针。试设计相应的入队和出队算法。template struct Node T data; Node * next;template class CirLinkQueue Node * rear; public:CirLinkQueue() rear=NULL;/构造函数void EnQueue(T x);/将元素x入队T DeQueue();/出队;templatevoid CirLinkQueue :EnQueue(T x)templateT CirLinkQueue :DeQueue()2.（12分）线性表存放在数组dataArrSize的前element个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，并保持线性表的有序性。const int ArrSize=100;templateclass SeqList T dataArrSize;int element; public: void Insert(T x); ;templatevoid SeqList:Insert(T x)数据结构练习题参考答案及评分标准一、解答题（共50分）1. （共8分）哈夫曼树（5分） 1.00 哈夫曼编码（2分） 0 1 0.42 0.58字符出现频率哈夫曼编码a0.050001b0.0300001c0.2401d0.16100e0.08001f0.2411g0.18101h0.0200000 0 1 0 1 0.18 0.24 0.34 0.24 0 1 0 1 0.10 0.08 0.16 0.18 0 1 0.05 0.05 0 1 0.02 0.03 WPL5*（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分 A B C D E F G I H 先序遍历序列为： ABDEGHCFI -1分层序遍历序列为： ABCDEFGIH -1分3（共16分）邻接表4分 abcdefgh12 02340137124567135346357236从顶点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分散列地址012345678910111213141516171819关键字39595843442584266712695215547392探查次数1131121311211123（5分）希尔排序第二趟结果为： 12，7，15，37，31，45，81，60，67，88（5分）堆排序第一趟结果为： 60，81，37，45，67，15，7，31，12，88或 60 81 37 45 67 15 7 31 12 88 二、完善程序（共20分，每空2分）1.(8分 ) l=h (l+h)/2 l=m+1 h=m-1 2.（8分） i=ri ij &rirh?lh+1:rh+1 三、编程题（共30分）1、（18分）（1）入队函数（9分）templatevoid CirLinkQueue :EnQueue(T x) Node *s=new Node; s-data=x;if(!rear) rear=s; rear-next=rear;else s-next=rear-next; rear-next=s; rear=s;（2）出队函数（9分）templateT CirLinkQueue :DeQueue() if(!rear) throw”队空n”; Node *p=rear-next; T x=p-data; if(rear-next=rear) rear=NULL;else rear-next=p-next; d