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