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