【正文】 的表頭可以是廣義表，也可以是單個元素。A. 15 B. 16 C. 17 D. 473. 假定一棵三叉樹的結點數(shù)為50，則它的最小高度為（ ）。A. 中序 B. 前序 C. 后序 D. 層次序11. 欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（ ）存儲結構。 （　）4. 哈夫曼樹的總結點個數(shù)（多于1時）不能為偶數(shù)。2. 設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非終端結點，則B中右指針域為空的結點有_______個。10. 設高度為h的二叉樹中只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為____。18. 線索是指___________________________________________。10．給定一組權值（5，9，11，2，7，16），試設計相應的哈夫曼樹。2. 解答：度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹不能交換。10. 解答：構造而成的哈夫曼樹如圖517所示。 A．健壯性和可讀性 B．并行性 C．正確性 D．時空復雜度2. 2. HL=p。 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（ ）。二、 二、A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為( )。 采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。 HLnext=p。6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結點的二叉樹。習題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，4，6，1，1，2，A，F(xiàn)，G2. n+13. 完全， ，最大，n4. 555. 中序6. 2n，n1，n+17. n2+18. 2k1，2k1，2k19. 510. 2h111. 單支樹，完全二叉樹12. 2i，2i+1，i/2（或?i/2?）13. 2n，n1，n+114. 帶權路徑長度最小15. 結點數(shù)為0，只有一個根結點的樹16. 二叉鏈表，三叉鏈表17. 雙親結點18. 指向結點前驅和后繼信息的指針19. 1，RChild20. 孩子表示法，雙親表示法，長子兄弟表示法四、應用題1. 解答：根據給定的邊確定的樹如圖515所示。8. 假設一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二叉樹的后序遍歷序列。16. 二叉樹的鏈式存儲結構有______________和_______________兩種。8. 一棵深度為k的滿二叉樹的結點總數(shù)為_______，一棵深度為k的完全二叉樹的結點總數(shù)的最小值為_____，最大值為______。 （?。?0. 樹的子樹是無序的。 （?。?. 二叉樹的前序遍歷中，任意結點均處在其子女結點之前。A. plc=NULL B. pltag=1 C. pltag=1 且plc=NULL D. 以上都不對9. 設n , m 為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是（ ）。（ ）習題4參考答案一、單項選擇題1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 二、填空題1. 線性結構，順序結構，以行為主序，以列為主序2. in+j個元素位置3. 5，34.（（0，2，2），（1，0，3），（2，2，1），（2，3，5））5. n(n+1)/26. e7. 418. head(head(tail(Ls)))9.（d c +1）（d c +1）（d c +1）10. 913三、判斷題1. 2.√ 3.√ 4.√ 5. 6. 7.√ 8. 9. 10.√ 11.√ 12.√ 13. 14.√ 15.√ 習題5一、單項選擇題1. 在一棵度為3的樹中，度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點數(shù)為2個，則度為0的結點數(shù)為（ ）個。（ ）8. 距陣中的數(shù)據元素可以是不同的數(shù)據類型。（其中：c1≤d1,c2≤d2,c3≤d3）10. 數(shù)組A[1…10，2…6，2…8]以行優(yōu)先的順序存儲，設第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。2. 對于一個二維數(shù)組A[m][n]，若按行序為主序存儲，則任一元素A[i][j]相對于A[0][0]的地址為______________。 10. 假定在數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內，存放該數(shù)組至少需要的單元數(shù)為（ ）。 +[i*n+j1]*k +[(i1)*n+j1]*k+[(j1)*n+i1]*k +[j*n+i1]*k2. 已知二維數(shù)組A1010中，元素a20的地址為560，每個元素占4個字節(jié)，則元素a10的地址為（ ）。 while((pt!=NULL)amp。j++)r[st+j]=r[j]。習題3參考答案一、單項選擇題1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空題1. 固定長度，設置長度指針2. 兩個串的長度相等，對應位置的字符相等3. “BCDEDE”4. 含n個字符的有限序列 （n≥0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設計題1．算法描述為：int delete(r,s,t,m) //從串的第m個字符以后刪除長度為t的子串char r[ ]。 二、填空題1. 計算機軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是___________，第二種是___________________。 2. 一個子串在包含它的主串中的位置是指（ ）。 i0 amp。}}（2）刪除（即出隊）算法：delete(LinkList *rear){ //設循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) //空隊 printf(underflow\n)。p=qnext。 qnext=p。 p=headnext。amp。 struct node *next,*prior。 q=head?！?p=L。j++。 q=qnext。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。6．共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7．在隊列的順序存儲結構中，設隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大?。閙axnum。2．線性表具有兩種存儲結構即順序存儲結構和鏈接存儲結構。5. 已知線性表的元素按遞增順序排列，并以帶頭結點的單鏈表作存儲結構。 qnext=NULL。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無頭結點的單鏈表LinkList *q,*p。 13. 對于一個棧作進棧運算時，應先判別棧是否為_______，作退棧運算時，應先判別棧是否為_______，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_______。6. 在雙向鏈表中，每個結點含有兩個指針域，一個指向_______結點，另一個指向_______結點。 18. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為________。A．top不變 B．top=0 C．top D．top++17. 向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執(zhí)行______。D．存在這樣的線性表：表中各結點都沒有直接前趨和直接后繼。A．ni B．ni+l C．ni1 D．i8. 在一個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執(zhí)行A．snext=pnext。 pnextprior=s。 pnext=s。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以 4. 從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較________個元素結點。A[i]!=k))j。i++)for(j=0。for(i=1。三、求下列程序段的時間復雜度。jn。i=s=0。7. 線性結構中元素之間存在__________________關系；樹型結構中元素之間存在__________________關系；圖型結構中元素之間存在__________________關系。 9. 數(shù)據結構只是研究數(shù)據的邏輯結構和物理結構，這種觀點（ ）。 i=n。!( Trchild)) n++。} （8分）平均時間復雜度：（2分）設元素個數(shù)記為n，則平均時間復雜度為：2（10分）void pop(Stack amp。 for(i=0。root,int amp。 其中結點定義如下： top typedef struct { Elemtype *base。7． 已知有如下的有向網： 2 5 36 4 10 6 1 2 2 AEBDC求頂點A到其它各頂點的最短路徑（采用Dijkstra算法，要有過程）。（5分）4． 已知一維數(shù)組中的數(shù)據為（18,12,25,53,18）, 試寫出插入排序（升序）過程。6．已知一有向無環(huán)圖如下： BACDFEG 任意寫出二種拓撲排序序列： 、 。 （C）、p=next。for(i=n1；i=0；i) for(j=0；ji；j++) S； (A)、n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法適用于（ ）。 （A）、k1 （B）、k （C）、k1和k （D）、1至k6．具有60個結點的二叉樹，其葉子結點有12個，則度過1的結點數(shù)為（ ）（A）、11 （B）、13 （C）、48 （D）、377．圖的DepthFirst Search(DFS)遍歷思想實際上是二叉樹（ ）遍歷方法的推廣。 Qnext=pnext。(6分)(1) 構造HASH表。（2）分別畫出以A為起點的DFS生成樹和BFS生成樹。 //當前長度（存儲元素個數(shù)） }SqList。設計算法，將棧頂元素出棧并存入e中． base3．設二叉鏈樹的類型定義如下： typedef int Elemtype。 qnext=p。 if(i=Llength) return ERROR。 。}}習題1一、單項選擇題1. 數(shù)據結構是指（ ）。 j++)x++。2. 數(shù)據的邏輯結構有四種基本形態(tài)，分別是________________、__________________、__________________和______________