數(shù)據(jù)結(jié)構(gòu)作業(yè)及答案講解

1、第一章 緒論一、選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的1 以及它們之間的 2和運算等的學(xué)科。 1 A. 數(shù)據(jù)元素B.計算方法C.邏輯存儲D.數(shù)據(jù)映像2A. 結(jié)構(gòu)B.關(guān)系C.運算D. 算法2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為 (K, R)，其中 K 是 1 的有限集， R是 K 上的 2 有限集。1A. 算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D. 邏輯結(jié)構(gòu)2A. 操作B.映像C.存儲D. 關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種1 的存儲結(jié)構(gòu)， 線

2、性表的鏈式存儲結(jié)構(gòu)是一種2的存儲結(jié)構(gòu)。 A. 隨機存取B.順序存取C.索引存取D.散列存取5. 算法分析的目的是 1 ，算法分析的兩個主要方面其一是指 2 ，其二是指正確性和簡 單性。 1 A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性2A. 空間復(fù)雜度和時間復(fù)雜度B.研究算法中的輸入和輸出的關(guān)系C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 k6. 計算機算法指的是 1 ，它必須具備輸入、輸出和 2 等 5 個特性。1 A. 計算方法B.排序方法C.解決問題的有限運算序列D. 調(diào)度方法2 A. 可執(zhí)行性、可移植性和可擴充性B.可

3、行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性7. 線性表的邏輯順序與存儲順序總是一致的，這種說法。 A. 正確 B. 不正確8 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址。A. 必須連續(xù)的 B.部分地址必須連續(xù)的C.一定是不續(xù)的 D 連續(xù)不連續(xù)都可以9. 以下的敘述中，正確的是。A. 線性表的存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進先出 D. 隊列的操作方式是先進后出10. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找，這種說法。 A. 正確 B.不正確二、填空題 1.數(shù)據(jù)邏輯結(jié)構(gòu)包括三種類型、 和 ，

4、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為。2.在線性結(jié)構(gòu)中，第一個結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；最后一個結(jié)點 后續(xù)結(jié)點，其余每個結(jié)點有且只有 個后續(xù)結(jié)點。 3.算法的五個重要特性是、 、 、 、 。4. 下面程序段的時間復(fù)雜度是。6.下面程序段的時間復(fù)雜度是。s = 0;for( i = 0; i n; i+) for( j = 0; j n; j+) s += Bij;sum = s;7.下面程序段的時間復(fù)雜度是i = 1;while ( i = n )i = i * 3;for( i = 0; i n; i+) for( j = 0; j m; j+) Aij = 0;5. 下面程序段的

5、時間復(fù)雜度是i = s = 0;while ( s n)i +; /* i = i +1*/ s += i;/* s = s + i*/第一章 緒論（參考答案）一、選擇題： 1. A. B。2. B. D。3. C。4. A. B。（順序存儲結(jié)構(gòu)的地址在內(nèi)存中是連 續(xù)的所以可以通過計算地址的相對變化而實現(xiàn)隨機存取， 而鏈式存儲結(jié)構(gòu)的存儲地址不一定連續(xù)，只能通過 結(jié)點 的指針按次序順序存取）5. C. A 。 6. C.B。7.B 。 8.D。 9. B 。 10. B。二、填空題：1. 線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖形結(jié)構(gòu)，非線性結(jié)構(gòu)。 2.沒有， 1，沒有， 1。3.有窮性，確定性，可行性，輸入，輸

6、出。4. O （m*n ）。 5.O（ n ）。6.2O（n2）。7. O（ log3n）。5. O （ n ）。解：設(shè)基本語句頻度為 N。N=1 ， i=1 ， s=1; N=2，i=2，s=1+2；N=1，i=1，s=1；N=3，i=3，s=1+2+3； 當頻度為 N 時， i=N ， s=1+2+3 +N 。則根據(jù)循環(huán)條件， s=1+2+3+ +Nn ， 即： N（N +1） n2所以，時間復(fù)雜度為 T（n） = O（ n）7. O（log 3n）。解：設(shè)基本語句的頻度為 N 。（注意此題沒有限制語句頻度）N=1,i=3;N=2,i=9;N=3,i=27; 當頻度為 N 時， i=3 N

7、 所以 3Nn （據(jù)語句 in） Ntop!=0 B. ST-top=NULLC. ST-top!= mD. ST-top= m6. 判斷一個棧 ST （最多元素為 m） 為滿棧的條件是 。A.ST-top!=0 B. ST-top=0 C. ST-top!= m-1 D. ST-top= m7. 棧的特點是 1 ，隊列的特點是 2 。A. 先進先出B. 先進后出8. 一個隊列的入隊序列是 1、2、3、 4，則隊列輸出序列是。A.4、3、2、1B. 1、2、3、4C. 1、4、 3、2D.3 、2、 4、 19. 判斷一個隊列 QU （最多元素為 m） 為空的條件是 。A. QU-rear Q

8、U-front = mB. QU-rear QU-front 1 = mC. QU-front = QU-rear D. QU-front QU-rear + 110. 判斷一個隊列 QU （最多元素為 m） 為滿隊列的條件是 。A. QU-rear QU-front = mB. QU-rear QU-front 1 = mC. QU-front = QU-rear D. QU-front QU-rear + 111. 判斷一個循環(huán)隊列 QU （最多元素為 m） 為空的條件是 。A. QU-front = QU-rear B. QU-front != QU-rearC. QU-front =

9、（QU-rear + 1） %mD. QU-front != （QU-rear + 1） %m12. 判斷一個循環(huán)隊列 QU （ 最多元素為 m） 為滿隊列的條件是 。A. QU-front = QU-rear B. QU-front != QU-rearC. QU-front = （QU-rear + 1） %mD. QU-front != （QU-rear + 1） %m13 循環(huán)隊列用數(shù)組 A0, m-1 存放其元素值，已知其頭尾指針分別是 front 和 rear，則當前隊 列中的元素個數(shù)是 。A.（rear front + m） %mB. rear front + 1C. rearf

10、ront1 D. rear front14.棧和隊列的共同點是。A. 都是先進后出B.都是先進先出C.只允許在端點處插入、刪除元素D.沒有共同點填空題1. 線性表、棧和隊列都是結(jié)構(gòu)，可以在線性表的 位置插入和刪除元素；對于棧只能在 插入和刪除元素；對于隊列只能在 插入元素和 刪除元 素。2. 在一個長度為 n的線性表的第 i個元素 （1in）之前插入一個元素時， 需向后移動 個3. 在一個長度為 n 的向量中的刪除第 i 個元素 （1 i n） 時，需要向前移動個元素。4. 若棧頂指針指向棧頂?shù)目瘴?，向棧中壓入元素的操作是?. 若棧頂指針指向棧頂元素，則對棧進行退棧時的操作是。6. 在一個循

11、環(huán)隊列中，隊首指針指向隊首元素的。7. 從循環(huán)隊列中刪除一個元素時，其隊頭指針 。8. 在具有 n 個單元的循環(huán)隊列中，隊滿時共有個元素的。9. 一個棧的輸入序列是 12345，則棧的輸出序列 43512 是。（填寫“可能”或“不可能”）10. 一個棧的輸入序列是 12345，則棧的輸出序列 12345 是 。（填寫“可能” 或“不 可能”） 第二章 線性表（參考答案）5. B。 6. D。 7. B，A 。 8. B。9. C 。10. A。 11. A 。 12. C。13. A 。 14. C。選擇題： 1. B。 2. C。 3. C。 4. A 。（2. C。堆棧講究先進后出， 后進

12、先出選項 1 是 abcde先入棧， 然后依次出棧， 正好是 edcba 選項 2是abcd先依次入棧，然后 d出棧， e再入棧， e出棧。選項 c是錯誤的，不可能 a先 出棧。選項 4 是 a入棧，然后 a出棧； b再入棧， b 出棧依此類推。所以選c。）（13. A 。因為 rear 有可能會轉(zhuǎn)一圈到 front 的后面，所以需要加一下 m）填空題： 1. 線性，任何，棧頂，隊尾，隊首。 2. n - i +1。 3. n - i。 4. 先移動棧 頂指針，后存入元素。 5. 先取出元素，后移動棧頂指針。 6. 前一個位置。 7. 要 加 1 8. n-1 。 9. 不可能的。 10. 可

13、能的。第三章 鏈表單項選擇題1. 不帶頭結(jié)點的單鏈表 head 為空的判定條件是 。A. head=NULLB.head-next=NULLC.head-next=headD.head!=NULL2. 帶頭結(jié)點的單鏈表 head 為空的判定條件是。A. head=NULLB.head-next=NULLC.head-next=headD.head!=NULL3. 非空的循環(huán)單鏈表 head的尾結(jié)點（由指針 p 所指向）滿足。A. p-next=NULL B.p=NULL C.p-next=head D.p=head4. 在循環(huán)雙鏈表的 p 所指結(jié)點之后插入 s所指結(jié)點的操作是。A. p-rig

14、ht=s;s-left=p;p-right-left=s;s-right=p-right;B. p-right=s;p-right-left=s;s-left=p;s-right=p-right;C. s-left=p;s-right=p-right;p-right=s;p-right-left=s;D. s-left=p;s-right=p-right; p-right-left=s;p-right=s;5. 在一個單鏈表中， 已知 q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點， 若在 q 和 p 之間插入 s 結(jié)點， 則執(zhí)行 。A. s-next = p-next; p-next=s;B. p-

15、next = s-next; s-next = p;C. q-next = s; s-next = p;D. p-next = s; s-next = q;6. 在一個單鏈表中， 已知 p所指結(jié)點不是最后結(jié)點， 在 p之后插入 s所指結(jié)點，則執(zhí)行A. s-next = p; p-next=s;B. s-next = p-next; p-next = s;C. s-next = p-next; p = s;D. p-next = s; s-next = p;7. 在一個單鏈表中，若刪除 p 所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行 。A. p-next = p-next-next;B. p = p-next;

16、 p-next=p-next-next;C. p-next = p-next;D. p =p-next -next;8. 從一個具有 n 個結(jié)點的單鏈表中查找其值等于 x 的結(jié)點時，在查找成功的情況下，需平均 比較 個結(jié)點。A. nB. n/2C. (n-1)/2D. (n+1)/29. 在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是。A. O(1) B. O(n)C. O(n2)D. O(nlog 2n)10. 給定有 n 個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是。2A. O(1) B. O(n)C. O(n2)D. O(nlog 2n)11. 向一個棧頂指

17、針為 HS 的鏈棧中插入 s 所指結(jié)點，則執(zhí)行。A. HS-next = s;B. s-next = HS-next; HS-next = s;C. s-next = HS; HS = s;D. s-next = HS; HS = HS-next;12. 從一個棧頂指針為 HS 的鏈棧中刪除一個結(jié)點， 用 x 保存被刪除結(jié)點的值， 則執(zhí)行A. x = HS; HS = HS-next;B. x = HS-data;C. HS = HS-next; x = HS-data;D. x = HS-data; HS = HS-next;13. 在一個鏈隊中，假設(shè) f 和 r 分別為隊首和隊尾指針，插入

18、 s 所指結(jié)點，則執(zhí)行 。A. f-next = s; f = s;B. r-next = s; r = s;C. s-next = r; r = s;D. s-next = f; f = s;14. 在一個鏈隊中，假設(shè) f 和 r 分別為隊首和隊尾指針，刪除一個結(jié)點，則執(zhí)行 。A. r = f-next;B. r = r-next;C. f = f-next;D. f = r-next;填空題1. 單鏈表是的鏈接存儲表示。2. 在雙鏈表中，每個結(jié)點有兩個指針域，一個指向，另一個指向 。3. 在一個單鏈表中， p 所指結(jié)點之前插入 s所指向結(jié)點，可執(zhí)行如下操作：（1）s-next = p-ne

19、xt ；（2）p-next = s ；（3）t = p-data；（4）p-data =；（5）s-data =；4. 在一單鏈表中，刪除 p 所指結(jié)點時，應(yīng)執(zhí)行以下操作：（1）q = p-next ；（2）p-data = p-next-data ；（3）p-next =；（4）free （q）；5. 帶頭結(jié)點（ head）的單鏈表為空的條件是。6. 在一個單鏈表中， p 所指結(jié)點之后插入 s所指向結(jié)點，應(yīng)執(zhí)行 s-next = 和 p-next = 的操作。7. 非空的單循環(huán)鏈表 head的尾結(jié)點（由 p 所指向），滿足 。8. 在棧頂指針為 HS 的鏈棧中，判定棧空的條件是 。9. 在帶

20、頭結(jié)點的鏈隊列 HQ 中，判定只有一個頭結(jié)點的條件是 。編程題1. 已知有一棧頂指針為 HS 的鏈棧，請編寫一計算該鏈棧中結(jié)點個數(shù)的函數(shù)。2. 已知有一帶頭結(jié)點的鏈隊列 HQ 中，請編寫求該鏈隊列中結(jié)點個數(shù)的函數(shù)。第三章 鏈表（參考答案）選擇題： 1.A 。2.B。3.C。4.D。5.C。6. B。 7. A。 8.D。9. B 。 10. C。 11. C。 12. D。 13. B 。 14. C。（8. D。說明：可能查找的次數(shù)從 1到 n次不等，這樣的話，總的查找次數(shù)是 （n+1）n/2 ，除 以 n 為平均查找次數(shù)，即為 D. （n+1）/210. C。說明：這本質(zhì)上是一個排序問題，

21、要寫雙重循環(huán)來排序，根據(jù)已經(jīng)學(xué)習(xí)過的程序知 識，比如起泡法排序等，其時間復(fù)雜度是C. O（n2）。11. C。說明：注意這是一個棧頂指針，而非棧頂結(jié)點，所以選C 不選 B。填空題： 1. 線性表。 2. 前驅(qū)結(jié)點，后續(xù)結(jié)點。 3. s-data， t。 4. p-next-next 或 q-next。 5. head-next=NULL 。 6. p-next ， s。 7. p -next= head。8. HS=NULL 。 9. HQ-front=HQ-rear 。(3. s-data，t。 這道題實質(zhì)上是在 p 后面插入了 s 結(jié)點，然后將 p 和 s 結(jié)點中的數(shù)據(jù)作 了交換，結(jié)果就如

22、同是“真正”在p前面插入了一個 s結(jié)點一樣。其中的 t 是一個數(shù)據(jù)域變量。4. p-next-next 或 q-next 。其實是把被刪結(jié)點之后的結(jié)點做了前移。)編程題1. int count (node *HS) node *p;int n=0;p=HS;while (p!=NULL) n+;p=p-next;return (n);2. int count (strruct linkqueue *HQ) strruct linkqueue *p;int n;p=HQ-first;if (p=NULL) return (0 );n=1;while (p!=HQ-rear) n+;p=p-nex

23、t; return (n);第四章 串 單項選擇題1. 空串與空格串是相同的，這種說法。A. 正確B. 不正確2. 串是一種特殊的線性表，其特殊性體現(xiàn)在。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C.可以鏈接存儲D. 數(shù)據(jù)元素可以是多個字符3. 設(shè)兩個字符串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運算稱作 。A. 連接B.模式匹配C.求子串D.求串長4. 設(shè)串 s1=ABCDEFG ，s2=PQRST，函數(shù) con (x, y) 返回 x 與 y 串的連接串， 函數(shù) subs (s, i, j) 返回串 s的從序號 i 的字符開始的 j 個字符組成的子串， 函數(shù) len (s) 返回串

24、 s的長度， 則 con (subs (s1, 2, len (s2), subs (s1, len (s2), 2) 的結(jié)果串是。A. BCDEFB. BCDEFG C. BCPQRST D. BCDEFEF填空題1.串的兩種最基本的存儲方式是。2.兩個串相等的充分必要條件是。3. 空串是，其長度等于 。4. 空格串是，其長度等于 。5. 設(shè) s = “I AM A TEACHER ”，其長度是 。第四章 串（參考答案）單項選擇題： 1. B。 2. B。 3. B。 4. D 。填空題：1. 順序存儲方式和鏈接存儲方式。 2. 兩個串的長度相等且對應(yīng)位置的字符相同。 3. 零個字符的串，

25、0。 4. 由一個或多個空格字符組成的串，其包含的空格個數(shù)。5. 14。第六章 樹形結(jié)構(gòu)單項選擇題1.如圖所示的 4 棵二叉樹中，不是完全二叉樹。2.在線索化二叉樹中， t 所指結(jié)點沒有左子樹的充要條件是 。A.t-left = NULL B.t-ltag = 1 C.t-ltag = 1 且 t-left = NULLD. 以上都不對3. 二叉樹按某種順序線索化后，任一結(jié)點均有指向其前趨和后繼的線索，這種說法A. 正確B.錯誤4. 二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法。A. 正確B.錯誤5. 由于二叉樹中每個結(jié)點的度最大為 2，所以二叉樹是一種特殊的樹，這種說

26、法。A. 正確B.錯誤6. 設(shè)高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點， 則此類二叉樹中所包含的結(jié)點數(shù)至少 為。A. 2h B. 2h-1 C. 2h +1D. h +17. 如圖所示二叉樹的中序遍歷序列是。A. abcdgef B. dfebagcC. dbaefcgD. defbagc8. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是 debac，前序遍歷序列是C. deabcD. cedbaA. acbedB. decabT 中結(jié)點的前序就是 T2 中結(jié)點的D. 層次序T 中結(jié)點的后序就是 T2 中結(jié)點的D. 層次序9. 如果 T2 是由樹 T 轉(zhuǎn)換而來的二叉樹，

27、那么 A. 前序B. 中序C. 后序10. 如果 T2 是由樹 T 轉(zhuǎn)換而來的二叉樹，那么 A. 前序B. 中序C. 后序11. 某二叉樹的先序遍歷結(jié)點訪問順序是abdgcefh，中序遍歷結(jié)點訪問順序是 dgbaechf，則其后序遍歷結(jié)點訪問順序是 。A. bdgcefhaB. gdbecfhaC. bdgaechf D. gdbehfca12. 二叉樹為二叉排序樹的充分必要條件是任一結(jié)點的值均大于其左孩子的值、小于其右孩 子的值，這種說法 。A. 正確 B. 錯誤13. 按照二叉樹的定義，具有 3 個結(jié)點的二叉樹有種。A. 3B. 4C. 5 D. 614. 如圖所示二叉樹的中序遍歷序列是。

28、A. abdgcefhB. dgbaechfC. gdbehfca D. abcdefgh15. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹基本遍歷策略可分為先序遍歷、 中序遍歷和后序遍歷。 這時， 我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。 結(jié)論 是正確的。A. 樹的先根遍歷序列與二叉樹的先序遍歷序列相同B. 樹的后根遍歷序列與二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與二叉樹的中序遍歷序列相同D. 以上都不對16. 深度為 5 的二叉樹至多有個結(jié)點。A. 16B. 32C. 31D. 1017. 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊。A. 只有右子樹上的所有結(jié)點B

29、. 只有右子樹上的部分結(jié)點C. 只有左子樹上的所有結(jié)點D. 只有左子樹上的部分結(jié)點18. 樹最適合用來表示。A. 有序數(shù)據(jù)元素B. 無序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無聯(lián)系的數(shù)據(jù)19. 任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對20. 實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用 存儲結(jié)構(gòu)。A. 二叉鏈表21.對于一個滿二叉樹，A. n = h + mB. 廣義表存儲結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲結(jié)構(gòu) m 個樹葉， n 個結(jié)點，深度為 h ，則 。

30、B. h + m = 2nC. m = h-1 D. n = 2 h -122.如果某二叉樹的前序為 stuwv，中序為 uwtvs ，那么該二叉樹的后序 A. uwvts B. vwuts C. wuvts D. wutsv23.如圖所示的 T2 是由有序樹 T1 轉(zhuǎn)換而來的二叉樹，那么樹 T1 有 個葉結(jié)點。A. 4C. 6D. 7B. 524.設(shè) n、 m 為A. n 在 m 右方 B. n 是 m 祖先 25.線索二叉樹是一種結(jié)構(gòu)。A. 邏輯 B. 邏輯和存儲 填空題 1.有一棵樹如圖所示，回答下面問題： （1）這棵樹的根結(jié)點是；（2）這棵樹的葉子結(jié)點是；（3）結(jié)點 c 的度是；（4）

31、這棵樹的度是；（5）這棵樹的深度是；（6）結(jié)點 c 的子女是；（7）結(jié)點 c 的父母結(jié)點是?？枚鏄渖系膬蓚€結(jié)點，在中序遍歷時， n 在 m 前的條件是C. n 在 m 左方D. n 是 m 子孫C. 物理 D. 線性2.指出樹和二叉樹的三個主要差別3.從概念上講， 樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，4.一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組 接表示形式為 。將樹轉(zhuǎn)化為二叉樹的基本目的是T 中，如圖所示，則該二叉樹的鏈eafdgcjihb1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 215.深度為 k 的完全二叉樹至少有個結(jié)點，至

32、多有 個結(jié)點，若按自上而下、從左到右次序給結(jié)點編號（從 1 開始），則編最小的葉子結(jié)點的編號是。6.在一棵二叉樹中， 度為零的結(jié)點的個數(shù)為 n0，度為 2 的結(jié)點的個數(shù)為 n2，則有 n0 =。7.一棵二叉樹的第 k 層最多有 個結(jié)點；一棵有 n個結(jié)點的滿二叉樹共有個葉子和 個非終端結(jié)點。8.結(jié)點最少的樹為，結(jié)點最少的二叉樹為9.現(xiàn)有按中序遍歷二叉樹的結(jié)果是abc，問有歷結(jié)果，這些二叉樹分別是 。 10.根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有 是種不同形態(tài)的二叉樹可以得到這一遍種不同的形態(tài)，它們分別11.由如圖所示的二叉樹，回答以下問題： （1） （2） （3） （4） （5） （6） 12

33、.已知一棵樹如圖所示，其孩子兄弟表示為。13.以數(shù)據(jù)集 4，5，6，7，10，12 ，18為結(jié)點權(quán)值所構(gòu)造的哈夫曼其中序遍歷序列其前序遍歷序列 其后序遍歷序列 該二叉樹的中序線索二叉樹為 該二叉樹的后序線索二叉樹為 該二叉樹對應(yīng)的森林是樹為 ，其帶權(quán)路徑長度為第六章 樹形結(jié)構(gòu)(參考答案)選擇題： 1. C。 2. B。 3. B。 4. A。 5. B。 6. B。 7. B。 8. D 。9. A 。 10. B。 11. D。 12. B。 13. C。 14. B。 15. A。 16. C。17. A 。 18. C。 19. A。 20. C。 21. D。 22. C。 23. D

34、。 24. C。 25. C 。(說明：6. B(除根結(jié)點，其余每層至少是 2 個，所以至少是 2h-1)。8. D (cedba 方法很簡單 dabec是后序遍歷 則 c 是根節(jié)點 將中序遍歷以 c 為中心分為兩邊 如此操作即可得到一棵樹 (dabec),(debac) (dabe)c),(deba)c) (dab)e)c),(d)e(ba)c) (d)(a)b)e)c),(d)e(b(a)c) 這樣就把樹給構(gòu)造了出來(11. D 。從先序訪問中可知 a為根結(jié)點，從中序訪問中可知 d為最左側(cè)結(jié)點， 因而在中序訪問次序中， 以 a 為中點，將結(jié)點分為兩部分，左側(cè)為 dgb，右側(cè)為 echf ，

35、然后結(jié)合先序遍歷次序，畫出 二叉樹，最后可得結(jié)果為 D)填空題： 1. a， b、e、d、g，2，3，4，e、f ，a。 結(jié)點個數(shù)可以為 0，樹中結(jié)點最大度數(shù)沒有限制而二叉樹的結(jié)點的最大度數(shù)為，樹的結(jié)點沒 有無左右之分而二叉樹的結(jié)點有左右之分。 3. 樹可采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹 的已有算法解決樹的有關(guān)問題。 4. 略。 5. 2 k-1 ，2 k -1，2 k-2 7. 2 k-1 ，2 log n ，2 log n 1。 8. 只有一個結(jié)點的樹，空的叉樹。10. 5，略。 11. dgbaechif， abdgcefhi ， gdbeihfca，略，略，略。 13. 略， 165。

36、2. 樹的結(jié)點個數(shù)至少為 1 而二叉樹的+1。 6. n 2 +1 。9. 5，略。12. 略。第七章 圖 1.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的A. 1/2B. 1C. 2D. 42.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度這和A. 1/2B. 1C. 2D. 43.一個有 n 個頂點的無向圖最多有條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n 4.具有 4 個頂點的無向完全圖有A. 6 B. 12C. 165.具有 6 個頂點的無向圖至少應(yīng)有A. 56.在一個具有 n 個頂點的無向圖中，要連通全部頂點至少需要A. n 7.對于一個具有A. n8

37、.對于一個具有1 ；所有鄰接矩陣中的結(jié)點總數(shù)是1 A. n B. n+1B. 6C. 7倍。倍。C. n(n-1)/2 條邊。D. 20 條邊才能確保是一個連通圖。D. 8條邊。B. n+1 C. n-1 D. n/2n 個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是22B. (n-1) 2C. n-1D. n2n 個頂點和 e 條邊的無向圖，若采用鄰接矩陣表示，則表頭向量的大小是 2C. n-1D. n+e2 A. e/2B. e9.已知一個圖如圖所示，若從頂點 到頂點序列為 1 為2C. 2e D. n+e a出發(fā)按深度搜索法進行遍歷，則可得 ；按寬度搜索法進行遍歷，則可得到頂點序列

38、1 A. abecdfB. acfebdC. aebcfd2 A. abcedfB. abcefdC. aebcfd10.已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖所示 (1)根據(jù)有向圖的深度優(yōu)先遍歷算法， 所得到的頂點序列是 1 。 (2)根據(jù)有向圖的寬度優(yōu)先遍歷算法，D. aedfcbD. acfdeb從 v1 頂點出發(fā)，從 v1 頂點出發(fā)，所得到的頂點序列是B. v1,v2,v3,v4,v5D. v1,v4,v3,v5,v2B. v1,v3,v2,v4,v5D. v1,v4,v3,v5,v21 A. v1,v2,v3,v5,v4C. v1,v3,v4,v5,v22 A. v1,v2,v3,v4,v

39、5C. v1,v2,v3,v5,v411. 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的D. 按層遍歷。D. 按層遍歷A. 先序遍歷B. 中序遍歷C. 后序遍歷12. 采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的A. 先序遍歷B. 中序遍歷C. 后序遍歷13. 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用。A. 求關(guān)鍵路徑方法B. 求最短路徑的 Dijkstra 方法C. 寬度優(yōu)先遍歷算法D. 深度優(yōu)先遍歷算法填空題1. n 個頂點的連通圖至少條邊。2. 在無權(quán)圖 G 的鄰接矩陣中， 若 (vi, vj) 或 屬于圖 G 的邊集，則對應(yīng)元素 Aij 等 于 ，否

40、則等于 。3. 在無權(quán)圖 G 的鄰接矩陣中，若 Aij 等于 1，則等于 Aji =。4. 已知圖 G 的鄰接表如圖所示， 其從 v1頂點出發(fā)的深度優(yōu)先搜索序列為 其從 v1 頂點出發(fā)的廣度優(yōu)先搜索序列為 。5. 已知一圖的鄰接矩陣表示，計算第i 個結(jié)點的入度的方法是6.已知一圖的鄰接矩陣表示，刪除所有從第 i 個結(jié)點出發(fā)的邊的方法是第七章 圖(參考答案)選擇題： 1.C 。 2.B。3.C。4. A 。5. A 。 6. C 。7. D 。 8. A ，C 。9. D ，B 。10. C，B。11.A。12. D 。13. D 。填空值： 1.n-1。 2. 1，0。3.1。 4. 1、 2

41、、 3、 6、5、 4，1、 2、 5、 4、 3、 6。5. 求矩陣第i 列非 0元素之和。6.將矩陣第i 行全部置為 0。第九章 查找單項選擇題1. 順序查找法適合于存儲結(jié)構(gòu)為的線性表。A. 散列存儲B. 順序存儲或鏈接存儲C. 壓縮存儲D. 索引存儲2. 對線性表進行二分查找時，要求線性表必須。A. 以順序方式存儲B. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C. 以鏈接方式存儲D. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列3. 采用順序查找方法查找長度為 n 的線性表時，每個元素的平均查找長度為。A. nB. n/2 C. (n+1)/2 D. (n-1)/24. 采用二分查找方法查找長度為 n 的線性表時，每個元素的平均查找長度