【正文】 725191813121096745 Huffman樹習(xí)題7 圖 單項選擇題1．在一個圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的____倍。4. 5. 2 k1 、 2 k1 、 2 k2+1 6. n2+1 7. 2 i1 2[log2n+1]1 2[log2n+1] –1 8. 只有一個結(jié)點(diǎn)的樹；空的二叉樹9. 5；a 樹形5種aaaacccccbbbbbb10. dgbaechif 、abdgcefhi 、gdbeihfca 、 1. 5種, EBEFAECDKGHIJ 樹形5種2. 。8. 試編寫算法，對一棵以孩子兄弟鏈表表示的樹統(tǒng)計葉子的個數(shù)。7. 假設(shè)用于通訊的電文僅有八個字母(a,b,c,d,e,f,g,h)組成，, , , , , , , 。5. 以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值，畫出構(gòu)造Huffman樹的每一步圖示，計算其帶權(quán)路徑長度為。2. 假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。7. 一棵二叉樹的第i（i≥1）層最多有____個結(jié)點(diǎn)；一棵有n（n0）個結(jié)點(diǎn)的滿二叉樹共有____個葉子和____個非終端結(jié)點(diǎn)。123456789101112131415161718192021eafdgcjlhb 一棵二叉樹的順序存儲數(shù)組t4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組t中，則該二叉樹的鏈接表示形式為__ __。結(jié)論____是正確的。這種說法____。A. 二叉鏈表 B. 廣義表存儲結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲結(jié)構(gòu)18. ，____不是完全二叉樹。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaagedbchf a14. ，其中序遍歷的序列為__ __。 A. uwvts B. vwuts C. wuvts D. wutsv10. 二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法____。A. 16 B. 32 C. 31 D. 106. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_ ___。A. 正確 B. 錯誤2. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個，則葉子結(jié)點(diǎn)數(shù)為 個。2. 向一個長度為n的向量的第i個元素（1≤i≤n+1）之前插入一個元素時，需向后移動____個元素。A. rear front= =m0 B. rearfront1= =m0C. front= = rear D. front= = rear+111. 判定一個循環(huán)隊列QU（最多元素為m0, m0= =Maxsize1）為滿隊列的條件是____。 D. x=HS—＞data。 HS= HS—＞next。D. s—＞next= HS。B. s—＞next= HS—＞next。A. top !=0 B. top= =0 C. top !=m0 D. top= =m015. 判定一個順序棧ST（最多元素為m0）為棧滿的條件是____。 }} 習(xí)題答案 1. B 2. A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 1. 線性結(jié)表 2. 前驅(qū)結(jié)點(diǎn)、后繼結(jié)點(diǎn) 3. s, p 4. qnext, q 5. pnext, s 6. O (1) , O (n)習(xí)題3 棧和隊列 單項選擇題1. 一個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是____。 pnext=Lnext。 { p=Lnext。}4. 試寫一算法，實現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行)。 qdatab){r=q。 qdataa){p=q。void del(LinkList L,elemtype a,elemtype b){p= L。 a[i]=a[j]。void reverse(int a[], int size){ int i,j,tmp。i) [i+1]=[i]。 for(i=。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。 //填空delete 。qnext= 。3. 在一個單鏈表中p所指結(jié)點(diǎn)之前插入一個s (值為e)所指結(jié)點(diǎn)時，可執(zhí)行如下操作：q=head。A. n B. n/2 C. (n1)/2 D. (n+1)/2 15. 在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是__ __。13. 在一個單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行____。C. snext=pnext。A. snext=p。 snext=p。 pnext=s。 prightleft=s。 pright=s。 sleft=p。 prightleft=s。A. head= =NULL B. headnext= =NULLC. headnext= =head D. head!=NULL9. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足____。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以5. 在以下的敘述中，正確的是__ _。 習(xí)題答案 1. C , A 2. B,D 3. C 4. C, A 5. C,B 1. 線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)，非線性結(jié)構(gòu) 2. 沒有、沒有、1 3. 前驅(qū)、后續(xù)、任意多個 4. 任意多個 5. 一對一、一對多、多對多 6. 有窮性、確定性、可行性、輸入、輸出 7. 最大語句頻度：n2 ， 時間復(fù)雜度：. O (n2) 8. 最大語句頻度：n (n+1)/2 ， 時間復(fù)雜度：. O (n2) 9. 最大語句頻度：n3 ， 時間復(fù)雜度：. O (n3)10. 最大語句頻度：n ， 時間復(fù)雜度：. O (n) 11. 最大語句頻度：log2n， 時間復(fù)雜度：. O (log2n )習(xí)題2 線性表 單項選擇題1. 一個向量（即一批地址連續(xù)的存儲單元）第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是__ __。i=1。i=s=0。kn。in。 j++)A[i][j]=0。for (i=0。i++) for (j=0。6. 算法的五個重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。2. 在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) 后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個后續(xù)結(jié)點(diǎn)。 ① A．算法 Ｂ．?dāng)?shù)據(jù)元素 Ｃ．?dāng)?shù)據(jù)操作 Ｄ．?dāng)?shù)據(jù)對象 ② A．操作 Ｂ．映象 Ｃ．存儲 Ｄ．關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。 ① A．操作對象　　?。拢嬎惴椒ā　。茫壿嫿Y(jié)構(gòu)　?。模?dāng)?shù)據(jù)映象 ② A．存儲結(jié)構(gòu) Ｂ．關(guān)系 Ｃ．運(yùn)算 Ｄ．算法2. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS=（D，R），其中D是① 的有限集合，R是D上的② 有限集合。 ① A. 計算方法 B. 排序方法C. 解決問題的有限運(yùn)算序列 D. 調(diào)度方法② A. 可行性、可移植性和可擴(kuò)充性 B. 可行性、確定性和有窮性 C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和安全性 填空題（將正確的答案填在相應(yīng)的空中）1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為 。5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。in。8. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。 ji。for (i=0。j++) for (k=0。10. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。 //s=s+i } 11. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。寫出最大語句頻度，該算法的時間復(fù)雜度。A. 正確 B. 不正確4. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址__ _。