-------------各類(lèi)專(zhuān)業(yè)好文檔，值得你下載，教育，管理，論文，制度，方案手冊(cè)，應(yīng)有盡有---------------------------各類(lèi)專(zhuān)業(yè)好文檔，值得你下載，教育，管理，論文，制度，方案手冊(cè)，應(yīng)有盡有--------------武漢工業(yè)學(xué)院2005–2006學(xué)年第1學(xué)期期末考試試卷（A卷）標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn)課程名稱數(shù)據(jù)結(jié)構(gòu)課程編號(hào)05110一、填空題（每空1分，共20分）1.四種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)分別是：表、樹(shù)、圖和集合。2.假設(shè)按低下標(biāo)行優(yōu)先存儲(chǔ)整數(shù)數(shù)組時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占四個(gè)字節(jié)，則的存儲(chǔ)地址是100，的存儲(chǔ)地址是168。3.在順序表中插入或刪除一個(gè)元素，平均需要移動(dòng)n/2個(gè)元素，具體移動(dòng)的元素個(gè)數(shù)與位置有關(guān)。4.二叉樹(shù)的五種基本形態(tài)是空樹(shù)、只有根節(jié)點(diǎn)、根節(jié)點(diǎn)和左子樹(shù)根節(jié)點(diǎn)和右子樹(shù)和根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。（也可用圖表示）5.常用的有向圖5種存儲(chǔ)方法分別是鄰接表、逆鄰接表、十字鏈表、鄰接矩陣和多重鄰接表。6.內(nèi)部排序算法中的兩種基本操作是比較和交換。二、簡(jiǎn)答題（每小題8分，共40分）請(qǐng)給出以下有向圖的：鄰接矩陣；（2分）鄰接表；（2分）從頂點(diǎn)a出發(fā)的深度優(yōu)先遍歷序列；（2分）從頂點(diǎn)e出發(fā)的廣度優(yōu)先遍歷序列；（2分）解答：（1）、鄰接矩陣（2）（2分）鄰接表abb^bff^cdd^dv^v^eeufuf^fvv^ua^a^cvbb^（3）abfvucde（其它符合規(guī)則的序列也可得分）（4）eufbvaca（其它符合規(guī)則的序列也可得分）2.假設(shè)一棵二叉樹(shù)的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK，請(qǐng)畫(huà)出該二叉樹(shù)。解答：該二叉樹(shù)為：（畫(huà)錯(cuò)一個(gè)分支扣0.5分）3、假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。試構(gòu)造一棵哈夫曼樹(shù)并為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。解答：哈夫曼樹(shù)為（4分）：（畫(huà)錯(cuò)一個(gè)分支扣0.5分）哈夫曼編碼為（4分）：（畫(huà)一個(gè)編碼扣0.5分）0.07：100 0.32：010.19：001 0.03：000010.02：00000 0.21：110.06：0001 0.10：1014、試從空樹(shù)開(kāi)始，畫(huà)出按以下次序向2-3樹(shù)（即3階B-數(shù)）插入關(guān)鍵碼的建樹(shù)過(guò)程：20，30，50，52，60，68，70。如果此后刪除50和68，畫(huà)出每一步執(zhí)行后2-3樹(shù)的狀態(tài)。解答：順序插入20，30，50，52，60，68，70的2-3樹(shù)的狀態(tài)分別為：（6分，畫(huà)錯(cuò)一個(gè)狀態(tài)扣0.5分） 刪除50和68后2-3樹(shù)的狀態(tài)分別為：（2分，畫(huà)錯(cuò)一個(gè)狀態(tài)扣1分） 5.求出下圖的最小生成樹(shù)，并計(jì)算最小生成樹(shù)的權(quán)值。解答：最小生成樹(shù)為：（6分）最小生成樹(shù)的權(quán)值為：26（2分）三、計(jì)算題（共10分）已知一組關(guān)鍵字為（19，14，23，01，68，20，84，27，55，11，10，79），假設(shè)哈希函數(shù)為，分別畫(huà)出以線形探測(cè)再散列（存儲(chǔ)空間為a[0..15]）和鏈地址法處理沖突的哈希表，并分別計(jì)算在記錄查找等概率的條件下的平均查找長(zhǎng)度。解答：（1）（4分）線形探測(cè)再散列存儲(chǔ)結(jié)構(gòu)為：0123456789101112131415017968551920842311101427121211311312等概率的條件下的平均查找長(zhǎng)度=（1*7+2*3+3*2）/12=1.583（1分）（2）（4分）鏈地址法的存儲(chǔ)結(jié)構(gòu)為：0^1017979^2^3685555^4^5^6198484^720^8^9^10231010^1111^12^13^14142727^15^等概率的條件下的平均查找長(zhǎng)度=（1*7+2*5）/12=1.417（1分）四、算法設(shè)計(jì)。算法描述可以采用類(lèi)C語(yǔ)言并給出必要注釋。（每題10分，共30分）1.試寫(xiě)一算法在帶頭節(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)length(L)。解答：節(jié)點(diǎn)類(lèi)型定義為（2分）typedefstructureLinkNode{ElemTypedata;LinkNodenext; }LinkNode,*LinkPoint;求單鏈表長(zhǎng)度的算法為：（8分）intlength(LinkPointL){intLength=0;LinkPointp; p=L->next;while(!p){Length++;p=p->next;} returnLength;}2.試寫(xiě)一算法實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線形表逆置為。解答：節(jié)點(diǎn)類(lèi)型定義為（2分）#defineMAXLENGTH100typedefstructureSqList{ElemTypea[MAXLENGTH];intLength;}SqList,數(shù)組逆置的算法為：（8分）statustraverlist(SqListLA){for(i=0;i<LA.Length/2;i++)LA.a[i]LA.a[LA.Length–i-1] returnOK;}3、試以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單選擇排序的算法。解答：節(jié)點(diǎn)類(lèi)型定義為（2分）typedefstructureLinkNode{ElemTypedata;LinkNodenext; }LinkNode,*LinkPoint;簡(jiǎn)單選擇排序的算法為：（8分）statusSelectSortLinkList(LinkPointL){//假設(shè)單鏈表帶附加頭節(jié)點(diǎn)intn=Length(l);//求單鏈表的長(zhǎng)度LinkPointp,q,t;for(i=1;i<n;i++){p=q=L->next;while(!q){q=q->next;;if(qdata<pdata)p=q;}//endwhile pp=GetElement(L,&q);//在鏈表L中，獲取q指向的節(jié)點(diǎn)，