作業(yè)及答案ppt

1、數(shù)據(jù)結(jié)構(gòu)作業(yè)及答案（C語言版）,,2,目 錄,1、第2章 線性表2、第3章 棧和隊列3、第6章 樹和森林4、第7章 圖5、第8章 集合與查找6、第9章 索引與散列,3,第2章 線性表作業(yè)及答案1-1,1、已知有一個單鏈表L，設(shè)計一個算法，通過一趟遍歷，在L中確定值最大的結(jié)點，返回指向該結(jié)點的指針。(注：遍歷是指從頭至尾訪問單鏈表中的每一個結(jié)點且指訪問一次),4,第2章 線性表作業(yè)及答案1-2,2、設(shè)計一個算法，在非遞減

2、有序的單鏈表L中刪除值相同的多余結(jié)點,5,第3章 棧和隊列作業(yè)及答案2-1,假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素，同時設(shè)置一個標(biāo)志tag==0和tag==1來區(qū)別當(dāng)隊頭指針front和隊尾指針rear相等時，隊列的狀態(tài)是“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的入隊(EnQueue)和出隊(DeQueue)算法。要求先寫明結(jié)構(gòu)，再寫算法,6,第3章 棧和隊列作業(yè)及答案2-2,Status EnQueue(SqQueue &Q,

3、 ElemType e) { assert(!IsFull(Q)); Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; Q.tag=1; //標(biāo)志改1，表示隊列非空 return OK;}Status DeQueue(SqQueue &Q, ElemType &e) { assert(!IsEmpty); e=Q.base[Q.front];

4、 Q.front=(Q.front+1)%MAXQSIZE; Q.tag=0; //標(biāo)志改0，表示隊列不滿 return OK;},7,第6章 樹和森林作業(yè)及答案4-1,1、編寫遞歸算法，統(tǒng)計二叉樹中度為2的結(jié)點個數(shù),8,第6章 樹和森林作業(yè)及答案4-2,2、給定權(quán)值集合{ 15, 3, 14, 2, 6, 9, 16, 17 }，構(gòu)造相應(yīng)的Huffman樹，并計算它的帶權(quán)路徑長度(要求畫出Huffman樹的構(gòu)造過程),

5、9,第6章 樹和森林作業(yè)及答案4-3,10,第6章 樹和森林作業(yè)及答案4-4,此樹的帶權(quán)路徑長度WPL=229,11,第7章 圖作業(yè)及答案5-1,1、用數(shù)學(xué)歸納法證明有n個頂點的完全無向圖有n(n-1)/2條邊,【證明】 (1) 當(dāng)n=1時，一個頂點時，邊數(shù)為0，成立。 (2) 當(dāng)n=2時，兩個頂點，邊數(shù)為1，成立。 (3) 設(shè)n=k時成立，即k個頂點的完全無向圖有k(k-1)/2條邊，則n=k+1時，第k+1個頂點到

6、其他k個頂點的邊數(shù)共k條，于是總邊數(shù)為 k(k-1)/2+k=(k+1)k/2。 ? 結(jié)論成立。,12,第7章 圖作業(yè)及答案5-2,2、對于如圖所示的有向圖，試畫出從頂點①出發(fā)進行深度優(yōu)先搜索得到的深度優(yōu)先生成樹,結(jié)果不唯一,13,第8章 集合與查找作業(yè)及答案6-1,將關(guān)鍵字{ DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN }依次插入到一棵初始為空

7、的AVL樹中，畫出每插入一個關(guān)鍵字后的AVL樹，需要平衡時標(biāo)明平衡旋轉(zhuǎn)的類型和結(jié)果(注：按字典順序比較),DEC,14,第8章 集合與查找作業(yè)及答案6-2,15,第8章 集合與查找作業(yè)及答案6-3,16,第8章 集合與查找作業(yè)及答案6-4,17,第9章 索引與散列作業(yè)及答案7-1,給定關(guān)鍵字序列{ 11, 78, 10, 1, 3, 2, 4, 21 }，分別用順序查找、折半查找、二叉排序樹、平衡二叉樹、散列表(用線性探查法和鏈

8、地址法)實現(xiàn)查找，畫出它們對應(yīng)的存儲結(jié)構(gòu)(順序查找的順序表，折半查找的二叉判定樹，二叉排序樹、平衡二叉樹以及兩種散列表)，并求出每一種查找在等概率下查找成功時的ASL。其中，散列表為HT[11]，散列函數(shù)為H(key)=key%11,18,第9章 索引與散列作業(yè)及答案7-2,可以得到順序查找的平均查找長度為：ASL=(1+2+3+4+5+6+7+8)/8=(8+1)/2=4.5(2) 先按關(guān)鍵字排序，折半查找的判定樹如圖所示，,從圖

9、可以得到折半查找的平均查找長度為：ASL=(1+2*2+3*4+4*1)/8=21/8=2.625,19,第9章 索引與散列作業(yè)及答案7-3,(3) 二叉排序樹和平衡二叉樹如圖所示，,從圖可以得到二叉排序樹查找的平均查找長度為：ASL=(1+2*2+3*2+4*1+5*2)/8=25/8=3.125平衡二叉樹的成功平均查找長度為：ASL=(1*1+2*2+3*3+4*2)/8=22/8=2.75,20,第9章 索引與散列作業(yè)及答