1、數(shù)據(jù)結(jié)構(gòu)練習題及參考答案11數(shù)據(jù)結(jié)構(gòu)練習題一、解答題（共50分）字符出現(xiàn)頻率a0.05b0.03c0.24d0.16e0.08f0.24g0.18h0.02Prime方法從頂點c1、（8分）假設(shè)用于通訊的電文字符集及其出現(xiàn)的頻率如下表所 示。請為這8個字符設(shè)計哈夫曼編碼，并畫出其哈夫曼樹，計算WPL。2. （8分）若一棵二叉樹中序遍歷和后序遍歷序列分別為： DBEHGAFIC 和DHGEBIFCA 。試畫出這棵二叉樹，并寫出其 先序遍歷和層序遍歷序列。3. （16分）以下無向網(wǎng)絡(luò)以鄰接表為存儲結(jié)構(gòu)（假設(shè)鄰接表的 頂點表按字母a、b、c、d、e、f、g、h的順序依次存儲，鄰接表 的邊表結(jié)點按頂點

2、的下標由小到大鏈接）。請畫出其鄰接表，并 寫出從頂點f出發(fā)，分別進行深度和廣度優(yōu)先遍歷的序列，寫出用 開始產(chǎn)生最小生成樹的邊的序列4. （8 分）已知鍵值序列為（44, 39, 67, 25, 52, 59, 43, 84, 54, 58, 15, 26, 12, 73, 92, 69）,取填充因子a =0.8,采用線性探查法處理沖突，試構(gòu)造散列表。5. （5分）已知一組記錄為（67,88,15,12,60,37,7,31,45,81）用希爾排序方法進行排序， d1=5,d2=3,d3=1，則第二趟的排序結(jié)果是（）。6. （5分）已知一組記錄為（67,88,15,12,60,37,7,31,4

3、5,81）,用堆（大根堆）排序方法進行排序，第一趟的排序結(jié)果是（）0二、完善程序(共20分，每空2分)1.假設(shè)一組遞減有序的原始數(shù)據(jù)存儲在數(shù)組r中，存放元素的下標下限為low,下標上限為high,以下是在數(shù)組中查找數(shù)值為k的折半查找算法。請?zhí)羁胀晟瞥绦颉nt BinSearch(int r , int low,int high,int k) int l,h,m;l= low; h= high;while ()m= ;if (k < rm) ;else if (k > rm)(4) ;else return m;return 0;2.以下程序功能是將數(shù)組r中，從下標first到en

4、d之間的元素進行快速排序的分區(qū)。 請?zhí)羁眨晟瞥绦颉nt Partition(int r , int first, int end) int i,j,t;i=first; j=end;/ 初始化while ()while (i<j &&(6) j- ；/ 右側(cè)掃描if (i<j) t=ri;ri=rj;rj=t;i+;/將較小記錄交換到前面while ( S ) i+ ；/ 左側(cè)掃描if (i<j) t=ri;ri=rj;rj=t;j-;/將較大記錄交換到后面 /i為軸值記錄的最終位置3、以下程序是計算以rt所指向的結(jié)點為根結(jié)點的二叉樹的深度算法，請?zhí)羁眨?/p>

5、善程 序。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 (10) ;三、編程題(共30分)1 .(18分)假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素所 在的結(jié)點，但不設(shè)頭指針。試設(shè)計相應的入隊和出隊算法。template <class T>struct Node T data;Node<T> *

6、next;；template <class T>class CirLinkQueue Node<T> * rear;public:CirLinkQueue()rear=NULL; 構(gòu)造函數(shù)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 分)線性表存放在數(shù)組dataArrSiz

7、e 的前 element 個單元中，且遞增有序。編寫算法，將元素x 插入到線性表的適當位置上，并保持線性表的有序性。const int ArrSize=100;template<class T >class SeqList T dataArrSize;int element;public:void Insert(T x);template<class T >void SeqList<T>:Insert(T x)數(shù)據(jù)結(jié)構(gòu)練習題參考答案及評分標準、解答題（共50分）1.（共8分）哈夫曼樹（5分）哈夫曼編碼（2分）/0421.0010.580<1字符出現(xiàn) 頻

8、率哈夫曼 編碼01a0.050001，.18 O 0 C0.240.340.24b0.0300001c0.2401d0.16100 dTo 1e0.08001011G)100.08f0.2411_g_0.18101h0.02000000.160.1801口 0350.0501_0.020.03WPE5* (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分B/、 /傘 Q Q、G 9/H先序遍歷序列為：ABDEGHCFI層序遍歷序列為：ABCDEFGIH3 （共16分）鄰接表

9、一4分從頂點f出發(fā)，深度優(yōu)先遍歷序列：f-d-b-a-c-h-g-e-4分從頂點f出發(fā)，廣度優(yōu)先遍歷序列：f-d-e-g-b-c-g-h-4分用Prime方法從頂點c開始產(chǎn)生最小生成樹的邊的序列：-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

10、, 15, 26, 12, 73, 92, 69),填充因子a =0.8元素個數(shù)n=16表長 m=n/ q=16/0.8=20-1 分取 P=19-1 分散列函數(shù)為H（key尸key%19散列表如下：-6分散列地址012345678910111213141516171819關(guān)鍵字39595843442584266712695215547392探查次數(shù)11311213112111235. （5分）希爾排序第二趟結(jié)果為：12, 7, 15,37 , 31 , 45 , 81 , 60 , 67 , 886. （5分）堆排序第一趟結(jié)果為：60, 81 , 37,45 , 67 , 15 , 7, 3

11、1 , 12 , 88或6081374567157311288:、完善程序（共20分，每空2分）1. (8 分) l<=h(l+h)/2l=m+1h=m-12. (8 分) i<j (6)rj>=ri i<j&&ri<=rj return i 或 return j3. (4 分)(9) !rt 或 rt=NULL 或 rt=0(10) lh>rh?lh+1:rh+1三、編程題(共30分)1、(18 分)(1)入隊函數(shù)(9分)template<class T> void CirLinkQueue <T>:EnQueue(

12、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)出隊函數(shù)(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、