1、2006年 A卷試卷A一、 選擇題（每小題分，共10分） 在下列備選答案中選出一個正確的, 將其號碼填在“_”上。   1. 若已有一個棧，輸入序列為A，B，C，D，E，那么下面哪種序列不可能得到？（   ）aABCDE    bEDCBA      cBAEDC      dECDBA   2. 在用鄰接表表示圖時, 對圖進行深度優(yōu)先搜索遍歷的算法的時間復雜度為_。  

2、60;   a. (n)       b. (n+e)      c. (n2)     d. (n3)   3. 下列排序算法中, 只有_排序算法是不穩(wěn)定的。      a. 快速排序     b. 冒泡排序  c. 二路歸并排序      d. 直接插入排序

3、0;  4. 快速排序算法的平均時間復雜度是（      ）aO（n2）   b. O (nlog2n)   c. O(n)       d.  O(logn) 5. 將含100個結點的完全二叉樹從根這一 層開始，每層上從左到右依次對結點編號，根結點的編號為1。編 號為49的結點X的雙親編號為（     ）a24      b.

4、 25       c.23        d.無法確定                                  

5、60;                                                 

6、60;                             二、判斷題：（每小題2分， 共20分）  判斷下列各題是否正確，若正確，在（）內打“”，否則打 “×”。 1. (  ) 線性表只能用順 序方式存放。   2. (  ) 在帶表頭結點的雙循環(huán)鏈表

7、中，每個結點的前趨和后繼指針均不為空。 3. (  ) 如果兩個串含有 相同的字符，則這兩個串相等。   4. (  ) 連通網(wǎng)絡的最小生成樹不一定是唯一的，并且權值可以不相等。 5. (  ) 棧可以作為實現(xiàn) 程序設計語言過程調用時的一種數(shù)據(jù)結構。   6. (  ) 無向圖G（設G中至少有2個頂點）采用鄰接矩陣存儲，若從某頂點開始對無向圖G進行廣度優(yōu)先遍歷, 則所 得的遍歷序列總是唯一的。   7. (  ) 圖的深度優(yōu)先遍歷是通過使用隊列隊列來實現(xiàn)的。   8

8、. (  ) 冒泡排序算法在最好情況下所作的比較元素的次數(shù)為n次。   9. (  )  廣義表的深度是指其中所含的不同原子的個數(shù)。  10. (  ) 一棵非空的二叉樹的后序遍歷序列的最后一個元素是其最右下結點。三、填空（每空分,共20分）: 1. 在帶頭結點的單鏈表L中, 第一個元素所對應的結點的指針 表達式是_。 2. 在雙向循環(huán)鏈表中，在結點*之前插入結點*的語 句序列是：      S-> prior = P-> prior ;

9、60;  S->next=P;   P->prior=S;   _。 3. 如果一個有向圖中沒有，則該圖的全部頂點可 能排成一個拓撲序列。 4. 以下為直接插入排序 的算法。請分析算法，并在_上填充適當?shù)恼Z句。    void straightsort(list r);      for(i=_;i<=n;i+)r0=ri;j=i-1;  5       wh

10、ile(r0.key<rj.key)rj+1=_;j-;  6         rj+1=_; 7. 已知完全二叉樹的第7層有20個結點, 則整個完全二叉樹的葉子結點數(shù)是_。 8. 樹有三種常用的存儲結構，即孩子鏈表法、孩子兄弟鏈表法 和_ . 9 . 所謂二叉排序樹是指滿足如下條件的二叉樹：其中每個結點的值_于其左子樹中任 10. 意結點的值，_于 其右子樹中任意結點的值。 四、解答下列各題（每小題10分， 共40分）   &#

11、160;1. 已知一棵二叉樹的后序、中序序列如下，畫出該二叉樹。后序：中序：  2. .對下面的數(shù)據(jù)表, 寫出 采用快速排序算法排序的每一趟的結果。     （24  10  19  41  7  50  81  58  200  1   12  400）    3. 已知一個無向圖的頂點集為a,b,c,d,e，其鄰接矩陣如下所示      

12、60;          (1)畫出該圖的圖形；（2分）  (2)根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍  歷序列。（8分）   4. 已知一表為（43，21，67，9，40，78，2，41，70，90）,按表中順序依次插入初始為     空的二叉排序樹，要求：    畫出建立的二叉排序樹。（5分）      

13、60;求出在等概率情況 下查找成功的平均查找長度。（5分）  五、算法設計: 分別寫出求解下列問題的算法。（每小題10分， 共10分）1. 已知遞增有序的帶頭結點的單鏈表表示一類集合，設計算法以判斷集合A是否是B的子集。若A是 B的子集，返回TRUE,否則返回FALSE。試卷A答案一、選擇題：                     1. (d) 注意: 入棧和出棧操作可以交替進行，因此

14、就可能 有多種輸出序列了。     2. (b) 在用鄰接表存儲圖時，故整個算法的時間復雜度為O(n+e)。如果用鄰接矩陣表示圖，則算法的時間復雜度就是O(n2)。     3. (a) 這里只有快速排序算法是不 穩(wěn)定的。     4. (b) O (Nlog2N)。     5. (a)。49/2取整 二、判斷題：          1. ( &

15、#215;)。也可以用鏈式方式。     2. ()。由定義可知。     3. ( ×)。由定義可知。     4. (×)。權值應該相等。     5. ()。棧可以作為實現(xiàn)程序設計語言過程調用時的一種數(shù)據(jù)結構。     6. ()。無向圖G（設G中至少有2個頂點）采用鄰接矩陣存儲，所 得的遍歷的結果是唯一的。     7. (

16、15;)。使用棧來實現(xiàn)的。8. (×)。 n-1次。只有在數(shù)據(jù)表已經(jīng)有序時，冒泡排序算法才能達到最好的情況，此時      只需比較一趟，也就是要作（n1）次比較元素的操作即可完成排序。     9. . ( ×)。由定義可知。     10. (×)。很顯然，應該是該樹的根 節(jié)點。 三、填空題：1.  L->next2.     S-> prior->nex

17、t=S; 3.  環(huán)（或回路）4.  25.  rj6.  r07.  42。本題有兩種解答方法，一種是直接計算其中的葉子結點數(shù)。另一種是先 算出總結點數(shù)再算出其中的葉子結點數(shù)，下面分別討論之。（a）直接計算法：已知第7層有20個結點，則這些都是葉子結點，只要再算出第6層中 的葉子數(shù)并求和就可以了。第6層有多少個葉子呢？由完全二叉樹的定義及性質1可 知，整個第6層結點數(shù)為32個， 其中的非葉子結點數(shù)是20/210個（為什么？），因此葉子數(shù)是321022，由此可知葉子總數(shù)是42。（b）     &

18、#160; 先計算總結點數(shù)，再算葉子數(shù)：由性質2可知，前面6層的總 結點數(shù)是63，因此整個二叉樹的結點數(shù)是83。若 整個二叉樹已經(jīng)編號（編號方式見教科書），則可推知最大編號（83）結點的父結點（編號41）為編號最大的非葉子結點，從4283全為葉子結點，即葉子總數(shù)是8341。8.雙親表示法     9. 大于    10. 小于       四、解答下列各題：1.       （10分）  符合條件的二叉樹如

19、圖1-4D              A            B               H       C     

20、60; F       I       L     D   E  G            J K     圖1-4 二叉樹          本題較典型， 其

21、求解方法在數(shù)據(jù)結構算法設計指導中已經(jīng)作了詳細介紹，故不多述。2.       （10分） 快速排序各趟的結果如下，其中用 所括的元素為不會再發(fā)生位置變化 的元素。   （24  10  19  41  7  50  81  58  200  1   12  400）一趟：(12  10  19  1  7 )  24  (81&

22、#160; 58  200  50  41  400)二趟：(7  10  1)  12  (19)  24  (41  58  50) 81(200  400)三趟：(1)  7  (10)  12  (19)  24  41  (58  50)  81  200  (400)四趟：1  7  10  12  19&

23、#160; 24  41  50  58  81  200  4003.(1)   （2分）                                    

24、60; a         b                                          

25、60;                c           e                        

26、0;                                   d (2) （8分）深度優(yōu)先序 列：a b d c e  廣度優(yōu)先序列：a b e d c 4.(1) （5分）D     &

27、#160;           43                21               67          &#

28、160;                 9      40              78               

29、;                        2          41         70      90   (2) （5分）&#

30、160;   ASL=(1+2*2+3*3+4*4)/10=3  五、算法設計（每小題10分，共10分）    1. 均約定按遞增有序次序排列，采用帶 頭結點的單鏈表存儲時，算法如下:        BOOL  judge( node* A, node* B)        P= A->next;  Q= B->next;  num= 0;         while (P!=NULL) && (Q!=NULL)  &