2009數(shù)據(jù)結(jié)構(gòu)學(xué)位考試試卷A參考答案

你一定要堅(jiān)強(qiáng)，即使受過傷，流過淚，也能咬牙走下去。因?yàn)?，人生，就是你一個(gè)人的人生。==============================================================================命運(yùn)如同手中的掌紋，無論多曲折，終掌握在自己手中==============================================================數(shù)據(jù)結(jié)構(gòu)學(xué)位考試試卷A參考答案一、單項(xiàng)選擇題(每題1分,只有一個(gè)正確答案）1、A 2、B 3、B 4、D 5、D 6、C 7、C 8、B 9、D 10、B二．判斷題(正確打“√”,錯(cuò)誤打“×”)1、× 2、√ 3、√ 4、√ 5、√ 6、√ 7、√ 8、× 9、× 10、×三．閱讀算法（ （1）、S1的功能：將p指向該單鏈表的最后一個(gè)節(jié)點(diǎn) （2）、S2的功能：將p的next指針指向第1個(gè)節(jié)點(diǎn)，原第1個(gè)節(jié)點(diǎn)的next指針置為空 （3）、(a2,……an-1,an,a1,)四．算法填空（每空2分,共10分）return1;return++c1;NodeLevel(BT->right,x)c2>=1return++c2;五．應(yīng)用題（共30分）1、已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHIJ和BCDAFEHJIG，試給出該二叉樹的后序遍歷序列并繪出該二叉樹對(duì)應(yīng)的森林。(10分）AABECDFGHIJ2.已知鄰接矩陣: v0 v1 v2 v3 v4 v5v0 0 ∞ 10 ∞ 30 100v1 ∞ 0 5 ∞ ∞ ∞v2 ∞ ∞ 0 50 ∞ ∞v3 ∞ ∞ ∞ ∞ ∞ 10v4 ∞ ∞ ∞ 20 ∞ 60v5 ∞ ∞ ∞ ∞ ∞ ∞(1).畫出該圖(2).求出頂點(diǎn)V0到其它頂點(diǎn)的最短路徑(要求寫出求解過程的表)(12分）V0V0V1V2V3V4V510301005501020601、v0->v2 102、v0->v2->v3 603、v0->v4 304、v0->v2->v3->v5 703．用給出的一組權(quán)值{7，19，2，6，32，3，21，10}，構(gòu)造一棵哈夫曼樹，并計(jì)算其帶權(quán)路徑長度WPL。（要求寫出哈夫曼樹構(gòu)造過程及WPL的計(jì)算過程）(8分） 100 60 40 28 32 19 21 11 17 5 6 7 102 3 WPL=(2+3)*5+(6+7+10)*4+(32+19+21)*2=261六．編寫算法（每小題10分,共20分）1、寫出統(tǒng)計(jì)二叉樹度為二的節(jié)點(diǎn)數(shù)intBTreeCountDegree2(BinTreeNode*BT) { if(BT==NULL)return0; if(BT->left&&BT->right) return1+BTreeCountDegree2(BT->left)+BTreeCountDegree2(BT->right); else returnBTreeCountDegree2(BT->left)+BTreeCountDegree2(BT->right);}2、現(xiàn)給出函數(shù)定義,請(qǐng)寫出快速排序的算法：(10分)voidQuickSort(intA[],ints,intt){ inti=s,j=t+1; intx=A[s]; do{ doi++;while(A[i]<x); doj--;while(A[j]>x); if(i<j) { inttemp=A[i]; A[i]=A[j];A[j]=temp; } }while(i