資源描述：
《2010上學期數據結構試卷答案》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、2009-2010學年第一學期期末考試《數據結構》試題A參考答案一、選擇題（2*15=30）CBABABCDCACDBDA二、簡答題（6*6=36）1)試舉例說明對相同的邏輯結構,同一種運算在不同的存儲方式下實現，其運算效率不同。答：對于順序表和單鏈表兩種數據結構：其邏輯結構都是線性表，而存儲結構分別為順序存儲與鏈式存儲。在順序表上進行插入操作，需要移動待插入元素之后的數據，平均次數為n/2（n為數據元素個數）；而在鏈表上進行插入操作，則僅僅需要把待插入元素的節(jié)點連接進鏈表的相應位置而無需移動數據元素，插入運算的效率比順序存
2、儲要好。從這個例子可以看出即使有相同的邏輯結構，同一運算在不同存儲方式下的運算效率也是會有所不同的。2)什么是順序隊列的‘假溢出’問題？給出一種解決的方案。答：順序隊列因多次入隊列和出隊列操作后出現的有存儲空間但不能進行入隊列操作造成的溢出稱為‘假溢出’?？刹扇∷姆N方法解決‘假溢出’的問題： 1)采用循環(huán)隊列；2)按最大可能的進隊操作次數設置順序隊列的最大元素個數；3)修改出隊算法，使每次出隊列后都把隊列中剩余數據元素向隊頭方向移動一個位置； ４)修改入隊算法，增加判斷條件，當假溢出時，把隊列中的數據元素向對頭移動，然后方完
3、成入隊操作。3)鏈表結構的序列適合使用折半查找么？為什么？答：不適合。因為鏈表結構的存儲結構式鏈式存儲，其中每個數據元素的物理存儲并不是按照線性順序的，在折半查找尋找中間節(jié)點時，需要對鏈表進行順序訪問以確定中間元素；而順序表的中間元素可以直接用公式n/2來定址，無需計算。因此鏈表結構進行折半查找的效率較低，不太適合使用折半查找。4)串是不定長的，表示串一般有哪些方法？C語言中的串是如何表示的？答:c串的順序存儲有兩種方法：一種方法是設置一個串的長度參數，此種方法的優(yōu)點是便于在算法中用長度參數控制循環(huán)過程；另一種方法是在串值的
4、末尾添加結束標記，此種方法的優(yōu)點是便于系統自動實現。鏈式存儲也有分為單字符結點和塊鏈兩種。C語言中的串是在串尾添加結束標記的方法來表示串的。5)簡單說明圖的最小生成樹普里姆算法及克魯斯卡爾算方法的基本思想。答：普里姆算法思想是：令集合U的初值為U={u0}（即假設構造最小生成樹時從頂點u0開始），集合T的初值為T={}。從所有頂點u∈U和頂點v∈V-U的帶權邊中選出具有最小權值的邊(u,v)，將頂點v加入集合U中，將邊(u,v)加入集合T中。如此不斷重復，當U=V時則最小生成樹構造完畢。克魯斯卡爾算法思想是：每次加入能夠連接
5、兩個連通分量的最小權邊。1)結合排序算法的衡量標準及算法設計的目標，談談在設計一個算法時需要注意的因素有哪些？答：算法設計滿足以下目標：a正確性；b可讀性;c健壯性;d高時間效率;e高空間效率。比較排序算法優(yōu)劣的標準包括:(1)時間復雜度:它主要是分析記錄關鍵字的比較次數和記錄的移動次數；(2)空間復雜度:算法中使用的內存輔助空間的多少；(3)穩(wěn)定性:若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的一、綜合題（10+10=20）1）解：B）a:0101,b:10,c:01000,d:
6、11,e:011,f:000,g:01001,h:001C)wpl=7*4+26*2+2*5+28*2+13*3+10*3+3*5+11*3=2132）解：鄰接矩陣為：最短路徑：stepABCDEF1{A}Distance06￥30￥￥Path[]AA-1A-1-12{A,B}Distance06830￥11Path[]AABA-1B3{A,B,C}Distance06823￥11Path[]AABC-1B4{A,B,C,F}Distance068232911Path[]AABC
7、
8、FFB5{A,B,C,F,D}Distan
9、ce068232711Path[]AABC
10、
11、FDB6{A,B,C,F,D,E}Distance068232711Path[]AABC
12、
13、FDB二、程序設計（8+6=14）注：程序不唯一，主體思路正確即可。1）依下圖所示，完成帶頭結點的鏈式堆棧壓入、彈出的函數。解：壓入函數：intStackPush(LnkStack*pS,DataTypex){LSNode*p=(LSNode*)malloc(sizeof(LSNode));if(NULL==p)exit(1);p->Data=x;p->next=pS->head->nex
14、t;pS->head->next=p;return1;}彈出函數：intStackPop(LnkStack*pS,DataType*x){LSNode*p;if(NULL==（p=pS->head->next））.../*容錯*/pS->head->next=p->next;*x=p->D
