應(yīng)用題復(fù)習(xí)含解

1、一、應(yīng)用題1. 已知線性表的存儲(chǔ)結(jié)構(gòu)為順序表，閱讀下列算法，并回答問(wèn)題：（1）設(shè)線性表L=（51，-9，-6，39，0，-11，34，70，-16），寫(xiě)出執(zhí)行算法f11(&L)后的L狀態(tài)；（2）簡(jiǎn)述算法f11的功能。void f11 (SeqList *L) int i,j;for (i=j=0;i<L->len; i+)if(L->elemi>=0)if(i!=j)L->elemj=L->elemi;j+；L->len=j;【答案】（1）L=(51,39,0,34,70)(2) 刪除順序表中小于0的數(shù)。2. 假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表,

2、閱讀下列算法f22,并回答問(wèn)題:(1)設(shè)線性表為( a1, a2, a3, a4, a5, a6, a7 ), 寫(xiě)出執(zhí)行算法f22后的線性表；(2)簡(jiǎn)述算法f22的功能。 void fun(LNode *L)/L為帶頭結(jié)點(diǎn)單鏈表的頭指針P =L;while (p &&p->next)q = p->next;p->next =q->next;p =q->next;free(q); 【答案】（1）(a2,a4,a6)(2) 刪除單鏈表中數(shù)據(jù)結(jié)點(diǎn)序號(hào)為奇數(shù)的那些結(jié)點(diǎn)。3.假設(shè)以數(shù)組seqnm存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列

3、中隊(duì)尾元素的位置和元素的個(gè)數(shù)。(1)寫(xiě)出隊(duì)滿的條件表達(dá)式；(2)寫(xiě)出隊(duì)空的條件表達(dá)式；(3)設(shè)m=50,rear=19,quelen=25,求隊(duì)頭元素的位置；(4)寫(xiě)出一般情況下隊(duì)頭元素位置的表達(dá)式?！敬鸢浮?1)quelen=m(2)quelen=0(3)45(4)front=(rear-quelen+1+m)%m4.假設(shè)以數(shù)組seqnm存放循環(huán)隊(duì)列的元素，設(shè)變量front和rear分別指示循環(huán)隊(duì)列中隊(duì)頭元素的位置和隊(duì)尾元素的位置。(1)寫(xiě)出隊(duì)滿的條件表達(dá)式；(2)寫(xiě)出隊(duì)空的條件表達(dá)式；(3)設(shè)m=40,rear=13,front=19,求隊(duì)列的元素的個(gè)數(shù)quelen；(4)寫(xiě)出一般情況下元

4、素的個(gè)數(shù)的表達(dá)式?！敬鸢浮?1)(rear+1)%m=front(2) rear=front(3)34(4) quelen=(rear-frontm)%m5. 假設(shè)有一個(gè)如下圖的8×8矩陣，矩陣元素都是整型量(次對(duì)角線以上的元素都是0)。若將上述矩陣中次對(duì)角線及其以下的元素按行優(yōu)先壓縮存儲(chǔ)在一維數(shù)組B中，請(qǐng)回答下列問(wèn)題：(1)B數(shù)組的體積至少是多少?(2)若a18存儲(chǔ)在B0中，a56存儲(chǔ)在Bk中，則k值為多少?(1) (2)【答案】（1）36 （2）136. 閱讀下列算法，并回答問(wèn)題：（1）Q、Q1和Q2都是隊(duì)列結(jié)構(gòu)，設(shè)隊(duì)列Q=（1，0，-5，2，-4，-6，9），其中1為隊(duì)頭元素，

5、寫(xiě)出執(zhí)行f33 (&Q,&Q1,&Q2)之后隊(duì)列Q、Q1和Q2的狀態(tài)；（2）簡(jiǎn)述算法f33的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分別是隊(duì)列初始化、入列、出隊(duì)和判隊(duì)空的操作）void f31 (Queue*Q, Queue*Q1, Queue*Q2) int e;lnitQueue (Q1);lnitQueue (Q2);while (!QueueEmpty (Q) e=DeQueue (Q);if (e>=0) EnQueue (Q1,e);else EnQueue (Q2,e)【答案】（1）Q=() Q1=(1,0

6、,2,9) q2=(-5,-4,-6)（2）將Q隊(duì)列中的數(shù)據(jù)全部出隊(duì)；不小于0的進(jìn)Q1，否則進(jìn)Q2。ABCGDEF7. 已知二叉樹(shù)如右圖所示。（1）畫(huà)出該二叉樹(shù)的二叉鏈表；（2）分別寫(xiě)出該二叉樹(shù)的先根、中根和后根遍歷序列?！敬鸢浮?(1) 二叉鏈表:DACBEGF（2）先根遍歷序列：ABDCEGF中根遍歷序列: DBAEGCF后根遍歷序列: DBGEFCA8、假設(shè)一棵二叉樹(shù)的先根遍歷序列為ABCDEFGH，中根遍歷序列為CDBEGFHA。(1)畫(huà)出該二叉樹(shù)；（2）寫(xiě)出后根遍歷序列。DBEHGFAC【答案】(1)二叉樹(shù)（2）后根遍歷序列:DCGHFEBA9、假設(shè)一棵二叉樹(shù)的中根遍歷序列為DGBE

7、ACHFI，后根遍歷序列為GDEBHIFCA(1)畫(huà)出該二叉樹(shù)；（2）寫(xiě)出先根遍歷序列。【答案】（1）二叉樹(shù)：（2）先根遍歷序列：ABDGECFHIABCIDHFGE10假設(shè)一棵二叉樹(shù)的層次遍歷序列為ABCDEFGHI，中根遍歷序列為DHBEAFCIG。(1)畫(huà)出該二叉樹(shù)；（2）寫(xiě)出先根和后根遍歷序列?！敬鸢浮浚?）二叉樹(shù)：ABCIDFGHE（2）先根遍歷序列：ABDHECFGI后根遍歷序列：HDEBFIGCA000000111111TGMSHDA25116145323517107186011設(shè)某通訊系統(tǒng)僅用七個(gè)英文字符A，D，G，H，M，S，T，每個(gè)字符的使用頻率分別為3，7，18，2，6，

8、10，14。請(qǐng)畫(huà)出對(duì)應(yīng)的哈夫曼編碼樹(shù)（按照每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的哈夫曼編碼?！敬鸢浮抗蚵幋aADGHMST00011001100000011010112. 假設(shè)通信電文使用的字符集為 S，T，B，F(xiàn)，C，字符的哈夫曼編碼依次為：011，10，00，010和11。 (1)請(qǐng)根據(jù)哈夫曼編碼畫(huà)出此哈夫曼樹(shù)，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符； (2)若這些字符在電文中出現(xiàn)的頻度分別為：4，7，5，2和9，求出電文的總長(zhǎng)度。160000111111275 6 7 2 4 9BFSTC【答案】（1）編碼哈夫曼樹(shù) (2) 電文的總長(zhǎng)度=4*3+7*2+5

9、*2+2*3+9*2=60v2v3v1v5v413、已知一個(gè)有向圖如右圖所示。(1)試畫(huà)出它的鄰接表。（表結(jié)點(diǎn)按頂點(diǎn)編號(hào)遞減排列） 1 2 3 4 5 5 4 3 2 4 4 2 (2)分別求出從v1出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到的頂點(diǎn)序列?！敬鸢浮浚?） (2)深度優(yōu)先搜索序列：v1，v 4，v 3， v 5，v 2 廣度優(yōu)先搜索序列：v1，v 4，v 3， v 2，v 514、已知一個(gè)AOV網(wǎng)如右圖所示。V51V11V41V21V61V31(1)試畫(huà)出它的鄰接鏈表。（表結(jié)點(diǎn)按頂點(diǎn)編號(hào)遞減排列）(2)試寫(xiě)出按照拓?fù)渑判蛩惴ǖ玫降耐負(fù)湫蛄小? v1 06 v6 3 5 v5 1

10、3 V3 24 v4 2 21 v2 0 6 4 6 4 3 6 5 3 【答案】 (1) （2）v2,v5,v1,v3,v6,v415、請(qǐng)用普里姆算法(從頂點(diǎn)V3開(kāi)始)和克魯斯卡爾算法構(gòu)造下圖所示網(wǎng)絡(luò)的最小生成樹(shù)，按照并入最小生成樹(shù)中邊的次序填寫(xiě)下表，并畫(huà)出最小生成樹(shù)。次序1 2 345始 點(diǎn) 終 點(diǎn)權(quán) 值14v1v4v5 v2v3V610818161210151920【答案】（1）普里姆算法14v1v4v5 v2v3V68161210構(gòu)造過(guò)程： 最小生成樹(shù)：次序1 2 345始 點(diǎn)V3V1V3V2V2終 點(diǎn)V1V4V2V5V6權(quán) 值121416810（2）克魯斯卡爾算法14v1v4v5 v

11、2v3V68161210構(gòu)造過(guò)程： 最小生成樹(shù)：次序1 2 345始 點(diǎn)V2V2V3V1V3終 點(diǎn)V5V6V1V4V2權(quán) 值81012141616、設(shè)關(guān)鍵字序列（17,8,13,25,24,16,3,19,1），寫(xiě)出用下列方法排序時(shí),第一趟結(jié)束時(shí)關(guān)鍵字的排列狀態(tài)。(1)冒泡排序 (2)希爾排序(d1=4) （3）快速排序【答案】 (1)冒泡排序 （8，13，17，24，16，3，19，1，25）(2)希爾排序(d1=4) （1，8，3，19，17，16，13，25，24）(3）快速排序（1，8，13，3，16）17（24，19，25）52243012617046798317、對(duì)有序表12,24

12、,30,46,52,61,70,79,83進(jìn)行折半查找方法查找，（1）求出查找24和83時(shí)所需比較的次數(shù)；（2）畫(huà)出判定樹(shù)； （3）求ASL和MSL?！敬鸢浮?1)24比較2次；83比較4次(2)判定樹(shù)：(3)ASL=(1+4+12+8)/9=25/9=2.78MSL=418已知一組數(shù)據(jù)元素為（68，21，95，71，14，57，28，33，80），要求：（1）試從空樹(shù)開(kāi)始畫(huà)出按元素排列順序輸入而生成的一棵二叉排序樹(shù)；（2）畫(huà)出刪除結(jié)點(diǎn)68后的二叉排序樹(shù)?！敬鸢浮?1) 二叉排序樹(shù):2114289571 68578033（2）刪除結(jié)點(diǎn)68后的二叉排序樹(shù): 或：2114289580 715733

13、 21149571 5728803319.選取哈希函數(shù)為H(K)=K % 7。用線性探測(cè)的開(kāi)放地址法處理沖突。試在08的散列地址空間中對(duì)關(guān)鍵字序列25,72,48,19,32,50,68構(gòu)造哈希表，并求出等概率下查找成功的平均查找長(zhǎng)度?！敬鸢浮?（1） 50722519483268 0 1 2 3 4 5 6 7 8哈希表: 比較次數(shù)： 1 1 1 1 1 4 4（2）20. 下列是一棵五階B-樹(shù),依次執(zhí)行以下兩步操作,畫(huà)出每一步執(zhí)行后所得到的B-樹(shù)形。(1)插入n;(2)刪除e 。【答案】(1)插入n: (2)刪除e:21已知關(guān)鍵字序列為：（70,31,52,41, 88,12,27,66）

14、哈希表長(zhǎng)為9，哈希函數(shù)為：H (k)k %9，用鏈地址法處理沖突，試構(gòu)造哈希表，并求等概率下查找成功的平均查找長(zhǎng)度?！敬鸢浮?1) 哈希表:012345678 27 12 31 52 41 70 88 66 (2) 22. 由森林轉(zhuǎn)換得到的對(duì)應(yīng)二叉樹(shù)如圖所示，寫(xiě)出原森林中第三棵樹(shù)的前序序列和后序序列?！敬鸢浮緼BDLKCFEGHIJ還原后的森林：第三棵樹(shù)的前序序列GHIJ ；后序序列HJIG23. 假設(shè)一棵樹(shù)的先根序列為ABCEFIJGHKD，后根序列為BEIJFGKHCDA。請(qǐng)畫(huà)出該樹(shù)?！敬鸢浮浚?）因?yàn)闃?shù)的先根和后根遍歷序列分別與其轉(zhuǎn)換后對(duì)應(yīng)的二叉樹(shù)的先根和中根遍歷序列相同，所以可先得到的對(duì)應(yīng)的二叉樹(shù)如下圖所示：（2）根據(jù)樹(shù)與二叉樹(shù)的轉(zhuǎn)換規(guī)則，可得到樹(shù)如下圖所示：24. 已知一個(gè)散列表如下圖所示：19 32485822 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探測(cè)序列為： hi=(h(key)+i *h1(key)%m i=1,，m1其中 h1(key)=key%11+1回答下列問(wèn)題：（1）對(duì)表中關(guān)鍵字19，32和22進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？【答案】（）對(duì)關(guān)鍵字19，32和22進(jìn)行查找的比較次數(shù)為、3； （）