級數(shù)據(jù)結(jié)構(gòu)與算法試卷A卷-參考答案

2013—2014學(xué)年第一學(xué)期閩江學(xué)院考試試卷《數(shù)據(jù)結(jié)構(gòu)與算法》A卷參考答案及評分標(biāo)準(zhǔn)一、選擇題答案（每題2分）30%123456789101112131415BACDCDBCCDDCABC二、填空題（每空2分）20%1、p->nexts2、53、1+n2+2n3+…+(k-1)nk4、n-1n+15、CDBGFEA6、2n-17、A[7]、A[3]、A[5]、A[4]8、2e三、判斷題（每題1分）10%12345678×√×××√××四、應(yīng)用題（5小題）32% 1、（6分）畫哈夫曼樹（每個葉子結(jié)點位置正確得0.5分，總5分）計算WPL正確得1分WPL=(2+4)*5+(5+7+8)*4+(9+10+15+18)*3+22*2=30+80+156+44=310100100415919262233910111518567824152、（8分）(1)二叉排序樹(每個結(jié)點在正確的位置正確得0.5分，總6分)10041100415919262233910111518567824152714663562283113212560(2)查找成功時的平均查找長度：（總2分）ASL=(1*1+2*2+4*3+5*4)/12=37/12=3.083、（5分）（每行正確得0.5分，總5分）原始數(shù)據(jù)：（27），10，21，37，9，55，16，61，103，2第一趟后:（10，27），21，37，9，55，16，61，103，2第二趟后:（10，21，27），37，9，55，16，61，103，2第三趟后:（10，21，27，37），9，55，16，61，103，2第四趟后:（9，10，21，27，37），55，16，61，103，2第五趟后:（9，10，21，27，37，55），16，61，103，2第六趟后:（9，10，16，21，27，37，55），61，103，2第七趟后:（9，10，16，21，27，37，55，61），103，2第八趟后:（9，10，16，21，27，37，55，61，103），2第九趟后:（2，9，10，16，21，27，37，55，61，103）4、（5分）哈希表，每個表結(jié)點在正確的位置得0.5分，計4分；查找成功時的平均查找長度正確得1分。Key23149630121829H（key）20262541014∧129∧223930∧3∧418∧512∧66∧ASL成功=（1*6+2*1+3*1）/8=11/8=1.3625(1分)5、（8分）鄰接表存儲（4分）V1V210V33∧V2V110V42∧V3V13V47∧V4V22V37V55V64∧V5V45V68V74∧V6V44V58V76V81∧V7V54V66∧V83∧V8V61V73∧得分標(biāo)準(zhǔn)：每個結(jié)點的鄰接點均正確得0.5分（即每行0.5分）克魯斯卡爾算法畫出最小生成樹的過程（4分）：V2V1V2V1V3V4V5V6V7V8V2V1V3V4V5V6V7V817（1）（2）2V2V12V2V1V3V4V5V6V7V81723V2V1V3V4V5V6V7V817（3） （4）323323V2V1V3V4V5V6V7V8173423V2V1V3V4V5V6V7V817（5） （6）3423423V2V1V3V4V5V6V7V8417342713V2V1V3V4V5V6V7V8417（7）（8）得分標(biāo)準(zhǔn)：依次得出上面八張圖，每張0.5分，計4分，其中第（4）、（5）張，第（6）、（7）張兩權(quán)值相同的邊順序可調(diào)換。五、編程題（2小題，每題5分）10%1、已知二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，試編寫按前序遍歷該二叉樹的遞歸算法。(5分)二叉鏈表的結(jié)點定義如下：typedefcharTElemType;typedefstructBiTNode{//結(jié)點結(jié)構(gòu)TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;答案：voidPreorder(BiTreeT)1%{if(T){1%printf(“%c”,T->data);1%Preorder(T->lchild);1%Preorder(T->rchild);1%}}2、試寫出折半查找算法的非遞歸實現(xiàn)算法。(5分)查找表定義如下：typedefintKeyType;typedefstruct{keyTypekey;//關(guān)鍵字域……//其它屬性域}ElemType;typedefstruct{ElemTypeelem[maxsize+1];//0號單元留空intlength;//表的長度}SSTable;答案：intSearch_Bin(SSTableST,KeyTypekval){intlow=1，high=ST.length;1%while(low<=high)0.5%{mid=(low+high)/2;0.5%if（kval==ST.elem[mid].key)0.5%returnmid;0.5%elseif(kval<ST.elem[mid].key))0.5%h