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