離線考核
《數(shù)據(jù)結構（高起專）》
滿分100分
一、簡答題（每小題8分，共40分。）
1．什么是有根的有向圖？
2．什么是負載因子？
3．試分析順序存儲結構的優(yōu)缺點。
4．算法的時間復雜度僅與問題的規(guī)模相關嗎？
5．舉例說明散列表的平均查找長度不隨表中結點數(shù)目的增加而增加，而是隨著負載因子的增大而增大。
二、圖示題（每小題15分，共30分。）
1．設待排序文件的初始排序碼序列為 { 32, 38, 10, 53, 80, 69, 32, 05 }，寫出采用冒泡排序算法排序時，每趟結束時的狀態(tài)。
2．設有關鍵字集合為 { 16,05,28,10,09,17 }，散列表的長度為8，用除留余數(shù)法構造散列函數(shù)，用線性探查法解決沖突，并按關鍵字在集合中的順序插入，請畫出此散列(哈希)表，并求出在等概率情況下查找成功的平均查找長度。
三、算法題（每小題15分，共30分。）
1. 二叉樹以二叉鏈表(lchild-rchild表示法)作為存儲結構，試編寫計算二叉樹中葉結點個數(shù)的算法(要求寫出存儲結構的描述)，并分析算法的時間復雜度。
2. 編寫一個求單循環(huán)鏈表中結點個數(shù)的算法，并分析算法的時間復雜度(要求寫出存儲結構的描述)。