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