測試一、 選擇題
1.乙個棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是 。
2. 乙個佇列的入隊序列是1、2、3、4，則佇列輸出序列是 。
a.4、3、2、1 b.1、2、3、4 c.1、4、3、2 d.3、2、4、1
3. 判斷乙個迴圈佇列qu (最多元素為m) 為滿佇列的條件是 。
a. qu->front == qu->rear b. qu->front != qu->rear
c. qu->front == (qu->rear + 1) %m d. qu->front != (qu->rear + 1) %m
4.在乙個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，
則執行 。
a. s->next = p->next; p->next=s; b. p->next = s->next; s->next = p;
c. q->next = s; s->next = p; d. p->next = s; s->next = q;
5. 如圖所示的4棵二叉樹中， 不是完全二叉樹。
6. 如圖所示二叉樹的中序遍歷序列是 。
a. abcdgef b. dfebagc c. dbaefcg d. defbagc
7. 已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列 。
a. acbed b. decab c. deabc d. cedba
8. 具有4個頂點的無向完全圖有條邊。
a. 6 b. 12 c. 16 d. 20
9. 已知乙個圖如圖所示，若從頂點a出發按深度搜尋法進行遍歷，則可得到頂點序列為 ；按寬度搜尋法進行遍歷，則可得到頂點序列為 。
a. abecdf b. acfebd c. aebcfd d. aedfcb
10.已知一有向圖的鄰接表儲存結構如圖所示
（1）根據有向圖的深度優先遍歷演算法，從v1頂點出發，所得到的頂點序列是 1 。
（2）根據有向圖的寬度優先遍歷演算法，從v1頂點出發，所得到的頂點序列是 2 。
1 a. v1,v2,v3,v5,v4 b. v1,v2,v3,v4,v5
c. v1,v3,v4,v5,v2 d. v1,v4,v3,v5,v2
2 a. v1,v2,v3,v4,v5 b. v1,v3,v2,v4,v5
c. v1,v2,v3,v5,v4 d. v1,v4,v3,v5,v2
11. 有乙個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當二分查詢值為82的結點時， 次比較後查詢成功。
a. 1 b. 2 c. 4 d. 8
12. 設雜湊表長m=14，雜湊函式h(key)=key%11。表中有4個結點：
addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其餘位址為空
如用二次探測再雜湊處理衝突，關鍵字為49的結點的位址是 。
a. 8 b. 3 c. 5 d. 9
13. 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序方法建立的初始堆為 。
a. 79，46，56，38，40，80 b. 84，79，56，38，40，46
c. 84，79，56，46，40，38 d. 84，56，79，40，46，38
14. 一組記錄的排序碼為（46，79，56，38，40，84），則利用快速排序方法，以第乙個記錄為基準得到的一次劃分結果為 。
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
二、 填空題
1. 下面程式段的時間複雜度是 。
for( i = 0; i < n; i++)
for( j = 0; j < m; j++)
a[i][j] = 0;
2. 在具有n個單元的迴圈佇列中，隊滿時共有個元素的。
3. 在乙個單鏈表中，p所指結點之前插入s所指向結點，可執行如下操作：
（1）s->next = ；
（2）p->next = s；
（3）t = p->data；
（4）p->data = ；
（5）s->data = ；
4. 已知二維陣列a[m][n]採用行序為主方式儲存，每個元素佔k個儲存單元，並且第乙個元素的儲存位址是loc(a[0][0])，則a[i][j]的位址是
5. 乙個稀疏矩陣如圖所示，則對應的三元陣列表示為 。
6. 有一棵樹如圖所示，回答下面問題：
（1）這棵樹的根結點是 ；
（2）這棵樹的葉子結點是 ；
（3）結點c的度是 ；
（4）這棵樹的度是 ；
（5）這棵樹的深度是 ；
（6）結點c的子女是 ；
（7）結點c的父母結點是 。
7. 一棵二叉樹的結點資料採用順序儲存結構，儲存於陣列t中，如圖所示，則該二叉樹的鏈結表示形式為
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8. 在無權圖g的鄰接矩陣中，若a[i][j]等於1，則等於a[j][i] = 。
9. 已知一圖的鄰接矩陣表示，計算第i個結點的入度的方法是
10. 在分塊查詢方法中，首先查詢 ，然後再查詢相應的 。
三、 演算法題
1. 由如圖所示的二叉樹，回答以下問題：
（1）該二叉樹的中序線索二叉樹為 ；
（2）該二叉樹對應的森林是 。
2.已知一棵樹如圖所示，轉化成二叉樹表示為 。
3. 以資料集｛4，5，6，7，10，12，18｝為結點權值所構造的哈夫曼樹為 ，其帶權路徑長度為 。
4. 已知如圖所示的有向圖，請給出該圖的:
（1） 每個頂點的入/出度；
（2） 鄰接矩陣；
（3） 鄰接表；
（4）逆鄰接表。
5.求下面這個圖的廣度優先生成樹和深度優先生成樹
6.用普里母演算法和克魯斯卡爾演算法求下圖的最小生成樹。
7.根據下圖以及圖的鏈式儲存寫出該圖的拓撲序列
8.求下圖的關鍵路徑。
9. 設關鍵字序列為，構造一棵二叉排序樹。
10. 給定乙個陣列10，13，9，7，4，8，15，20，18,按給定順序建立一棵平衡二叉樹。
11. 對下圖的三階b-樹依次執行下列操作。
（1）插入70 （2）插入30
12. 已知雜湊表長為12，關鍵碼集合為，採用除留餘數法構造雜湊函式。解決衝突的方法分別有（1）設為線性探測再雜湊（2）二次探測法處理衝突。並求出每種查方法的平均查詢複雜度。
13. 已知表長為14的雜湊表，採用除留餘數法構造雜湊函式：h(key)=key % 13，鏈位址法處理衝突，將關鍵字集合填入雜湊表；並求其平均查詢複雜度。
14. 給出一組關鍵字t=（12，2，16，30，8，28，4，10，20，6，18）。寫出用下列演算法從小到大的排序時第一趟結束時的序列。
（1）希爾排序（第一趟排序的增量為5）
（2）快速排序（選第乙個記錄為樞軸（分隔））
（3）氣泡排序
15（討論題）假設漢字有6870個，組成700000個詞彙，現在要把700000個詞彙存放在計算機中，便於以後查詢；應該採用哪種資料結構的存放方式，如何存能使查詢效能最好（必須做）。
設計測試資料
1.引言 1.1編寫目的 為了保證專案團隊按時保質地完成專案目標，便於專案團隊成員更好地了解專案情況，使專案工作開展的各個過程合理有序，有必要以檔案化的形式，把對於在專案生命週期內的工作任務範圍 各項工作的任務分解 專案團隊組織結構 各團隊成員的工作責任 團隊內外溝通協作方式 開發進度 經費預算 專...
測試資料的設計
戴德承 摘要 除錯是當今程式設計中至關重要的乙個環節，既考驗了程式設計人員糾查錯誤的能力，更考驗其發現錯誤，即設計測試資料的能力。本文主要從針對性和廣泛性兩方面談談競賽中的測試資料設計。關鍵字 除錯測試資料 一 引論 除錯是程式設計中必不可少的環節，甚至比編寫程式本身還要花更多的時間和精力。這一點在...
資料結構測試 20111119
a rear n front b front l rear c rear front d rear l n front 10 兩個字串相等的條件是 a 兩串的長度相等b 兩串包含的字元相同 c 兩串的長度相等，並且兩串包含的字元相同 d 兩串的長度相等，並且對應位置上的字元相同 11 在一棵度為3的...