1、1. 以下與數據的存儲結構無關的術語是（ c ）C、哈希表 2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ） B、1083. 假設帶頭結點的單向循環鏈表的頭指針為head,則該鏈表為空的判定條件是（ C ）C、headnext= =head 4. 若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現的出棧序列是（ D ）D、2，3，5，1，6，45. 下列關鍵字序列中，構成小根堆的是（ A ）A、12，21，49，33，81，56，69，41 6. 下列數據結構中，不屬于二叉樹的是（ A ）A、B樹 7. 用順序存儲的方法來存

2、儲一棵二叉樹，存放在一維數組A1.N中，若結點Ai有右孩子，則其右孩子是（ C ）。 C、A2i+1 8. 設樹T的高度為4，其中度為1、2、3、4的結點個數分別為4、2、1、1，則T中葉子數為（ D ） D、 89. 有數據53，30，37，12，45，24，96，從空二叉樹開始逐個插入數據來形成二叉排序樹，若希望高度最小，則應選擇下面哪個序列輸入（ B ）B、37，24，12，30，53，45，9610. 對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是（ C ）C、5，1，6，3，4，2 11. m階B-樹中所有非終端（除根之外）結點中的關鍵字個數必須大于或等于( B ) B、m/2-

3、112. 散列文件也稱為( C ) B 、索引文件13. 數據結構是（ D ）D、相互之間存在一種或多種特定關系的數據元素的集合14. 從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（ C ）C、線性結構和樹型結構 15. 設p為指向雙向循環鏈表中某個結點的指針，p所指向的結點的兩個鏈域分別用pllink和prlink表示，則同樣表示p指針所指向結點的表達式是（ D ） D、pllinkrlink16. 若棧采用順序存儲方式存儲，現兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ B ）B、 top1+1=top

4、2 17. 若一棵二叉樹有11個葉子結點，則該二叉樹中度為2的結點個數是（ A ）A、1018. 樹的先根序列等同于與該樹對應的二叉樹的（ A ）A、先序序列19. 下面關于哈希(Hash，雜湊)查找的說法正確的是( C )C、不存在特別好與壞的哈希函數，要視情況而定20. 下列序列中，（ D ）是執行第一趟快速排序后所得的序列。 D、 68，11，69，23，18 93，7321. 下列關鍵字序列中，構成小根堆的是( D )D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件屬于( C ) C、索引順序文件 23. 下面程序段的時間復雜度為（ C ）fo

5、r (i=0; im; i+)for (j=0; jnext=s-next；s-next=p； 25. 為便于判別有向圖中是否存在回路，可借助于（ D ）D、拓撲排序算法26. 若以S和X分別表示進棧和退棧操作，則對初始狀態為空的棧可以進行的棧操作系列是（ D ）D、SSSXXSXX27. 設有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應該是( B )B、3 28. 假設以數組Am存放循環隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位 置為（

6、B ）。B、(rear-length+m)%m 29. 在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（ D ）。D、rear-next=s;rear=s;30. 對于哈希函數H(key)=key%13,被稱為同義詞的關鍵字是（ D ）D、25和5131. 采用二叉鏈表存儲的n個結點的二叉樹，共有空指針（ A ）個。A、n+132. 連通網的最小生成樹是其所有生成樹中（ D ）D、邊的權值之和最小的生成樹33. 對記錄序列(314，298，508，123，486，145)依次按個位和十位進行兩趟基數排序之后所得結果為（ B ） B、508，314，123，1

7、45，486，29834. 任何一個無向連通圖的最小生成樹( C )。C、一棵或多棵 35. 無向圖的鄰接矩陣是一個( C ) C、對稱矩陣 36. 設無向圖G-=(V,E)和G=(V,E),如G為G的生成樹，則下列說法中不正確的是( B )。B、G為G 連通分量37. 以v1為起始結點對下圖進行深度優先遍歷，正確的遍歷序列是（ D ）D、 v1，v2，v5，v6，v7，v3，v438. 下面幾個符號串編碼集合中，不是前綴編碼的是（ B ）B、0,1,00,1139. 希爾排序的增量序列必須是（B ）。B、遞減的 40. 采用起泡排序法對n個關鍵字進行升序排序，若要使排序過程中比較關鍵字的次數

8、最多，則初始時的序列應滿足條件（ D ） D、關鍵字從大到小排列41. 在下列內部排序中( A )是不穩定的。A、希爾排序42. 分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是( C )。A、（100，80， 90， 60， 120，110，130） 43. 在查找過程中，沖突指的是（ C ）。C、不同鍵值對應相同的存儲地址44. 對有14個元素的有序表A1.14作二分查找，查找元素A4時的被比較元素依次為（ D ）。D、A7，A3，A5，A445. 以v1為起始結點對下圖進行廣度度優先遍歷，正確的遍歷序列是（ A ）A、 v1，v2，v3，v4，v5，v6，v7二、填空題

9、(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)1. 數據的物理結構包括 數據元素 的存儲和 數據之間關系 的存儲。2. 若一個算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時間復雜度為 nlogn 。 3. 下面程序段的時間復雜度是 。 i=1； while (inext-next=L 17. 邊 種不同的拓撲序列。18. 從空樹起，依次插入關鍵字1l，27，35，48，52，66和73構造所得的二叉排序樹，在等概率查找的假設下，查找成功時的平均查找長度為 384 。19. 帶頭結點的雙循環鏈表L中只有一個元素結點的條件是 隊列 。 20. 求最小生

10、成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中 邊稠密 、邊稀疏 的數目正相關。21. 已知一棵完全二叉樹中共有768結點，則該樹中共有 5 個葉子結點。22. 實現圖的廣度優先搜索，除了一個標志數組標志已訪問的圖的結點外，還需要 8、64 存放被訪問的結點以實現遍歷。23. Prim（普里姆）算法適用于求 2h-1 的網的最小生成樹；kruskal（克魯斯卡爾）算法適用于求 2h-1 的網的最小生成樹。24. 對長度為20的有序表進行二分查找的判定樹的高度為 n-1 。25. 設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為 n ，有_ 個葉子結點。26. 高度為h的完全二叉樹

11、中最少有 棧 個結點，最多有 個結點。27. 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有 3 條邊。28. 構造n個結點的強連通圖，至少有 O(n2) 條弧。29. 表達式求值是 （42,13,94,55,05,46,17） 應用的一個典型例子。30. 設棧S和隊列Q的初始狀態為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應該是 。31. 快速排序算法在最差的情況下其時間復雜度是 。32. 對序列55，46，13，05，94，17，42進行基數排序，第一趟排序后的結果是 。

12、三、應用題（本大題共5小題，每小題6分，共30分）1. 已知二叉樹的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態 2. 如圖請給出鄰接表、鄰接矩陣及逆鄰接表。V1V3V2V4參考答案如下：（1）鄰接表：(注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標值-1) vertex firstedge next （2）逆鄰接表：（3）3. 。答案：原來的電文為：eatst4. 請畫出下圖所示的樹所對應的二叉樹，并寫出對應二叉樹的先序遍歷和中序遍歷。12345678答案：12345678先序遍歷為：12345687 中序遍歷為：34867521

13、5. 設散列表為HT13, 散列函數為 H (key) = key %13。用閉散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用線性探查法尋找下一個空位, 畫出相應的散列表, 并計算等概率下搜索成功的平均搜索長度。答案：使用散列函數 H(key) = key mod 13，有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.利用線性探查法造表： 0 1 2 3 4

14、 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功的平均搜索長度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 6. 已知帶權圖G如圖所示，畫出圖G的一棵最小生成樹。答：7. 假設用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構成，這8個字母在電文中出現的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，請為這8個字母設計哈夫曼編碼。哈夫曼編碼為：a

15、:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000注意：答案不唯一8. 試用權集合12,4,5,6,1,2構造哈夫曼樹，并計算哈夫曼樹的帶權路徑長度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=699. 畫出與如圖所示森林對應的二叉樹。答：10. 已知一個散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m-1其中： h1(key)

16、=key%11+1回答下列問題：（1）對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？答：（）對關鍵字35、20、33和48進行查找的比較次數為、；（）平均查找長度11. 請畫出與下列二叉樹對應的森林。答：12. 對于給定結點的關鍵字集合K=5，7，3，1，9，6，4，8，2，10，（1）試構造一棵二叉排序樹；（2）求等概率情況下的平均查找長度ASL。答：74312596108（2）ASL=(1*1+2*2+3*4+4*3)/10=2.913. 給出下圖對應的鄰接矩陣，并給出A，B，C三個頂點的出度與入度 答案

17、: 鄰接矩陣為： A B C D E F其中頂點A的入度為2，出度為1；其中頂點B的入度為2，出度為2；其中頂點C的入度為1，出度為3；14. 已知圖5.32如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）543223356abdfce答：終點最短路徑求解過程b6 (a,b)5 (a,c,b)c3 (a,c)d6 (a,c,d)6 (a,c,d)e7 (a,c,e)7 (a,c,e)7 (a,c,e)f9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f15. 閱讀下列算法，并回答問題：（1）假設串由合法的英文字母和空格組成

18、，并以0作結束符。設串s=”Iamastudent”(表示空格符)，寫出f30（s）的返回值；（2）簡述算法f30的功能。int f30 (char*s)答案：(1) 4(2)算法功能：統計單詞的個數。16. 閱讀下列函數,并回答問題：（1）假設隊列q中的元素為(a,b,c,d,e),其中“a”為隊頭元素。寫出執行函數調用Conv(&q)后的隊列q；（2）簡述算法Conv的功能。答案：（1） e，d，c，b，a（2） 將隊列里的值反轉17. 閱讀下列函數,并回答問題：已知整形數組L1.8中的元素依次為（19，18，15，17，16，13，12，10），閱讀下列函數，并寫出執行函數調用sort(

19、L, 8)時，對L進行的頭兩趟（pass分別為0和1）處理結果。答案：（1）第一趟（pass = 0）19 15 18 16 17 12 13 10（2）第二趟（pass = 1）19 15 16 18 12 17 10 13keynext18. 已知帶頭結點的單鏈表中的關鍵字為整數，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設散列表的長度為m，散列函數為Hash(key)=key%m。鏈表的結點結構為： 。請在空缺處填入適當內容，使其成為一個完整算法。void f33 (LinkList L, LinkList H, int m)答案：（1） NULL （2）p-next=Hj

20、 p=q19. 下列函數的功能是，對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表（表中不存在值相同的數據元素）進行如下操作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內容，使其成為一個完整的算法。答案：（1）pre-next=pb （2）pre-next=pa （3）pre-next=pb20. 閱讀算法f30，并回答問題：下列算法為有向圖拓撲排序,請在空缺處填入合適的內容，使其成為一個完整的算法。答案：(1）top=-1 （2）top=graphj.count （3）graphk.count=021. 閱讀算法f31，并

21、回答問題：下列算法功能為在數組a的前n(n=1)個元素中找出第k(1=kai+1,將二者交換;以后重復上述二趟過程,直至整個數組有序。請在空缺處填入合適的內容，使其成為一個完整的算法。答案： (1)ai=t (2)(i=2;inext) return ERROR; p=head-next; q=p-next; p-next =NULL; while(q) p=q; q=q-next; p-next=head-next; head-next=p; 2. 編寫一個函數，要求借助一個棧把一個數組中的數據元素逆置。其中，棧類型為SeqStack，可以直接使用InitStack(SeqStack*)、P

22、ush(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函數。參考答案：void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;in;i+) /數組元素依次入棧Push(s,arri);for(i=0;ileft); num2=twochild1(b-right);if ( b-left!=NULL&b-right!=NULL) return (num1+num2+1); else return (num1+num2); 4. 假設以帶雙親指針的二叉鏈表作為二叉樹的存

23、儲結構，其結點結構的類型說明如下所示：typedef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; /左右孩子指針 struct node *parent; /指向雙親的指針 BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結點的指針，可借助該結構求得px所指結點在二叉樹的中序序列中的后繼。(1)就后繼的不同情況，簡要敘述實現求后繼操作的方法；參考答案：（1）分兩種情況討論當*px的右子樹不為空時，則從*px的右孩子開始，沿其左孩子往

24、下查找，直到找到一個沒有左孩子的節點為止，則該結點為*px在中序序列中的后繼；當*px的右孩子為空時，則沿*px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，則該祖先結點為*px在中序序列中的后繼。(2)編寫算法求px所指結點的中序序列后繼，并在算法語句中加注注釋。（2）BinTree f34(BinTree px)BinTree q=px-rchild;if(q!=NULL)/沿左孩子往下查找px=q;while(px-lchild!=NULL)px=px-lchild;else/沿雙親指針鏈向上查找while(px!=NULL & px-rchild=q)q=px;px=px-parent;return px;/返回所找到的中序序列后繼結點的指針 /或者無后繼結點時返回空指針5. 已有鄰接表表示的有向圖，請編程判斷從第u頂點至第v頂點是否有簡單路徑，若有則印出