資源描述：
《2010上學(xué)期數(shù)據(jù)結(jié)構(gòu)試卷答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、2009-2010學(xué)年第一學(xué)期期末考試《數(shù)據(jù)結(jié)構(gòu)》試題A參考答案一、選擇題（2*15=30）CBABABCDCACDBDA二、簡(jiǎn)答題（6*6=36）1)試舉例說(shuō)明對(duì)相同的邏輯結(jié)構(gòu),同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。答：對(duì)于順序表和單鏈表兩種數(shù)據(jù)結(jié)構(gòu)：其邏輯結(jié)構(gòu)都是線性表，而存儲(chǔ)結(jié)構(gòu)分別為順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)。在順序表上進(jìn)行插入操作，需要移動(dòng)待插入元素之后的數(shù)據(jù)，平均次數(shù)為n/2（n為數(shù)據(jù)元素個(gè)數(shù)）；而在鏈表上進(jìn)行插入操作，則僅僅需要把待插入元素的節(jié)點(diǎn)連接進(jìn)鏈表的相應(yīng)位置而無(wú)需移動(dòng)數(shù)據(jù)元素，插入運(yùn)算的效率比順序存
2、儲(chǔ)要好。從這個(gè)例子可以看出即使有相同的邏輯結(jié)構(gòu)，同一運(yùn)算在不同存儲(chǔ)方式下的運(yùn)算效率也是會(huì)有所不同的。2)什么是順序隊(duì)列的‘假溢出’問(wèn)題？給出一種解決的方案。答：順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有存儲(chǔ)空間但不能進(jìn)行入隊(duì)列操作造成的溢出稱(chēng)為‘假溢出’?？刹扇∷姆N方法解決‘假溢出’的問(wèn)題： 1)采用循環(huán)隊(duì)列；2)按最大可能的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大元素個(gè)數(shù)；3)修改出隊(duì)算法，使每次出隊(duì)列后都把隊(duì)列中剩余數(shù)據(jù)元素向隊(duì)頭方向移動(dòng)一個(gè)位置；?。?修改入隊(duì)算法，增加判斷條件，當(dāng)假溢出時(shí)，把隊(duì)列中的數(shù)據(jù)元素向?qū)︻^移動(dòng)，然后方完
3、成入隊(duì)操作。3)鏈表結(jié)構(gòu)的序列適合使用折半查找么？為什么？答：不適合。因?yàn)殒湵斫Y(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)式鏈?zhǔn)酱鎯?chǔ)，其中每個(gè)數(shù)據(jù)元素的物理存儲(chǔ)并不是按照線性順序的，在折半查找尋找中間節(jié)點(diǎn)時(shí)，需要對(duì)鏈表進(jìn)行順序訪問(wèn)以確定中間元素；而順序表的中間元素可以直接用公式n/2來(lái)定址，無(wú)需計(jì)算。因此鏈表結(jié)構(gòu)進(jìn)行折半查找的效率較低，不太適合使用折半查找。4)串是不定長(zhǎng)的，表示串一般有哪些方法？C語(yǔ)言中的串是如何表示的？答:c串的順序存儲(chǔ)有兩種方法：一種方法是設(shè)置一個(gè)串的長(zhǎng)度參數(shù)，此種方法的優(yōu)點(diǎn)是便于在算法中用長(zhǎng)度參數(shù)控制循環(huán)過(guò)程；另一種方法是在串值的
4、末尾添加結(jié)束標(biāo)記，此種方法的優(yōu)點(diǎn)是便于系統(tǒng)自動(dòng)實(shí)現(xiàn)。鏈?zhǔn)酱鎯?chǔ)也有分為單字符結(jié)點(diǎn)和塊鏈兩種。C語(yǔ)言中的串是在串尾添加結(jié)束標(biāo)記的方法來(lái)表示串的。5)簡(jiǎn)單說(shuō)明圖的最小生成樹(shù)普里姆算法及克魯斯卡爾算方法的基本思想。答：普里姆算法思想是：令集合U的初值為U={u0}（即假設(shè)構(gòu)造最小生成樹(shù)時(shí)從頂點(diǎn)u0開(kāi)始），集合T的初值為T(mén)={}。從所有頂點(diǎn)u∈U和頂點(diǎn)v∈V-U的帶權(quán)邊中選出具有最小權(quán)值的邊(u,v)，將頂點(diǎn)v加入集合U中，將邊(u,v)加入集合T中。如此不斷重復(fù)，當(dāng)U=V時(shí)則最小生成樹(shù)構(gòu)造完畢?？唆斔箍査惴ㄋ枷胧牵好看渭尤肽軌蜻B接
5、兩個(gè)連通分量的最小權(quán)邊。1)結(jié)合排序算法的衡量標(biāo)準(zhǔn)及算法設(shè)計(jì)的目標(biāo)，談?wù)勗谠O(shè)計(jì)一個(gè)算法時(shí)需要注意的因素有哪些？答：算法設(shè)計(jì)滿足以下目標(biāo)：a正確性；b可讀性;c健壯性;d高時(shí)間效率;e高空間效率。比較排序算法優(yōu)劣的標(biāo)準(zhǔn)包括:(1)時(shí)間復(fù)雜度:它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)；(2)空間復(fù)雜度:算法中使用的內(nèi)存輔助空間的多少；(3)穩(wěn)定性:若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱(chēng)這種排序算法是穩(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二、程序設(shè)計(jì)（8+6=14）注：程序不唯一，主體思路正確即可。1）依下圖所示，完成帶頭結(jié)點(diǎn)的鏈?zhǔn)蕉褩喝搿棾龅暮瘮?shù)。解：壓入函數(shù)：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;}彈出函數(shù)：intStackPop(LnkStack*pS,DataType*x){LSNode*p;if(NULL==（p=pS->head->next））.../*容錯(cuò)*/pS->head->next=p->next;*x=p->D
