1、第1頁共129頁貴州大學(xué)理學(xué)院數(shù)學(xué)系信息與計(jì)算科學(xué)專業(yè)《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案(2003200420032004學(xué)年第學(xué)年第2學(xué)期學(xué)期)一、一、單項(xiàng)選擇題單項(xiàng)選擇題1對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為（）。(A)、正確性、正確性(B).可行性可行性(C).健壯性健壯性(D).輸入性輸入性2設(shè)設(shè)S為C語言的

2、語句語言的語句計(jì)算機(jī)執(zhí)行下面算法時(shí)，算法的時(shí)間復(fù)雜度為計(jì)算機(jī)執(zhí)行下面算法時(shí)，算法的時(shí)間復(fù)雜度為（）。f(i=n1；i=0；i)f(j=0；jnextpnext=Q.frontnext（B）、p=Q.frontnextQ.frontnext=pnext（C）、p=Q.rearnextpnext=Q.rearnext（D）、p=QnextQnext=pnext9HuffmanHuffman樹的帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度WPLWPL等于（等

3、于（）（A）、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和（B）、所有結(jié)點(diǎn)權(quán)值之和、所有結(jié)點(diǎn)權(quán)值之和bcd∧afrontrear第3頁共129頁2給定表（給定表（19142215202156101914221520215610）.（8分）分）（1）按元素在表中的次序，建立一棵二叉排序樹按元素在表中的次序，建立一棵二叉排序樹（2）對(duì)(1)(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。中所建立的二叉排序樹進(jìn)行中序遍

4、歷，寫出遍歷序列。（3）畫出對(duì)畫出對(duì)(2)(2)中的遍歷序列進(jìn)行折半查找過程的判定樹。中的遍歷序列進(jìn)行折半查找過程的判定樹。3已知二個(gè)稀疏矩陣已知二個(gè)稀疏矩陣A和B的壓縮存儲(chǔ)三元組表如下：的壓縮存儲(chǔ)三元組表如下：ABijVijV135525224633725241342115299529558寫出寫出ABAB壓縮存儲(chǔ)的三元組表。壓縮存儲(chǔ)的三元組表。（5分）分）4已知一維數(shù)組中的數(shù)據(jù)為（已知一維數(shù)組中的數(shù)據(jù)為（18122553181225

5、531818）試寫出插入排序（升序）試寫出插入排序（升序）過程。并指出具有過程。并指出具有n個(gè)元素的插入排序的時(shí)間復(fù)雜度是多少？個(gè)元素的插入排序的時(shí)間復(fù)雜度是多少？(5(5分)5已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)A開始的最小生成樹。開始的最小生成樹。(8(8分，要有分，要有過程過程)ABCDEF（1）求從頂點(diǎn)）求從頂點(diǎn)A開始的最小生成樹。開始的最小生成樹。（2）分別畫出以）分別畫出以A為起點(diǎn)的為起點(diǎn)的D

6、FSDFS生成樹和生成樹和BFSBFS生成樹。生成樹。6已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：ABCDEF0.150.150.150.150.10.10.10.10.20.20.30.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(7(7分，要有過程分，要有過程)。????????????????????????????????????64