【正文】 的一個(gè)元素，兩者不等時(shí)，將其較小者跳過(guò)，繼續(xù)后面的比較。Cnext=NULL。while (p amp。 sdata=pdata。 q=qnext。 return C。【提示】在定位操作的同時(shí)，需要調(diào)整鏈表中結(jié)點(diǎn)的次序：每次進(jìn)行定位操作后，要查看所查找結(jié)點(diǎn)的freq域，將其同前面結(jié)點(diǎn)的freq域進(jìn)行比較，同時(shí)進(jìn)行結(jié)點(diǎn)次序的調(diào)整。}DLnode,*DLinkList。pdata!=x) p=pnext。amp。k=ppriorfreq。 } return(p)。Topnext=p。Top=Topnext。A．a(chǎn)bcd*+ B．a(chǎn)bc*d+ C．a(chǎn)bc*d+ D．+*abcd5．采用順序存儲(chǔ)的兩個(gè)棧共享空間S[1..m]，top[i]代表第i個(gè)棧( i=1,2)的棧頂，棧1的底在S[1]，棧2的底在S[m]，則棧滿的條件是（B）。f=s。r=s。A．僅修改頭指針 B．僅修改尾指針C．頭、尾指針都要修改 D．頭、尾指針可能都要修改9．遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（C）的數(shù)據(jù)結(jié)構(gòu)。（√）3．若輸入序列為1,2,3,4,5,6，則通過(guò)一個(gè)棧可以輸出序列3,2,5,6,4,1。設(shè)有循環(huán)隊(duì)列sq，隊(duì)滿的判別條件為：（sqrear+1）%maxsize==sqfront。棧的應(yīng)用如數(shù)制轉(zhuǎn)換、遞歸算法的實(shí)現(xiàn)等，隊(duì)列的應(yīng)用如樹(shù)的層次遍歷等。遞歸程序的優(yōu)點(diǎn)是程序結(jié)構(gòu)簡(jiǎn)單、清晰，易證明其正確性。A．串是字符的有限序列 B．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)C．空串是由空格構(gòu)成的串 D．模式匹配是串的一種重要運(yùn)算2．串的長(zhǎng)度是指（B）。（1）A．80 B．100 C．240 D．270（2）A．SA+141 B．SA+144 C．SA+222 D．SA+225（3）A．SA+141 B．SA+180 C．SA+117 D．SA+2256．稀疏矩陣采用壓縮存儲(chǔ)，一般有（C）兩種方法。（√）4．?dāng)?shù)組是線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入，刪除等操作。（） 簡(jiǎn)答題1．KMP算法較樸素的模式匹配算法有哪些改進(jìn)?KMP算法主要優(yōu)點(diǎn)是主串指針不回溯。（1）給出S和P的next值和nextval值； （2）若S作主串，P作模式串，試給出利用KMP算法的匹配過(guò)程。【解答】由題目可知，每一行有兩個(gè)非0元素。（1）三元組表表示法（2）十字鏈表法。A．2n1 B．n1 C．n+1 D．2n+13．線索化二叉樹(shù)中，某結(jié)點(diǎn)*p沒(méi)有孩子的充要條件是（B）。A． 中序遍歷序列 B． 先序遍歷序列 C． 后序遍歷序列 D． 層次順序 6．設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn),B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（C）個(gè)。A．N1 B．N1+N2 C．N2 D．N2+N39．任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序、后序遍歷序列中的相對(duì)次序（A）。A．所有的結(jié)點(diǎn)均無(wú)左孩子 B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn) D．是一棵滿二叉樹(shù)13．引入線索二叉樹(shù)的目的是（A）。A． B． C． D．93765 356797953676539 判斷題1．二叉樹(shù)是樹(shù)的特殊形式。（）5．完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是葉子。（）7．若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。（）11．先序和中序遍歷用線索樹(shù)方式存儲(chǔ)的二叉樹(shù)，不必使用棧。（）15．用一維數(shù)組存放二叉樹(shù)時(shí)，總是以先序遍歷存儲(chǔ)結(jié)點(diǎn)。（）19．完全二叉樹(shù)可采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)，非完全二叉樹(shù)則不能。2．對(duì)于圖1所示二叉樹(shù)，試給出：（1）它的順序存儲(chǔ)結(jié)構(gòu)示意圖；（2）它的二叉鏈表存儲(chǔ)結(jié)構(gòu)示意圖；（3）它的三叉鏈表存儲(chǔ)結(jié)構(gòu)示意圖。5．將題5圖所示的二叉樹(shù)轉(zhuǎn)換成相應(yīng)的森林。證明：n個(gè)葉結(jié)點(diǎn)，需經(jīng)n1次合并形成哈夫曼樹(shù)，而每次合并產(chǎn)生一個(gè)分支結(jié)點(diǎn)，所以樹(shù)中共有2n1個(gè)結(jié)點(diǎn)。根據(jù)前序遍歷中“根—左子樹(shù)—右子樹(shù)”的順序，則由從第二元素開(kāi)始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹(shù)，由前序序列最后r個(gè)元素序列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹(shù)。 n。【解答】對(duì)應(yīng)的二叉樹(shù)和樹(shù)分別如下左、右圖所示：GBIEADKFCHJGBIEADKFCHJ14．畫(huà)出和下列已知序列對(duì)應(yīng)的森林F：森林的先根次序訪問(wèn)序列為：ABCDEFGHIJKL；森林的后根訪問(wèn)次序?yàn)椋篊BEFDGAJIKLH。對(duì)右子樹(shù)也作類似的分析。（2）對(duì)這7個(gè)字母進(jìn)行等長(zhǎng)編碼，至少需要幾位二進(jìn)制數(shù)？111111總長(zhǎng)壓縮多少？ （1）哈夫曼樹(shù)：a：10b：110c：010d：1110e：011f：00g：1111（2）對(duì)這7個(gè)字母進(jìn)行等長(zhǎng)編碼，至少需要3位二進(jìn)制數(shù)。 else return (count(rootlchild)+count(rootrchild)+1)。而題目要求是將二叉樹(shù)中的葉子結(jié)點(diǎn)按從左至右順序建立一個(gè)單鏈表，因此，可以采用三種遍歷中的任意一種方法遍歷。LinkList head,pre=NULL。 Trchild==NULL) /*當(dāng)前是葉子結(jié)點(diǎn)*/if (pre==NULL) { head=T。 } /*將葉子結(jié)點(diǎn)鏈入鏈表*/InOrder(Trchild)?！咎崾尽坎扇∵f歸算法。 hr=Height(rootrchild)?！咎崾尽坎捎孟刃蜻f歸遍歷算法實(shí)現(xiàn)。fun(rootrchild,n+1)。if (root) { Exchange(rootlchild)。rootrchild=p。但是在順序存儲(chǔ)結(jié)構(gòu)下，判二叉樹(shù)結(jié)點(diǎn)為空的條件為：結(jié)點(diǎn)下標(biāo)大于n，或結(jié)點(diǎn)值為0（一般二叉樹(shù)中的“虛結(jié)點(diǎn)”）。 t=1。data[t]!=0) { Visite(data[t])。 } if (top=0) return。 } } }7．二叉樹(shù)中查找值為x的結(jié)點(diǎn)，試設(shè)計(jì)打印值為x 的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)算法。void PrintNode (BiTree T, datatype x){ Init_Stack(S)。 } return。 /*當(dāng)棧非空，棧頂元素出棧，進(jìn)入右子樹(shù)*/ p=rrchild。void InPost (char in [ ] , char post [ ] , int il , int ir, int pl, int pr, BiTree t)/*數(shù)組in和數(shù)組post中存放著二叉樹(shù)的中序遍歷序列和后序遍歷序列，il和ir表示中序遍歷序列的左右端*//*點(diǎn)， pl和 pr表示后序遍歷序列的左右端點(diǎn)，t表示二叉樹(shù)的根*/{ t=(BiTNode *) malloc(sizeof(BiTNode))。 if (m== il) tlchild=NULL 。}9．編寫(xiě)算法判斷一棵二叉鏈表表示的二叉樹(shù)是否是完全二叉樹(shù)。int CompleteBT(BiTree T){ Init_Queue(Q)。 while(!Empty_Queue(Q)) /*當(dāng)隊(duì)列不為空時(shí)執(zhí)行循環(huán)*/ { p=Out_Queue(Q)。In_Queue(Q,plchild)。}}10．有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存放在一維數(shù)組A[1..n]中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹(shù)。if (2*in) Tlchild=NULL。 }return (T)。int Similar(BiTree s, BiTree t) { if(s==NULL amp。amp。else return(Similar(slchild,tlchild) amp。typedef struct tnode{ datatype data。void PreOrder(Btree bt){ Bnode *r, *p, *q。 /*訪問(wèn)p所指結(jié)點(diǎn)*/ if(plchild) /*下降進(jìn)入左子樹(shù)*/ { ptag=1。 p=q。 p=q。amp。amp。 r=q。 p=r。 q=rrchild。} /*從左子樹(shù)回來(lái)，準(zhǔn)備進(jìn)入右子樹(shù)*/}}}}13．對(duì)以孩子－兄弟鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法。 /**h1為T(mén)的第一棵子樹(shù)的深度*/ h2=high(tnextsibling )。樹(shù)的深度＝1 若根結(jié)點(diǎn)沒(méi)有子樹(shù)max(所有子樹(shù)的深度)＋1 若根結(jié)點(diǎn)有子樹(shù)define MAXNODE 樹(shù)中結(jié)點(diǎn)的最大個(gè)數(shù)int high(SNode t[MAXNODE],int j){ if(t[j].firstchild==NULL) return(1)。while(p){ h=high(t,pdata)。}}15．對(duì)以雙親鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法。in 。 while (t[s].parent != 1 ) { s=t[s].parent 。} 選擇題1．n條邊的無(wú)向圖的鄰接表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有（A）。A．普里姆算法 B．克魯斯卡爾算法 C．迪杰斯特拉算法 D．哈夫曼算法5．一個(gè)無(wú)向圖的鄰接表如下圖所示：序號(hào)vertexfirstedge0v11v22v33v43∧203∧101∧1∧（1）從頂點(diǎn)v0出發(fā)進(jìn)行深度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋˙）。A．O (elog2e) B．O (en ) C．O ( elog2n) D．O (nlog2n)8．關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（A）。（）2．圖的最小生成樹(shù)的形狀可能不唯一。（）6．有回路的圖不能進(jìn)行拓?fù)渑判?。（?0．若一個(gè)有向圖的鄰接矩陣對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。（√?4．縮短關(guān)鍵路徑上活動(dòng)的工期一定能夠縮短整個(gè)工程的工期。（2）鄰接矩陣：0 0 0 1 0 01 0 1 0 0 00 0 0 1 1 10 0 0 0 0 01 1 0 1 0 00 1 0 0 1 0（3）鄰接表：013 ^0 2 ^345 ^013 ^14 ^122334^4556（4）逆鄰接表：012 ^4 5 ^024 ^1 ^25 ^14 ^1223344556 （5）強(qiáng)連通分量：145632v2v1v3v5v4v7v6（圖2）2．設(shè)無(wú)向圖G如圖2所示，試給出：（1）該圖的鄰接矩陣；（2）該圖的鄰接表；（3）該圖的多重鄰接表；（4）從V1出發(fā)的“深度優(yōu)先”遍歷序列；（5）從V1出發(fā)的“廣度優(yōu)先”遍歷序列。v2v1v3v6v5v41圖3【解答】（1）G的十字鏈表結(jié)構(gòu)：0v1^1v22v33v4^5v64v51415^^25^43^53^54^^02^^01（2）G的兩個(gè)拓?fù)湫蛄校簐1v2v3v6v5v4。A．哈希存儲(chǔ) B．壓縮存儲(chǔ) C．順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) D．索引存儲(chǔ)4．用順序查找法對(duì)具有n個(gè)結(jié)點(diǎn)的線性表查找一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（C）。A．1 B．2 C．4 D．58．設(shè)哈希表長(zhǎng)為14，哈希函數(shù)為H(key)=key%1