數(shù)據(jù)結(jié)構(gòu)與算法期末練習(xí)題(含答案)

《數(shù)據(jù)結(jié)構(gòu)與算法》期末練習(xí)一選擇題以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（D。循環(huán)隊(duì)列 B.鏈表 C.哈希表 D.棧算法的時(shí)間復(fù)雜度取決于（A）問(wèn)題的規(guī)模 B.待處理數(shù)據(jù)的初態(tài) C.A和B D.計(jì)算機(jī)cpu一個(gè)棧的輸入序列為1234則下列序列中不可能是棧的輸出序列的是（BA.23415 B.54132 C.23145 D.15432它存取表中第i個(gè)元素的時(shí)間與i(2)靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定(3)B）A（2） 1） 1（,(3) D）對(duì)于有n（D）nlogn n n|+1 D．不確定2 2 2（C）A．B．當(dāng)K≥1時(shí)高度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。C．D．在設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（B）條邊。A．n-1 B．n(n-1)/2 n(n+1)/2 8G=(V,EV={V,V,V,V,V,V,VE={<V,V>,<V,V>,<V,V>,<V,V>,1 2 3 4 5 6 7 1 2 1 3 1 4 2 5<V,V<V,V<V,V<V,V<V,V>},G（A。3 5 3 6 4 6 5 7 6 7A．V,V,V,V,V,V,V ,V,V,V,V,V,V1 3 4 6 2 5 7 1 3 2 6 4 5 7C．V,V,V,V,V,V,V ,V,V,V,V,V,V1 3 4 5 2 6 7 1 2 5 3 4 6 79．下列排序算法中，其中（D）是穩(wěn)定的。A.堆排序，冒泡排序B.快速排序，堆排序C.希爾排序，歸并排序D.歸并排序，冒泡排序?qū)σ唤M數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過(guò)程中的變化為1）8447251521）1547258421（3）1521258447(）1521254784A)。A.選擇 B.冒泡 C.快速 D.插入以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（D）？廣義表 B.二叉樹 C.稀疏矩陣 D.串下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（B）A．B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C．D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。設(shè)一個(gè)棧的輸入序列是則下列序列中是棧的合法輸出序列的（DA.51234 B.45132 C.43125 D.32154 n的語(yǔ)句的頻度為（Bi=1;k=0;do{@k+=10*i;i++;}While(i<=n-1);n–1 B.n C.n+1 D.n-2 一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（A）A．logn+1 B．logn+1 一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）元素是（B。不確定 B.n-i+1 C.i D.n-i18．n（D。A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）穩(wěn)定的排序方法是（B）直接插入排序和快速排序 B．折半插入排序和起泡排序C．希爾排序和四路歸并排序 樹形選擇排序和shell排有一組數(shù)據(jù)據(jù)的排序?yàn)?A)按遞增序。A．下面的B，C，D都不對(duì)。 C．20，15，8，9，7，-1，4，7 D.9，4，7，8，7，-1，15，20以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（A）棧 B.哈希表 C.線索樹 D.雙向鏈表下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（B）A．串是字符的有限序列 空串是由空格構(gòu)成的C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)某堆棧的輸入序列為a,b，c，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（D。a，c，b，d B.b,C.c,a D.d,c，a，b0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K叉樹。正確的是（D）A．①②③B．②③④C．②④D．①④K（C。2k2k-1

-1 D．2k-1-1（C）A．B．當(dāng)K≥1時(shí)高度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。C．用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。D．哈27.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（A。A．從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長(zhǎng)回路D．最短回路DFSDFSAA．逆拓?fù)溆行?拓?fù)溆行?無(wú)序的一組記錄的關(guān)鍵碼為46，7，5，3840，8記錄為基準(zhǔn)得到的一次劃分結(jié)果為（C。A．(38,40,46,56,79,84) B.(40,38,46,79,56,84)C．(40,38,46,56,79,84) D.(40,38,46,84,56,79)一個(gè)向量的第一個(gè)元素的地址是ki(D)A.begin+(k-1)i B.begin+(k-2)iC.begin+kiD.begin+(i-1)k31.有一個(gè)有序表為{1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要經(jīng)過(guò)(C)次與63比較。A.12 B.6 C.4 D.5一個(gè)序列的初始狀態(tài)為4677，8，5，3，70D)。C.（46，31,D.(46將一個(gè)長(zhǎng)度為niB)個(gè)元素。A.i B.n-i C.n+1 D.n-i+1不帶表頭的單鏈表，頭指針為headA)A.head==0B.head->next==nullC.head==headD.head->next==head*q表示指針q*q之后插入結(jié)點(diǎn)*s，正確的操作步驟序列是(A)。A)q->next=s;s->next=p B)s->next=p->next;q->next=s;C)p->nexr=s;s->next=p; D)p->next=s;s->next=q;非空循環(huán)鏈表head的尾結(jié)點(diǎn)*p滿足下列(C)條件A)head->next==p;B)head==p;C)p->next==head;D)p->next==0一個(gè)棧的輸入序列是a,b,c,d,eD)。A.ecdabB)cebdaC)daecbD)abcde設(shè)棧ssqstackC)。A.s==NULLB)s->top==0C)s.top==0 D)s.top==NULL5的二叉樹至多有個(gè)(B)結(jié)點(diǎn)。A.12B.31C.14D.15已知二叉樹的后、中根序列分別是bedfca和badecf，則該二叉樹的前根遍歷序列是(C)。A)defbcaB)fedbcaC)abcdefD)fedcba一個(gè)有nB)弧。A)n(n+1)B)n(n-1)C)n(n+1)/2 D)n(n-1)/2具有n個(gè)頂點(diǎn)的無(wú)向圖至少要(B條邊才有可能是一個(gè)連通圖A) n(n+1)B)n-1C)n+1 D)n(n-1)已知有向圖的正鄰接鏈表的存儲(chǔ)結(jié)構(gòu)如下，從頂點(diǎn)1出發(fā)的按深度優(yōu)先遍歷序列是(B)。A)1234 B) 1423 C) 1324 D)143214 ^2 ^3 ^23 ^4 ^314 ^2 ^3 ^23 ^4 ^32 ^4 ^4一個(gè)向量的第一個(gè)元素的地址是100，每個(gè)元素的長(zhǎng)度是2，則第五個(gè)元素的地址是(C)A)102B)110C)108D)120一個(gè)循環(huán)順序隊(duì)列,隊(duì)頭、尾指針的值分別為front,rear，則隊(duì)列中元素個(gè)數(shù)為(A（maxlen）(rear-front+maxlen)%maxlen(rear-front)%maxlenrear-front+1front-rear+1一個(gè)有nD)條邊。A)n(n+1)B)n(n-1)C)n(n+1)/2 D) 0具有5個(gè)頂點(diǎn)的無(wú)向圖至少要(A條邊才能確保是一個(gè)連通圖A)4 B)5C)6 D) 7設(shè)棧s的類型為sqstack，最多可容納maxlenB)。A.s==maxlen-1B)s.top==maxlen-1C)s->top==maxlen-1 D)s.top==0一個(gè)順序隊(duì)列q的類型為sqqueuefront,reaC)。A)front==rearB)rear==0C)q.front==q.rearD)rear==maxlen-1在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度( B )A.O(1) B.O(n)C.O(nlogn) D.O(n*n)鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)( D )A.插入操作更加方便 刪除操作更加方C.不會(huì)出現(xiàn)下溢的情況 不會(huì)出現(xiàn)上溢的情二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多( C )A.8 B.15C.1653.下列編碼中屬前綴碼的是(D.32A)A.{1,01,000,001}C.{0,10,110,11}B.{1,01,011,010}D.{0,1,00,11}如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用（BA．深度優(yōu)先搜索算法 B．廣度優(yōu)先搜索算法C．求最小生成樹的prim算法 D．拓?fù)渑判蛩惴▽?duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度(BA.O(1) B.O(logn)C.O(n) D.O(nlogn)對(duì)表長(zhǎng)為n度為(C)A.(n-1)/2 B.n/2C.(n+1)/2 D.n對(duì)于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字( D )A.35和41 B.23和39C.15和44 D.25和51（B）A線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼B線性表是具有n(n>=0)個(gè)元素的一個(gè)有限序列C線性表就是順序存儲(chǔ)的表D線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)表長(zhǎng)為n時(shí)，刪除一個(gè)元素需要移動(dòng)元素的平均個(gè)數(shù)為（A）A(n-1)/2 Bn/2 CnDn-1設(shè)雙向循環(huán)鏈表中節(jié)點(diǎn)的結(jié)構(gòu)為(data,LLink,RLink)，且不帶頭節(jié)點(diǎn)。若想在指針?biāo)腹?jié)點(diǎn)之后插入指針s？（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->RLink;Cs->LLink=p;s->RLink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;棧和隊(duì)列都是（A）A限制存取位置的線性結(jié)構(gòu)B鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C順序存儲(chǔ)的線性結(jié)構(gòu)D限制存取位置的非線性結(jié)構(gòu)單循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則入隊(duì)的時(shí)間復(fù)雜度為（AAO(n) BO(1) CO(n*n) DO(n*logn)一棵含有n個(gè)節(jié)點(diǎn)的k叉樹，可能達(dá)到的最小深度為多少？（CAn-k Bn-k+1C|logn|+1D|logn| 其|k|表示下取整k kB)不是堆。A.12365368486075B.12485368366075C.12483660756853D.12366053486875在下列內(nèi)排序方法中，(C)的平均時(shí)間復(fù)雜性是O(nlogn)。直接插入排序 B.簡(jiǎn)單選擇排序 C.快速排序 D.希爾排序設(shè)順序棧s非空，則語(yǔ)句段(C)可實(shí)現(xiàn)棧s的出棧操作，其中s.tops.elemxs.top:=s.top+1; B.x:=s.elem[s.top];x:=s.elem[s.top]; s.top:=s.top+1;C.s.top:=s.top-1; D.x:=s.elem[s.top];x:=s.elem[s.top]; s.top:=s.top-1;已知L指向表中某結(jié)點(diǎn)，則要?jiǎng)h除p作(A)；要在psD)。pnext:=pnextnext; B..next;C.pnext:=s;snext:=pnext; D.snext:=pnext;pnext:=s;關(guān)鍵字有序（D。二叉排序樹BC．AVLD．堆69.下面給出的四種排序法中(D)排序法是不穩(wěn)定性排序法。A.插入 B.冒泡C.二路歸并D.快速排序70.O(nlogn)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序2方法是（C。A.快速排序 B.堆排序 C.歸并排序 D.直接插入排序二填空題1、在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：p->next!=null2、表達(dá)式23+((12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是：(請(qǐng)?jiān)诒磉_(dá)式中用點(diǎn)(.)將數(shù)隔開)23.12.3*2-4/34.5*7/++108.9/+3、有一個(gè)100*90092該矩陣時(shí)，所需的字節(jié)數(shù)是604、深度為9的完全二叉樹具有的 個(gè)結(jié)點(diǎn)2565、已知二叉樹后序?yàn)镈GEBFCA，中序?yàn)镈BGEACF，則前序一定是ABDEGCF6、先根遍歷樹林正好等同于先序

_遍歷對(duì)應(yīng)的二叉樹.7、構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少條弧n8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標(biāo)依次為6,9,11,129ps10、有N個(gè)頂點(diǎn)的有向圖，至少需要條弧才能保證是連通的N-111、在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值12，需做的關(guān)鍵碼比較次數(shù)為413、下面是一個(gè)無(wú)向圖的鄰接矩陣，試將有關(guān)數(shù)據(jù)填入本題的空白處（頂點(diǎn)號(hào)由1開始）0101110100010101010110010該圖的頂點(diǎn)數(shù)為 該圖的邊數(shù)為 頂點(diǎn)3的度為 56214、后根遍歷樹林正好等同于(6) 遍歷對(duì)應(yīng)的二叉樹中序15、n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)n*（n－l）16、當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法。時(shí)間復(fù)雜度17、假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列得到輸出序列的操序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列。SXSSXXSSXSSXXX18、在一棵度為3的樹中，度為2的結(jié)點(diǎn)個(gè)數(shù)是1，度為0的結(jié)點(diǎn)個(gè)數(shù)是6，則度為3的結(jié)點(diǎn)個(gè)數(shù)219、如圖所示的有向無(wú)環(huán)圖可以排種不同的拓?fù)湫蛄小?220、利用篩選法將關(guān)鍵字序列(37，66，48，29，31，75)建成的大根堆為( 75,66,48,29,31,3721、對(duì)長(zhǎng)度為20的有序表進(jìn)行二分查找的判定樹的高度。522、n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的條數(shù)至少n-123、排序(sorting)有哪幾種方法 ， ， ， ， 。直接插入排序，冒泡排序，快速排序，希爾排序，歸并排序，基數(shù)排序，堆排序24、下面程序段的時(shí)間復(fù)雜度（用O估計(jì)）FORi:=1TOnDOFORj:=iTOns=s+j;O（n*n）25、非線性結(jié)構(gòu)包和 樹，圖26、在線性表存儲(chǔ)結(jié)構(gòu)上進(jìn)行插入或刪除操作要移動(dòng)元素順序存儲(chǔ)結(jié)構(gòu)27、用一維數(shù)組r[0..m-1]表示順序存儲(chǔ)的循環(huán)隊(duì)列，設(shè)隊(duì)頭和隊(duì)尾指針分別是front和rear，且隊(duì)頭指針?biāo)傅膯卧e置，則隊(duì)滿的條件隊(duì)空的條件。Front=rear,rear+1=front28、下面表達(dá)式樹所對(duì)應(yīng)的表達(dá)式的前綴表達(dá)式，后表達(dá)式。+*a-bc/de,abc-*de/+29在AOE-網(wǎng)中設(shè)e(i)和l(i)分別表示活動(dòng)ai的最早開始時(shí)間和最晚開始時(shí)間，則當(dāng)僅當(dāng) 時(shí)，ai為關(guān)鍵活動(dòng)。e(i)==l(i)30．對(duì)有向圖進(jìn)行拓?fù)渑判颍敉負(fù)渑判虿怀晒?，則說(shuō)明該。下面向圖的一個(gè)拓?fù)溆行蛐蛄?。存在回路?2345679831、二叉排序樹的特點(diǎn)是其 序列是有序的中序遍歷三簡(jiǎn)答題11）（）算法的時(shí)間復(fù)雜性；（3）(hashing4）23、快速分類法的基本思想是什么?4用prime(5,4),則，下一條邊應(yīng)在哪幾條邊中選??？選取哪一條？175 225 383 641445 35、二叉樹的后根遍歷的序列中，任何一個(gè)非葉子結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)后面。該論斷是否正確？6、有一棵哈夫曼樹共有5個(gè)葉子結(jié)點(diǎn)其權(quán)值分別為0.1,0.25,0.08,0.21,0.9,試畫出該哈夫曼樹。假設(shè)該葉子分別表示a,b,c,d,e，分別給出五個(gè)葉子對(duì)應(yīng)的哈夫曼編碼。7、對(duì)于一個(gè)隊(duì)列，若入隊(duì)的順序?yàn)閍,b,c,則所有可能的出隊(duì)序列是什么？8、已知一個(gè)圖如下，試畫出其逆鄰接鏈表。112349、若一個(gè)棧的輸入序列是1,2,3……，n,其輸出序列為p1,p2,……pn,若p1=n，則pi為多少？10嗎？11、已知二叉樹的中根遍歷序列為abc，試畫出該二叉樹的所有可能的形態(tài)。12、已知一個(gè)圖如圖所示，如從頂點(diǎn)aacebdf?為什么？若按廣度優(yōu)先遍歷，能否得到序列abedfc?為什么？aacbefd13、棧的存儲(chǔ)方式有哪兩種？14、對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針p，能否將p所指結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換?請(qǐng)對(duì)每一種鏈表作出判斷，若可以，寫出程序段；否則說(shuō)明理由。其中：priordatenextdatenextpriordatenextdatenext15、假設(shè)通信電文使用的字符集為{a,b,c,d,e,f,g}，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111。請(qǐng)根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符；和9，帶權(quán)路徑長(zhǎng)度。1、對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)？試說(shuō)明理由。17、內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個(gè)棧s1和s2并對(duì)兩個(gè)棧的容量進(jìn)行分析。18（1）2）畫出該二叉樹后序線索化圖（3）試畫出該二叉樹對(duì)應(yīng)的森林。19、一棵二叉排序樹結(jié)構(gòu)如下,各結(jié)點(diǎn)的值從小到大依次為1-9，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。201,2,…,nP,PP（它是輸入序列的1 2 n一個(gè)排列，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<kP<P<P。j k i四算法閱讀1、voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={1,5,8,12,15};for(i=0;i<5;i++)Push(S,2*a[i]);while(!StackEmpty(S))print(Pop(S));}該算法被調(diào)用后得到的輸出結(jié)果為：2、voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT->left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2);}//if}該函數(shù)執(zhí)行的功能是什么？3、在下面的每個(gè)程序段中，假定線性表La的類型為的類型為ElemType,元素類型ElemType為L(zhǎng)a。InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)ListInsert(La,1,a[i]);ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);ClearList(La);ForListInsert(La,i+1,a[i]);4、intPrime(intn){inti=1;intx=(int)while(++i<=x)if(n%i==0)if(i>x)return1;elsereturn0;}指出該算法的功能；該算法的時(shí)間復(fù)雜度是多少？寫出下述算法A其中BiTreeTypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){ DeQueue(Q,e);If(e==NULL)Else{Print(e.data);ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}}閱讀下列函數(shù)algo,并回答問(wèn)題：假設(shè)隊(duì)列q中的元素為(2,4,5,7,8)algo(&q)后的隊(duì)列q；簡(jiǎn)述算法algovoidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,while(!ＥnQueue(Q,Pop(&S));}五算法填空1、下面是在帶表頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列上，進(jìn)行出隊(duì)操作，并將出隊(duì)元素的值保留在x中的函數(shù)，其中rear是指向隊(duì)尾結(jié)點(diǎn)的指針。請(qǐng)?jiān)跈M線空白處填上適當(dāng)?shù)恼Z(yǔ)句。typedefstructnode{intdata;structnode*next;}lklist;voiddel(lklistrear,int&x);{lklistp,q;q=rear->next;if( printf(“itisempty!\n”);else{p=q->next;x=p->data; ;if( )rear=q;;};};2typedefstruct{char*int }HString；HStringStatusStrCat(s，t)/*將串t連接在串s的后面*/{inti;char*temp;if(temp==NULL)return(0);for(i=0; temp［i］=s->ch［i］;for( ;i<s->len+t.len;i++)temp［i］=t.ch［i-s->len］;s->len+=t.len;frs->ch=temp;return(1);}3、向單鏈表的末尾添加一個(gè)元素的算法。LNode是一個(gè)包含（data，Next）的結(jié)構(gòu)體VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newIf( ){cerr<<"Memoryallocationfailare!"<<endl;exit(1);} newptr->next=NULL;if(HL==NULL)HL= ;else{LNode*P=HL;While(P->next!=NULL) p->next=newptr;}}4Lf30的功能是刪除L中數(shù)據(jù)域data的值大于c請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。LinkListf30(LinkListL,intc){LinkListLc,p,pre;pre=L;p= (1) ;Lc=(LinkList)malloc(sizeof(ListNode));Lc->next=Lc;while(p!=L)if(p->data>c){pre->next=p->next;(2) ;Lc->next=p;p=pre->next;}else{pre=p;(3) ;}returnLc;}adjvexnextvertexfirstedgeadjvexnextvertexfirstedge下列算法計(jì)算有向圖G中頂點(diǎn)vi的入度。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。intFindDegree(ALGraph*G,inti)//ALGraph為圖的鄰接表類型{intdgree,EdgeNode*p;degree= (1) for(j=0;j<G->n;j++){p=G->adjlist［j］.firstedge;while( (2) ){if( (3) ){degree++;break;}p=p->next;}}returndegree;}六簡(jiǎn)單應(yīng)用題1GBAHEDJFIBCHEJIFDA試將這樣二元樹構(gòu)造出來(lái);若已知先根和后根的遍歷結(jié)果，能否構(gòu)造這棵二元樹，為什么?2、對(duì)于下圖，畫出按Kruskal（克魯斯卡爾）算法和Prim（普里姆）算法構(gòu)造最小生成樹的過(guò)程。3、畫出由下面的二叉樹轉(zhuǎn)換成的森林。4、用Floyed（弗洛伊徳）算法求下圖每一對(duì)頂點(diǎn)之間的最短路徑及其長(zhǎng)度，將計(jì)算過(guò)程的中間和最后結(jié)果填入下表：1A1A(0)231A(1)231A(2)231A(3)231PATH(0)231PATH(1)231PATH(2)231PATH(3)23123PATH1235、哈夫曼樹在構(gòu)造時(shí)，首先進(jìn)行初始化存儲(chǔ)空間，結(jié)果如左下圖，當(dāng)構(gòu)造完成后，請(qǐng)?zhí)顚懽詈鬆顟B(tài)表，如右下圖。weightParentLchildRchildweightParentLchildRchild150001229000237000380080001400023000300011000--000--000--000--000--000--000--000456789101112131415567891011121314156、考慮右圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(4分)(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(4分)(3）(Prim)算法，求它的最小生成樹(請(qǐng)畫出過(guò)程)列)(6答案如下：七編寫算法題1、設(shè)計(jì)函數(shù)，求一個(gè)單鏈表中值為x的結(jié)點(diǎn)個(gè)數(shù)。并將結(jié)果放在頭結(jié)點(diǎn)的data域中。voidcount1(lklisthead,intx)2、設(shè)計(jì)遞歸函數(shù)，求一棵二叉樹的深度。intdepth(bitreptrroot)3、設(shè)計(jì)建立有向圖正鄰接矩陣的函數(shù)（數(shù)據(jù)輸入格式自定Typedefstruct{intdata[maxsize][maxsize];intdem,e;}sqgraph;sqgraphcrt(sqgraphg)4、設(shè)計(jì)函數(shù)，將不帶表頭結(jié)點(diǎn)的單鏈表清除。5、設(shè)計(jì)遞歸函數(shù)，求一棵非空的二叉樹的深度。6、設(shè)線性表A=(a1,a2,a3,…,anA7、試編寫一個(gè)算法，能由大到小遍歷一棵二元樹。8、假設(shè)二元樹用左右鏈表示，試編寫一算法，判別給定二元樹是否為完全二元樹?9、利用直接插入排序的方法對(duì)一組記錄按關(guān)鍵字從小到大的順序排序。10、給出一棵表示表達(dá)式的二叉樹，其中運(yùn)算符和運(yùn)算對(duì)象都用一個(gè)字符表示，求該表達(dá)式的值。設(shè)二叉樹用二叉鏈表表示，表達(dá)式中僅包含二元運(yùn)算，函數(shù)operate(a,b,op)op和b算法中允許直接引用函數(shù)operate(函數(shù)operate不必定義)，如果需要還允許引用棧和隊(duì)列的基本操作。11、編寫算法，將一單鏈表逆轉(zhuǎn)。要求逆轉(zhuǎn)在原鏈表上進(jìn)行，不允許重新構(gòu)造一個(gè)鏈表（以申明零時(shí)變量、指針。該鏈表帶頭節(jié)點(diǎn)、頭節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)的結(jié)構(gòu)定義如下typedefstructLNode{ElemTypedata;StructLNode*}List,LNode;函數(shù)定義：voidinvert(List&L)12、編寫算法計(jì)算給定二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。其中樹節(jié)點(diǎn)定義如下typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*RChild;}BiTNode,*BiTree;函數(shù)定義：CountLeaf(BiTreeT,int&LeafNum)13已知二叉樹結(jié)點(diǎn)定義為：structnode{elemtpdata;structnode*lc,*rc;);Typedefstructnode*bitreptr(指向根),*tpointer(指向一般結(jié)點(diǎn));voidpreorder(bitreptrP)//P指向樹根節(jié)點(diǎn)voidpreorder(bitreptrP){If(P!=0){printf(P->data);preorder(P->lc);preorder(P->rc);}}14、在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：InsertVex(G,v)//插入頂點(diǎn)StatusInsert_Vex(MGraph&G,charv)//在鄰接矩陣表示的圖G上插入頂點(diǎn)v{if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G.vexnum]=v;returnOK;}//Insert_Vex15、已知某哈希表的裝載因子小于1，哈希函數(shù)為關(guān)鍵字（標(biāo)識(shí)符）voidPrint_Hash(HashTableH)//按第一個(gè)字母順序輸出Hash表中的所有關(guān)鍵字,voidPrint_Hash(HashTableH)//按第一個(gè)字母順序輸出Hash表中的所有關(guān)鍵字,其中處理沖突采用線性探測(cè)開放定址法{for(i=1;i<=26;i++)for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])if(H(H.elem[j].key)==i)p