《數據結構》期末考試及答案

函授站：姓名：專業(yè)：學號：座位號：《數據結構》期末考試試卷考生注意：1．本試卷滿分100分。2．考試時間90分鐘。3．卷面整潔，字跡工整。4．填寫內容不得超出密封線?？偡诸}號題分得分一二三四五六核分人復查人201466一、單項選擇題（每題2分，共計20分）1．對于一個算法，當輸入非法數據時，也要能作出相應的處理，這種要求稱為（）。(A)、正確性(B).可行性(C).健壯性(D).輸入性2．設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．順序存儲結構的優(yōu)勢是（）。（A）、利于插入操作（B）、利于刪除操作（C）、利于順序訪問（D）、利于隨機訪問5．深度為k的完全二叉樹，其葉子結點必在第（）層上。（A）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60個結點的二叉樹，其葉子結點有12個，則度過1的結點數為（（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樹的帶權路徑長度WPL等于（（A）、除根結點之外的所有結點權值之和（B）、所有結點權值之和（C）、各葉子結點的帶權路徑長度之和（D）、根結點的值10．線索二叉鏈表是利用（））域存儲后繼結點的地址。（A）、lchild（B）、data（C）、rchild（D）、root二、填空題（每題2分，共計14分）1．邏輯結構決定了算法的2．棧和隊列都是一種，而存儲結構決定了算法的。的線性表，棧的插入和刪除只能在進行。3．線性表（a1,a2,…,an）的順序存儲結構中，設每個單元的長度為L，元素ai的存儲地址LOC(ai)為4．已知一雙向鏈表如下(指針域名為next和prior)：qp現將p所指的結點插入到x和y結點之間，其操作步驟為：；；；；5．n個結點無向完全圖的的邊數為，n個結點的生成樹的邊數為6．已知一有向無環(huán)圖如下：。任意寫出二種拓撲排序序列：、。7．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為，層序遍歷序列為。三、應用題（每題11分共計66分）1．設散列函數H(k)=k%13,設關鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測法處理沖突。(6分)(1)構造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．已知一維數組中的數據為（18,12,25,53,18）,試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時間復雜度是多少？(5分)5．已知一網絡的鄰接矩陣如下，求從頂點A開始的最小生成樹。(8分，要有過程)ABCDEF（1）求從頂點A開始的最小生成樹。（2）分別畫出以A為起點的DFS生成樹和BFS生成樹。6．已知數據六個字母及在通信中出現頻率如下表：ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結點及權值，完成如下工作(7分，要有過程)。（1）畫出對應的Huffman樹。（2）計算帶權路徑長度WPL。（3）求A、B、C、D、E、F的Huffman編碼?！稊祿Y構》期末考試答案選擇題（每題1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C一、填空題1．設計、實現2．特殊、棧頂3．LOC（a1）+(i-1)*L4．p->next=q->next;q->next->prior=p;q->next=p;p->prior=q;5．n(n-1)/2、n-16．ADCBFEG、ABCDEFFG7．ABC、ABC二、應用題1（1）Hash表（4分）地址關鍵安探測次數0131121723456617452873922110811241121213（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）、構造（3分）1914221015205621(2)、1014151920212256（2分）（3）、（3分）3、(5分，每行0.5)ijv12344553431225-5673-11884、初始關鍵字：[18]12255318第一趟：[1218]255318第二趟：[121825]5318第三趟：[12182553]18第四趟：[1218182553]（4分）O（n2）（1分）。5、7分（1）4分