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