1、選擇(共 20分 每題只冇一個正確答案 每題 2分)1. 數(shù)據(jù)結(jié)構(gòu)是 ( )A. 一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元索的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元索的集合2. 若進(jìn)棧序列為 1, 2, 3, 4, 5, 6, 且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為 ()A. 3, 2, 6, 1, 4, 5 B. 3, 4, 2, 1, 6, 5 C. 1, 2, 5, 3, 4, 6D. 5, 6, 4, 2, 3, 13. 求單鏈表屮當(dāng)前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是 ()A. 0 (n) 和 0 (1) B. 0 (1) 和 0 (1) C. 0

2、(1) 和 0 (n) D. O(n) 和 0 (n)4. 已知指針p和q分別指向某單鏈表中笫一個結(jié)點和最后一個結(jié)點。假設(shè)指針s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后 插入上述鏈表應(yīng)執(zhí)行的語句為 ()A.q->next=s->next ； s- next=p ； B.s- next=p；q->next=s->next ； C. p- next 二 s->next ； s->next 二 q； D.s->next 二 q； p->next=s->next ；5. 已知兩數(shù)Sub(s, i, j)的功能是返回串s中從第i個字符起長度為j

3、的了串，函數(shù)Scopy(s, t)的功能為復(fù)制串t到s。若字符串SCIENCESTUDY則調(diào)用函數(shù) Scopy (S, Sub(S, 1, 7) 后得到()A. P 二"SCIENCEB. P二" STUDYC. S=" SCIENCED. S=" STUDY"6. 對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均杳找長度為()A. (N+1)/2B. N/2 C. N D. (l+N)*N/27. 下列陳述中正確的是 ()A.二叉樹是度為2的有序樹B.二叉樹中結(jié)點只有一個孩子時無左右之分C.二叉樹中必有度為2的結(jié)點D.二叉樹中最多

4、只有兩棵子樹，并且有左右之分8. 設(shè)有一個10階的對稱矩陣A,采用下三角壓縮存儲方式，以行序為主存儲，all為第一元素，其存儲地址為1,每個元素占一個地 址空 間，則 &85的地址為 () 。A. 13 B. 33 C. 181).409. 設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范囤是1? n, 其頭尾指針分別為 f 和 r, 則其元素個數(shù)為 ()A. rf B. r-f+1 C. (rf) mod n+1 D. (r-f+n) mod n10. 下列關(guān)鍵字序列中，構(gòu)成小頂堆的是 ()A. 84, 46, 62, 41, 28, 58, 15, 37B. 84, 62, 58, 46, 41, 37,

5、 28, 15)C. 15, 28, 46, 37, 84, 41, 58, 62) D. 15, 28, 46, 37, 84, 58, 62, 41二、填空題 (共 20分每空 2 分)1. 鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是借助(指針)來表示數(shù)據(jù)元素Z間的邏輯關(guān)系。2. 假設(shè)帶頭結(jié)點的非空單循環(huán)鏈表屮僅設(shè)尾指針L,則在第1個數(shù)據(jù)元素結(jié)點Z前?插入指針s所指結(jié)點的語句依次是(s->next=L->next->next; ) , (L->next->next= s;)。3. 無表頭結(jié)點的鏈隊列Q為空的條件是(Q. front=Q. rear二Null)。4. 不含任何字符的串

6、稱為 (空串 ) 。6. 如果排序過程（具有相同關(guān)鍵字的待排記錄的相對位置沒有發(fā)生改變）稱該排序方法是穩(wěn)定的7. 由權(quán)值分別為4, 6, 2, 3的葉子生成一個哈夫曼樹，它的帶權(quán)路徑長度為（29）8. 從空樹起，依次插入關(guān)鍵字73, 11,35, 48, 52, 27, 66構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找成功時的平均查找長度為（25/7）。9. 判斷線索二叉樹屮某結(jié)點指針P所指結(jié)點有左孩子的條件是（P->Lt礙二二0）。三、應(yīng)用題（共50分）1. 簡述順序表和鏈農(nóng)存儲方式的特點。（6分）順序表在邏輯關(guān)系上相鄰的兩個元索在物理位置上也相鄰，因此可以隨機(jī)存儲表中的任一元索。

7、2. （ 1）已知一個二叉樹如圖1所示：寫出該二叉樹的先序，中序，后序遍歷序列（3分）（2） 把圖1對應(yīng)的：義樹轉(zhuǎn)換為所對應(yīng)的森林。（3分）（3） 已知一棵二叉樹的中序遍歷序列為:dfebagc,先序遍歷序列為:abdefcg，請畫出這棵二叉樹（4分）3.對一組關(guān)鍵字:26, 85, 37, 20, 62, 13, 29, 15, 18（只寫每趟結(jié)果）（8分）4.依次輸入序列 （62, 68, 30, 61,25, 14, 53, 47, 90, 84（1） rtfll生成后的二叉排序樹（3分）（2） imi出刪除結(jié)點30后的.:叉排序樹。（4分）采用快速排序方法進(jìn)行排序，用第一個關(guān)鍵字作樞軸

8、,請寫出每趟排序結(jié)果）中元素,生成一棵二叉排序樹5.畫出右圖所示二叉樹的中序線索鏈表的存儲表示（帶頭結(jié)點）（7分）6.利用廣義表的head和tail操作,可從廣義表L= （ a, b）,（c, d）中分解得到原子c,其操作表達(dá)式為head （ head （tai 1（ L）;分別寫出從下列廣義表小分解得到b的操作表達(dá)式（1）L1 二 （ a. , b, c, d ）:（2） L2=（ a） , （ b） , （c） , （d） o （6 分）7.求出下圖的一棵繪小生成樹試畫出構(gòu)造過程（表明你使用的算法以及起始頂點）四、算法設(shè)計（任選一題，共10分）1.假設(shè)以帶頭結(jié)點的單鏈表表示非遞減冇序表，設(shè)

9、計一算法刪除表中所冇值大于（6 分）pHm算法min且小于max （假設(shè)minvmaX同時科放結(jié)點空間。2. 編寫算法統(tǒng)計二叉樹的葉子結(jié)點個數(shù)一、 選擇 ( 共 20 分每題只有一個正確答案每題2 分)1. 一個算法應(yīng)該是 ( ) 。A.程序B.問題求解步驟的描述C.要滿足五個基木特性D. A和C.2. 下面程序段的時間復(fù)雜度為 () 。s=0；for(i=l: i<n ； i+)for(j=l ； j<i: j+)s+=i*j ；A. 0(1)B. 0( logri)C. 0(ri)D. 0(n2)3. 已知拆針 p 和 q 分別指向某單鏈表屮第一個結(jié)點和最后一個結(jié)點。假設(shè)指針

10、s 指向另一個單鏈表中某個結(jié)點，則在 s 所指結(jié)點 Z 后插入上述鏈表應(yīng)執(zhí)行的語句為 () 。A. q->next=s->next ； s>next=p ； B. s->ncxt=p ； q->ncxt=s->ncxt ； C. p->next=s->next ； s->ncxt=q D. s->next=q ； p->ncxt=s->ncxt ；4. 已知循環(huán)隊列的存儲空間為數(shù) mdata21, 且當(dāng)前隊列的頭指針和尾指針的值分別為 8 和 3, 則該隊列的當(dāng)前長度為 () 。A. 5B. 6C. 16D. 175. 通

11、常將鏈串的結(jié)點大小設(shè)登為大于 1 是為了 () 。A.提高串匹配效率 B.提高存儲密度C.便于插入操作D.便于刪除操作6. 表頭和表尾均為空表的廣義表是 () 。A. 0B. () C. () D. (), 0)7. 設(shè)棧的輸入序列是 1, 2, 3, 4則() 不可能是其出棧序列。A. 1, 2, 4, 3,B. 2, 1, 3, 4,C. 1, 4, 3, 2,D. 4, 3, 1, 2,8. 用二叉鏈表表示具有 n 個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為 () 。A. n-1B. n C. n+1D. 2n9. 為便于判別冇向圖屮是否存在回路，可借助于 ( )<>A. 廣度

12、優(yōu)先搜索算法B. 域小生成樹算法C .最短路徑算法 D. 拓?fù)渑判蛩惴?0. 下列四個序列中，哪一個是堆 () 。A. 75, 65, 30, 15, 25, 45, 20, 10 B. 75,65, 45,10, 30, 25, 20, 15 C. 75, 45, 65, 30, 15, 25, 20,10 D. 75,45,65,10,25,30,20,15二、 填空題 ( 共 20 分，每空 2 分)1. 線性表 (al,a2, -,an) 含冇 n 個元素，用數(shù)紐表示，假定刪除表中任一元素的概率和同，則刪除一個元素平均需要移動元素的個 數(shù)是o2.是棧3. 在目標(biāo)串 S0. n-1 二&

13、quot;xwxxyxy "中 T二” xy”，貝U Index （S, T, 0 ）的執(zhí)行結(jié)果是 。4. 山權(quán)值分別為4, 6, 2, 8的葉子生成一個哈夫曼樹，它的帶權(quán)路徑長度為 。5. 三元組表適合存儲矩陣?一6. 從空樹起，依次插入關(guān)鍵字73, 81, 35, 48, 52, 27, 66和構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找成功時的平均查找長度為。7. 在折半査找中，要求被査找的元素必須采用 存儲結(jié)構(gòu)。8. 產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的 o9. 若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后根遍歷應(yīng)對應(yīng)采用二叉樹的 遍歷。10. 對一個棧S,棧底指針用

14、base表示，棧頂指針用top表示，數(shù)組的長度為L,則棧滿的條件為 o三、應(yīng)用題（共50分）1. 簡述順序表和鏈表存儲方式的特點。（5分）2. （ 1）已知一個二叉樹如圖1所示：寫出該二叉樹的先序，中序，后序遍歷序列（3分）（2） 把圖1對應(yīng)的二叉樹轉(zhuǎn)換為所對應(yīng)的森林。（3分）（3） 己知一棵二叉樹的中序遍歷序列為：dfebagc,先序遍歷序列為：abdefcg，請畫出這棵二叉樹（4分）3. 畫出圖2所示二叉樹的中序線索鏈表的存儲表示（帶頭結(jié)點） （5分）4. 已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點的結(jié)構(gòu)為：（8分）Ai_ZL_nBCr一DEi F i 1_dI4CM3%AriI依此鄰接表從

15、頂點C出發(fā)進(jìn)行深度優(yōu)先遍歷。（1）寫出依次從頂點C出發(fā)進(jìn)行的深度優(yōu)先遍歷序列（2）寫出依次從頂點C出發(fā)進(jìn)行的廣度優(yōu)先遍歷序列5.對一組關(guān)鍵字:26, 85, 37, 10, 62, 18, 29, 15采用快速排序方法進(jìn)行排序,用第一個關(guān)鍵字作樞軸,請寫出每趟排序結(jié)果。（只寫每趟結(jié)果）（7分）6.利用廣義表的head和tail操作，可從廣義表L=（a, b）, （c, d） 中分解得到原子c,其操作表達(dá)式為head（head（tai 1 （L）；分別寫出從下列廣義表小分解得到b的操作表達(dá)式。(1 )L1=( (a. , b) , c, d)(2)L2=(a), (b), (c), d)。 (7

16、 分)造過程7. 已知一個無向圖如下圖所示，要求分別用 Prim （普里姆）（假設(shè)以為起點）和Kruskal （克魯斯卡爾）算法生成最小樹，試畫出構(gòu) （8分）四、算法設(shè)計（10分）1. 假設(shè)以帶頭結(jié)點的單鏈表表示非遞減有序表，單鏈表的類型定義如卜一：typedef struct node DataTypc data;struct node *n ext;Li nkNode, *Li nkList;設(shè)計一算法使得插入一個數(shù)值為X的結(jié)點后，單鏈表仍有序。（5分）2. 設(shè)從鍵盤輸入一整數(shù)的序列：al, a2, a3,，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)冇儲輸入的整數(shù)，當(dāng)aiH-1時，將ai進(jìn)棧；當(dāng)ai=

17、-l時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異簾情況（入棧滿等）給出相應(yīng)的信息。（注意：算法中遼接利川棧的基本操作，如push （） , pop(),stackempty ( ), stack len gth等來實現(xiàn)）。（5分）一、單項選擇 (共 20分，每小題 2分)1. 下列關(guān)于存儲結(jié)構(gòu)的敘述中，正確的是 _ 。A. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。B . 線性表的邏輯順序與存儲順序總是致的。C . 散列法存儲的基木思想是山關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。D ?靜態(tài)鏈表具有動態(tài)鏈表的優(yōu)點，它存取表中第i 個元素的時間與 i 無關(guān)。2. 在一個長度為n的順序存儲線性表中，向第i個元秦(IWiWn+1

18、)之前插入一個新元素時，需要從后向前依次厲移 個元索。A. n-iB. n-i-1C. n-i+1D. i3. 設(shè)n個元索的進(jìn)棧序列是a 1 , a 2 , a 3 ,，a n,出棧序列是1,2, 3,，n,若a 3 =1,貝U o 1的值是 。A. 可能是 2B. 定是 2C. 不可能是 2D. 不可能是 34. 設(shè)棧s和隊列Q的初始狀態(tài)為空，元索bl , b 2, b 3 , b 4 , 匕5和匕6依次通過棧S,個元素出棧后即進(jìn)隊列Q,若6個元素出隊的序列是 b 2, b 4 , b 3, b 6 , b 5 , b 1 ,則棧S的容量至少應(yīng)該是 。A. 3B.4 C. 5D.其它5. 由

19、權(quán)值分別為 3, & 6,2,5 的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為 。0. 24A. 53 B. 48 C. 726. 如將一棵有 n 個結(jié)點的完全二叉樹按順序存放方式，存放在下標(biāo)編號為 0, 1, ， n-I 的一維數(shù)組中，設(shè)某結(jié)點下標(biāo)為 k(k>0), 貝其 雙親結(jié)點的下標(biāo)是A. (k-I)/2 B. (k+I)/2 C. k/2 D. k-17. 在一棵高度小于3的二叉樹屮，若結(jié)點的前序序列為ABCDEF則結(jié)點的中序序列有可能為 A. DCEBAI； B. CBDAFE C. BCDAFE D. I'CADBE8. 在下面兒組關(guān)鍵字中，哪個是最小堆_。

20、C. 05,42, 17,94, 55, 13,46D. 94,42, 55,01, 17, 13, 469. 有數(shù)據(jù)53, 30, 37, 12, 45, 24,96), 從空二叉樹開始逐個插入數(shù)據(jù)來形成二義搜索樹，若希架高度最小，貝應(yīng)選擇下面哪個序A. 05, 13, 55, 94, 17,46, 42 B. 05, 42, 13, 55, 94, 17, 46列輸入 A.45, 24, 53, 12, 37, 96, 30B. 37, 24, 12, 30, 53, 45, 9610. 如右圖所示A.1534276C.1354267給出由 7 個頂點組成的無向圖。 從頂點 1出發(fā)，對它進(jìn)

21、行深度優(yōu)先遍彷町能得到的頂點序列是 B.1347625D. 1247653二、判斷題(共20分，每題2分)1. 算法的時間復(fù)雜度取決于代碼的長度和占用內(nèi)存的大小。2. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。3. 可以隨機(jī)訪問任一元素是鏈表不貝有的特點。4. 順序隊列的隊首指針指向的并不是隊首元素。5. 遞歸工？作棧的棧頂記錄必定是當(dāng)前正在執(zhí)行的工作記錄。6. 樹中結(jié)點的度是指從根到該結(jié)點所經(jīng)過分支的條數(shù)。7. AVL樹是高度平衡的二叉樹，其平均捜索長度可以保持在O(log 2 n ) o8. 無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣也可能是對稱的。9. 玄接插入排序的關(guān)鍵碼比較次數(shù)與初始排列冇關(guān)

22、。10. 裝載因子越人，插入元素時發(fā)生沖突的可能性就越人。三、應(yīng)用題(共36分，毎題6分)1.寫出下圖所示的樹的先根遍歷序列，并將它轉(zhuǎn)化為二叉樹。2?設(shè)某帶權(quán)無向圖如圖，畫岀用Kruskal算法牛成最小牛成樹每一步的結(jié)果題5圖亠步插40, 38, 86, 65, 27, 34),使之按關(guān)鍵字遞增次序排序時,寫出按最左兀索作為劃分基準(zhǔn)的快速排序，第一趟排序后的結(jié)果。4. 已知AVL樹如圖，現(xiàn)向其中依次插入關(guān)鍵碼 59和65,分別畫出每 入后AVL樹的形態(tài)，若有旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。5. 試對圖所示的AOE網(wǎng)絡(luò)(1)求每個活動的最早開始時間e ()和最遲開始時間1()L2如一紹兒索的排序碼為(46

23、t 74, K 53. 1譏26,(2)確定哪些活動是關(guān)鍵活動6.設(shè)散列表為HT13，散列函數(shù)為H(key)二key%13,用閉散列法解決沖突,對下列關(guān)鍵碼序列12, 23, 45, 57, 20, 3, 78, 31, 15,36造農(nóng)。采用線性探查法尋找下一個空位,畫出相應(yīng)的散列表，并計算等概率卜？育找成功的平均搜索長度和搜索不成功的平均搜索長度四、算法題 (共 24分)1. 程序填空：完善起泡排序算法。 (6 分 )template <class Type>void BubbleSort(Type aJ, int n)int pass = 1, exchange = 1;whi

24、le (pass < n && exchange = 1) exchange = 0;for (int i = n - 1; i >= pass; i) if (ai - 1 > ai ) swap(ai - 1, ai);first 定2. 設(shè)冇一帶表頭結(jié)點的單鏈表 , first 是指向其表頭結(jié)點的指針，請寫出計算單鏈表長度 Length 的算法。已知單鏈表的結(jié)點類以及 義如下： (8 分 )template <class Type> class ListNode aaiprivate:Type data ;/ 數(shù)據(jù)域ListNode *lin

25、k; / 鏈指針域；IJstNode *f irst;(10 分 )3. 試以二義鏈表作存儲結(jié)構(gòu)，編寫算法統(tǒng)計二義樹中的葉子結(jié)點的個數(shù)，要求用屮序遍歷的思想實現(xiàn)、單項選擇 (共 20分，每小題 2分)A.先進(jìn)性B.正確性C.高效性D.冇窮性1 ?算法與程序的主耍區(qū)別在丁 ?算法必須滿足則算法的時間復(fù)雜度為2?若算法中語句頻度Z和為 T(n) = 123n + n 2 /45 + 6nlog 2 n + 7891,A ? 0(1) C ? 0( nlo £ 2 n )B . ( n - 1)/2D ? ( n + 1)/23. 若長度為 n 的無序線性農(nóng)采用順序存儲結(jié)構(gòu)，在其中插入某個

26、元索的平均移動次數(shù)為4. 在單鏈表中 , 若要在指針P所指結(jié)點后面插入一個由指針q 所指結(jié)點，設(shè) next 域存放指針，則執(zhí)行的語句系列是A. p -> nextq -> next;q 二 P；B. q - next =p -> next;p -> next = q;C? p-> next = q -> next;q -> next = p;D.p -> next = q;q -> next = p -> next;A. ( front + 1 ) % nr etirB? frontr etirC. ( rear + 1 ) % n5

27、?假設(shè)一個循環(huán)順序隊列的隊首和隊尾指針分別為f rontD. frontfront 和rear, 存儲空間大小為 n, 則判斷隊空的條件是6?如果將一棵有n個結(jié)點的完全二叉樹按層次遍歷次序，存放在卜？標(biāo)編號為0,1，n-1的一維數(shù)組中，設(shè)某結(jié)點卜？標(biāo)為k( k>0 ),如果其左孩子存在，則其左孩子結(jié)點的下標(biāo)是A? 2k - 1B. 2kC. 2k + 1D. 2k + 2A.5217463B. 5714623C. 2471536D. 51436727. 若編號 17的 7 個數(shù)按照 5274163的次序進(jìn)棧 , 進(jìn)棧的中間可以出棧，則出棧序列不可能是 .8?用整數(shù) 5, 7, 3, 6,

28、 4 作為五個樹葉的權(quán)值，可以構(gòu)造一棵帶權(quán)路徑長度值為的 Huffman 樹。A. 78B. 62C. 57D. 259?由某樹等價轉(zhuǎn)換得到的二叉樹稱為該樹對應(yīng)的二叉樹，則以下結(jié)論正確的是 oA. 樹的先根遍歷序列與其對應(yīng)二叉樹的前序遍歷序列相同B. 樹的先根遍歷序列與其對應(yīng)二義樹的中序遍歷序列相同C. 樹的后根遍歷序列與其對應(yīng)二叉樹的前序遍歷序列相同D. 樹的后根遍歷序列與其對應(yīng)二叉樹的后序遍歷序列和同10.在一棵空AVL樹中依次插入關(guān)鍵字:55, 71,92, 6, 38, 69, 12, 16, 56, 15,則插入過程中使得樹產(chǎn)生旋轉(zhuǎn)的關(guān)鍵碼個數(shù)是一A. 5B. 7C. 8D. 10判

29、斷題（共 20分，毎題 2分）1. 線性結(jié)構(gòu)的基木特征是每個結(jié)點至多只冇一個直接前驅(qū)和一個直接后繼2. 隊列的特點是先進(jìn)先出，優(yōu)先級隊列也不例外，同樣也是先進(jìn)先出。3. 在棧為空的情況下，不能作出棧操作，否則會產(chǎn)生下溢。4. 二叉樹中每個結(jié)點的兩棵子樹的高度差不人:于1。5. 廣義表(,(2)的衣尾是(2)。6. 如果樹用二叉樹鏈表表示，則判斷某個結(jié)點是不是樹葉的條件是該結(jié)點左、右兩個指針域的值都為空7. 若鄰接表屮有奇數(shù)個邊結(jié)點，則該圖一定為有向圖。8. 9階樹中，除根以外的任何一個非葉子結(jié)點中的關(guān)鍵字?jǐn)?shù)目均在5? 9之間。9. 直接插入排序是一種穩(wěn)定的排序方法。10. 散列衣的裝載因子衣明表的裝滿程度，它與預(yù)設(shè)的最人桶長冇關(guān)。三、應(yīng)用題(共36分，第1-4題每題6分，第5題5分，笫6題7分)1?求廣義表L二( d, ( b , ( ), ( c ) )