【正文】 編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來(lái)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。 else if(i= =0) { s=q?！?ListList *p。 }4．定義類型LinkList如下：typedef struct node{ int data。 if (head!=NULL) { q=head。free(p)。}for ( i=(*L).len 。＞0 B. i≤n ≤i≤n ≤i≤n+19. 字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（ ）。j=s。} //find 習(xí)題4一、單項(xiàng)選擇題1. 設(shè)二維數(shù)組A[0…m1][0…n1]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素aij的地址為（ ）。 ，后句錯(cuò) 二、填空題1. 一維數(shù)組的邏輯結(jié)構(gòu)是______________，存儲(chǔ)結(jié)構(gòu)是______________；對(duì)于二維或多維數(shù)組，分為______________和______________兩種不同的存儲(chǔ)方式。（ ）7. 矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。A. 邏輯 B. 邏輯和存儲(chǔ) C. 物理 D. 線性8. 線索二叉樹中，結(jié)點(diǎn)p沒(méi)有左子樹的充要條件是（ ）。 （　）9. 哈夫曼樹一定是完全二叉樹。15. 空樹是指________________________，最小的樹是指_______________________。若沒(méi)有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)，分別輸出相應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。3. 3. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。A．行號(hào) B．列號(hào) C．元素值 D．非零元素個(gè)數(shù)9. 9. AOV網(wǎng)是一種（ ）。 C. pnext=HL。試題及答案一、 五、算法設(shè)計(jì)題1. 一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對(duì)該完全二叉樹進(jìn)行先序遍歷的算法。11. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，______形態(tài)達(dá)到最大深度，____形態(tài)達(dá)到最小深度。 （?。?. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。A. 3 B. 4 C. 5 D. 64. 在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（ ）。（ ）3. 以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲(chǔ)沒(méi)有影響。 13. 若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（ ）。 if(pt= =NULL)ps=NULL。 for(i=1。 ，并且兩串包含的字符相同，并且對(duì)應(yīng)位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個(gè)字符開始的連續(xù)k個(gè)字符組成的子串的操作，則對(duì)于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。 //rearnext指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)}8．只要從終端結(jié)點(diǎn)開始往前找到第一個(gè)比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。 p=headnext。 } sprior=p。 q=p。 else { pnext=snext。算法描述如下：delete(LinkList *q,int i){ //在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn) LinkList *p,*s。4．應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。2. 在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength(L)運(yùn)算。15. 無(wú)論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為__________。A．front=frontnext 　 B．rear=rearnextC．rear=frontnext 　D．front=rearnext二、填空題1. 線性表是一種典型的_________結(jié)構(gòu)。A．基地址 B．結(jié)點(diǎn)大小 C．向量大小 D．基地址和結(jié)點(diǎn)大小12. 在等概率情況下，順序表的插入操作要移動(dòng)______結(jié)點(diǎn)。A．pnext=pnextnext。 sprior=p。for(k=0。in。}10. 下面程序段的時(shí)間復(fù)雜度是__________________。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。}}習(xí)題1一、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。 if(i=Llength) return ERROR。設(shè)計(jì)算法，將棧頂元素出棧并存入e中． base3．設(shè)二叉鏈樹的類型定義如下： typedef int Elemtype。（2）分別畫出以A為起點(diǎn)的DFS生成樹和BFS生成樹。 Qnext=pnext。for(i=n1；i=0；i) for(j=0；ji；j++) S； (A)、n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法適用于（ ）。6．已知一有向無(wú)環(huán)圖如下： BACDFEG 任意寫出二種拓?fù)渑判蛐蛄校? 、 。7． 已知有如下的有向網(wǎng)： 2 5 36 4 10 6 1 2 2 AEBDC求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑（采用Dijkstra算法，要有過(guò)程）。root,int amp。} （8分）平均時(shí)間復(fù)雜度：（2分）設(shè)元素個(gè)數(shù)記為n，則平均時(shí)間復(fù)雜度為：2（10分）void pop(Stack amp。 i=n。7. 線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。jn。for(i=1。A[i]!=k))j。 pnext=s。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。A．top不變 B．top=0 C．top D．top++17. 向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。6. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無(wú)頭結(jié)點(diǎn)的單鏈表LinkList *q,*p。5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。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ǔ)的空間大?。閙axnum。 q=qnext。　 p=L。 struct node *next,*prior。 p=headnext。p=qnext。 i0 amp。 二、填空題1. 計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的方法：一種是___________，第二種是___________________。j++)r[st+j]=r[j]。 +[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的地址為（ ）。2. 對(duì)于一個(gè)二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素A[i][j]相對(duì)于A[0][0]的地址為______________。（ ）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。A. plc=NULL B. pltag=1 C. pltag=1 且plc=NULL D. 以上都不對(duì)9. 設(shè)n , m 為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（ ）。 （?。?0. 樹的子樹是無(wú)序的。16. 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有______________和_______________兩種。習(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)路徑長(zhǎng)度最小15. 結(jié)點(diǎn)數(shù)為0，只有一個(gè)根結(jié)點(diǎn)的樹16. 二叉鏈表，三叉鏈表17. 雙親結(jié)點(diǎn)18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 1，RChild20. 孩子表示法，雙親表示法，長(zhǎng)子兄弟表示法四、應(yīng)用題1. 解答：根據(jù)給定的邊確定的樹如圖515所示。 采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（ ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。 HL=p。10. 解答：構(gòu)造而成的哈夫曼樹如圖517所示。10．給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計(jì)相應(yīng)的哈夫曼樹。10. 設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____。 （?。?. 哈夫曼樹的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。A. 15 B. 16 C. 17 D. 473. 假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（ ）。（ ）2. 多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。+141 +144 +222 +22512. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ ）。(psdata!=ptdata)) pt=ptnext。{ int i,j。，則T一定是S的一個(gè)子串4. 兩個(gè)字符串相等的條件是（ ）。elserearnext=rearnextnext。 q=head。 q=qprior。 while (p!=head) //當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置 { s=q。t delete)。四、算法設(shè)計(jì)題 1．算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)i0或in1時(shí)，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：（3）當(dāng)０in時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。3．應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。}四、算法設(shè)計(jì)題