1、一、應用題1. 已知線性表的存儲結構為順序表，閱讀下列算法，并回答問題：（1）設線性表L=（51，-9，-6，39，0，-11，34，70，-16），寫出執(zhí)行算法f11(&L)后的L狀態(tài)；（2）簡述算法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. 假設以帶頭結點的單鏈表表示線性表,

2、閱讀下列算法f22,并回答問題:(1)設線性表為( a1, a2, a3, a4, a5, a6, a7 ), 寫出執(zhí)行算法f22后的線性表；(2)簡述算法f22的功能。 void fun(LNode *L)/L為帶頭結點單鏈表的頭指針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ù)結點序號為奇數(shù)的那些結點。3.假設以數(shù)組seqnm存放循環(huán)隊列的元素，設變量rear和quelen分別指示循環(huán)隊列

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

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

5、寫出執(zhí)行f33 (&Q,&Q1,&Q2)之后隊列Q、Q1和Q2的狀態(tài)；（2）簡述算法f33的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分別是隊列初始化、入列、出隊和判隊空的操作）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隊列中的數(shù)據(jù)全部出隊；不小于0的進Q1，否則進Q2。ABCGDEF7. 已知二叉樹如右圖所示。（1）畫出該二叉樹的二叉鏈表；（2）分別寫出該二叉樹的先根、中根和后根遍歷序列。【答案】 (1) 二叉鏈表:DACBEGF（2）先根遍歷序列：ABDCEGF中根遍歷序列: DBAEGCF后根遍歷序列: DBGEFCA8、假設一棵二叉樹的先根遍歷序列為ABCDEFGH，中根遍歷序列為CDBEGFHA。(1)畫出該二叉樹；（2）寫出后根遍歷序列。DBEHGFAC【答案】(1)二叉樹（2）后根遍歷序列:DCGHFEBA9、假設一棵二叉樹的中根遍歷序列為DGBE

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

8、10，14。請畫出對應的哈夫曼編碼樹（按照每個結點的左子樹根結點的權小于等于右子樹根結點的權的次序構造），并求出每個字符的哈夫曼編碼。【答案】哈夫曼編碼ADGHMST00011001100000011010112. 假設通信電文使用的字符集為 S，T，B，F(xiàn)，C，字符的哈夫曼編碼依次為：011，10，00，010和11。 (1)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結點中標注相應字符； (2)若這些字符在電文中出現(xiàn)的頻度分別為：4，7，5，2和9，求出電文的總長度。160000111111275 6 7 2 4 9BFSTC【答案】（1）編碼哈夫曼樹 (2) 電文的總長度=4*3+7*2+5

9、*2+2*3+9*2=60v2v3v1v5v413、已知一個有向圖如右圖所示。(1)試畫出它的鄰接表。（表結點按頂點編號遞減排列） 1 2 3 4 5 5 4 3 2 4 4 2 (2)分別求出從v1出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到的頂點序列。【答案】（1） (2)深度優(yōu)先搜索序列：v1，v 4，v 3， v 5，v 2 廣度優(yōu)先搜索序列：v1，v 4，v 3， v 2，v 514、已知一個AOV網(wǎng)如右圖所示。V51V11V41V21V61V31(1)試畫出它的鄰接鏈表。（表結點按頂點編號遞減排列）(2)試寫出按照拓撲排序算法得到的拓撲序列。1 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、請用普里姆算法(從頂點V3開始)和克魯斯卡爾算法構造下圖所示網(wǎng)絡的最小生成樹，按照并入最小生成樹中邊的次序填寫下表，并畫出最小生成樹。次序1 2 345始 點 終 點權 值14v1v4v5 v2v3V610818161210151920【答案】（1）普里姆算法14v1v4v5 v2v3V68161210構造過程： 最小生成樹：次序1 2 345始 點V3V1V3V2V2終 點V1V4V2V5V6權 值121416810（2）克魯斯卡爾算法14v1v4v5 v

11、2v3V68161210構造過程： 最小生成樹：次序1 2 345始 點V2V2V3V1V3終 點V5V6V1V4V2權 值81012141616、設關鍵字序列（17,8,13,25,24,16,3,19,1），寫出用下列方法排序時,第一趟結束時關鍵字的排列狀態(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、對有序表12,24

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

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

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