1、習題1一、單項選擇題1. 數據結構是指（ a ）。a.數據元素的組織形式b.數據類型c.數據存儲結構 d.數據定義2. 數據在計算機存儲器內表示時，物理地址與邏輯地址不相同的，稱之為（ c ）。a.存儲結構b.邏輯結構 c.鏈式存儲結構d.順序存儲結構3. 樹形結構是數據元素之間存在一種（d ）。a.一對一關系b.多對多關系 c.多對一關系d.一對多關系4. 設語句x+的時間是單位時間，則以下語句的時間復雜度為（ b ）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;a.o(1)b.o()c.o(n)d.o()5. 算法分析的目的是（1.c），算法分析的兩個主要方面

2、是（2.a）。（1） a.找出數據結構的合理性 b.研究算法中的輸入和輸出關系c.分析算法的效率以求改進 d.分析算法的易懂性和文檔性（2） a.空間復雜度和時間復雜度 b.正確性和簡明性c.可讀性和文檔性 d.數據復雜性和程序復雜性6. 計算機算法指的是（1.c），它具備輸入，輸出和（2.b）等五個特性。（1） a.計算方法 b.排序方法c.解決問題的有限運算序列 d.調度方法（2） a.可行性，可移植性和可擴充性 b.可行性，確定性和有窮性c.確定性，有窮性和穩定性 d.易讀性，穩定性和安全性7. 數據在計算機內有鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要（ b

3、 ）。a.低 b.高 c.相同d.不好說8. 數據結構作為一門獨立的課程出現是在（ d）年。a.1946b.1953c.1964d.19689. 數據結構只是研究數據的邏輯結構和物理結構，這種觀點（ b ）。a.正確b.錯誤c.前半句對，后半句錯d.前半句錯，后半句對10. 計算機內部數據處理的基本單位是（ b ）。a.數據 b.數據元素c.數據項d.數據庫二、填空題 1. 數據結構按邏輯結構可分為兩大類，分別是_線性結構_和_非線性結構_。2. 數據的邏輯結構有四種基本形態，分別是_集合_、_線性_、_樹_和_圖_。3. 線性結構反映結點間的邏輯關系是_一對一_的，非線性結構反映結點間的邏輯

4、關系是_一對多或多對多_的。4. 一個算法的效率可分為_時間_效率和_空間_效率。5. 在樹型結構中，樹根結點沒有_前趨_結點，其余每個結點的有且只有_一_個前趨驅結點；葉子結點沒有_后趨_結點；其余每個結點的后續結點可以_多_。6. 在圖型結構中，每個結點的前趨結點數和后續結點數可以_有多個_。7. 線性結構中元素之間存在_一對一_關系；樹型結構中元素之間存在_一對多_關系；圖型結構中元素之間存在_多對多_關系。8. 下面程序段的時間復雜度是_（）_。for(i=0;in;i+)for(j=0;jn;j+)aij=0;9. 下面程序段的時間復雜度是_（）_。i=s=0;while(sn) i

5、+; s+=i;10. 下面程序段的時間復雜度是_（）_。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=bij;sum=s;11. 下面程序段的時間復雜度是_（）_。i=1;while(i=n)i=i*3;12. 衡量算法正確性的標準通常是_程序對于精心設計的典型合法數據輸入能得出符合要求的結果_。13. 算法時間復雜度的分析通常有兩種方法，即_事后統計_和_事前估計_的方法，通常我們對算法求時間復雜度時，采用后一種方法。三、求下列程序段的時間復雜度。1. x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;（）2. x=0;for(i=1;in

6、;i+)for(j=1;j=n-i;j+) x+;（）3. int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+) cij=0;for(k=0;k=0)&ai!=k)j-;return (i);（）5. fact(n) if(n=1) return (1); else return (n*fact(n-1);（） 習題2一、單項選擇題 1. 線性表是_。a一個有限序列，可以為空b一個有限序列，不可以為空c一個無限序列，可以為空d一個無限序列，不可以為空2. 在一個長度為n的順序表中刪除第i個元素(0=inext=s; s-prior=p; p-next-prior=s;

7、 s-next=p-next;b s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;c p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;d s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 6. 設單鏈表中指針p指向結點m，若要刪除m之后的結點（若存在），則需修改指針的操作為_。ap-next=p-next-next;bp=p-next;cp=p-next-next; dp-next=p; 7. 在一個長度為n的順序表中向第i個元素(0

8、 inext=p-next; p-next=sbq-next=s; s-next=pcp-next=s-next; s-next=pdp-next=s; s-next=q9. 以下關于線性表的說法不正確的是_c_。 a線性表中的數據元素可以是數字、字符、記錄等不同類型。b線性表中包含的數據元素個數不是任意的。c線性表中的每個結點都有且只有一個直接前趨和直接后繼。d存在這樣的線性表：表中各結點都沒有直接前趨和直接后繼。10. 線性表的順序存儲結構是一種_a_的存儲結構。 a隨機存取b順序存取c索引存取d散列存取11. 在順序表中，只要知道_d_，就可在相同時間內求出任一結點的存儲地址。a基地址b

9、結點大小 c向量大小 d基地址和結點大小12. 在等概率情況下，順序表的插入操作要移動_b_結點。 a全部 b一半 c三分之一 d四分之一13. 在_c_運算中，使用順序表比鏈表好。 a插入 b刪除 c根據序號查找 d根據元素值查找14. 在一個具有n個結點的有序單鏈表中插入一個新結點并保持該表有序的時間復雜度是_b_。 ao(1) bo(n) co(n2) do(log2n)15. 設有一個棧，元素的進棧次序為a, b, c, d, e,下列是不可能的出棧序列_c_。aa, b, c, d, e bb, c, d, e, ace, a, b, c, d de, d, c, b, a 16.

10、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為_c_。atop不變 btop=0 ctop- dtop+17. 向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執行_b_。ahs-next=s; bs-next=hs; hs=s;cs-next=hs-next;hs-next=s; ds-next=hs; hs=hs-next; 18. 在具有n個單元的順序存儲的循環隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為_d_。arearn= = front b（front+l）n= = rearcre

11、arn -1= = front d(rear+l)n= = front 19. 在具有n個單元的順序存儲的循環隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為_c_。arearn= = front bfront+l= rearcrear= = front d(rear+l)n= front20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為_。afront=front-next brear=rear-nextcrear=front-next dfront=rear-next二、填空題 1. 線性表是一種典型的_線性_結構。2.

12、 在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移_個元素。3. 順序表中邏輯上相鄰的元素的物理位置_相鄰_。4. 要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_前移_一個位置，移動過程是從_前_向_后_依次移動每一個元素。5. 在線性表的順序存儲中，元素之間的邏輯關系是通過_物理存儲位置_決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過_鏈域的指針值_決定的。6. 在雙向鏈表中，每個結點含有兩個指針域，一個指向_前趨_結點，另一個指向_后繼_結點。7. 當對一個線性表經常進行存取操作，而很少進行插入和刪除操作時，則采用_順序_存儲結構為宜。相反，當經常進行的是

13、插入和刪除操作時，則采用_鏈接_存儲結構為宜。8. 順序表中邏輯上相鄰的元素，物理位置_一定_相鄰，單鏈表中邏輯上相鄰的元素，物理位置_不一定_相鄰。9. 線性表、棧和隊列都是_線性_結構，可以在線性表的_任何_位置插入和刪除元素；對于棧只能在_棧頂_位置插入和刪除元素；對于隊列只能在_隊尾_位置插入元素和在_隊頭_位置刪除元素。10. 根據線性表的鏈式存儲結構中每個結點所含指針的個數，鏈表可分為_單鏈表_和_雙鏈表_；而根據指針的聯接方式，鏈表又可分為_非循環鏈表_和_循環鏈表_。11. 在單鏈表中設置頭結點的作用是_使空鏈表和非空鏈表統一，算法處理一致_。12. 對于一個具有n個結點的單鏈

14、表，在已知的結點p后插入一個新結點的時間復雜度為_（）_，在給定值為x的結點后插入一個新結點的時間復雜度為_（）_。 13. 對于一個棧作進棧運算時，應先判別棧是否為_棧滿_，作退棧運算時，應先判別棧是否為_?？誣，當棧中元素為m時，作進棧運算時發生上溢，則說明棧的可用最大容量為_。為了增加內存空間的利用率和減少發生上溢的可能性，由兩個棧共享一片連續的內存空間時，應將兩棧的_棧底_分別設在這片內存空間的兩端，這樣只有當_兩個棧的棧頂在?？臻g的某一位置相遇_時才產生上溢。14. 設有一空棧，現有輸入序列1，2，3，4，5，經過push, push, pop, push, pop, push, p

15、ush后，輸出序列是_，_。15. 無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復雜度均相同為_（）_。 習題3一、單項選擇題1. 空串與空格字符組成的串的區別在于（b ）。a.沒有區別 b.兩串的長度不相等c.兩串的長度相等d.兩串包含的字符不相同2. 一個子串在包含它的主串中的位置是指（ d ）。a.子串的最后那個字符在主串中的位置b.子串的最后那個字符在主串中首次出現的位置c.子串的第一個字符在主串中的位置d.子串的第一個字符在主串中首次出現的位置3. 下面的說法中，只有（ c ）是正確的。a.字符串的長度是指串中包含的字母的個數b.字符串的長度是指串中包含的不同

16、字符的個數c.若t包含在s中，則t一定是s的一個子串d.一個字符串不能說是其自身的一個子串4. 兩個字符串相等的條件是（ d ）。a.兩串的長度相等 b.兩串包含的字符相同c.兩串的長度相等，并且兩串包含的字符相同d.兩串的長度相等，并且對應位置上的字符相同5. 若substr（s，i，k）表示求s中從第i個字符開始的連續k個字符組成的子串的操作，則對于s=“beijingnanjing”，substr（s，4，5）=（ b ）。a. “ijing”b. “jing” c. “ingna”d. “ingn”6. 若index（s，t）表示求t在s中的位置的操作，則對于s=“beijingnan

17、jing”，t=“jing”，index（s，t）=（ c ）。a.2 b.3 c.4 d.57. 若replace（s，s1，s2）表示用字符串s2替換字符串s中的子串s1的操作，則對于s=“beijingnanjing”，s1=“beijing”，s2=“shanghai”，replace（s，s1，s2）=（ b ）。a. “nanjingshanghai” b. “nanjingnanjing”c. “shanghainanjing” d. “shanghainanjing”8. 在長度為n的字符串s的第i個位置插入另外一個字符串，i的合法值應該是（ c ）。a.i0 b. in c.

18、1in d.1in+19. 字符串采用結點大小為1的鏈表作為其存儲結構，是指（ d ）。a.鏈表的長度為1b.鏈表中只存放1個字符c.鏈表的每個鏈結點的數據域中不僅只存放了一個字符d.鏈表的每個鏈結點的數據域中只存放了一個字符二、填空題1. 計算機軟件系統中，有兩種處理字符串長度的方法：一種是_固定長度_，第二種是_設置長度指針_。2. 兩個字符串相等的充要條件是_兩個串的長度相等_和_對應位置的字符相等_。3. 設字符串s1= “abcdef”，s2= “pqrs”，則運算s=concat（sub（s1，2，len（s2），sub（s1，len（s2），2）后的串值為_。4. 串是指_含個字

19、符的有限序列（）_。5. 空串是指_不含任何字符的串_，空格串是指_僅含空格字符的字符串_。 習題4一、單項選擇題1. 設二維數組a0m-10n-1按行優先順序存儲在內存中，第一個元素的地址為p，每個元素占k個字節，則元素aij的地址為（ a ）。a.p +i*n+j-1*kb.p+(i-1)*n+j-1*kc.p+(j-1)*n+i-1*kd.p+j*n+i-1*k2. 已知二維數組a1010中，元素a20的地址為560，每個元素占4個字節，則元素a10的地址為（ a ）。a.520b.522c.524d.5183. 若數組a0m0n按列優先順序存儲，則aij地址為（ a ）。a.loc(a

20、00)+j*m+i b. loc(a00)+j*n+ic.loc(a00)+(j-1)*n+i-1 d. loc(a00)+(j-1)*m+i-14. 若下三角矩陣ann，按列順序壓縮存儲在數組sa0(n+1)n/2中，則非零元素aij的地址為（ b ）。（設每個元素占d個字節）a. (j-1)*n-+i-1*db. (j-1)*n-+i*dc(j-1)*n-+i+1*dd(j-1)*n-+i-2*d5. 設有廣義表d=(a,b,d)，其長度為（b ），深度為（ a ）。a.無窮大 b.3c.2 d.56. 廣義表a=（a），則表尾為（ c ）。a.a b.( )c.空表 d.(a)7. 廣義

21、表a=(x,(a,b),(x,(a,b),y)，則運算head(head(tail(a)的結果為（ a ）。a.x b.(a,b) c.(x,(a,b) d.a8. 下列廣義表用圖來表示時，分支結點最多的是（ a ）。a.l=(x,(a,b),(x,(a,b),y)b.a=(s,(a,b)c.b=(x,(a,b),y)d.d=(a,b),(c,(a,b),d)9. 通常對數組進行的兩種基本操作是（ c ）。a.建立與刪除b.索引和修改 c.查找和修改 d.查找與索引10. 假定在數組a中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址sa開始連續存放在存儲器內，存放該

22、數組至少需要的單元數為（ c ）。a.80b.100c.240d.27011. 數組a中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址sa開始連續存放在存儲器內，該數組按行存放時，元素a85的起始地址為（ c ）。a.sa+141b.sa+144c.sa+222d.sa+22512. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ c ）。a.二維數組和三維數組 b.三元組和散列c.三元組和十字鏈表 d.散列和十字鏈表13. 若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算，這種觀點（ b ）。a.正確b.不正確14. 一個廣

23、義表的表頭總是一個（ d ）。a.廣義表b.元素c.空表d.元素或廣義表15. 一個廣義表的表尾總是一個（ a ）。a.廣義表b.元素c.空表 d.元素或廣義表16. 數組就是矩陣，矩陣就是數組，這種說法（ b ）。a.正確 b.錯誤 c.前句對，后句錯 d.后句對二、填空題1. 一維數組的邏輯結構是_線性結構_，存儲結構是_順序結構_；對于二維或多維數組，分為_以行為主_和_以列為主_兩種不同的存儲方式。2. 對于一個二維數組amn，若按行序為主序存儲，則任一元素aij相對于a00的地址為_個元素_。3. 一個廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長度為_，深度為_

24、。4. 一個稀疏矩陣為 ，則對應的三元組線性表為_（，），（，），（，），（，）_。5. 一個nn的對稱矩陣，如果以行為主序或以列為主序存入內存，則其容量為_（）_。6. 已知廣義表a=(a,b,c),(d,e,f)，則運算head(tail(tail(a)=_。7. 設有一個10階的對稱矩陣a，采用壓縮存儲方式以行序為主序存儲，a為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a的地址為_。8. 已知廣義表ls=(a,(b,c,d),e)，運用head和tail函數取出ls中的原子b的運算是_（）_。9. 三維數組rc1d1,c2d2,c3d3共含有_（）（）（）_個元素。（其

25、中：c1d1,c2d2,c3d3）10. 數組a110，-26，28以行優先的順序存儲，設第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素a5，0，7的存儲地址為_。三、判斷題1. 數組可看作基本線性表的一種推廣，因此與線性表一樣，可以對它進行插入、刪除等操作。（ ）2. 多維數組可以看作數據元素也是基本線性表的基本線性表。（ ）3. 以行為主序或以列為主序對于多維數組的存儲沒有影響。（ ）4. 對于不同的特殊矩陣應該采用不同的存儲方式。（ ）5. 采用壓縮存儲之后，下三角矩陣的存儲空間可以節約一半。（ ）6. 在一般情況下，采用壓縮存儲之后，對稱矩陣是所有特殊矩陣中存儲空

26、間節約最多的。（ ）7. 矩陣不僅是表示多維數組，而且是表示圖的重要工具。（ ）8. 距陣中的數據元素可以是不同的數據類型。（ ）9. 矩陣中的行列數往往是不相等的。（ ）10. 廣義表的表頭可以是廣義表，也可以是單個元素。（ ）11. 廣義表的表尾一定是一個廣義表。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）13. 廣義表不能遞歸定義。（ ）14. 廣義表實際上是基本線性表的推廣。（ ）15. 廣義表的組成元素可以是不同形式的元素。（ ）習題5一、單項選擇題1. 在一棵度為3的樹中，度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（ c ）

27、個。a. 4b. 5c. 6d. 72. 假設在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為（ b）個。a. 15b. 16c. 17d. 473. 假定一棵三叉樹的結點數為50，則它的最小高度為（ c ）。a. 3 b. 4c. 5d. 64. 在一棵二叉樹上第4層的結點數最多為（ d ）。a. 2b. 4 c. 6d. 85. 用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數組中r1.n，結點ri若有左孩子，其左孩子的編號為結點（ b ）。a. r2i+1b. r2ic. ri/2d. r2i-16. 由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，

28、它的帶權路徑長度為（ d ）。a. 24b. 48c. 72d. 537. 線索二叉樹是一種（ c ）結構。a. 邏輯 b. 邏輯和存儲c. 物理 d. 線性8. 線索二叉樹中，結點p沒有左子樹的充要條件是（ b ）。a. p-lc=null b. p-ltag=1 c. p-ltag=1 且p-lc=null d. 以上都不對9. 設n , m 為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是（ b ）。 a. n在m右方 b. n在m 左方 c. n是m的祖先 d. n是m的子孫10. 如果f是由有序樹t轉換而來的二叉樹，那么t中結點的前序就是f中結點的（ b ）。a. 中序b.

29、 前序c. 后序d. 層次序11. 欲實現任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（ a ）存儲結構。a. 三叉鏈表b. 廣義表c. 二叉鏈表 d. 順序12. 下面敘述正確的是（ d ）。a. 二叉樹是特殊的樹b. 二叉樹等價于度為2的樹c. 完全二叉樹必為滿二叉樹d. 二叉樹的左右子樹有次序之分13. 任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序（ a ）。a. 不發生改變 b. 發生改變c. 不能確定 d. 以上都不對14. 已知一棵完全二叉樹的結點總數為9個，則最后一層的結點數為（ b ）。a. 1 b. 2c. 3d. 415. 根據先序序

30、列abdc和中序序列dbac確定對應的二叉樹，該二叉樹（ a ）。a. 是完全二叉樹 b. 不是完全二叉樹c. 是滿二叉樹d. 不是滿二叉樹二、判斷題1. 二叉樹中每個結點的度不能超過2，所以二叉樹是一種特殊的樹。（f）2. 二叉樹的前序遍歷中，任意結點均處在其子女結點之前。（t）3. 線索二叉樹是一種邏輯結構。（f）4. 哈夫曼樹的總結點個數（多于1時）不能為偶數。（t）5. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。（f）6. 樹的后序遍歷與其對應的二叉樹的后序遍歷序列相同。（t）7. 根據任意一種遍歷序列即可唯一確定對應的二叉樹。（t）8. 滿二叉樹也是完全二叉樹。（t）9.

31、哈夫曼樹一定是完全二叉樹。（f）10. 樹的子樹是無序的。（f）三、填空題1. 假定一棵樹的廣義表表示為a（b（e），c（f（h，i，j），g），d），則該樹的度為_3_，樹的深度為_4_，終端結點的個數為_6_，單分支結點的個數為_1_，雙分支結點的個數為_1_，三分支結點的個數為_2_，c結點的雙親結點為_a_，其孩子結點為_f_和_g_結點。2. 設f是一個森林，b是由f轉換得到的二叉樹，f中有n個非終端結點，則b中右指針域為空的結點有_n+1_個。3. 對于一個有n個結點的二叉樹，當它為一棵_完全_二叉樹時具有最小高度，即為_，當它為一棵單支樹具有_最大_高度，即為_。4. 由帶權為3

32、，9，6，2，5的5個葉子結點構成一棵哈夫曼樹，則帶權路徑長度為_。5. 在一棵二叉排序樹上按_中序_遍歷得到的結點序列是一個有序序列。6. 對于一棵具有n個結點的二叉樹，當進行鏈接存儲時，其二叉鏈表中的指針域的總數為_個，其中_個用于鏈接孩子結點，_個空閑著。7. 在一棵二叉樹中，度為0的結點個數為n0，度為2的結點個數為n2，則n0=_。8. 一棵深度為k的滿二叉樹的結點總數為_，一棵深度為k的完全二叉樹的結點總數的最小值為_（）_，最大值為_。9. 由三個結點構成的二叉樹，共有_種不同的形態。10. 設高度為h的二叉樹中只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為_。11

33、. 一棵含有n個結點的k叉樹，_形態達到最大深度，_形態達到最小深度。12. 對于一棵具有n個結點的二叉樹，若一個結點的編號為i(1in)，則它的左孩子結點的編號為_，右孩子結點的編號為_，雙親結點的編號為_。13. 對于一棵具有n個結點的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數為_個，其中_個用于鏈接孩子結點，_個空閑著。14. 哈夫曼樹是指_的二叉樹。15. 空樹是指_，最小的樹是指_。16. 二叉樹的鏈式存儲結構有_和_兩種。17. 三叉鏈表比二叉鏈表多一個指向_的指針域。18. 線索是指_。19. 線索鏈表中的rtag域值為_時，表示該結點無右孩子，此時_域為指向該結點后繼線索的

34、指針。20. 本節中我們學習的樹的存儲結構有_、_和_。四、應用題1. 已知一棵樹邊的集合為，請畫出這棵樹，并回答下列問題：（1）哪個是根結點？（2）哪些是葉子結點？（3）哪個是結點g的雙親？（4）哪些是結點g的祖先？（5）哪些是結點g的孩子？（6）哪些是結點e的孩子？（7）哪些是結點e的兄弟？哪些是結點f的兄弟？（8）結點b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結點c為根的子樹深度是多少？2. 一棵度為2的樹與一棵二叉樹有何區別。3. 試分別畫出具有3個結點的樹和二叉樹的所有不同形態？4. 已知用一維數組存放的一棵完全二叉樹：abcdefghijkl，寫出該二叉樹的先序、中

35、序和后序遍歷序列。5. 一棵深度為h的滿k叉樹有如下性質：第h層上的結點都是葉子結點，其余各層上每個結點都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對全部結點編號，回答下列問題：（1）各層的結點數目是多少？（2）編號為n的結點的父結點如果存在，編號是多少？（3）編號為n的結點的第i個孩子結點如果存在，編號是多少？（4）編號為n的結點有右兄弟的條件是什么？其右兄弟的編號是多少？6. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；（2）它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；7. 假設

36、一棵二叉樹的先序序列為ebadcfhgikj，中序序列為abcdefghijk，請寫出該二叉樹的后序遍歷序列。8. 假設一棵二叉樹的后序序列為dcegbfhkjia，中序序列為dcbgeahfijk，請寫出該二叉樹的后序遍歷序列。9. 給出如圖5-14所示的森林的先根、后根遍歷結點序列，然后畫出該森林對應的二叉樹。10給定一組權值（5，9，11，2，7，16），試設計相應的哈夫曼樹。abdefcghjiknoml圖5-14五、算法設計題1. 一棵具有n個結點的完全二叉樹以一維數組作為存儲結構，試設計一個對該完全二叉樹進行先序遍歷的算法。2. 給定一棵用二叉鏈表表示的二叉樹，其中的指針t指向根結

37、點，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結點按從左至右的次序訪問。3. 寫出在中序線索二叉樹中結點p的右子樹中插入一個結點s的算法。4. 給定一棵二叉樹，用二叉鏈表表示，其根指針為t，試寫出求該二叉樹中結點n的雙親結點的算法。若沒有結點n或者該結點沒有雙親結點，分別輸出相應的信息；若結點n有雙親，輸出其雙親的值。習題5參考答案一、單項選擇題1. c 2. b 3. c 4. d 5. b 6. d 7. c 8. b 9. b 10. b 11. a 12. d 13. a 14. b 15. a二、判斷題1. 2. 3. 4. 5. 6. 7. 8. 9. 10.三、填空題1. 3

38、，4，6，1，1，2，a，f，g2. n+13. 完全，最大，n4. 555. 中序6. 2n，n-1，n+17. n2+18. 2k-1，2k-1，2k-19. 510. 2h-111. 單支樹，完全二叉樹12. 2i，2i+1，i/2（或i/2）13. 2n，n-1，n+114. 帶權路徑長度最小15. 結點數為0，只有一個根結點的樹16. 二叉鏈表，三叉鏈表17. 雙親結點18. 指向結點前驅和后繼信息的指針19. 1，rchild20. 孩子表示法，雙親表示法，長子兄弟表示法四、應用題1. 解答：abcdegfhimnjki圖5-15根據給定的邊確定的樹如圖5-15所示。其中根結點為a

39、；葉子結點有：d、m、n、j、k、f、l；c是結點g的雙親；a、c是結點g的祖先；j、k是結點g的孩子；m、n是結點e的子孫；e是結點d的兄弟；g、h是結點f的兄弟；結點b和n的層次號分別是2和5；樹的深度為5。2. 解答：度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹不能交換。3. 解答：略4. 解答：先序序列：abdhiejkcflg中序序列：hdibjekalfcg后序序列：hidjkeblfgca5. 解答：（1）第i層上的結點數目是mi-1。（2）編號為n的結點的父結點如果存在，編號是(n-2)/m)+1。（3）編號為n的結點的第i個孩子結點

40、如果存在，編號是(n-1)*m+i+1。（4）編號為n的結點有右兄弟的條件是(n-1)%m0。其右兄弟的編號是n+1。6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結點的二叉樹。7. 解答：后序序列：acdbgjkihfe8. 解答：先序序列：abcdgeihfjk9. 解答：先根遍歷：abcdefghijklmno后根遍歷：bdefcahjigknoml森林轉換成二叉樹如圖5-16所示。10. 解答：構造而成的哈夫

41、曼樹如圖5-17所示。bgdchkeifjlmnoa圖5-1650 92030111614 7 7 2 5圖5-17五、算法設計題1. 解答：這個問題可以用遞歸算法，也可用非遞歸算法，下面給出的為非遞歸算法。假設該完全二叉樹的結點以層次為序，按照從上到下，同層從左到右順序編號，存放在一個一維數組r1.n中，且用一個有足夠大容量為maxlen的順序棧作輔助存儲，算法描述如下：preorder (r) /先序遍歷二叉樹rint rn; int root;sqstack *s; /s為一個指針棧，類型為seqstack，其中包含top域和數組datas-top= -1; /s棧置空root=1;wh

42、ile (roottop-1) while (roottop+;s-datas-top=root;root=2*root; if (s-top-1) /棧非空訪問，遍歷右子樹 root=s-datas-top*2+1; s-top-;2. 解答：考慮用一個順序隊que來保存遍歷過程中的各個結點，由于二叉樹以二叉鏈表存儲，所以可設que為一個指向數據類型為bitree的指針數組，最大容量為maxnum，下標從1開始，同層結點從左到右存放。算法中的front為隊頭指針，rear為隊尾指針。levelorder (bitree *t) /按層次遍歷二叉樹t bitree *quemaxnum;int

43、 rear,front;if (t!=null) front=0; /置空隊列rear=1;que1=t;do front=front%maxsize+1; /出隊 t=quefront; printf(t-data); if (t-lchild!=null) /左子樹的根結點入隊 rear=rear%maxsize+1; querear=t-lchild; if (t-rchild!=null) /右子樹的根結點入隊 rear=rear%maxsize+1; querear=t-rchild;while (rear= =front); /隊列為空時結束3. 解答：設該線索二叉樹類型為bithptr，包含5個域：lchild，ltag，data，rchild，rtag。insert(p, s) /將s結點作為p的右子樹插入bithrnode *p,*s; bithrnode *q;if (p-rtag= =1) /無右子樹，則有右線索 s-rchild=p-rchild;s-rtag=1;p-rchi