期末考試試卷(A卷)標(biāo)準(zhǔn)答案及評分標(biāo)準(zhǔn)1

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