數據結構習題集(包含全部答案).

《數據結構習題集(包含全部答案).》由會員分享，可在線閱讀，更多相關《數據結構習題集(包含全部答案).（57頁珍藏版）》請在裝配圖網上搜索。

1、1 / 51 數據結構習題集（自編） 第一章緒論 一、 選擇題 1 數據結構是一門研究非數值計算的程序設計問題中的操作對象以及它們之間 的（）和運算的學科。 A. 結構 _B.關系 C .運算 D .算法 2 在數據結構中，從邏輯上可以把數據結構分成（）。 A. 動態(tài)結構和靜態(tài)結構 B .緊湊結構和非緊湊結構 C線性結構和非線性結構 D .邏輯結構和存儲結構 3. 線性表的邏輯順序和存儲順序總是一致的，這種說法（）。 A .正確 B.不正確 C .無法確定 D .以上答案都不對 4. 算法分析的目的是（）o A.找出算法的合理性 B .研究算法的輸人與輸出關系 C.分析算法的有效性以求改進 D

2、 .分析算法的易懂性 5. 算法的時間復雜度取決于（） A.問題的規(guī)模B待處理數據的初態(tài)C. A和B 6. 一個算法應該是（ ） A.程序 B.問題求解步驟的描述 C .要滿足五個基本特性 D . A和C. 7. 下面關于算法說法錯誤的是（ ） A. 算法最終必須由計算機程序實現 B. 為解決某問題的算法與為該問題編寫的程序含義是相同的 C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的 8. 以下與數據的存儲結構無關的術語是（ ） A.循環(huán)隊列 B. 鏈表 C. 哈希表 D.棧 9. 在下面的程序段中，對x的賦值語句的頻度為（ ） for （i=0;in;i+ ） for（j=

3、0;j n ;j+） x=x+1; A. 2n B . n C. n2 D . log 2 10. 以下數據結構中，（ ）是非線性數據結構 A.樹 B .字符串 C .隊列 D .棧 11. 下列數據中，（ ）是線性數據結構。 A.哈夫曼樹 B. 有向無環(huán)圖 C. 二叉排序樹 D.棧 12. 以下屬于邏輯結構的是（ ） A.順序表 B. 哈希表 C.有序表 D. 單鏈表 二、 填空題 1、 _ 信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、 存儲、加工和處理， _ 對能夠有效的輸人到計算機中并且能夠被計算機 處理的符號的總稱。（數據、數據） 2 、數據元素是數據的 _ ，有些情況下也

4、稱為元素、結點、頂點、記錄 等。（基本單位） 3、 _ 數據不可分割的最小單元，是具有獨立含義的最小標識單位。 2 / 51 例如構成一個數據元素的字段、域、屬性等都可稱之為 _ 。（數據項、數 據項） 4 、數據的邏輯結構是指數據之間的 _ 。邏輯結構是從 _ 上描 述數據，它與具體存儲無關， 是獨立于計算機的。 因此邏輯結構可以看作是從具 體問題抽象出來的 _ 。（邏輯關系、邏輯關系、數學模型） 5 、數據 的 _ 指數據元素 及 其關系在 計算機 存儲器內的 表示。 _ 是邏輯結構在計算機里的實現， 也稱之為映像。（存儲結構、 存儲結構） 6 、數據邏輯結構可以分為四種基本的類型， _

5、結構中的元素除了僅僅 只是同屬于一個 _ ，不存在什么關系。（集合、集合） 7 、數據邏輯結構的四種基本類型中， _ 中的元素是一種一對一的關 系，這種結構的特征是： 若結構是非空集， 則有且只有一個開始結點和一個終端 結點，并且所有結點最多只能有一個直接前驅和一個直接后繼。 （線性結構） 8 、數據邏輯結構的四種基本類型中， _ 中的元素是一種一對多 的關系。（樹形結構） 9 、圖型結構或圖狀結構是一種 _ 的關系。在這種邏輯結構中，所有 結點均可以有多個前驅和多個后繼。 （多對多） 10 、有時也可將樹型結構、 集合和圖型結構稱為 _ ，這樣數據的邏 輯結構就可以分為 _ 和 _ 兩大類。

6、（非線性結構、線性結構、非 線性機構） 11 、_ 方式是指邏輯上相鄰的結點被存儲到物理上也相鄰的存儲 單元中。這種存儲結構只存儲結點的數值， 不存儲結點之間的關系， 結點之間的 關系是通過存儲單元的相鄰關系隱含的表示出來的。 （順序存儲） 12 、_ 方式是種存儲方法， 不要求邏輯上相鄰的結點在物理上也相鄰， 即數據元素可以存儲在任意的位置上。 （鏈式存儲） 13 、_ 方式是利用結點關鍵字的值直接計算出該結點存儲單元地址， 然后將結點按某種方式存人該地址的一種方法。 （散列存儲或哈希存儲） 14 、所謂算法（ Algorithm ）是對特定問題求解步驟的一種描述，它是指令 的其中每個指令表

7、示一個或多個操作。算法的五個重要特性是 _ 、 _ 、 _ 、 _ 和 _ 。（有限序列、有窮性、確 定性、可行性、輸入、輸出） 15、算法的 _ 性是指算法必須能夠在執(zhí)行有限個步驟之后結束，并且 每個步驟都必須在有窮的時間內完成。 （有窮性） 16、算法的 _ 性是指算法中的每一個步驟必須是有明確定義的，不允 許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟 一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到 _ 的輸出結果。 （確定性、相同） 17 、算法的 _ 性又稱為算法的能行性， 是指算法中描述的操作是 可以通過已經實現的基本運算執(zhí)行有限次來實現。 （可行性） 18

8、 、判斷一個算法的好壞主要以下幾個標準： _ 、 _ 、 _ 、 _ 。（正確性、可讀性、健壯性、時間效率和空間效率） 19 、算法分析是對一種算法所消耗的計算機資源的估算，其中包括計算機 _ 的長短和 _ 的大小。（運行時間、所占據空間） 20 、空間復雜度（ SPaceComPlexity ）也是度量一個算法好壞的標準，它所 描述的是算法在3 / 51 運行過程中所占用 _ 的大小。（存儲空間）4 / 51 三、判斷題 1 順序存儲方式只能用于存儲線性結構。(X) 2 數據元素是數據的最小單位。(X) 3 算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。 ( X ) 4 健壯的算法不會因

9、非法的輸入數據而出現莫名其妙的狀態(tài)。 () 5數據的邏輯結構是指各元素之間的邏輯關系，是根據用戶需要而建立的。 6數據結構、數據元素、數據項在計算機中的映像分別稱為存儲結構、結 點、數據域。() 7 數據的物理結構是指數據在計算機中實際的存儲形式。 () 8 具有存取任一元素的時間相等這一特點的存儲結構稱為隨機存取結構。 9算法實際上就是程序，程序也一定是算法。 ( X ) 10. 在順序存儲結構中，有時也存儲數據結構中元素之間的關系。 (X ) 11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 (X) 12. 數據結構的基本操作的設置的最重要的準則是，實現應用程序與存儲結構的

10、獨立 13. 數據的邏輯結構說明數據元素之間的順序關系 , 它依賴于計算機的儲存結構。 14. 判斷一個算法的好壞主要以下幾個標準：正確性、有窮性、健壯性和可 行性。 ( X ) 15算法的時間復雜度 T( n) =O(f(n) 表示隨問題規(guī)模 n 的增大，算法執(zhí)行 時間的增長率與函數 f(n) 的增長率相同。() 四、綜合題 1 用大0形式表示下面算法的時間復雜度： for (i=0 ； i v m i 十十) for (j=0 ; j v n； j + + ) Aij=i*j ； 2 寫出下面算法的時間復雜度： i = 0； s=0 ； while(s v n) i+； s+=i; 3寫出

11、以下算法的時間復雜度： 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. 該算法的時間復雜度為：O(mx n)。 2. 該算法的時間復雜度為：0(. n) 3. 該算法的時間復雜度為：0(mx nx t) o 4. 該算法的時間復雜度為：logn) o 5.

12、 該算法的時間復雜度為：0(.n) o 6. 將下列函數，按它們在nx時的無窮大階數，從小到大排序。 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

13、. p=p-next; p-next=p-next-next 14. 在一個單鏈表中，已知q所指結點是p所指結點的前驅，若在q和p之 間插入 s 所指的C .部分地址必須連續(xù) D. 連續(xù)與否均可以 5 .在一個具有 n 個結點的有序單鏈表中插人一個新的結點，使得鏈表仍然 有序，該算( )O(n2) DO(n) 7. 在一個長度為 n 的順序表中，向第 元素時，需要向后移動 ( ) 個元素。 A . n-i B. n-i +1 8. 如果某鏈表中最常用的操作是取第 方式最節(jié)省時間。 A .單鏈表 B .雙向鏈表 .一個有限序列，不可以為空 .一個無限序列，不可以為空 個位置(0 1vn+ 1)插

14、入一個新 . n i 1 D . i + 1 個結點及其前驅，則采用 ( ) 存儲 .單循環(huán)鏈表 90， 9. 一個順序存儲線性表的第一個元素的存儲地址是 2，則第 6 個元素的存儲地址是() 。 A . 98 B. 100 C . 102 D.順序表 每個元素的長度是 106 7 / 51 結點，則執(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在單鏈表中附加頭結點的目的是為了（ ）。 A. 保證單鏈表中至少有一個節(jié)點 B. 標識單

15、鏈表中首結點的位置 C. 方便運算的實現 D. 說明單鏈表是線性表的鏈式存儲 16. 循環(huán)單鏈表的主要優(yōu)點是（ ）。 A. 不再需要頭指針了 B. 從表中任意一個結點出發(fā)都能掃描到整個鏈表 C已知某個結點的位置后，能夠容易找到它的前驅 D.在進行插入、刪除操作時，能更好地保證鏈表不斷開 17. 非空的循環(huán)單鏈表L的尾結點p滿足（）。 A. p-next=NULL B. p=NULL C. p-next=L D. p=L 18. 在雙向循環(huán)鏈表中 ,在 p 指針所指向的結點前插入一個指針 q 所指向的 新結點 , 其修改指針的操作是 （ ） 。 注: 雙向鏈表的結點結構為 （prior,data

16、,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. 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。 A. p-prior-next=p-next;

17、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 ）是最簡單、最常用的一種數據結構。線性表中的元素 存在著 _ 的相互關系。（一對一） 2. 線性表中有且僅有一個開始結點，表中有且僅有一個終端結點，除開始結點 外，其他每個元素有且僅有一個 _ ，除終端結點外，其他每個元素

18、有且僅有一個 _ 。 3. _ 線性表是n （n=0）個數據元素的 。 其中n為數據元素的個數，定 義為線性表的 _ 。當 n 為零時的表稱為 _ 。 4. 所謂順序表（ Sequential LISt ）是線性表的 _ ，它是將線性表中的 結點按其 _ 依次存放在內存中一組連續(xù)的存儲單元中，使線性表 8 / 51 中相鄰的結點存放在 _ 的存儲單元中。 5. 單鏈表不要求邏輯上相鄰的存儲單元在物理上也一定要相鄰。它是分配一些 _ 的存儲單元來存儲線性表中的數據元素， 這些存儲單元可以分散在內 存中的 的位置上， 它們在物理上可以是一片連續(xù)的存儲單元， 也可 以是 _ 的。因此在表示線性表這種

19、數據結構時，必須在存儲線性表 元素的同時，也存儲線性表的 6 線性表的鏈式存儲結構的每一個結點（Node）需要包括兩個部分：一部分用 來存放元素的數據信息， 稱為結點的 _ ；另一部分用來存放元素的指 向直接后繼元素的指針 （即直接后繼元素的地址信息 ），稱為 _ 或 7線性鏈表的邏輯關系是通過每個結點指針域中的指針來表示的。其邏輯順序 和物理存儲順序不再一致， 而是一種 _ 存儲結構，又稱為 _ 。 8如果將單鏈表最后一個結點的指針域改為存放鏈表中的頭結點的地址值，這 樣就構成了 。 9為了能夠快速地查找到線性表元素的直接前驅，可在每一個元素的結點中再 增加一個指向其前驅的指針域，這樣就構成

20、了 _ 。 10雙向鏈表某結點的指針 P,它所指向結點的后繼的前驅與前驅的后繼都是 p _ 。 11在單鏈表中,刪除指針 P 所指結點的后繼結點的語句是 _ 。 12 在雙循環(huán)鏈表中，刪除指針 P所指結點的語句序列是 P-prior-next = p-next 及 _ 。 13單鏈表是 _ 的鏈接存儲表示。 14可以使用 _ 表示樹形結構。 15. _ 向一個長度為n的向量的第i個元素（I i n+1）之前插人一個元素時，需 向后移動 _ 個元素。 16刪除一個長度為n的向量的第i個元素（I i next=p-next-next 12. P-next-prior=P-prior 13. 線性表

21、 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 線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續(xù)的。 (X) 2. 在具有頭結點的鏈式存儲結構中，頭指針指向鏈表中的第一個數據結點。(X) 3順序存儲的線性表不可以隨機存取。 (X) 4.

22、單鏈表不是一種隨機存取結構。 () 5. 順序存儲結構線性表的插入和刪除運算所移動元素的個數與該元素的位置無 關。 ( X ) 6. 順序存儲結構是動態(tài)存儲結構，鏈式存儲結構是靜態(tài)存儲結構。 (X) 7. 線性表的長度是線性表所占用的存儲空間的大小。 (X) 8. 雙循環(huán)鏈表中， 任意一結點的后繼指針均指向其邏輯后繼。 (X) 9. 線性表的惟一存儲形式是鏈表。 (X ) 1. 錯誤：鏈表存儲中，結點之間可以連續(xù)也可以不連續(xù)，但結點內部是連 續(xù)的。 2. 錯誤：頭指針指向頭結點而不是數據結點。 3. 錯誤：順序存儲的線性表可以隨機存取。 4. 正確。 5. 錯誤。 6. 錯誤：順序存儲結構是靜

23、態(tài)存儲結構，鏈式存儲結構是動態(tài)存儲結構。 7. 錯誤：先行表的長度是線性表中結點的個數。 8. 錯誤：注意最后一個結點。 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

24、. 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 的不帶頭結點的鏈棧中插人一個 *S 結點的時候,應當 執(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. 向一個帶頭結點、棧頂

25、指針為 top 的鏈棧中插人一個 *S 結點的時候,應當執(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.

26、 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 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數據 緩沖區(qū)，主機將要輸出的數據依次寫人該緩沖區(qū)， 而打印機則從該緩沖區(qū)中取走 C Q-front= =（Q-rear +1） 10.判定一個循環(huán)隊列Q （最多有 A Q-rear = =

27、 front n D n 個元素） B n 和 rear B D 和 rear ） 限制存取點的線性結構 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 分別為頭指針和尾指針,刪除一個結 . rear=rear-next .front-next = rear A.鏈式存儲的線性

28、結構 B .鏈式存 D 限制存取點的非線性結構 ）不可能是一個出棧序列。 C4, 2, 3, 1 D 4, 3, 2, l 11 / 51 數據打印。該緩沖區(qū)應該是一個（ ）結構。 A .堆棧 B.隊列 C .數組 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 ）是限定在 _ 一端進行插人或刪除操作的線性表。在棧中， 允許插人和刪除操作的一端稱為 _ ，而另一端稱為 _ 。不含元 素的棧稱為 _ 。 2在棧的運算中，棧的插人操作稱為 _ 或

29、 _ ，棧的刪除操作稱為 _ 或 _ 。 3根據棧的定義，每一次進棧的元素都在原 _ 之上，并成為新的 _ ；每一次出棧的元素總是當前的 ，因此最后進棧的元 素總是 ， 所以棧也稱為 _ 線性表，簡稱為 _ 表。 4棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有 _ 和 兩種存儲結構，分別稱為 _ 和 _ 5當棧滿的時候，再進行人棧操作就會產生 ， 這種情況的溢出稱 為 _ ；當棧空的時候，如果再進行出棧操作，也會 _ ，這 種情況下的溢出稱為 _ 。 6棧的鏈式存儲結構簡稱為 _ ，是一種 _ 。 7人們日常計算用到的表達式都被稱為 _ ，這是由于這種算術表達 式的運算符被置于

30、兩個操作數中間。 8計算機中通常使用 _ ，這是一種將運算符置于兩個操作數后面的算 術表達式。這種表達式是由波蘭科學家謝維奇提出的， 因此又稱為 _ 9. _ 隊列（Queue）也是一種 但它與棧不同，隊列中所有的插人均 限定在表的一端進行， 而所有的刪除則限定在表的另一端進行。 允許插人的一端 稱為 ， 允許刪除的一端稱為 _ 。 10. _ 隊列的特點是 _ ，因此隊列又被稱為 _ .的線性表， 或稱為 _ 表。 11. _ 隊列的 _ 又稱為 ，是用一組地址連續(xù)的存儲單元依次存 放隊列中的元素。 12. 由于隊列中的元素經常變化， 對于隊列的刪除和插人分別在隊頭和隊尾進行， 因此需要設置

31、兩個指針分別指向 _ 和 _ ，這兩個指針又稱為 _ 和 _ 。 13. _ 循環(huán)順序隊列（Circular SequenceQueue經常簡稱為 _ 它是 將存儲順序隊列的存儲區(qū)域看成是一個首尾相連的一個環(huán)， 即將隊首和隊尾元素 連接起來形成一個環(huán)形表。首尾相連的狀態(tài)是通過數學上的 _ 來實現的。 14. 在算法或程序中， 當一個函數直接調用自己或通過一系列語句間接調用自己 的時候，則稱這個函數為，也稱為 _ 。函數直接調用自己，則稱為 _ ；當一個函數通過另一個函數來調用自己則稱為 _ 。 15. _ 在循12 / 51 環(huán)隊列中規(guī)定： 當 Q-rear= =Q-front 的時候循環(huán)隊列

32、為 _ ，13 / 51 當（Q-rear+1 ）% MAXSIZ旨 front 16 用鏈表方式表示的隊列稱為 _ 17已知棧的輸人序列為1, 2, 3,，n,輸出序列為al, a2,，an,符合 a2= =n的輸出序列共有 _ 。 18一個棧的輸人序列是 12345,則棧的輸出序列為 可能）。 19一個棧的輸人序列是 12345,則棧的輸出序列為 否可能）。 20設 sq1 maxsize 為一個順序存儲的棧,變量 則作入棧操作的條件是 _ 。 21設 sq1 maxsize 為一個順序存儲的棧,變量 top 指示棧頂元素的位置, 如果把棧頂元素彈出并送到 X中，則需執(zhí)行語句 _ 。 22

33、棧的特性是 _ 23對棧進行退棧時的操作是先取出元素,后移動 _ 。 24. _ 設s1 . max為一個順序存儲的棧，變量top指示棧頂位置，棧為滿的條 件是 。 25. _ 設鏈棧的棧頂指針為top，則棧非空的條件是 _。 26. _ 已知循環(huán)隊列用數組data1n存儲元素值，用f, r分別作為頭尾指針， 則當前元素個數為 _ 。 27在一個循環(huán)隊列中，隊首指針指向隊首元素的 _ 位置。（前一個或后 一個） 28隊列中允許進行刪除的一端稱為 _ 。 29.鏈隊列實際上是一個同時帶有頭指針和尾指針的單鏈表（1. n）,尾指針指 向該單鏈表的第 _ 個元素。 30設雙向鏈表鏈列為 lq ， l

34、q 的頭指針為 lq.Front ，尾指針為 lq.Rear ，則隊 列為空的條件是 _ 。 的時候循環(huán)隊列為 43512 是 _ （填是否 12345 是 _ （填是 top 指示棧頂元素的位置, 1. 表尾、棧頂、棧底、空棧 2. 進棧、入棧、退棧、出棧 3. 棧頂元素、棧頂元素、棧頂元素、 最先出棧、后進先出、 4. 順序、鏈式、順序棧、鏈棧 5. 溢出、上溢、溢出、下溢 6. 鏈棧、特殊的單鏈表 7. 中綴表達式 8. 后綴表達式、波蘭式 9. 特殊的線性表、隊尾、隊頭 10. 先進先出、先進先出、 FIFO 11. 順序存儲結構、順序隊列 12. 隊頭元素、隊尾元素、隊頭指針 、隊尾

35、指針 13. 循環(huán)隊列、取模運算 14. 遞歸函數、自調用函數、直接遞歸調用、間接遞歸調用 15. 空、滿 1 鏈隊列 LIFO 31從循環(huán)隊列中刪除一個元素， 其操作是先取出一個元素， 后移動 _ 32隊列中允許進行插入的一端稱為 _ 。 14 / 51 17n-1 18 不可能的 19 可能的 20 top!=maxsize 21 x=sqtop; 1 22 先進后出 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棧和隊列都是限

36、制存取點的線性結構。 （ ） 2不同的入棧和出棧組合可能得到相同輸出序列。 （ ） 3消除遞歸一定要用棧。 （ ） 4循環(huán)隊列是順序存儲結構。 （ ） 5循環(huán)隊列不會產生溢出。 （ ） 6循環(huán)隊列滿的時候 rear= =front 。（ ） 7在對鏈隊列（帶頭結點）做出隊操作時不會改變 front 指針的值。（） 1. 正確。 2 錯誤： 不同的入棧和出棧組合得到不同輸出序列。 3. 錯誤： 某些情況如尾遞歸可以轉換為遞推的形式。 4 正確。 5. 錯誤： 循環(huán)隊列不會產生假溢出。 6 錯誤。 7 正確。 四、綜合題 1 設有4個元素A、B、C和D進棧，給出它們所有可能的出棧秩序 可能的出棧序

37、列： （共 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 習題四 一、選擇項 l 空串與空格串（ ）。 15 / 51 A 相同 B 不相同 C 可能相同 D 無法確 定 2設有兩個申S1與S2,求串S2在S1中首次出現位置的運算稱作（ ） A 連接 B 求子串 C 模式匹配 D 判子串 3串與普通的線性表相比較,它的特殊性體現在（ ）。 A 順序的存儲結構

38、 B 鏈接的存儲結構 C 數據元素是一個字符 D 數據元素可以任意 4. 設有串S= Computer,則其子串的數目是（ ）。 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）個 的有序組合，數組中的數據是 按順序存儲在一塊 _ 的存儲單元中。 2. _ 數組中的每一個數據通常稱為 ， 用下標區(qū)分，其中下標的 個數由數組的 _ 決定。 3. 由于計算機內存中的存儲單元是一個一維的存儲結構，因此對于

39、多維數 組要想按順 序存儲到計算機存儲單元中就必須有一個排列順序問題。 對于二維數組， 有 兩種排列形式：一種是 _ ；另一種是 _。 4. _ 對于需要壓縮存儲的矩陣可以分為 _ 和 _ 。對那些具有 19 / 51 相同值元素或零元素在矩陣中分布具有一定規(guī)律的矩陣，我們稱之為 ；而對于那些零元素數目遠遠多于非零元素數目，并且非零元素的 分布沒有規(guī)律的矩陣稱為 。 5. _ 在一個n階方陣a中，若元素滿足性質：aj = (0=i , j=0)個元素的序列。記作：A=( al, a2,，an),其 中， A 是廣義表的 _ ， n 是它的 _ ， 當 n=0 的時候稱為 9. 在一個非空的廣義

40、表中，其元素 ai可以是某一確定類型的單個元素，稱 為 _ ，也可以又是一個廣義表，稱為 _ 。 10. 廣義表的定義是一種遞歸的定義，廣義表是一種遞歸的數據結構。當廣 義表非空的時候，稱第一個元素 ai為廣義表A的 _ ，稱其余元素組成 的表(a2，a3,，an)是A的 _ 。 11 .廣義表的深度一般定義為廣義表元素 _ ，或者說是廣義表 _ 。 利用 遞 歸 的 定 義 ， 廣 義 表 的 深 度 就 是 所 有 子 表 中 1. 相同類型數據、地址連續(xù) 2. 數組元素、數組元素、維數 3. 以行序為主、以列序為主 4. 特殊矩陣、稀疏矩陣、特殊矩陣、稀疏矩陣 5. 對稱矩陣 6. 三元

41、組順序表、三元組 7. 矩陣轉置 8. 名稱、長度、空表 9. 原子、子表 10. 表頭、表尾 11. 最大的層數、括號的重數、最大深度加 1 三、判斷題 1 .十字鏈表不是順序存儲結構。 ( ) 2. 三元組表不是一個隨機存取結構。 ( ) 3. 稀疏矩陣壓縮存儲后， 必然會失去隨機存取功能。 ( ) 4. 若一個廣義表的表頭為空表，則此廣義表也為空表。 ( ) 5. 廣義表是線性表的推廣，是一類線性數據結構。 ( ) 6. 任何一個非空廣義表，其表頭可能是單元素或廣義表，其表尾必定是廣 義表。 () 7. 一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關行下標與列 下標的值互換，并

42、把 m和n的值互換，則就完成了 Am*n的轉置運算。( ) 20 / 51 8數組中每個元素必定具有相同的數據類型。 （ ） 9線性表是廣義表的特例。 （ ） 10如果廣義表中的每個元素都是原子，則廣義表便成為線性表。 （） 11廣義表中原子個數即為廣義表的長度。 （） 12廣義表最大子表的深度為廣義表的深度。 （） 13廣義表中元素最大的層數稱為廣義表的深度。 （） 14廣義表是一種多層次結構。 （） 15廣義表是一種線性結構。 （） 16廣義表是一種共享結構。 （） 17廣義表是一種遞歸結構。 （） 18廣義表是一種單鏈表結構。 （） 1. 正確：十字鏈表是鏈接存儲結構。 2. 正確：具有

43、存取任一元素的時間相等這一特點的存儲結構稱為隨機存取 結構，三元組表存儲矩陣的時候，要訪問第 i 行 j 列元素必須掃描三元組表， 顯然查找三元組表前面的元素與后面元素所耗費的時間不同，因此三元組表不 是一個隨機存取結構。 3. 正確：隨機存取結構是指存取任一元素的時間相等這一特點的存儲結 構，對稀疏矩陣壓縮存儲所用的存儲結構是十字鏈表和三元組，而這兩種存儲 結構都不是隨機存取結構。 4. 錯誤：如廣義表 L=（）,（A, B） 為非空，而表頭為空表。 5. 錯誤：廣義表是線性表的推廣，是一類非線性數據結構。 6. 正確：表尾的定義是除表頭元素以外其余元素（可以為空）構成的表， 所以必定是廣義

44、表。 7. 錯誤：應該在互換行列后再按照行優(yōu)先重新存儲。 8. 正確。 9. 正確。 10. 正確。 11. 錯誤：廣義表中元素個數為廣義表的長度。 12. 錯誤：廣義表最大子表的深度加 1 為廣義表的深度。 13. 正確。 14. 正確。 15. 錯誤：廣義表是一種非線性結構。 16. 正確。 17. 正確。 18. 正確：注意單鏈表結構不一定是線性的。 第六章 樹和二叉樹 一、選擇題 l 在二叉樹后序遍歷中， 任一個結點均在其子女結點后面， 這種說法（ ） A.正確 B .不正確 C .無法判斷 D .以上均不對 2在二叉樹先序遍歷中， 任一個結點均在其子女結點前面， 這種說法（ ） A.

45、正確 B .不正確 C .無法判斷 D .以上均不對 3. 設深度為 h 的二叉樹上只有葉子結點和同時具有左右子樹的結點，則此 類二叉樹中所包含的結點數目至少為（ ）。 A 2h B 2h C 2h1 D 2h-l 4 .二叉村第k層上最多有（ ）個結點。 A 2k B k 2 -1 k-1 C 2k-1 D 2k+ 5 二叉樹的深度為 k， 則二叉樹最多有（ ）個結點。 A 2k B 2k-1 C 2k-1 D 2k 6. 設某一二叉樹先序遍歷為 abdec， 中序遍歷為dbeac,則該二叉樹后序遍 歷的順序是 （ ） 。 A . abdec B . debac C. debca D .ab

46、edc 21 / 51 7. 設某一二叉樹中序遍歷為 badce，后序遍歷為bdeca，則該二叉樹先序遍 歷的順序是（ ）。 A .adbec B .decab C .debac D.abode 8 .將一棵樹T轉換為一棵二叉樹T2,則T的先序遍歷是T2的（ ）。 A.先序 B .中序 C .后序 D .無法確定 9.將一棵樹T轉換為一棵二叉樹T2,則T的后序遍歷是T2的（ ）。 A.先序 B中序 C .后序 D .無法碉定 l0 .樹最適合于用來表示（ ）。 A.線性結構的數據 B .順序結構的數據 C. 元素之間無前驅和后繼關系的數據 D. 元素之間有包含和層次關系的數據 11二叉樹的葉子

47、結點在先序、中序和后序遍歷過程中的相對秩序（ ）。 A.發(fā)生改變 B.不發(fā)生改變 C.無法確定 D .以上均不正確 12 設一棵二叉樹度為 2 的結點數是 7，度為 1 的結點數是 6，則葉子結點 數是（ ）。 A 6 B 7 C 8 D 9 13 用順序存儲的方法， 將完全二叉樹中所有結點按層逐個從左到右的順序 存放在一維數組R1 . n中，若結點Ri有左孩子，則其左孩子是（ ）。 AR2i-1 B R2i+1 CR2i D R2/i 144用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順 序存放在一維數組R1. . n中，若結點Ri有右孩子，則其右孩子是（ ）。 AR2i-1

48、BR2i l C R2i D R2/i 15一棵非空的二叉樹， 先序遍歷與后序遍歷正好相反， 則該二叉樹滿足（ ）。 A.無左孩子 B .無右孩子 C.只有一個葉子結點 D .任意二叉樹 16 .設a、b為一棵二叉樹的兩個結點，在后序遍歷中，a在b前的條件是（）。 A. a在b上方 B . a在b下方22 / 51 C a 在 b 左方 D a 在 b 右方 17線索二叉樹是一種（ ）。 A.邏輯結構 B 線性結構 C.邏輯和線性結構 D.物理結構 18N 個結點的線索二叉樹中，線索的數目是（ ）。 AN-1 BN1 C 2N D 2N1 二、填空題 1 .樹（Tree）是n（n 0）個結點的

49、_ 。 2 任何 一個非空樹 中：有且僅有 一個特 定的結點,稱 為該樹 的 _ 的結點， 吉點之外的其余結點可分為 m（m 0）個互 不相交的有限集合 T1, T2,，Tm且其中每一個集合又是一棵樹，稱之為 的 。 3樹的 _ 是指一個數據元素及指向其子樹的分支。通常通過 一個 _ 來描述,在樹型表示中,用一個圓圈及短線表示。 4 結點的度是指結點所擁有的 _ 。 5 樹內各結點度的 _ 為樹的度。 6 度大于 0 的結點稱為 _ 或 _ 。 7 _ 稱為葉子結點,簡稱為葉子,又稱作終端結點。 8 一個結點的 _ ,或者說一個結點的 _ 稱為該 結點的孩子結點,簡稱為孩子。 9 一個結點稱為

50、其后繼結點（即孩子結點）的 _ 。 10 一個結點的子樹中的任一結點都稱為該結點的 _ 。 11 從根到該結點所經分支上的所有結點稱為該結點的 _ 。 12 具有 _ 的結點互稱為兄弟結點， 簡稱為兄弟。 19.權值為 l ,2,6,8的四個結點構成的哈夫曼樹的帶權路徑長度是 （ ）。 A18 B 28 C 19 D 20實現任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構, 二叉村采用（ ）存儲結構。 A.二叉鏈表 C.三叉鏈表 21 對一個滿二叉樹, A. n= m 1 B 29 最佳方案B D m個樹葉, m+1=2n 23 具有五層結點的二叉平衡樹至少有（ A 10 B 12 C 24

51、設 n, 是（ ）。 A. n在m右方 B C. n在m左方 D 25 線索二又樹是一種（ ）結構 A 邏輯 B 邏輯和物理 廣義表存儲結構 順序存儲結構 k 個分枝結點, n 個結點, C . m= k-1 ）個結點 15 D D 則（ ）。 n=2k+1 m為一棵二叉樹上的二個結點，在中序遍歷時， 17 n在m.n是m祖先 n 是 m 子孫 C.物理 線性 每一層上從左到右 26 將一棵有 100 個結點的完全二又樹從根這一層開始, 依次對結點進行編號,根結點的編號為 1,則編號為 49的結點的左孩子編號為 （） A 98 B 99 C 50 D 48 23 / 51 13 從根結點開始定

52、義，根為 _ 層，根的孩子為 _ 層， 依次往下類推，若某結點在第 k 層，則其子樹的根就在 _ 層。 14 其雙親在同一層次上的結點互稱為 _ 。 15 樹中結點的 _ 稱為樹的深度，又稱為樹的高度。 16 如果樹中各結點的各子樹從左至右是有序排列，不可互換的，則稱 該樹為 。 17 如果樹中各結點的各子樹無排列順序，即可以互換位置，則稱為該 樹為 。 18 . n(n 0)棵互不相交的樹的集合稱為 _ 。 19 二又樹( Binary Tree )是結點的有限集合，這個集合或者是空， 或者是由一個根結點和 _ 的稱為 _ 和 _ 的二 叉樹構成。 20 .二叉樹第 i 層上最多有 _ 個結

53、點。 21 .深度為k的二又樹最多有 _ 結點(k I)。 22 .在任意二叉樹中，葉子結點的數目 (即度為 0的結點數 )等于度為 2 的結點數 _ 。 23 .一棵深度為 k 且具有 2k-1 個結點的二叉樹稱為 _ 。這類 二叉樹的特點是，二叉樹中每一層結點的個數都是 _ 的個數。 24 . _ 是那種在一棵二叉樹中，除最后一層外，若其余層都是 滿的，并且最后一層或者是滿的，或者所缺少的結點都在右邊。 25 .具有 n 個結點的完全二叉樹的深度是 _ 。 26 .對于一棵有 n 個結點的完全二叉樹的結點進行編號(自上而下，自 左至右)，則對任一結點i (I i I ，則其雙親 Paren

54、t(i) 的序號是結點 _ ;如果2i n,則結點i的左孩子Lchild(BT, , i )是 _ , 否則結點i無左孩子(結點i必為葉子結點)；如果2i +1 lchild=nil)&(p-rchild=nil) 52. 69 53. 99 54. 2 55. 36 56. 98 5 中序 三、判斷題 1完全二叉樹的某個結點若無左孩子，則它必然是葉結點。 （ ） 2存在這樣一種二叉樹，對它采用任何次序的遍歷結果相同。 （ ） 3. 度為二的樹稱為二叉樹。（X ） 4二叉樹中不存在度大于 2 的結點。（ ） 5. 當二叉樹中某個結點只有一棵子樹的時候，無左右子樹之分。 （X ） 6. 任何一棵

55、二叉樹都可以不用棧實現前序線索樹的前序遍歷。 （ ） 7. 哈夫曼編碼是一種前綴編碼，不允許出現兩個字符編碼相同的情況。 （） 8. 完全二叉樹某結點有右子樹，則必然有左子樹。 （ ） 9. 前序遍歷一棵二叉樹的結點就可以得到排好序的結點序列。 （X ） 10. 將一棵擁有子樹的樹轉換為二叉樹后， 根結點可能沒有左子樹。（X ） 11. 根據二叉樹的前序遍歷和中序遍歷可以得到二又樹的后序遍歷。 （ ） 12. 哈夫曼樹是帶權路徑長度最短的二叉樹。 （ ） 28 / 51 13. 哈夫曼樹上權值較大的結點離根較遠。 （X ） 14. 中序遍歷森林與后序遍歷與森林相對應的二叉樹結果相同。 （X ）

56、 15. 在二叉樹中，具有一個孩子的結點，在中序遍歷序列中，沒有后繼子女 結點。 16先序遍歷森林與先序遍歷相對應的二叉樹結果不同。 (X ) 17若一棵二叉樹的任一非葉子結點的度為 2，則該二叉樹為滿二叉樹 (X ) 18二叉樹只能采用二叉鏈表來存儲。 (X ) 19給定結點數的平衡二叉樹的高度是惟一的。 (X ) 1. 正確：根據完全二叉樹定義可以知道，若完全二叉樹無左孩子，則它必 然無右孩子。 2. 正確：二叉樹只有一個結點的時候。 3. 錯誤：二叉樹子樹還有左右次序之分。 4. 正確。 5. 錯誤。 6. 正確。 7. 正確。 8. 正確：根據完全二叉樹定義可以知道， 9. 錯誤：中序

57、遍歷一棵二叉樹的結點就可以得到排好序的結點序列。 10. 錯誤：將一棵擁有子樹的樹轉換為二叉樹后，根結點必然有左子樹。 11. 正確。 12. 正確。 13. 錯誤：哈夫曼樹的路徑上權值較大的結點離根較近。 14. 錯誤：后序遍歷森林與中序遍歷與森林相對應的二叉樹結果相同。 15. 錯誤：在二叉樹中，具有一個左孩子的結點，在中序遍歷序列中，沒 有后繼子女結點。 16. 錯誤：前序遍歷森林與前序遍歷與森林相對應的二叉樹結果相同。 17. 錯誤：任一非葉子結點的度為 2 也不能保證滿足滿足滿二叉樹的定義 18. 錯誤：也可以采用順序存儲和三叉鏈表等形式進行表示。 19. 錯誤：給定結點數的平衡二叉

58、樹的高度不一定是惟一的。 四、綜合題 1 一棵樹表達成如下形式： 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為結點集合，R為邊的集合。請根據以上內容回答以下問題： (1) 畫出這棵樹。 (2) 該樹的根結點是哪一個？ (3) 哪些是葉子結點？ (4) F 結點的雙親是誰？ (5) F 結點的祖先是哪些？ (6) F 結點的孩子是哪些？ (7) F 結點的兄弟是哪些？ 29 / 51 (8) F 結點的堂兄弟是哪些？ (9) F 結點的度是多少？ (

59、10) F 結點的層次是多少？30 / 51 (11) D結點的子孫有哪些？ (12) 以結點D為根的子樹度是多少？ (13) 以結點D為根的子樹層是多少？ (14) 該樹的層是多少？ (15) 該樹的度是多少？ 2. 畫出圖6-1中樹的二叉樹表示形式。 (a) (b) ( c) 圖6-1 3. 已知某二叉樹的先序遍歷的結果是： A, B, D, QC E，H, L，I，K, M F和J，它的中序遍歷的結果是： QD B, A, L, H, E, K, LM C, F和J，請畫 出這棵二叉樹，并且寫出該二叉樹后序通歷的結果。 4. 寫一個將一棵二叉樹復制給另一棵二又樹的算法。 5. 已知一個二

60、叉樹用二叉鏈表表示，其根指針為 t，請寫一個算法，從根 結點開始按層次通歷該二叉樹，同層的結點接從左到右的次序進行訪問。 6. 已知一棵二叉樹的先序遍歷序列和中序遍歷序列，請寫出根據二又樹先 序遍歷序列和中序遍歷序列構造一棵二叉樹的算法。 7. 假設一棵哈夫曼樹共有nO個葉子結點，試證明樹中共有 2no-l個結點。 8 .假設通信用的報文由9個字母A、B、C、D E、F、G H和I構成，它們 出現的頻率分別是：10、20、5、15、8、2、3、7和30。請用這9個字母出現 得頻率作為權值求： (l )設計一棵哈夫曼樹。 (2) 計算其帶權路徑長度 WPLSo (3) 寫出每個字符的哈夫曼編碼。

61、 1. (1) 該樹的圖形如圖B-1所示。 A K L M 圖B-1 (2) 該樹的根結點是Ao B C E F G I 31 / 51 (3) 葉子結點是：E、K、L、M G H N 0和J (4) F結點的雙親是Bo (5) F結點的祖先是A和Bo32 / 51 (6) F結點的孩子是K、L和M (7) F結點的兄弟是E。 (8) F結點的堂兄弟是G H、I和J。 (9) F結點的度是3。 (10) F結點的層是3。 (11) D結點的子孫有I、N和0。 (12) 以結點D為根的子樹度為3。 (13) 以結點D為根的子樹層為3。 (14) 該樹的層是4。 (15) 該樹的度是3。 2. 本

62、題樹對應的二叉樹形式如圖 B-2所示 圖B-2 3. 該二叉樹的圖形表示如圖 B-3所示，該二叉樹后序遍歷的結果是：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 *CreateBiT

63、ree() /* 用遞歸方法建立一棵二叉樹 */ 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); /* 生成新結點 */ t-data=c; /* 為數據域賦值 */ t-lchild=CreateBiTree(); t-rchild=CreateBiTree(); return(t); /*CreateBiTree()*/ /* 遞歸創(chuàng)建左子樹 *

64、/ /* 遞歸創(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. 將一棵二叉樹復制給另一棵二叉樹的算法如下所示： define NULL 0 typede

65、f struct btnode elemtype data; struct btnode *lchild, *rchild; bitnode, *bitree; 35 / 51 bitree *CopyTree( bitnode *p ) /* 復制一棵二叉樹 */ 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

66、); /*CopyTree*/ 6.可以使用隊列Q來保存遍歷過程中的各個結點，隊列可以設定為bitree 類型的指針數組，下標從 1 開始，同層結點按從左到右的順序存放。算法如下： define NULL 0 define MAXSIZE 100 typedef char elemtype; typedef struct btnode elemtype data; struct btnode *lchild, *rchild; bitnode, *bitree; void LevelOrderTraverse( bitree t ) /* 使用隊列對二叉樹進行按層序遍歷 */ bitree *QMAXSIZE; /*隊列Q是一個指向bitree類型的指針數組，下標從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