【正文】 貴州大學理學院數(shù)學系信息與計算科學專業(yè)《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案(20032004學年第2學期)一、 單項選擇題1．對于一個算法，當輸入非法數(shù)據(jù)時，也要能作出相應(yīng)的處理，這種要求稱為（ ）。 (A)、正確性 (B). 可行性 (C). 健壯性 (D). 輸入性2．設(shè)S為C語言的語句,計算機執(zhí)行下面算法時，算法的時間復雜度為（ ）。for(i=n1；i=0；i) for(j=0；ji；j++) S； (A)、n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法適用于（ ）。（A）、有序順序表 （B）、有序單鏈表（C）、有序順序表和有序單鏈表都可以 （D）、無限制4．順序存儲結(jié)構(gòu)的優(yōu)勢是（ ）。 （A）、利于插入操作 （B）、利于刪除操作 （C）、利于順序訪問 （D）、利于隨機訪問5．深度為k的完全二叉樹，其葉子結(jié)點必在第（ ）層上。 （A）、k1 （B）、k （C）、k1和k （D）、1至k6．具有60個結(jié)點的二叉樹，其葉子結(jié)點有12個，則度過1的結(jié)點數(shù)為（ ）（A）、11 （B）、13 （C）、48 （D）、377．圖的DepthFirst Search(DFS)遍歷思想實際上是二叉樹（ ）遍歷方法的推廣。 （A）、先序 （B）、中序 （C）、后序 （D）、層序8．在下列鏈隊列Q中，元素a出隊的操作序列為（ ）b c d ∧afrontrear Q （A）、p=next。 pnext= next。 （B）、p=next。 next=pnext。 （C）、p=next。 pnext= next。 （D）、p=Qnext。 Qnext=pnext。9． Huffman樹的帶權(quán)路徑長度WPL等于（ ）（A）、除根結(jié)點之外的所有結(jié)點權(quán)值之和 （B）、所有結(jié)點權(quán)值之和（C）、各葉子結(jié)點的帶權(quán)路徑長度之和 （D）、根結(jié)點的值10．線索二叉鏈表是利用（ ）域存儲后繼結(jié)點的地址。 （A）、lchild （B）、data （C）、rchild （D）、root二、填空題1． 邏輯結(jié)構(gòu)決定了算法的 ，而存儲結(jié)構(gòu)決定了算法的 。2． 棧和隊列都是一種 的線性表，棧的插入和刪除只能在 進行。3． 線性表（a1,a2,…,an）的順序存儲結(jié)構(gòu)中，設(shè)每個單元的長度為L，元素ai的存儲地址LOC(ai)為 4． 已知一雙向鏈表如下(指針域名為next和prior)： y x e q p現(xiàn)將p所指的結(jié)點插入到x和y結(jié)點之間，其操作步驟為： ； ； ； ；5．n個結(jié)點無向完全圖的的邊數(shù)為 ， n個結(jié)點的生成樹的邊數(shù)為 。6．已知一有向無環(huán)圖如下： BACDFEG 任意寫出二種拓撲排序序列： 、 。7．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為 ，層序遍歷序列為 。三、應(yīng)用題1． 設(shè)散列函數(shù)H(k)=k % 13,設(shè)關(guān)鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測法處理沖突。(6分)(1) 構(gòu)造HASH表。(2) 分別求查找成功和不成功時的平均查找長度。2． 給定表（19,14,22,15,20,21,56,10）.（8分）（1） 按元素在表中的次序，建立一棵二叉排序樹（2） 對(1)中所建立的二叉排序樹進行中序遍歷，寫出遍歷序列。（3） 畫出對(2)中的遍歷序列進行折半查找過程的判定樹。3． 已知二個稀疏矩陣A和B的壓縮存儲三元組表如下： A BijVijV135252246337252413421529529558寫出AB壓縮存儲的三元組表。（5分）4． 已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）, 試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時間復雜度是多少？(5分)5． 已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點A開始的最小生成樹。(8分，要有過程) A B C D E F（1）求從頂點A開始的最小生成樹。（2）分別畫出以A為起點的DFS生成樹和BFS生成樹。6．已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表：ABCDEF把這些字母和頻率作為葉子結(jié)點及權(quán)值，完成如下工作(7分，要有過程)。（1） 畫出對應(yīng)的Huffman樹。（2） 計算帶權(quán)路徑長度WPL。（3） 求A、B、C、D、E、F的Huffman編碼。7． 已知有如下的有向網(wǎng)： 2 5 36 4 10 6 1 2 2 AEBDC求頂點A到其它各頂點的最短路徑（采用Dijkstra算法，要有過程）。（6分）三、 設(shè)計題（30分，每題10分,用C語言寫出算法，做在答題紙上）1． 已知線性表（a1,a2,…,an）以順序存儲結(jié)構(gòu)為存儲結(jié)構(gòu)，其類型定義如下： define LIST_INIT_SIZE 100 //順序表初始分配容量 typedef struct { Elemtype *elem。 //順序存儲空間基址 int length。 //當前長度（存儲元素個數(shù)） }SqList。設(shè)計一個算法，刪除其元素值為x的結(jié)點（假若x是唯一的）。并求出其算法的平均時間復雜度。其算法函數(shù)頭部如下： Status ListDelete(Sqlist amp。L,Elemtype x) {…… }an…a2a12．設(shè)順序棧如左圖所示。 其中結(jié)點定義如下： top typedef struct { Elemtype *base。 //棧底指針Elemtype *top。 //棧頂指針 }Stack。設(shè)計算法，將棧頂元素出棧并存入e中． base3．設(shè)二叉鏈樹的類型定義如下： typedef int Elemtype。 typedef struct node{ Elemtype data。 struct node *lchild, *rchild。 }BinNode, *BinTree。試寫出求該二叉樹葉子結(jié)點數(shù)的算法: Status CountLeaves(BinTree amp。root,int amp。n) {//n is the number of leaves…… }答案：選擇題（每題1分）C D A D C D A B C C 一、 填空題1． 設(shè)計、實現(xiàn)2． 特殊、棧頂3． LOC（a1）+(i1)*L4． pnext=qnext。qnextprior=p。 qnext=p。pprior=q。5． n(n1)/n16． ADCBFEG、ABCDEFFG7． ABC、ABC二、 應(yīng)用題1 （1）Hash表（4分）地址0123456789101112關(guān)鍵安132164572282412探測次數(shù)171231311（2）查找成功的平均查找長度：（1分） （5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找長度：（1分） （2+1+9+8+7+6+5+4+3+2+1）/13=2（1）、構(gòu)造（3分） 19 14 22 10 15 20 56 21(2)、10 14 15 19 20 21 22 56（2分）（3）、（3分）(5分，)ijv1352463374134215218558 初始關(guān)鍵字： [18] 12 25 53 18 第 一 趟：[12 18] 25 53 18第 二 趟：[12 18 25] 53 18第 三 趟：[12 18 25 53] 18第 四 趟：[12 18 18 25 53] （4分） O（n2）（1分）。7分（1）4分A B 1 C 3 2 5 D 4 E F（2）4分(1) 3分 E F A B C D （2）WPL=*3+*3+*2+*3+*3+03*21= (1分)（3）A：010 B：011 C：110 D：111 E：00 F；10 （3分）1AB：（A、B） 1分AC：（A、D、C） 2分AD：（A、D） 1分 AE：（A、D、E） 2分 三，設(shè)計題（20分）(10分)Status ListDelete(Sqlist amp。L,ElemType x){ int i,j。 for(i=0。iLlength。i++)if(Lelem[i]==x) break。 if(i=Llength) return ERROR。 for(j=i。jLlengthi1。j++) Lelem[j]=Lelem[j+1]。 Llength。} （8分）平均時間復雜度：（2分）設(shè)元素個數(shù)記為n，則平均時間復雜度為：2（10分）void pop(Stack amp。S,Elemtype amp。e){ if(==) return ERROR。 。 e=*。}（10分）voidCountLeaves(BinTree T,int amp。n){if(T){if((!(Tlchild)amp。amp。!( Trchild)) n++。 CountLeaves (Tlchild,n)。 CountLeaves (Trchild,n)。}}習題1一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。 2. 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（ ）。 3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存