北京 1998年上半年自考數據結構試題內容簡介
北京1998年上半年自考數據結構試題
一、 單項選擇題（在每小題的四個備選答案中選出一個正確的答案，並將其號碼填在題幹後的號碼內，每小題2分，共10分）
1.一個棧的輸入序列為1，2，3，4，下麵哪一個序列不可能是這個棧的輸出序列？（ ）
A. 1，3，2，4B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1
2.下列排序方法中，哪一種方法的比較次數與紀錄的初始排列狀態無關？（ ）
A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接選擇排序
3.對n個記錄的文件進行二路歸並排序，總的時間代價為
A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）
4.若一棵二叉樹具有10個度為2的結點，則該二叉樹的度為0的結點個數是（）
A. 9 B. 11 C. 12D. 不確定
5.下麵關於B樹和B+樹的敘述中，不正確的是
A. B樹和B+樹都是平衡的多分樹 B. B樹和B+樹都是可用於文件的索引結構
C. B樹和B+樹都能有效地支持順序檢索 D. B樹和B+樹都能有效地支持隨機檢索
二、 填空題（每空2分，共20分）
1.從邏輯結構看，線性表是典型的 ，樹是典型的 。
2.設有二維數組A[0..9,0..19]，其每個元素占兩個字節，第一個元素的存儲地址為100，若按行優先順序存儲，則元素A[6,6]的存儲地址為，按列優順序存儲，元素A[6,6]的存儲地址為 。
3.若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那麼當i為 且小於n時，結點I的右兄弟是結點，否則結點i沒有右兄弟。
4.求具有最小帶權外部路徑長度的擴充二叉樹的算法稱為 算法。堆排序中建堆的方法稱作 。
5.6階B樹中，每個結點至多包含 個關鍵碼，除根和葉結點外，每個結點至少包含個關鍵碼。
三、 簡答題（每小題6分，共18分）
1.請簡述散列函數在散列法存儲中的作用，並舉出一個散列函數的例子。
2.請簡述散列法存儲中處理碰撞（衝突）的兩類基本方法。
3.請簡述負載因子的定義，為什麼說負載因子是散列法存儲的一個重要參數？
四、 求解下列問題（每小題6分，共30分）
..............................