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

你一定要堅強，即使受過傷，流過淚，也能咬牙走下去。因為，人生，就是你一個人的人生。==============================================================================PAGE命運如同手中的掌紋，無論多曲折，終掌握在自己手中==============================================================科目名稱：數(shù)據(jù)結(jié)構(gòu)1Ｏ八-Ｏ九學(xué)年第一學(xué)期申請廣州大學(xué)學(xué)士學(xué)位抽考課程試卷（A）課程名稱數(shù)據(jù)結(jié)構(gòu)考試形式（開/閉卷）系別專業(yè)班級學(xué)號姓名試題一二三四五六總分評卷人分值2010183220100得分考試時間：2009年1月日答題時間：120分鐘考試地點：考試形式：閉卷一、單項選擇題(每題1分,只有一個正確答案）分值20得分線性表的鏈式存儲比順序存儲最有利于進行（）。A.查找 B.表尾插入或刪除 C.按值插入或刪除 D.表頭插入或刪除在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A．3 B.2 C.1 利用n個值作為葉子節(jié)點的權(quán)生成的哈夫曼樹中共包含有（）個節(jié)點。A．n B.n+1 C.2×n D.2×n-1為了實現(xiàn)樹的層次遍歷算法,使用的一個輔助數(shù)據(jù)結(jié)構(gòu)為（）。A．隊列 B.棧 C.二叉樹 D.樹一個棧的輸入序列是SWXYZ，則棧的不可能的輸出序列是（）。A.ZYXWSB.YZXWSC.YXZSWD.SWXYZ假定一個帶頭節(jié)點的循環(huán)鏈隊的隊首和隊尾指針分別用front和rear表示，則判斷隊空的條件為（）。A．front!=rearB.rear！=NULLC.front==NULLD.front==rear在一個長度為N的數(shù)組空間中，順序存儲著一個隊列，該隊列的隊首和隊尾指針分別用front和rear表示，則該隊列中的元素個數(shù)為（）。A．(rear-front)%NB.(rear-front+N)%NC．(rear+N)%ND.(front+N)%N在一棵具有n個節(jié)點的二叉樹的第i層上（根節(jié)點為第1層），最多具有（）個節(jié)點。A．2i B.2i+1 C.2i-1 D.2n根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度為（）。A．O(n) B.O(log2n) C.O(n2) D.O(nlog2n)n(n>1)個頂點的強連通圖中至少含有（）條有向邊。A．n-1 B.n C.n(n-1)/2 D.n(n-1)

輸入序列為ABC，若變?yōu)镃BA時，經(jīng)過的棧操作為（）A.push,push,push,pop,pop,popB.push,pop,push,pop,push,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（）A．9B．11C．15D．不確定在一個表頭指針為ph的單鏈表中，若要在指針q所指節(jié)點的后面插入一個由指針p所指向的節(jié)點，則執(zhí)行（）操作。A．q->next=p->next;p->next=q;B.p->next=q->next;q=p;C．q->next=p->next;p->next=q;D.p->next=q->next;q->next=p;在一個帶頭節(jié)點的循環(huán)雙向鏈表中，若要在指針p所指向的節(jié)點之后插入一個q指針所指向的節(jié)點，則需要對q->right賦值為（）。A．p->left B.p->right C.p->right->rightD.p->left->left假定利用數(shù)組a[N]順序存儲一個棧，用top表示棧頂指針，top=-1表示?？?，并已知棧未滿，當(dāng)元素x進棧時所執(zhí)行的操作為（）。A．a(chǎn)[--top]=x;B.a[top--]=x;C.a[++top]=x;D.a{top++}=x;如果一個元素序列基本有序時，則選用（）方法較快。A．直接插入排序B.直接選擇排序C.堆排序D.快速排序假如一棵二叉樹有3個結(jié)點,其有多少種不同的形態(tài)（）：A.4種 B.5種 C.6種 D.7種對于具有e條邊的無向圖，它的鄰接表中有（）個邊節(jié)點。A．e-1 B.e C.2(e-1) D.2e下述二叉樹中,哪一種滿足性質(zhì):從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序（）。A．二叉排序樹B．哈夫曼樹 C．AVL樹 D．堆排序二叉樹的_______遍歷的序列是一個關(guān)鍵字的遞增的有序序列A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷二．判斷題(正確打“√”,錯誤打“×”)分值10得分1.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。()2.取線性表的第i個元素的時間與i的大小有關(guān).()3．完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。()4．完全二叉樹的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)。()5．將一棵樹通過孩子兄弟鏈表轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹；()6．任何無向圖都存在生成樹。（）7.關(guān)鍵路徑是AOE網(wǎng)中從源點到終點的最長路徑。（）8.循環(huán)隊列也存在空間溢出問題。（）9．在待排序數(shù)據(jù)基本有序的情況下，快速排序效果最好。（）10．（101，88，46，70，34，39，45，58，66，10）是堆。（）三．算法填空（每空2分,共18分）分值18得分1、采用快速排序算法對在A[s]~A[t]區(qū)間的關(guān)鍵字進行排序。voidQuickSort(intA[],ints,intt){ inti=s,j=t+1; intx=A[s]; do{ do_________;while(A[i]<x); do__________;while(A[j]>x); if(_____________) { inttemp=A[i]; A[i]=A[j];A[j]=temp; } }while(________); A[s]=A[j];A[j]=x; if(____________)QuickSort(A,s,j-1); if(____________)QuickSort(A,j+1,t);}2、統(tǒng)計二叉樹葉子節(jié)點數(shù)intBTreeleafCount(BinTreeNode*BT) { if(BT==NULL)return_______; if(BT->left==NULLandBT->right==NULL)return________; else return____________________________________________________;}四．應(yīng)用題（每題8分共32分）分值32得分下圖表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的代價，如何選擇能溝通每個城市且總代價最省的n-1條線路，并畫出可能的選擇。(8分)2.假設(shè)一個二叉樹的兩種遍歷如下：前序：ABFGCHDEIJLK中序：FGBHCDILJKEA畫出這棵二叉樹,并求其后序遍歷。（8分）

3．用給出的一組權(quán)值{7，19，2，6，32，3，21，10}，構(gòu)造一棵哈夫曼樹，并計算其帶權(quán)路徑長度WPL。（要求寫出哈夫曼樹構(gòu)造過程及WPL的計算過程）(8分）4、己知一組關(guān)鍵字為（32，75，29，63，48，94，25，46，18，70，19），按哈希函數(shù)H(key)=key%13和鏈接法處理沖突構(gòu)造哈希表，并計算其平均查找長度。（8分）

五．編寫算法（每小題10分,共20分）分值20得分根據(jù)函數(shù)聲明voidOrderInsertList(sNode*head,intx),向帶附加表頭節(jié)點head的循環(huán)