數據結構復習題及答案-預覽頁

　

【正文】 組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。 int others。while (hashtable[j].key!=kamp。} if (_______________________ ) return(j)。 struct node *lchild。else while (t!=0)if (tkey==k)_____________。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數是H（K）= K mod 7，若發生沖突采用線性探查法處理，試：（1）計算出每一個元素的散列地址并在下圖中填寫出散列表： ` 0 1 2 3 4 5 6（2）求出在查找每一個元素概率相等情況下的平均查找長度。數據結構試卷（四）一、選擇題(每題1分共 20分)1．設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（ ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（ ）條有向邊。 (A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆9．設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（ ）。3． 根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。7． 設有一個順序循環隊列中有M個存儲單元，則該循環隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。11． 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。 void createlkhash(lklist *hashtable[ ]){int i,k。i++)_____________________。 skey=a[i]。}}三、計算題(每題10分，共30分)畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲結構。3. 在鏈式存儲結構上建立一棵二叉排序樹。(A) 15，25，35，50，20，40，80，85，36，70(B) 15，25，35，50，80，20，85，40，70，36(C) 15，25，35，50，80，85，20，36，40，70(D) 15，25，35，50，80，20，36，40，70，854．函數substr(“DATASTRUCTURE”，5，9)的返回值為（ ）。 (A) 25 (B) 10 (C) 7 (D) 18．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為（ ）。2. 在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是____________________。6. 設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。void bubble(int r[n]){for(i=1。j++) if (r[j]r[j+1]){temp=r[j+1]。}if (exchange==0) return；}}10. 下面程序段的功能是實現二分查找算法，請在下劃線處填上正確的語句。int bisearch(struct record r[ ], int k){ int low=0,mid,high=n1。else low=mid+1。3. 設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。數據結構試卷（一）參考答案一、 選擇題（每題2分，共20分） 二、填空題（每空1分，共26分）1. 正確性 易讀性 強壯性 高效率2. O(n)3. 9 3 34. 1 3 4 X * + 2 Y * 3 / 5. 2n n1 n+16. e 2e7. 有向無回路8. n(n1)/2 n(n1)9. （12，40） （ ） （74） （23,55，63）10. 增加111. O(log2n) O(nlog2n)12. 歸并三、計算題（每題6分，共24分）1. 線性表為：（78，50，40，60，34，90）2. 鄰接矩陣： 鄰接表如圖11所示：圖113. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 見圖124444422255285283452843圖12四、 讀算法（每題7分，共14分）1. （1）查詢鏈表的尾結點（2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 遞歸地后序遍歷鏈式存儲的二叉樹。 p=pnext。 prlinkllink=q。 while(ij){while (ij amp。i=i+1。 if (ij) {r[j]=r[i]。typedef struct node {int data。hc){lklist *p,*q,*t。q!=0。tnext=hc。二、填空題1. 順序存儲結構、鏈式存儲結構2. 9，5013. 54. 出度，入度5. 06. e=d7. 中序8. 79. O(1)10. i/2，2i+111. (5，16，71，23，72，94，73)12. (1，4，3，2)13. j+1，hashtable[j].key==k14. return(t)，t=trchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。 ….沖突H(15)=15 mod 7=1。H(63)=63 mod 7=0。typedef struct node {datatype data。head){ lklist *p,*q,*s。q!=0。} else {s=q,q=qnext。} bitree。amp。 q[r]=bt。 preorder(bt,x)。 if (flag==0) printf(not found x\n)。 prlinkllink=prlink3. 34. 2k15. n/26. 50，517. m1，(RF+M)%M8. n+1i，ni9. (19，18，16，20，30，22)10. (16，18，19，20，32，22)11. A[i][j]=112. 等于13. BDCA14. hashtable[i]=0，hashtable[k]=s三、計算題1．2． (1) ABCDEF。typedef struct node {datatype data。ha,lklist *amp。 for(p=head。 if (pdata=39。 pdata=39。} else if (pdata=39。 pdata=39。} else {pnext=hc。 struct node *lchild,*rchild。swapbitree(btlchild)。 btrchild=p。}bitree。btlchild=btrchild=0。bt){ int i。}數據結構試卷（五）參考答案一、選擇題1．A 2．B 3．A 4．A 5．D6．B 7．B 8．B 9．C 10．C二、填空題1. top1+1=top22. 可以隨機訪問到任一個頂點的簡單鏈表3. i(i+1)/2+j14. FILO，FIFO5. ABDECF，DBEAFC，DEBFCA6. 8，647. 出度，入度8. ki=k2i amp。 struct node *lchild,*rchild。 bt2==0) return(1)。void mergelklist(lklist *ha,lklist *hb,lklist *amp。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。ha=hanext。}。}