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

1、第第 頁共23頁4、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9鄰接表表示時0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5四、閱讀算法，回答問題（每小題8分，共16分）3、此二叉樹的后序遍歷結(jié)果是:EDCBIHJGFA1、該算法的輸入結(jié)果是：3491304563782、該算法的功能是：交換二叉樹的左右子樹的遞歸算法五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)是：(low+high)/2;是：Binsch(A,low,mid-1,K);是：Binsch(A,mid+1,high,K);

2、是：-1;六、編寫算法(10分)根據(jù)編程情況，酌情給分。Lnode*P=HL;HL=NULL;While(p!=null)Lnode*q=p;P=pTnext;qfnext=HL;HL=q;數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案3一、單項(xiàng)選擇題1對于一個算法，當(dāng)輸入非法數(shù)據(jù)時，也要能作出相應(yīng)的處理，這種要求稱為()。(A)、正確性(B)可行性(C)健壯性(D)輸入性設(shè)S為C語言的語句,計算機(jī)執(zhí)行下面算法時，算法的時間復(fù)雜度為()。for(i=n-1;i=0;i-)for(j=0;jnext;p-next=Q.rear-next;、p=Q-next;Q-next=p-next;9.Huffman樹的帶權(quán)路徑

3、長度WPL等于(A)、(A)、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和(B)、所有結(jié)點(diǎn)權(quán)值之和(C)、各葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和(D)(C)、各葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和(D)、根結(jié)點(diǎn)的值10.線索二叉鏈表是利用()域存儲后繼結(jié)點(diǎn)的地址。(A)、Ichild(B)、data(C)、rchild(D)、root二、填空題1.邏輯結(jié)構(gòu)決定了算法的，而存儲結(jié)構(gòu)決定了算法的。2棧和隊列都是一種的線性表，棧的插入和刪除只能在進(jìn)行。3.線性表(a.,a2a)的順序存儲結(jié)構(gòu)中，設(shè)每個單元的長度為L,元素a的存儲地址i2nLOC(a)為4.已知一雙向鏈表如下(4.已知一雙向鏈表如下(指針域名為next和prior):

4、現(xiàn)將p所指的結(jié)點(diǎn)插入到x和y結(jié)點(diǎn)之間，其操作步驟為：TOC o 1-5 h z，個結(jié)點(diǎn)無向完全圖的的邊數(shù)為已知一有向無環(huán)圖如下：n個結(jié)點(diǎn)的生成樹的邊數(shù)為。已知一有向無環(huán)圖如下：任意寫出二種拓?fù)渑判蛐蛄校阂阎鏄涞闹行虮闅v序列為BCA后序遍歷序列為CBA則該二叉樹的先序遍歷序列為，層序遍歷序列為。三、應(yīng)用題1.設(shè)散列函數(shù)H(k)=k%13,設(shè)關(guān)鍵字系列為22,12,24,6,45,7,8,13,21,要求用線性探測法處理沖突。(6分)構(gòu)造HASH表。分別求查找成功和不成功時的平均查找長度。2.給定表(19,14,22,15,20,21,56,10).(8分)按元素在表中的次序，建立一棵二叉排序

5、樹對(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列(3)畫出對(2)中的遍歷序列進(jìn)行折半查找過程的判定樹。已知二個稀疏矩陣A和B的壓縮存儲三元組表如下:ABijVijV13-525224633725241342-152-9529558寫出A-B壓縮存儲的三兀組表。(5分)4.已知一維數(shù)組中的數(shù)據(jù)為(18,12,25,53,18_),試寫出插入排序(升序)過程。并指出具有n個元素的插入排序的時間復(fù)雜度是多少？(5分)5.已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)A開始的最小生成樹。(8分，要有過程)ABCDEFA651B653C572D15764E366F246(1)求從頂點(diǎn)A開始的最小生成樹。（

6、2）分別畫出以A為起點(diǎn)的DFS生成樹和BFS生成樹。6.已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表:ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作（7分，要有過程）。（1）畫出對應(yīng)的Huffman樹。（2）計算帶權(quán)路徑長度WPL（3）求A、BC、D、E、F的Huffman編碼。7.已知有如下的有向網(wǎng):AEB6246CD27.已知有如下的有向網(wǎng):AEB6246CD2求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑（采用Dijkstra算法，要有過程）。（6分）四、設(shè)計題（30分，每題10分，用C語言寫出算法，做在答題紙上）1.已知線性表（ai5a2,-,a）以順

7、序存儲結(jié)構(gòu)為存儲結(jié)構(gòu)，其類型定義如下：12n#defineLIST_INIT_SIZE100順序表初始分配容量typedefstructElemtype*elem;/順序存儲空間基址intlength;/當(dāng)前長度（存儲元素個數(shù)）SqList;設(shè)計一個算法，刪除其元素值為x的結(jié)點(diǎn)（假若x是唯一的）。并求出其算法的平均時間復(fù)雜度。其算法函數(shù)頭部如下：StatusListDelete(Sqlist&L,Elemtypex)2設(shè)順序棧如左圖所示。其中結(jié)點(diǎn)定義如下:typedefstructElemtype*base;/棧底指針Elemtype*top;/棧頂指針Stack;base設(shè)計算法，將棧頂元素

8、出棧并存入e中.base3.設(shè)二叉鏈樹的類型定義如下：typedefintElemtype;typedefstructnodeElemtypedata;structnode*lchild,*rchild;BinNode,*BinTree;試寫出求該二叉樹葉子結(jié)點(diǎn)數(shù)的算法：StatusCountLeaves(BinTree&root,int&n)/nisthenumberofleaves試題3答案一、選擇題（每題1分）1.C2、D3、A4、D5、C6、D7、A8、B9、C10、C二、填空題1設(shè)計、實(shí)現(xiàn)2.特殊、棧頂3.LOC(a1)+(i-1)*Lp_next=q_next;q_next-pri

9、or=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分）21(2)、1014151920212256(2分)、(3分3、（5分，每行0.5）ijv13-524633741342-152185584初始關(guān)

10、鍵字：1812255318、第一趟：12-18255318第二趟：1218255318第三趟:1218255318第四趟：121818-2553（4分）O（n2）（1分）。5、7分（1）4分A（2）4分6、（1）3分TOC o 1-5 h z（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*2仁（1分）（3）A:010B:011C:110D:111E：00F;10（3分）7、A-B:（A、B）1分A-C:（A、D、C）2分A-D:（A、D）1分A-E:（A、D、E）2分四、設(shè)計題(30分)1、(10分)StatusListDelete(Sqlist&L,ElemTypex)inti,j;for(i=0;ilength;i+)if(L-elemi=x)break;if(i=L-length)returnERROR;for(j=i;jlengthi_1;j+)L-elemj=L-elemj+1;L-length-;(8分)平均時間復(fù)雜度：(2分)設(shè)元素個數(shù)記為n,則平均時間復(fù)雜度為：1(ni)ni12、(10分)voidpop(Stack&S,Elemtyp