貴州大學理學院數(shù)學系信息與計算科學專業(yè)《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案(2003-2004學年第2學期)一、單項選擇題1．對于一個算法，當輸入非法數(shù)據(jù)時，也要能作出相應的處理，這種要求稱為（）。(A)、正確性(B).可行性(C).健壯性(D).輸入性2．設(shè)S為C語言的語句,計算機執(zhí)行下面算法時，算法的時間復雜度為（）。for(i=n-1；i>=0；i--)for(j=0；j<i；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）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60個結(jié)點的二叉樹，其葉子結(jié)點有12個，則度過1的結(jié)點數(shù)為（（A）、11（B）、13（C）、48（D）、37）7．圖的Depth-FirstSearch(DFS)遍歷思想實際上是二叉樹（）遍歷方法的推廣。（A）、先序（B）、中序（C）、后序（D）、層序8．在下列鏈隊列Q中，元素a出隊的操作序列為（）Q（A）、p=Q.front->next;p->next=Q.front->next;（B）、p=Q.front->next;Q.front->next=p->next;（C）、p=Q.rear->next;p->next=Q.rear->next;（D）、p=Q->next;Q->next=p->next;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)決定了算法的2．棧和隊列都是一種，而存儲結(jié)構(gòu)決定了算法的。的線性表，棧的插入和刪除只能在進行。3．線性表（a1,a2,…,an）的順序存儲結(jié)構(gòu)中，設(shè)每個單元的長度為L，元素ai的存儲地址LOC(ai)為4．已知一雙向鏈表如下(指針域名為next和prior)：qp現(xiàn)將p所指的結(jié)點插入到x和y結(jié)點之間，其操作步驟為：；；；；5．n個結(jié)點無向完全圖的的邊數(shù)為n個結(jié)點的生成樹的邊數(shù)為，。6．已知一有向無環(huán)圖如下：任意寫出二種拓撲排序序列：、。7．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為，層序遍歷序列為。三、應用題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的壓縮存儲三元組表如下：ABijV-56ijV212245345222345553125723-19-98寫出A-B壓縮存儲的三元組表。（5分）4．已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）,試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時間復雜度是多少？(5分)5．已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點A開始的最小生成樹。(8分，要有過程)ABCDEF（1）求從頂點A開始的最小生成樹。（2）分別畫出以A為起點的DFS生成樹和BFS生成樹。6．已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表：ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點及權(quán)值，完成如下工作(7分，要有過程)。（1）畫出對應的Huffman樹。（2）計算帶權(quán)路徑長度WPL。（3）求A、B、C、D、E、F的Huffman編碼。7．已知有如下的有向網(wǎng)：求頂點A到其它各頂點的最短路徑（采用Dijkstra算法，要有過程）。（6分）三、設(shè)計題（30分，每題1