【正文】 對于一個(gè)長度為n的單鏈存儲的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_________，在表尾插入元素的時(shí)間復(fù)雜。 當(dāng)用長度為N的數(shù)組順序存儲一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。 隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。當(dāng)結(jié)點(diǎn)之間存在M對N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_____________________。 運(yùn)算題（每題 6 分，共24分）1. 1.二、 二、A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A．值 B．函數(shù) C．指針 D．引用8. 8. 采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ ）。 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6. pnext=HL。 p=HL。 HL=p。 HLnext=p。 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A．健壯性和可讀性 B．并行性 C．正確性 D．時(shí)空復(fù)雜度2. 2.10. 解答：構(gòu)造而成的哈夫曼樹如圖517所示。6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。（4）編號為n的結(jié)點(diǎn)有右兄弟的條件是(n1)%m≠0。（2）編號為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號是((n2)/m)+1。2. 解答：度為2的樹有兩個(gè)分支，但分支沒有左右之分；一棵二叉樹也有兩個(gè)分支，但有左右之分，左右子樹不能交換。習(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. 單支樹，完全二叉樹12. 2i，2i+1，i/2（或?i/2?）13. 2n，n1，n+114. 帶權(quán)路徑長度最小15. 結(jié)點(diǎn)數(shù)為0，只有一個(gè)根結(jié)點(diǎn)的樹16. 二叉鏈表，三叉鏈表17. 雙親結(jié)點(diǎn)18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 1，RChild20. 孩子表示法，雙親表示法，長子兄弟表示法四、應(yīng)用題1. 解答：根據(jù)給定的邊確定的樹如圖515所示。4. 給定一棵二叉樹，用二叉鏈表表示，其根指針為t，試寫出求該二叉樹中結(jié)點(diǎn)n的雙親結(jié)點(diǎn)的算法。2. 給定一棵用二叉鏈表表示的二叉樹，其中的指針t指向根結(jié)點(diǎn)，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結(jié)點(diǎn)按從左至右的次序訪問。10．給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計(jì)相應(yīng)的哈夫曼樹。8. 假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二叉樹的后序遍歷序列。3. 試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和二叉樹的所有不同形態(tài)？4. 已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。20. 本節(jié)中我們學(xué)習(xí)的樹的存儲結(jié)構(gòu)有_____________、___________和___________。18. 線索是指___________________________________________。16. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有______________和_______________兩種。14. 哈夫曼樹是指________________________________________________的二叉樹。12. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號為________，右孩子結(jié)點(diǎn)的編號為________，雙親結(jié)點(diǎn)的編號為________。10. 設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____。8. 一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_____，最大值為______。6. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時(shí)，其二叉鏈表中的指針域的總數(shù)為_______個(gè)，其中_______個(gè)用于鏈接孩子結(jié)點(diǎn)，_______個(gè)空閑著。4. 由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為___。2. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_______個(gè)。 （?。?0. 樹的子樹是無序的。 （?。?. 滿二叉樹也是完全二叉樹。 （?。?. 樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。 （?。?. 哈夫曼樹的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。 （　）2. 二叉樹的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。A. 1 B. 2 C. 3 D. 415. 根據(jù)先序序列ABDC和中序序列DBAC確定對應(yīng)的二叉樹，該二叉樹（ ）。A. 二叉樹是特殊的樹B. 二叉樹等價(jià)于度為2的樹C. 完全二叉樹必為滿二叉樹D. 二叉樹的左右子樹有次序之分13. 任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（ ）。A. 中序 B. 前序 C. 后序 D. 層次序11. 欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（ ）存儲結(jié)構(gòu)。A. plc=NULL B. pltag=1 C. pltag=1 且plc=NULL D. 以上都不對9. 設(shè)n , m 為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（ ）。A. 24 B. 48 C. 72 D. 537. 線索二叉樹是一種（ ）結(jié)構(gòu)。A. 2 B. 4 C. 6 D. 85. 用順序存儲的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號為結(jié)點(diǎn)（ ）。A. 15 B. 16 C. 17 D. 473. 假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（ ）。（ ）習(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. 線性結(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的樹中，度為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è)。（ ）14. 廣義表實(shí)際上是基本線性表的推廣。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）10. 廣義表的表頭可以是廣義表，也可以是單個(gè)元素。（ ）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（ ）6. 在一般情況下，采用壓縮存儲之后，對稱矩陣是所有特殊矩陣中存儲空間節(jié)約最多的。（ ）4. 對于不同的特殊矩陣應(yīng)該采用不同的存儲方式。（ ）2. 多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（其中：c1≤d1,c2≤d2,c3≤d3）10. 數(shù)組A[1…10，2…6，2…8]以行優(yōu)先的順序存儲，設(shè)第一個(gè)元素的首地址是100，每個(gè)元素占3個(gè)存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。8. 已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是______________。6. 已知廣義表A=((a,b,c),(d,e,f))，則運(yùn)算head(tail(tail(A)))=____________。4. 一個(gè)稀疏矩陣為 ，則對應(yīng)的三元組線性表為_____________。2. 對于一個(gè)二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?，則任一元素A[i][j]相對于A[0][0]的地址為______________。 16. 數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（ ）。 14. 一個(gè)廣義表的表頭總是一個(gè)（ ）。+141 +144 +222 +22512. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。 10. 假定在數(shù)組A中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。 B.(a,B) C.(x,(a,B)) 8. 下列廣義表用圖來表示時(shí)，分支結(jié)點(diǎn)最多的是（ ）。 6. 廣義表A=（a），則表尾為（ ）。(a00)+[j*m+i] B. LOC(a00)+[j*n+i](a00)+[(j1)*n+i1] D. LOC(a00)+[(j1)*m+i1]4. 若下三角矩陣Ann，按列順序壓縮存儲在數(shù)組Sa[0…(n+1)n/2]中，則非零元素aij的地址為（ ）。 +[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的地址為（ ）。 }}return s。 else { ps=psnext。(psdata!=ptdata)) pt=ptnext。 while((pt!=NULL)amp。 ps=s。LinkString find(s,t)LinkString *s, *t。} //delete2．算法思想為：（1）鏈表s中取出一個(gè)字符；將該字符與單鏈表t中的字符依次比較；（2）當(dāng)t中有與從s中取出的這個(gè)字符相等的字符，則從t中取下一個(gè)字符重復(fù)以上比較；（3）當(dāng)t中沒有與從s中取出的這個(gè)字符相等的字符，則算法結(jié)束。j++)r[st+j]=r[j]。 for(j=m+ti。i=m。{ int i,j。習(xí)題3參考答案一、單項(xiàng)選擇題1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空題1. 固定長度，設(shè)置長度指針2. 兩個(gè)串的長度相等，對應(yīng)位置的字符相等3. “BCDEDE”4. 含n個(gè)字符的有限序列 （n≥0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計(jì)題1．算法描述為：int delete(r,s,t,m) //從串的第m個(gè)字符以后刪除長度為t的子串char r[ ]?，F(xiàn)要求從此串的第m個(gè)字符以后刪除長度為t的子串，ms，t(sm)，并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計(jì)此刪除算法。5. 空串是指___________________，空格串是指___________________。3. 設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。 二、填空題1. 計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是___________，第二種是___________________。A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing”C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”8. 在長度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)該是（ ）。A. “ijing” B.