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