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