《數(shù)據(jù)結(jié)構(gòu)》期末考試及答案

PAGE第3頁共3頁密封線函授站：密封線函授站：姓名：專業(yè)：學(xué)號：座位號：期末考試試卷考生注意：1．本試卷滿分100分。2．考試時間90分鐘。 3．卷面整潔，字跡工整。4．填寫內(nèi)容不得超出密封線?？偡诸}號一二三四五六核分人題分201466復(fù)查人得分單項選擇題（每題2分，共計20分）1．對于一個算法，當(dāng)輸入非法數(shù)據(jù)時，也要能作出相應(yīng)的處理，這種要求稱為（）。(A)、正確性(B).可行性(C).健壯性(D).輸入性2．設(shè)S為C語言的語句,計算機(jī)執(zhí)行下面算法時，算法的時間復(fù)雜度為（）。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）、利于隨機(jī)訪問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）、377．圖的Depth-FirstSearch(DFS)遍歷思想實際上是二叉樹（）遍歷方法的推廣。（A）、先序（B）、中序（C）、后序（D）、層序8．在下列鏈隊列Q中，元素a出隊的操作序列為（）bbcd∧afrontrearQ（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填空題（每題2分，共計14分）邏輯結(jié)構(gòu)決定了算法的，而存儲結(jié)構(gòu)決定了算法的。棧和隊列都是一種的線性表，棧的插入和刪除只能在進(jìn)行。線性表（a1,a2,…,an）的順序存儲結(jié)構(gòu)中，設(shè)每個單元的長度為L，元素ai的存儲地址LOC(ai)為已知一雙向鏈表如下(指針域名為next和prior)：yyxeep現(xiàn)將p所指的結(jié)點插入到x和y結(jié)點之間，其操作步驟為：；；；；5．n個結(jié)點無向完全圖的的邊數(shù)為，n個結(jié)點的生成樹的邊數(shù)為。6．已知一有向無環(huán)圖如下：BABACDFEG任意寫出二種拓?fù)渑判蛐蛄校?、?．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為，層序遍歷序列為。應(yīng)用題（每題11分共計66分）設(shè)散列函數(shù)H(k)=k%13,設(shè)關(guān)鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測法處理沖突。(6分)(1)構(gòu)造HASH表。(2)分別求查找成功和不成功時的平均查找長度。給定表（19,14,22,15,20,21,56,10）.（8分）按元素在表中的次序，建立一棵二叉排序樹對(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。畫出對(2)中的遍歷序列進(jìn)行折半查找過程的判定樹。已知二個稀疏矩陣A和B的壓縮存儲三元組表如下：ABijVijV13-525224633725241342-152-9529558寫出A-B壓縮存儲的三元組表。（5分）已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）,試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時間復(fù)雜度是多少？(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分，要有過程)。畫出對應(yīng)的Huffman樹。計算帶權(quán)路徑長度WPL。求A、B、C、D、E、F的Huffman編碼?！稊?shù)據(jù)結(jié)構(gòu)》期末考試答案選擇題（每題1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C填空題設(shè)計、實現(xiàn)特殊、棧頂LOC（a1）+(i-1)*Lp->next=q->next;q->next->prior=p;q->next=p;p->prior=q;n(n-1)/2、n-1ADCBFEG、ABCDEFFGABC、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分）191914221015205621(2)、1014151920212256（2分）（3）、（3分）3、(5分，每行0.5)ijv13-524633741342-152185584、初始關(guān)鍵字：[18]12255318第一趟：[1218]255318第二趟：[121825]5318第三趟：[12182553]18第四趟：[1218182553]（4分）O（n2）（1分）。5、7分（1）4分AB1C325D4EF（2）4分6、(1)3分EFE