一、選擇題(2’x10)

1. 在非空雙向循環鏈表中q所指的結點前插入一個由p所指的鏈接點的過程依次為：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。

(A)rlink(q)←p (B)rlink(llink(q))←p

(C)rlink(llink(p))←p (D)rlink(rlink(p))←p

2. 若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數組B 中，則在B中確定aij(i

(A) (B)
(C) (D)
3. 某堆棧的輸入序列為a，b，c，d，下面的四個序列中，_________不可能是它的輸出序列。

(A)a，c，b，d (B)b，c，d，a

(C)c，d，b，a (D)d，c，a，b

4. 深度為h的滿m叉數的第k層有_________個結點。(1≤k≤h)

(A)mk-1 (B)mk-1 (C)mh-1 (D)mh-1

5. 具有10個葉結點的二叉樹中有_________個度為2的結點。

(A)8 (B)9 (C)10 (D)11

6. 要連通具有n個頂點的有向圖，至少需要_________條邊。

(A)n-1 (B)n (C)n+1 (D)2n

7. 已知有向圖G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，
E={，，，，，，
，，}，G的拓撲序列是_________。

(A)v1，v3，v4，v6，v2，v5，v7 (B)v1，v3，v2，v6，v4，v5，v7

(C)v1，v3，v4，v5，v2，v6，v7 (D)v1，v2，v5，v3，v4，v6，v7

8. 若查找每個記錄的概率均等，則在具有n個記錄的連續順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為_________

(A) (B) (C) (D)n

9. 下面關于B樹和B+樹的敘述中，不正確的是_________

(A)B樹和B+樹都是平衡的多分樹。

(B)B樹和B+樹都可用于文件的索引結構。

(C)B樹和B+樹都能有效地支持隨機檢索。

(D)B樹和B+樹都能有效地支持順序檢索。

10. 下面給出的四種排序方法中，排序過程中的比較次數與排序方法無關的是_________。

(A)選擇排序法 (B)插入排序法

(C)快速排序法 (D)堆積排序法

二、(10’)

有實現同一功能的兩個算法A1和A2，其中A1的時間復雜度為T1=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好。

三、(5’+10’+10’+5’)

為建立一個具有n份檔案的檔案庫需要設計如下數據結構：所有檔案存儲在一個動態存儲的雙向循環鏈表中，每份檔案占用一個地址連續的存儲塊成為該鏈表中的一個結點，整個鏈表為一個鏈接順序文件，取名為dossier(檔案)，同時分別建立兩個索引，其中一個為稠密索引，取名為dense，另一個是表長為m的雜湊表索引，取名為bucket，該雜湊表采用鏈地址法處理沖突。上述兩種索引中都分別存儲在每一份檔案的存儲地址。

1. 請分別畫出dossier、dense、bucket的結構示意圖。

2. 分別設計出dossier、dense、bucket的數據結點的結構，即為了滿足檔案的插入、刪除、查找的操作，每個結點必要的數據項的名稱及其作用。

3. 針對上述結構，用簡明的文字分別說明所有可能的查找方法(查找路徑)。

4. 分別給出每一種查找方法在查找成功時的平均查找長度。

四、(10’)

已知num為無符號十進制整數，請寫一非遞歸算法，該算法依次輸出num對應的r進制的各位數字。要求算法中用到的堆棧采用線性鏈表存儲結構。(1

五、(10’)

已知長度為n的線性表A采用順序存儲結構，請寫一時間復雜度為O(n)、空間復雜度為O(1)的算法，該算法刪除線性表中所有值為item的數據元素。(O(1)表示算法的輔助空間為常量)

六、(10’x2)

設有一集合，其成員為任意類型的數據元素，基本操作為插入、刪除和成員測試。若為該集合設計一個集合類型，則

1. 該集合可以采用哪幾種存儲結構？就存儲空間開銷以及操作而言，分別說明每種存儲結構的特點