數(shù)據(jù)結(jié)構(gòu)習(xí)題集(包含全部答案).

1 / 51 數(shù)據(jù)結(jié)構(gòu)習(xí)題集（自編） 第一章緒論 一、 選擇題 1 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象以及它們之間 的（）和運算的學(xué)科。 A. 結(jié)構(gòu) _B.關(guān)系 C .運算 D .算法 2 在數(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 .邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 3. 線性表的邏輯順序和存儲順序總是一致的，這種說法（）。 A .正確 B.不正確 C .無法確定 D .以上答案都不對 4. 算法分析的目的是（）o A.找出算法的合理性 B .研究算法的輸人與輸出關(guān)系 C.分析算法的有效性以求改進(jìn) D .分析算法的易懂性 5. 算法的時間復(fù)雜度取決于（） A.問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C. A和B 6. 一個算法應(yīng)該是（ ） A.程序 B.問題求解步驟的描述 C .要滿足五個基本特性 D . A和C. 7. 下面關(guān)于算法說法錯誤的是（ ） A. 算法最終必須由計算機程序?qū)崿F(xiàn) B. 為解決某問題的算法與為該問題編寫的程序含義是相同的 C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的 8. 以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ ） A.循環(huán)隊列 B. 鏈表 C. 哈希表 D.棧 9. 在下面的程序段中，對x的賦值語句的頻度為（ ） for （i=0;in;i+ ） for（j=0;j n ;j+） x=x+1; A. 2n B . n C. n2 D . log 2 10. 以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu) A.樹 B .字符串 C .隊列 D .棧 11. 下列數(shù)據(jù)中，（ ）是線性數(shù)據(jù)結(jié)構(gòu)。 A.哈夫曼樹 B. 有向無環(huán)圖 C. 二叉排序樹 D.棧 12. 以下屬于邏輯結(jié)構(gòu)的是（ ） A.順序表 B. 哈希表 C.有序表 D. 單鏈表 二、 填空題 1、 _ 信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、 存儲、加工和處理， _ 對能夠有效的輸人到計算機中并且能夠被計算機 處理的符號的總稱。（數(shù)據(jù)、數(shù)據(jù)） 2 、數(shù)據(jù)元素是數(shù)據(jù)的 _ ，有些情況下也稱為元素、結(jié)點、頂點、記錄 等。（基本單位） 3、 _ 數(shù)據(jù)不可分割的最小單元，是具有獨立含義的最小標(biāo)識單位。 2 / 51 例如構(gòu)成一個數(shù)據(jù)元素的字段、域、屬性等都可稱之為 _ 。（數(shù)據(jù)項、數(shù) 據(jù)項） 4 、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間的 _ 。邏輯結(jié)構(gòu)是從 _ 上描 述數(shù)據(jù)，它與具體存儲無關(guān)， 是獨立于計算機的。 因此邏輯結(jié)構(gòu)可以看作是從具 體問題抽象出來的 _ 。（邏輯關(guān)系、邏輯關(guān)系、數(shù)學(xué)模型） 5 、數(shù)據(jù) 的 _ 指數(shù)據(jù)元素 及 其關(guān)系在 計算機 存儲器內(nèi)的 表示。 _ 是邏輯結(jié)構(gòu)在計算機里的實現(xiàn)， 也稱之為映像。（存儲結(jié)構(gòu)、 存儲結(jié)構(gòu)） 6 、數(shù)據(jù)邏輯結(jié)構(gòu)可以分為四種基本的類型， _ 結(jié)構(gòu)中的元素除了僅僅 只是同屬于一個 _ ，不存在什么關(guān)系。（集合、集合） 7 、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中， _ 中的元素是一種一對一的關(guān) 系，這種結(jié)構(gòu)的特征是： 若結(jié)構(gòu)是非空集， 則有且只有一個開始結(jié)點和一個終端 結(jié)點，并且所有結(jié)點最多只能有一個直接前驅(qū)和一個直接后繼。 （線性結(jié)構(gòu)） 8 、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中， _ 中的元素是一種一對多 的關(guān)系。（樹形結(jié)構(gòu)） 9 、圖型結(jié)構(gòu)或圖狀結(jié)構(gòu)是一種 _ 的關(guān)系。在這種邏輯結(jié)構(gòu)中，所有 結(jié)點均可以有多個前驅(qū)和多個后繼。 （多對多） 10 、有時也可將樹型結(jié)構(gòu)、 集合和圖型結(jié)構(gòu)稱為 _ ，這樣數(shù)據(jù)的邏 輯結(jié)構(gòu)就可以分為 _ 和 _ 兩大類。（非線性結(jié)構(gòu)、線性結(jié)構(gòu)、非 線性機構(gòu)） 11 、_ 方式是指邏輯上相鄰的結(jié)點被存儲到物理上也相鄰的存儲 單元中。這種存儲結(jié)構(gòu)只存儲結(jié)點的數(shù)值， 不存儲結(jié)點之間的關(guān)系， 結(jié)點之間的 關(guān)系是通過存儲單元的相鄰關(guān)系隱含的表示出來的。 （順序存儲） 12 、_ 方式是種存儲方法， 不要求邏輯上相鄰的結(jié)點在物理上也相鄰， 即數(shù)據(jù)元素可以存儲在任意的位置上。 （鏈?zhǔn)酱鎯Γ?13 、_ 方式是利用結(jié)點關(guān)鍵字的值直接計算出該結(jié)點存儲單元地址， 然后將結(jié)點按某種方式存人該地址的一種方法。 （散列存儲或哈希存儲） 14 、所謂算法（ Algorithm ）是對特定問題求解步驟的一種描述，它是指令 的其中每個指令表示一個或多個操作。算法的五個重要特性是 _ 、 _ 、 _ 、 _ 和 _ 。（有限序列、有窮性、確 定性、可行性、輸入、輸出） 15、算法的 _ 性是指算法必須能夠在執(zhí)行有限個步驟之后結(jié)束，并且 每個步驟都必須在有窮的時間內(nèi)完成。 （有窮性） 16、算法的 _ 性是指算法中的每一個步驟必須是有明確定義的，不允 許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟 一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到 _ 的輸出結(jié)果。 （確定性、相同） 17 、算法的 _ 性又稱為算法的能行性， 是指算法中描述的操作是 可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。 （可行性） 18 、判斷一個算法的好壞主要以下幾個標(biāo)準(zhǔn)： _ 、 _ 、 _ 、 _ 。（正確性、可讀性、健壯性、時間效率和空間效率） 19 、算法分析是對一種算法所消耗的計算機資源的估算，其中包括計算機 _ 的長短和 _ 的大小。（運行時間、所占據(jù)空間） 20 、空間復(fù)雜度（ SPaceComPlexity ）也是度量一個算法好壞的標(biāo)準(zhǔn)，它所 描述的是算法在3 / 51 運行過程中所占用 _ 的大小。（存儲空間）4 / 51 三、判斷題 1 順序存儲方式只能用于存儲線性結(jié)構(gòu)。(X) 2 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(X) 3 算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。 ( X ) 4 健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。 () 5數(shù)據(jù)的邏輯結(jié)構(gòu)是指各元素之間的邏輯關(guān)系，是根據(jù)用戶需要而建立的。 6數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結(jié)構(gòu)、結(jié) 點、數(shù)據(jù)域。() 7 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機中實際的存儲形式。 () 8 具有存取任一元素的時間相等這一特點的存儲結(jié)構(gòu)稱為隨機存取結(jié)構(gòu)。 9算法實際上就是程序，程序也一定是算法。 ( X ) 10. 在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。 (X ) 11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 (X) 12. 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立 13. 數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系 , 它依賴于計算機的儲存結(jié)構(gòu)。 14. 判斷一個算法的好壞主要以下幾個標(biāo)準(zhǔn)：正確性、有窮性、健壯性和可 行性。 ( X ) 15算法的時間復(fù)雜度 T( n) =O(f(n) 表示隨問題規(guī)模 n 的增大，算法執(zhí)行 時間的增長率與函數(shù) f(n) 的增長率相同。() 四、綜合題 1 用大0形式表示下面算法的時間復(fù)雜度： for (i=0 ； i v m i 十十) for (j=0 ; j v n； j + + ) Aij=i*j ； 2 寫出下面算法的時間復(fù)雜度： i = 0； s=0 ； while(s v n) i+； s+=i; 3寫出以下算法的時間復(fù)雜度： for (i = 0; i v m; i + + ) for (j = 0 ; j v t; j + + ) cij=0 ； for ( i=0 ； i v m； i +) for ( j=o; j sqrt(n) printf (” d is a prime number. n”，n)； else printf (” d is not a prime number. n”，n)； 1. 該算法的時間復(fù)雜度為：O(mx n)。 2. 該算法的時間復(fù)雜度為：0(. n) 3. 該算法的時間復(fù)雜度為：0(mx nx t) o 4. 該算法的時間復(fù)雜度為：logn) o 5. 該算法的時間復(fù)雜度為：0(.n) o 6. 將下列函數(shù)，按它們在nx時的無窮大階數(shù)，從小到大排序。 n, n-n 3+7n5, nlogn, 2 n/2, n 3, logn, n 2+logn, (3/2) n, ,n!, n 2+logn 從小至卩大排列為：logn, n2+logn, n, nlogn, n2+logn，n3, n-n 3+7n5, 2n/2, (3/2) n, n!,6 / 51 第二章 線性表 一、選擇題 1 在一個長度為 n 的順序表中刪除第 i 個元素( 0inext=p-next-next B. p-next=p-next C. p=p-next-next D. p=p-next; p-next=p-next-next 14. 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)，若在q和p之 間插入 s 所指的C .部分地址必須連續(xù) D. 連續(xù)與否均可以 5 .在一個具有 n 個結(jié)點的有序單鏈表中插人一個新的結(jié)點，使得鏈表仍然 有序，該算( )O(n2) DO(n) 7. 在一個長度為 n 的順序表中，向第 元素時，需要向后移動 ( ) 個元素。 A . n-i B. n-i +1 8. 如果某鏈表中最常用的操作是取第 方式最節(jié)省時間。 A .單鏈表 B .雙向鏈表 .一個有限序列，不可以為空 .一個無限序列，不可以為空 個位置(0 1vn+ 1)插入一個新 . n i 1 D . i + 1 個結(jié)點及其前驅(qū)，則采用 ( ) 存儲 .單循環(huán)鏈表 90， 9. 一個順序存儲線性表的第一個元素的存儲地址是 2，則第 6 個元素的存儲地址是() 。 A . 98 B. 100 C . 102 D.順序表 每個元素的長度是 106 7 / 51 結(jié)點，則執(zhí)行( )操作。 As-next=p-next; p-next=s; Bq-next=s; s-next=p; Cp-next=s-next; s-next=p; Dp-next=s; s-next=q; 15在單鏈表中附加頭結(jié)點的目的是為了（ ）。 A. 保證單鏈表中至少有一個節(jié)點 B. 標(biāo)識單鏈表中首結(jié)點的位置 C. 方便運算的實現(xiàn) D. 說明單鏈表是線性表的鏈?zhǔn)酱鎯?16. 循環(huán)單鏈表的主要優(yōu)點是（ ）。 A. 不再需要頭指針了 B. 從表中任意一個結(jié)點出發(fā)都能掃描到整個鏈表 C已知某個結(jié)點的位置后，能夠容易找到它的前驅(qū) D.在進(jìn)行插入、刪除操作時，能更好地保證鏈表不斷開 17. 非空的循環(huán)單鏈表L的尾結(jié)點p滿足（）。 A. p-next=NULL B. p=NULL C. p-next=L D. p=L 18. 在雙向循環(huán)鏈表中 ,在 p 指針?biāo)赶虻慕Y(jié)點前插入一個指針 q 所指向的 新結(jié)點 , 其修改指針的操作是 （ ） 。 注: 雙向鏈表的結(jié)點結(jié)構(gòu)為 （prior,data,next） 。 供選擇的答案： A. p-prior=q ；q-next=p ； p-prior-next=q ；q-prior=q ； B. p-prior=q ；p-prior-next=q; q-next=p ；q-prior=p-prior ； C. q-next=p ；q-prior=p-prior ； p-prior-next=q; p-prior=q; D. q-prior=p-prior ； q-next=p ； p-prior=q ； p-prior=q ； 19. 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）。 A. p-prior-next=p-next; p-next-prior=p-prior; B. p-prior=p-prior-prior; p-prior-next=p;（ 刪 p 的前趨 ） C. p-next-prior=p; p-next=p-next-next; D. p-next= p-prior-prior; p-prior= p-next-next; 二、填空題 1. 線性表（ Linear List ）是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中的元素 存在著 _ 的相互關(guān)系。（一對一） 2. 線性表中有且僅有一個開始結(jié)點，表中有且僅有一個終端結(jié)點，除開始結(jié)點 外，其他每個元素有且僅有一個 _ ，除終端結(jié)點外，其他每個元素 有且僅有一個 _ 。 3. _ 線性表是n （n=0）個數(shù)據(jù)元素的 。 其中n為數(shù)據(jù)元素的個數(shù)，定 義為線性表的 _ 。當(dāng) n 為零時的表稱為 _ 。 4. 所謂順序表（ Sequential LISt ）是線性表的 _ ，它是將線性表中的 結(jié)點按其 _ 依次存放在內(nèi)存中一組連續(xù)的存儲單元中，使線性表 8 / 51 中相鄰的結(jié)點存放在 _ 的存儲單元中。 5. 單鏈表不要求邏輯上相鄰的存儲單元在物理上也一定要相鄰。它是分配一些 _ 的存儲單元來存儲線性表中的數(shù)據(jù)元素， 這些存儲單元可以分散在內(nèi) 存中的 的位置上， 它們在物理上可以是一片連續(xù)的存儲單元， 也可 以是 _ 的。因此在表示線性表這種數(shù)據(jù)結(jié)構(gòu)時，必須在存儲線性表 元素的同時，也存儲線性表的 6 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的每一個結(jié)點（Node）需要包括兩個部分：一部分用 來存放元素的數(shù)據(jù)信息， 稱為結(jié)點的 _ ；另一部分用來存放元素的指 向直接后繼元素的指針 （即直接后繼元素的地址信息 ），稱為 _ 或 7線性鏈表的邏輯關(guān)系是通過每個結(jié)點指針域中的指針來表示的。其邏輯順序 和物理存儲順序不再一致， 而是一種 _ 存儲結(jié)構(gòu)，又稱為 _ 。 8如果將單鏈表最后一個結(jié)點的指針域改為存放鏈表中的頭結(jié)點的地址值，這 樣就構(gòu)成了 。 9為了能夠快速地查找到線性表元素的直接前驅(qū)，可在每一個元素的結(jié)點中再 增加一個指向其前驅(qū)的指針域，這樣就構(gòu)成了 _ 。 10雙向鏈表某結(jié)點的指針 P,它所指向結(jié)點的后繼的前驅(qū)與前驅(qū)的后繼都是 p _ 。 11在單鏈表中,刪除指針 P 所指結(jié)點的后繼結(jié)點的語句是 _ 。 12 在雙循環(huán)鏈表中，刪除指針 P所指結(jié)點的語句序列是 P-prior-next = p-next 及 _ 。 13單鏈表是 _ 的鏈接存儲表示。 14可以使用 _ 表示樹形結(jié)構(gòu)。 15. _ 向一個長度為n的向量的第i個元素（I i n+1）之前插人一個元素時，需 向后移動 _ 個元素。 16刪除一個長度為n的向量的第i個元素（I i next=p-next-next 12. P-next-prior=P-prior 13. 線性表 14 雙鏈表 15 n-i+1 16 n-i 17 S-next=P-next; P-next=S 18. p-prior-next=S; s-prior=p-prior; s-next=p; p-prior=s; 19 head(tail(tail(head(tail(head(A) 20 O(n) 21 (L=L-Next) & (L=L-Prior) 22 線性 23 頂 三、判斷題 1 線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。 (X) 2. 在具有頭結(jié)點的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指向鏈表中的第一個數(shù)據(jù)結(jié)點。(X) 3順序存儲的線性表不可以隨機存取。 (X) 4. 單鏈表不是一種隨機存取結(jié)構(gòu)。 () 5. 順序存儲結(jié)構(gòu)線性表的插入和刪除運算所移動元素的個數(shù)與該元素的位置無 關(guān)。 ( X ) 6. 順序存儲結(jié)構(gòu)是動態(tài)存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)是靜態(tài)存儲結(jié)構(gòu)。 (X) 7. 線性表的長度是線性表所占用的存儲空間的大小。 (X) 8. 雙循環(huán)鏈表中， 任意一結(jié)點的后繼指針均指向其邏輯后繼。 (X) 9. 線性表的惟一存儲形式是鏈表。 (X ) 1. 錯誤：鏈表存儲中，結(jié)點之間可以連續(xù)也可以不連續(xù)，但結(jié)點內(nèi)部是連 續(xù)的。 2. 錯誤：頭指針指向頭結(jié)點而不是數(shù)據(jù)結(jié)點。 3. 錯誤：順序存儲的線性表可以隨機存取。 4. 正確。 5. 錯誤。 6. 錯誤：順序存儲結(jié)構(gòu)是靜態(tài)存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)是動態(tài)存儲結(jié)構(gòu)。 7. 錯誤：先行表的長度是線性表中結(jié)點的個數(shù)。 8. 錯誤：注意最后一個結(jié)點。 9. 錯誤：也可以有順序存儲的形式。10 / 51 第三章 棧和隊列 一、選擇題 l 一個棧的序列是： a, b, c, d, e,則棧的不可能輸出的序列是（）。 Aa，b，c，d，e B d，e，c ，b，a Cd，c，e，a，b D e，d， c，b， a 2 若一個棧的輸人序列是1, 2, 3,，n,輸出序列的第一個元素是n,則 第 k 個輸出元素是（ ）。 A k B n-k-1 Cn-k+1 D 不確定 3 判定一個棧S （最多有n個元素）為空的條件是（）。 A . S-top != 0 B. S-top= =0 C . S-top!=n D . S-top= =n 4 判定一個棧S （最多有n個元素）為滿的條件是（）。 A S-top!=0 B S-top= =0 C S-top!=n DS-top= =n 5. 向一個棧頂指針為 top 的不帶頭結(jié)點的鏈棧中插人一個 *S 結(jié)點的時候,應(yīng)當(dāng) 執(zhí)行語句（ ）。 A . top-next=S； B. S-next=top ；top=S； C . S-next = top-next ; top-next = S; D. S-next = top ; top = S-next ; 6. 向一個帶頭結(jié)點、棧頂指針為 top 的鏈棧中插人一個 *S 結(jié)點的時候,應(yīng)當(dāng)執(zhí) 行語句（ ）。 A . top-next=S ； B . S-next=top； top=S； C. S-next=top-next ； top-next=S ； D . S-next=top ； top=S-next ； 7 .判定一個隊列Q （最多有n個元素）為空的條件是（ ）。 A . Q-rear-Q-front= =n B . Q-rear-Q-front+1= =n C. Q-rear = = Q-front D . Q-rear +1= = Q-front 8 .判定一個隊列Q （最多有n個元素）為滿的條件是（）。 A. Q-rear-Q-front= =n B . Q-rear-Q-front+1= =n C . Q-rear = = Q-front D . Q-rear +1= = Q-front 9 .判定一個循環(huán)隊列Q （最多有n個元素）為空的條件是（ ）。 A. Q-rear = = Q-front B . Q-rear = = Q-front l 15 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù) 緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫人該緩沖區(qū)， 而打印機則從該緩沖區(qū)中取走 C Q-front= =（Q-rear +1） 10.判定一個循環(huán)隊列Q （最多有 A Q-rear = = front n D n 個元素） B n 和 rear B D 和 rear ） 限制存取點的線性結(jié)構(gòu) l , 2, 3, 4,則（ 1 B l , 2, 3, 4 . Q-front= = （Q-rear -1） 為滿的條件是（ ）。 . Q-rear = = Q-front . Q-front= = （Q-rear -1） n l n D 分別為頭指針和尾指針,則插入一個 S-next=rear ； rear=S .S-next=front ； front = S 分別為頭指針和尾指針,刪除一個結(jié) . rear=rear-next .front-next = rear A.鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu) B .鏈?zhǔn)酱?D 限制存取點的非線性結(jié)構(gòu) ）不可能是一個出棧序列。 C4, 2, 3, 1 D 4, 3, 2, l 11 / 51 數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。 A .堆棧 B.隊列 C .數(shù)組 D .線性表 1. C 2. C 3. B 4. D 5. B 6. C 7. C 8. A 9. A 10. C 11. C 1A 13. C 14. C 15. B 二、填空回 1棧（ stack ）是限定在 _ 一端進(jìn)行插人或刪除操作的線性表。在棧中， 允許插人和刪除操作的一端稱為 _ ，而另一端稱為 _ 。不含元 素的棧稱為 _ 。 2在棧的運算中，棧的插人操作稱為 _ 或 _ ，棧的刪除操作稱為 _ 或 _ 。 3根據(jù)棧的定義，每一次進(jìn)棧的元素都在原 _ 之上，并成為新的 _ ；每一次出棧的元素總是當(dāng)前的 ，因此最后進(jìn)棧的元 素總是 ， 所以棧也稱為 _ 線性表，簡稱為 _ 表。 4棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有 _ 和 兩種存儲結(jié)構(gòu)，分別稱為 _ 和 _ 5當(dāng)棧滿的時候，再進(jìn)行人棧操作就會產(chǎn)生 ， 這種情況的溢出稱 為 _ ；當(dāng)棧空的時候，如果再進(jìn)行出棧操作，也會 _ ，這 種情況下的溢出稱為 _ 。 6棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為 _ ，是一種 _ 。 7人們?nèi)粘Ｓ嬎阌玫降谋磉_(dá)式都被稱為 _ ，這是由于這種算術(shù)表達(dá) 式的運算符被置于兩個操作數(shù)中間。 8計算機中通常使用 _ ，這是一種將運算符置于兩個操作數(shù)后面的算 術(shù)表達(dá)式。這種表達(dá)式是由波蘭科學(xué)家謝維奇提出的， 因此又稱為 _ 9. _ 隊列（Queue）也是一種 但它與棧不同，隊列中所有的插人均 限定在表的一端進(jìn)行， 而所有的刪除則限定在表的另一端進(jìn)行。 允許插人的一端 稱為 ， 允許刪除的一端稱為 _ 。 10. _ 隊列的特點是 _ ，因此隊列又被稱為 _ .的線性表， 或稱為 _ 表。 11. _ 隊列的 _ 又稱為 ，是用一組地址連續(xù)的存儲單元依次存 放隊列中的元素。 12. 由于隊列中的元素經(jīng)常變化， 對于隊列的刪除和插人分別在隊頭和隊尾進(jìn)行， 因此需要設(shè)置兩個指針分別指向 _ 和 _ ，這兩個指針又稱為 _ 和 _ 。 13. _ 循環(huán)順序隊列（Circular SequenceQueue經(jīng)常簡稱為 _ 它是 將存儲順序隊列的存儲區(qū)域看成是一個首尾相連的一個環(huán)， 即將隊首和隊尾元素 連接起來形成一個環(huán)形表。首尾相連的狀態(tài)是通過數(shù)學(xué)上的 _ 來實現(xiàn)的。 14. 在算法或程序中， 當(dāng)一個函數(shù)直接調(diào)用自己或通過一系列語句間接調(diào)用自己 的時候，則稱這個函數(shù)為，也稱為 _ 。函數(shù)直接調(diào)用自己，則稱為 _ ；當(dāng)一個函數(shù)通過另一個函數(shù)來調(diào)用自己則稱為 _ 。 15. _ 在循12 / 51 環(huán)隊列中規(guī)定： 當(dāng) Q-rear= =Q-front 的時候循環(huán)隊列為 _ ，13 / 51 當(dāng)（Q-rear+1 ）% MAXSIZ旨 front 16 用鏈表方式表示的隊列稱為 _ 17已知棧的輸人序列為1, 2, 3,，n,輸出序列為al, a2,，an,符合 a2= =n的輸出序列共有 _ 。 18一個棧的輸人序列是 12345,則棧的輸出序列為 可能）。 19一個棧的輸人序列是 12345,則棧的輸出序列為 否可能）。 20設(shè) sq1 maxsize 為一個順序存儲的棧,變量 則作入棧操作的條件是 _ 。 21設(shè) sq1 maxsize 為一個順序存儲的棧,變量 top 指示棧頂元素的位置, 如果把棧頂元素彈出并送到 X中，則需執(zhí)行語句 _ 。 22棧的特性是 _ 23對棧進(jìn)行退棧時的操作是先取出元素,后移動 _ 。 24. _ 設(shè)s1 . max為一個順序存儲的棧，變量top指示棧頂位置，棧為滿的條 件是 。 25. _ 設(shè)鏈棧的棧頂指針為top，則棧非空的條件是 _。 26. _ 已知循環(huán)隊列用數(shù)組data1n存儲元素值，用f, r分別作為頭尾指針， 則當(dāng)前元素個數(shù)為 _ 。 27在一個循環(huán)隊列中，隊首指針指向隊首元素的 _ 位置。（前一個或后 一個） 28隊列中允許進(jìn)行刪除的一端稱為 _ 。 29.鏈隊列實際上是一個同時帶有頭指針和尾指針的單鏈表（1. n）,尾指針指 向該單鏈表的第 _ 個元素。 30設(shè)雙向鏈表鏈列為 lq ， lq 的頭指針為 lq.Front ，尾指針為 lq.Rear ，則隊 列為空的條件是 _ 。 的時候循環(huán)隊列為 43512 是 _ （填是否 12345 是 _ （填是 top 指示棧頂元素的位置, 1. 表尾、棧頂、棧底、空棧 2. 進(jìn)棧、入棧、退棧、出棧 3. 棧頂元素、棧頂元素、棧頂元素、 最先出棧、后進(jìn)先出、 4. 順序、鏈?zhǔn)?、順序棧、鏈?5. 溢出、上溢、溢出、下溢 6. 鏈棧、特殊的單鏈表 7. 中綴表達(dá)式 8. 后綴表達(dá)式、波蘭式 9. 特殊的線性表、隊尾、隊頭 10. 先進(jìn)先出、先進(jìn)先出、 FIFO 11. 順序存儲結(jié)構(gòu)、順序隊列 12. 隊頭元素、隊尾元素、隊頭指針 、隊尾指針 13. 循環(huán)隊列、取模運算 14. 遞歸函數(shù)、自調(diào)用函數(shù)、直接遞歸調(diào)用、間接遞歸調(diào)用 15. 空、滿 1 鏈隊列 LIFO 31從循環(huán)隊列中刪除一個元素， 其操作是先取出一個元素， 后移動 _ 32隊列中允許進(jìn)行插入的一端稱為 _ 。 14 / 51 17n-1 18 不可能的 19 可能的 20 top!=maxsize 21 x=sqtop; 1 22 先進(jìn)后出 23 棧頂指針 24 top=max 25 top!=nil 26 (n+r-f)mod n 27 前一個 28 隊首 29 n 30 lq-front=lq-rear 31 棧頂指針 32 隊尾 、判斷題 1棧和隊列都是限制存取點的線性結(jié)構(gòu)。 （ ） 2不同的入棧和出棧組合可能得到相同輸出序列。 （ ） 3消除遞歸一定要用棧。 （ ） 4循環(huán)隊列是順序存儲結(jié)構(gòu)。 （ ） 5循環(huán)隊列不會產(chǎn)生溢出。 （ ） 6循環(huán)隊列滿的時候 rear= =front 。（ ） 7在對鏈隊列（帶頭結(jié)點）做出隊操作時不會改變 front 指針的值。（） 1. 正確。 2 錯誤： 不同的入棧和出棧組合得到不同輸出序列。 3. 錯誤： 某些情況如尾遞歸可以轉(zhuǎn)換為遞推的形式。 4 正確。 5. 錯誤： 循環(huán)隊列不會產(chǎn)生假溢出。 6 錯誤。 7 正確。 四、綜合題 1 設(shè)有4個元素A、B、C和D進(jìn)棧，給出它們所有可能的出棧秩序 可能的出棧序列： （共 14 個） ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 不可能的出棧序列：（共 10個） ADBC BDAC CABD CADB CDAB DABC DACB DBAC DBCA DCAB 習(xí)題四 一、選擇項 l 空串與空格串（ ）。 15 / 51 A 相同 B 不相同 C 可能相同 D 無法確 定 2設(shè)有兩個申S1與S2,求串S2在S1中首次出現(xiàn)位置的運算稱作（ ） A 連接 B 求子串 C 模式匹配 D 判子串 3串與普通的線性表相比較,它的特殊性體現(xiàn)在（ ）。 A 順序的存儲結(jié)構(gòu) B 鏈接的存儲結(jié)構(gòu) C 數(shù)據(jù)元素是一個字符 D 數(shù)據(jù)元素可以任意 4. 設(shè)有串S= Computer,則其子串的數(shù)目是（ ）。 A . 36 B . 37 C . 8 D .9 1. B 2. C 3. C 4. B 二、境空題 1. _ 串是由零個或多個字符組成的 。 通常記作：s = “cl , c2，, cn” （n=0），其中，S稱為 _ 串中的Ci （1=i1）個 的有序組合，數(shù)組中的數(shù)據(jù)是 按順序存儲在一塊 _ 的存儲單元中。 2. _ 數(shù)組中的每一個數(shù)據(jù)通常稱為 ， 用下標(biāo)區(qū)分，其中下標(biāo)的 個數(shù)由數(shù)組的 _ 決定。 3. 由于計算機內(nèi)存中的存儲單元是一個一維的存儲結(jié)構(gòu)，因此對于多維數(shù) 組要想按順 序存儲到計算機存儲單元中就必須有一個排列順序問題。 對于二維數(shù)組， 有 兩種排列形式：一種是 _ ；另一種是 _。 4. _ 對于需要壓縮存儲的矩陣可以分為 _ 和 _ 。對那些具有 19 / 51 相同值元素或零元素在矩陣中分布具有一定規(guī)律的矩陣，我們稱之為 ；而對于那些零元素數(shù)目遠(yuǎn)遠(yuǎn)多于非零元素數(shù)目，并且非零元素的 分布沒有規(guī)律的矩陣稱為 。 5. _ 在一個n階方陣a中，若元素滿足性質(zhì)：aj = (0=i , j=0)個元素的序列。記作：A=( al, a2,，an),其 中， A 是廣義表的 _ ， n 是它的 _ ， 當(dāng) n=0 的時候稱為 9. 在一個非空的廣義表中，其元素 ai可以是某一確定類型的單個元素，稱 為 _ ，也可以又是一個廣義表，稱為 _ 。 10. 廣義表的定義是一種遞歸的定義，廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。當(dāng)廣 義表非空的時候，稱第一個元素 ai為廣義表A的 _ ，稱其余元素組成 的表(a2，a3,，an)是A的 _ 。 11 .廣義表的深度一般定義為廣義表元素 _ ，或者說是廣義表 _ 。 利用 遞 歸 的 定 義 ， 廣 義 表 的 深 度 就 是 所 有 子 表 中 1. 相同類型數(shù)據(jù)、地址連續(xù) 2. 數(shù)組元素、數(shù)組元素、維數(shù) 3. 以行序為主、以列序為主 4. 特殊矩陣、稀疏矩陣、特殊矩陣、稀疏矩陣 5. 對稱矩陣 6. 三元組順序表、三元組 7. 矩陣轉(zhuǎn)置 8. 名稱、長度、空表 9. 原子、子表 10. 表頭、表尾 11. 最大的層數(shù)、括號的重數(shù)、最大深度加 1 三、判斷題 1 .十字鏈表不是順序存儲結(jié)構(gòu)。 ( ) 2. 三元組表不是一個隨機存取結(jié)構(gòu)。 ( ) 3. 稀疏矩陣壓縮存儲后， 必然會失去隨機存取功能。 ( ) 4. 若一個廣義表的表頭為空表，則此廣義表也為空表。 ( ) 5. 廣義表是線性表的推廣，是一類線性數(shù)據(jù)結(jié)構(gòu)。 ( ) 6. 任何一個非空廣義表，其表頭可能是單元素或廣義表，其表尾必定是廣 義表。 () 7. 一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列 下標(biāo)的值互換，并把 m和n的值互換，則就完成了 Am*n的轉(zhuǎn)置運算。( ) 20 / 51 8數(shù)組中每個元素必定具有相同的數(shù)據(jù)類型。 （ ） 9線性表是廣義表的特例。 （ ） 10如果廣義表中的每個元素都是原子，則廣義表便成為線性表。 （） 11廣義表中原子個數(shù)即為廣義表的長度。 （） 12廣義表最大子表的深度為廣義表的深度。 （） 13廣義表中元素最大的層數(shù)稱為廣義表的深度。 （） 14廣義表是一種多層次結(jié)構(gòu)。 （） 15廣義表是一種線性結(jié)構(gòu)。 （） 16廣義表是一種共享結(jié)構(gòu)。 （） 17廣義表是一種遞歸結(jié)構(gòu)。 （） 18廣義表是一種單鏈表結(jié)構(gòu)。 （） 1. 正確：十字鏈表是鏈接存儲結(jié)構(gòu)。 2. 正確：具有存取任一元素的時間相等這一特點的存儲結(jié)構(gòu)稱為隨機存取 結(jié)構(gòu)，三元組表存儲矩陣的時候，要訪問第 i 行 j 列元素必須掃描三元組表， 顯然查找三元組表前面的元素與后面元素所耗費的時間不同，因此三元組表不 是一個隨機存取結(jié)構(gòu)。 3. 正確：隨機存取結(jié)構(gòu)是指存取任一元素的時間相等這一特點的存儲結(jié) 構(gòu)，對稀疏矩陣壓縮存儲所用的存儲結(jié)構(gòu)是十字鏈表和三元組，而這兩種存儲 結(jié)構(gòu)都不是隨機存取結(jié)構(gòu)。 4. 錯誤：如廣義表 L=（）,（A, B） 為非空，而表頭為空表。 5. 錯誤：廣義表是線性表的推廣，是一類非線性數(shù)據(jù)結(jié)構(gòu)。 6. 正確：表尾的定義是除表頭元素以外其余元素（可以為空）構(gòu)成的表， 所以必定是廣義表。 7. 錯誤：應(yīng)該在互換行列后再按照行優(yōu)先重新存儲。 8. 正確。 9. 正確。 10. 正確。 11. 錯誤：廣義表中元素個數(shù)為廣義表的長度。 12. 錯誤：廣義表最大子表的深度加 1 為廣義表的深度。 13. 正確。 14. 正確。 15. 錯誤：廣義表是一種非線性結(jié)構(gòu)。 16. 正確。 17. 正確。 18. 正確：注意單鏈表結(jié)構(gòu)不一定是線性的。 第六章 樹和二叉樹 一、選擇題 l 在二叉樹后序遍歷中， 任一個結(jié)點均在其子女結(jié)點后面， 這種說法（ ） A.正確 B .不正確 C .無法判斷 D .以上均不對 2在二叉樹先序遍歷中， 任一個結(jié)點均在其子女結(jié)點前面， 這種說法（ ） A.正確 B .不正確 C .無法判斷 D .以上均不對 3. 設(shè)深度為 h 的二叉樹上只有葉子結(jié)點和同時具有左右子樹的結(jié)點，則此 類二叉樹中所包含的結(jié)點數(shù)目至少為（ ）。 A 2h B 2h C 2h1 D 2h-l 4 .二叉村第k層上最多有（ ）個結(jié)點。 A 2k B k 2 -1 k-1 C 2k-1 D 2k+ 5 二叉樹的深度為 k， 則二叉樹最多有（ ）個結(jié)點。 A 2k B 2k-1 C 2k-1 D 2k 6. 設(shè)某一二叉樹先序遍歷為 abdec， 中序遍歷為dbeac,則該二叉樹后序遍 歷的順序是 （ ） 。 A . abdec B . debac C. debca D .abedc 21 / 51 7. 設(shè)某一二叉樹中序遍歷為 badce，后序遍歷為bdeca，則該二叉樹先序遍 歷的順序是（ ）。 A .adbec B .decab C .debac D.abode 8 .將一棵樹T轉(zhuǎn)換為一棵二叉樹T2,則T的先序遍歷是T2的（ ）。 A.先序 B .中序 C .后序 D .無法確定 9.將一棵樹T轉(zhuǎn)換為一棵二叉樹T2,則T的后序遍歷是T2的（ ）。 A.先序 B中序 C .后序 D .無法碉定 l0 .樹最適合于用來表示（ ）。 A.線性結(jié)構(gòu)的數(shù)據(jù) B .順序結(jié)構(gòu)的數(shù)據(jù) C. 元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù) D. 元素之間有包含和層次關(guān)系的數(shù)據(jù) 11二叉樹的葉子結(jié)點在先序、中序和后序遍歷過程中的相對秩序（ ）。 A.發(fā)生改變 B.不發(fā)生改變 C.無法確定 D .以上均不正確 12 設(shè)一棵二叉樹度為 2 的結(jié)點數(shù)是 7，度為 1 的結(jié)點數(shù)是 6，則葉子結(jié)點 數(shù)是（ ）。 A 6 B 7 C 8 D 9 13 用順序存儲的方法， 將完全二叉樹中所有結(jié)點按層逐個從左到右的順序 存放在一維數(shù)組R1 . n中，若結(jié)點Ri有左孩子，則其左孩子是（ ）。 AR2i-1 B R2i+1 CR2i D R2/i 144用順序存儲的方法，將完全二叉樹中所有結(jié)點按層逐個從左到右的順 序存放在一維數(shù)組R1. . n中，若結(jié)點Ri有右孩子，則其右孩子是（ ）。 AR2i-1 BR2i l C R2i D R2/i 15一棵非空的二叉樹， 先序遍歷與后序遍歷正好相反， 則該二叉樹滿足（ ）。 A.無左孩子 B .無右孩子 C.只有一個葉子結(jié)點 D .任意二叉樹 16 .設(shè)a、b為一棵二叉樹的兩個結(jié)點，在后序遍歷中，a在b前的條件是（）。 A. a在b上方 B . a在b下方22 / 51 C a 在 b 左方 D a 在 b 右方 17線索二叉樹是一種（ ）。 A.邏輯結(jié)構(gòu) B 線性結(jié)構(gòu) C.邏輯和線性結(jié)構(gòu) D.物理結(jié)構(gòu) 18N 個結(jié)點的線索二叉樹中，線索的數(shù)目是（ ）。 AN-1 BN1 C 2N D 2N1 二、填空題 1 .樹（Tree）是n（n 0）個結(jié)點的_ 。 2 任何 一個非空樹 中：有且僅有 一個特 定的結(jié)點,稱 為該樹 的 _ 的結(jié)點， 吉點之外的其余結(jié)點可分為 m（m 0）個互 不相交的有限集合 T1, T2,，Tm且其中每一個集合又是一棵樹，稱之為 的 。 3樹的 _ 是指一個數(shù)據(jù)元素及指向其子樹的分支。通常通過 一個 _ 來描述,在樹型表示中,用一個圓圈及短線表示。 4 結(jié)點的度是指結(jié)點所擁有的 _ 。 5 樹內(nèi)各結(jié)點度的 _ 為樹的度。 6 度大于 0 的結(jié)點稱為 _ 或 _ 。 7 _ 稱為葉子結(jié)點,簡稱為葉子,又稱作終端結(jié)點。 8 一個結(jié)點的 _ ,或者說一個結(jié)點的 _ 稱為該 結(jié)點的孩子結(jié)點,簡稱為孩子。 9 一個結(jié)點稱為其后繼結(jié)點（即孩子結(jié)點）的 _ 。 10 一個結(jié)點的子樹中的任一結(jié)點都稱為該結(jié)點的 _ 。 11 從根到該結(jié)點所經(jīng)分支上的所有結(jié)點稱為該結(jié)點的 _ 。 12 具有 _ 的結(jié)點互稱為兄弟結(jié)點， 簡稱為兄弟。 19.權(quán)值為 l ,2,6,8的四個結(jié)點構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是 （ ）。 A18 B 28 C 19 D 20實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu), 二叉村采用（ ）存儲結(jié)構(gòu)。 A.二叉鏈表 C.三叉鏈表 21 對一個滿二叉樹, A. n= m 1 B 29 最佳方案B D m個樹葉, m+1=2n 23 具有五層結(jié)點的二叉平衡樹至少有（ A 10 B 12 C 24 設(shè) n, 是（ ）。 A. n在m右方 B C. n在m左方 D 25 線索二又樹是一種（ ）結(jié)構(gòu) A 邏輯 B 邏輯和物理 廣義表存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) k 個分枝結(jié)點, n 個結(jié)點, C . m= k-1 ）個結(jié)點 15 D D 則（ ）。 n=2k+1 m為一棵二叉樹上的二個結(jié)點，在中序遍歷時， 17 n在m.n是m祖先 n 是 m 子孫 C.物理 線性 每一層上從左到右 26 將一棵有 100 個結(jié)點的完全二又樹從根這一層開始, 依次對結(jié)點進(jìn)行編號,根結(jié)點的編號為 1,則編號為 49的結(jié)點的左孩子編號為 （） A 98 B 99 C 50 D 48 23 / 51 13 從根結(jié)點開始定義，根為 _ 層，根的孩子為 _ 層， 依次往下類推，若某結(jié)點在第 k 層，則其子樹的根就在 _ 層。 14 其雙親在同一層次上的結(jié)點互稱為 _ 。 15 樹中結(jié)點的 _ 稱為樹的深度，又稱為樹的高度。 16 如果樹中各結(jié)點的各子樹從左至右是有序排列，不可互換的，則稱 該樹為 。 17 如果樹中各結(jié)點的各子樹無排列順序，即可以互換位置，則稱為該 樹為 。 18 . n(n 0)棵互不相交的樹的集合稱為 _ 。 19 二又樹( Binary Tree )是結(jié)點的有限集合，這個集合或者是空， 或者是由一個根結(jié)點和 _ 的稱為 _ 和 _ 的二 叉樹構(gòu)成。 20 .二叉樹第 i 層上最多有 _ 個結(jié)點。 21 .深度為k的二又樹最多有 _ 結(jié)點(k I)。 22 .在任意二叉樹中，葉子結(jié)點的數(shù)目 (即度為 0的結(jié)點數(shù) )等于度為 2 的結(jié)點數(shù) _ 。 23 .一棵深度為 k 且具有 2k-1 個結(jié)點的二叉樹稱為 _ 。這類 二叉樹的特點是，二叉樹中每一層結(jié)點的個數(shù)都是 _ 的個數(shù)。 24 . _ 是那種在一棵二叉樹中，除最后一層外，若其余層都是 滿的，并且最后一層或者是滿的，或者所缺少的結(jié)點都在右邊。 25 .具有 n 個結(jié)點的完全二叉樹的深度是 _ 。 26 .對于一棵有 n 個結(jié)點的完全二叉樹的結(jié)點進(jìn)行編號(自上而下，自 左至右)，則對任一結(jié)點i (I i I ，則其雙親 Parent(i) 的序號是結(jié)點 _ ;如果2i n,則結(jié)點i的左孩子Lchild(BT, , i )是 _ , 否則結(jié)點i無左孩子(結(jié)點i必為葉子結(jié)點)；如果2i +1 lchild=nil)&(p-rchild=nil) 52. 69 53. 99 54. 2 55. 36 56. 98 5 中序 三、判斷題 1完全二叉樹的某個結(jié)點若無左孩子，則它必然是葉結(jié)點。 （ ） 2存在這樣一種二叉樹，對它采用任何次序的遍歷結(jié)果相同。 （ ） 3. 度為二的樹稱為二叉樹。（X ） 4二叉樹中不存在度大于 2 的結(jié)點。（ ） 5. 當(dāng)二叉樹中某個結(jié)點只有一棵子樹的時候，無左右子樹之分。 （X ） 6. 任何一棵二叉樹都可以不用棧實現(xiàn)前序線索樹的前序遍歷。 （ ） 7. 哈夫曼編碼是一種前綴編碼，不允許出現(xiàn)兩個字符編碼相同的情況。 （） 8. 完全二叉樹某結(jié)點有右子樹，則必然有左子樹。 （ ） 9. 前序遍歷一棵二叉樹的結(jié)點就可以得到排好序的結(jié)點序列。 （X ） 10. 將一棵擁有子樹的樹轉(zhuǎn)換為二叉樹后， 根結(jié)點可能沒有左子樹。（X ） 11. 根據(jù)二叉樹的前序遍歷和中序遍歷可以得到二又樹的后序遍歷。 （ ） 12. 哈夫曼樹是帶權(quán)路徑長度最短的二叉樹。 （ ） 28 / 51 13. 哈夫曼樹上權(quán)值較大的結(jié)點離根較遠(yuǎn)。 （X ） 14. 中序遍歷森林與后序遍歷與森林相對應(yīng)的二叉樹結(jié)果相同。 （X ） 15. 在二叉樹中，具有一個孩子的結(jié)點，在中序遍歷序列中，沒有后繼子女 結(jié)點。 16先序遍歷森林與先序遍歷相對應(yīng)的二叉樹結(jié)果不同。 (X ) 17若一棵二叉樹的任一非葉子結(jié)點的度為 2，則該二叉樹為滿二叉樹 (X ) 18二叉樹只能采用二叉鏈表來存儲。 (X ) 19給定結(jié)點數(shù)的平衡二叉樹的高度是惟一的。 (X ) 1. 正確：根據(jù)完全二叉樹定義可以知道，若完全二叉樹無左孩子，則它必 然無右孩子。 2. 正確：二叉樹只有一個結(jié)點的時候。 3. 錯誤：二叉樹子樹還有左右次序之分。 4. 正確。 5. 錯誤。 6. 正確。 7. 正確。 8. 正確：根據(jù)完全二叉樹定義可以知道， 9. 錯誤：中序遍歷一棵二叉樹的結(jié)點就可以得到排好序的結(jié)點序列。 10. 錯誤：將一棵擁有子樹的樹轉(zhuǎn)換為二叉樹后，根結(jié)點必然有左子樹。 11. 正確。 12. 正確。 13. 錯誤：哈夫曼樹的路徑上權(quán)值較大的結(jié)點離根較近。 14. 錯誤：后序遍歷森林與中序遍歷與森林相對應(yīng)的二叉樹結(jié)果相同。 15. 錯誤：在二叉樹中，具有一個左孩子的結(jié)點，在中序遍歷序列中，沒 有后繼子女結(jié)點。 16. 錯誤：前序遍歷森林與前序遍歷與森林相對應(yīng)的二叉樹結(jié)果相同。 17. 錯誤：任一非葉子結(jié)點的度為 2 也不能保證滿足滿足滿二叉樹的定義 18. 錯誤：也可以采用順序存儲和三叉鏈表等形式進(jìn)行表示。 19. 錯誤：給定結(jié)點數(shù)的平衡二叉樹的高度不一定是惟一的。 四、綜合題 1 一棵樹表達(dá)成如下形式： A A, B, C, D, E, F, G, H, I , J, K, L, M N 0 R=,v A, C,v A, D,v B, E,v B, F,v C, G,V D, I , 其中D為結(jié)點集合，R為邊的集合。請根據(jù)以上內(nèi)容回答以下問題： (1) 畫出這棵樹。 (2) 該樹的根結(jié)點是哪一個？ (3) 哪些是葉子結(jié)點？ (4) F 結(jié)點的雙親是誰？ (5) F 結(jié)點的祖先是哪些？ (6) F 結(jié)點的孩子是哪些？ (7) F 結(jié)點的兄弟是哪些？ 29 / 51 (8) F 結(jié)點的堂兄弟是哪些？ (9) F 結(jié)點的度是多少？ (10) F 結(jié)點的層次是多少？30 / 51 (11) D結(jié)點的子孫有哪些？ (12) 以結(jié)點D為根的子樹度是多少？ (13) 以結(jié)點D為根的子樹層是多少？ (14) 該樹的層是多少？ (15) 該樹的度是多少？ 2. 畫出圖6-1中樹的二叉樹表示形式。 (a) (b) ( c) 圖6-1 3. 已知某二叉樹的先序遍歷的結(jié)果是： A, B, D, QC E，H, L，I，K, M F和J，它的中序遍歷的結(jié)果是： QD B, A, L, H, E, K, LM C, F和J，請畫 出這棵二叉樹，并且寫出該二叉樹后序通歷的結(jié)果。 4. 寫一個將一棵二叉樹復(fù)制給另一棵二又樹的算法。 5. 已知一個二叉樹用二叉鏈表表示，其根指針為 t，請寫一個算法，從根 結(jié)點開始按層次通歷該二叉樹，同層的結(jié)點接從左到右的次序進(jìn)行訪問。 6. 已知一棵二叉樹的先序遍歷序列和中序遍歷序列，請寫出根據(jù)二又樹先 序遍歷序列和中序遍歷序列構(gòu)造一棵二叉樹的算法。 7. 假設(shè)一棵哈夫曼樹共有nO個葉子結(jié)點，試證明樹中共有 2no-l個結(jié)點。 8 .假設(shè)通信用的報文由9個字母A、B、C、D E、F、G H和I構(gòu)成，它們 出現(xiàn)的頻率分別是：10、20、5、15、8、2、3、7和30。請用這9個字母出現(xiàn) 得頻率作為權(quán)值求： (l )設(shè)計一棵哈夫曼樹。 (2) 計算其帶權(quán)路徑長度 WPLSo (3) 寫出每個字符的哈夫曼編碼。 1. (1) 該樹的圖形如圖B-1所示。 A K L M 圖B-1 (2) 該樹的根結(jié)點是Ao B C E F G I 31 / 51 (3) 葉子結(jié)點是：E、K、L、M G H N 0和J (4) F結(jié)點的雙親是Bo (5) F結(jié)點的祖先是A和Bo32 / 51 (6) F結(jié)點的孩子是K、L和M (7) F結(jié)點的兄弟是E。 (8) F結(jié)點的堂兄弟是G H、I和J。 (9) F結(jié)點的度是3。 (10) F結(jié)點的層是3。 (11) D結(jié)點的子孫有I、N和0。 (12) 以結(jié)點D為根的子樹度為3。 (13) 以結(jié)點D為根的子樹層為3。 (14) 該樹的層是4。 (15) 該樹的度是3。 2. 本題樹對應(yīng)的二叉樹形式如圖 B-2所示 圖B-2 3. 該二叉樹的圖形表示如圖 B-3所示，該二叉樹后序遍歷的結(jié)果是：GD B、L、H、K、M I、E、J、F、C 和 A B-3 用遞歸方法建立二叉樹并求其深度的算法如下所示: typedef struct btnode elemtype data; struct btnode *lchild, *rchild; E C i D F G K H L I M J (a) (b) 圖 4. define NULL 0 A B N (c) A E 33 / 51 bit no de, *bitree;34 / 51 bitnode *CreateBiTree() /* 用遞歸方法建立一棵二叉樹 */ bitnode *t; char c; printf(Please input the data,# is the end.n) c=getchar(); if ( c=# ) return(NULL); else t=( bitnode * )malloc (sizeof(bitnode); /* 生成新結(jié)點 */ t-data=c; /* 為數(shù)據(jù)域賦值 */ t-lchild=CreateBiTree(); t-rchild=CreateBiTree(); return(t); /*CreateBiTree()*/ /* 遞歸創(chuàng)建左子樹 */ /* 遞歸創(chuàng)建右子樹 */ int TreeDepth(bitnode *p) /* 遞歸求二叉樹深度 */ int hl,hr,h; if ( p!=NULL ) hl=TreeDepth(p-lchild); hr=TreeDepth(p-rchild); if ( hlhr ) h=hl; else /* 遞歸求左子樹深度 */ /* 遞歸求右子樹深度 */ h=hr; return（h 1）;/* 返回較大左右子樹深度加 1*/ else return(0); /*TreeDepth*/ 5. 將一棵二叉樹復(fù)制給另一棵二叉樹的算法如下所示： define NULL 0 typedef struct btnode elemtype data; struct btnode *lchild, *rchild; bitnode, *bitree; 35 / 51 bitree *CopyTree( bitnode *p ) /* 復(fù)制一棵二叉樹 */ bitnode *t; if ( p!=NULL ) t=(bitnode *)malloc (sizeof (bitnode); t-data=p-data; t-lchild=CopyTree(p-lchild); t-rchild=CopyTree(p-rchild); return(t); else return(NULL); /*CopyTree*/ 6.可以使用隊列Q來保存遍歷過程中的各個結(jié)點，隊列可以設(shè)定為bitree 類型的指針數(shù)組，下標(biāo)從 1 開始，同層結(jié)點按從左到右的順序存放。算法如下： define NULL 0 define MAXSIZE 100 typedef char elemtype; typedef struct btnode elemtype data; struct btnode *lchild, *rchild; bitnode, *bitree; void LevelOrderTraverse( bitree t ) /* 使用隊列對二叉樹進(jìn)行按層序遍歷 */ bitree *QMAXSIZE; /*隊列Q是一個指向bitree類型的指針數(shù)組，下標(biāo)從1開始*/ int rear, front; if (t!=NULL) front=0; /* 置空隊列 */ rear=1; Q1=t; do front=front%MAXSIZE+1; /* 元素出隊列 */ t=Qfront; printf(%c,t-data); if ( t-lchild!=NULL ) /* r