《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測試題帶答案 (8)

1、數(shù)據(jù)結(jié)構(gòu)模擬試題08一、單項選擇題（每題 2 分，共20分）1數(shù)據(jù)的最小單位是（ ）。(A) 數(shù)據(jù)項(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ ）。(A) 40，50，20，95(B) 15，40，60，20(C) 15，20，40，45(D) 45，40，15，203設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)果為（ ）。(

2、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函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（ ）。(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”5設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（ ）。(A) O(log2n)(B)

3、O(1)(C) O(n2)(D) O(n)6設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（ ）。(A) Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm(C) N2+2N3+3N4+(m-1)Nm(D) 2Nl+3N2+(m+1)Nm7設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（ ）次。(A) 25(B) 10(C) 7(D) 18設(shè)連通圖G中的邊集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（ ）。(A) abed

4、fc(B) acfebd(C) aebdfc(D) aedfcb9設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（ ）。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準而得到一趟快速排序的結(jié)果是（ ）。(A) 40，42，45，55，80，83(B) 42，40，45，80，85，88(C) 42，40，45，55，80，85(D) 42，40，45，85，55，80二、填空題（每題2分，共16分）1 設(shè)有一個順序共享棧S0：

5、n-1，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是_。2 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是_。3 設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則Aij與A00之間有_個數(shù)據(jù)元素。4 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為_表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_表。5 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為_，中序遍

6、歷序列為_，后序遍歷序列為_。6 設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為_，有_個葉子結(jié)點。7 設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的_，第i列中所有非零元素個數(shù)之和等于頂點i的_。8 設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，kn)是堆，則對i=1，2，n/2而言滿足的條件為_。三、算法填空題（每題 8 分，共16分）1. 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int rn)for(i=1;i<=n-1; i+)for(exchange=0,j=0; j<_;j+) if

7、 (rj>rj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return；2. 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordint key; int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(low<=high) _; if(rmid.key=k) return(mid+1); else if(_) high=mid-1;else low=mid+1; return(0);四、

8、算法簡答題（每題 6 分，共24分）1. 設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2. 設(shè)無向圖G（如下圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。3. 設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。4. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。五、算法設(shè)計題（每題12分，共24分）1 設(shè)計判斷兩個二叉樹是

9、否相同的算法。2 設(shè)計兩個有序單鏈表的合并排序算法。5數(shù)據(jù)結(jié)構(gòu)模擬試題08參考答案一、單項選擇題（每題 2 分，共20分）1A2B3A4A5D6B7B8B9C10C二、填空題（每小題2分，共16分）1. top1+1=top22. 可以隨機訪問到任一個頂點的簡單鏈表3. i(i+1)/2+j-14. FILO，F(xiàn)IFO5. ABDECF，DBEAFC，DEBFCA6. 8，647. 出度，入度8. ki<=k2i && ki<=k2i+1三、算法填空題（每題 8分，共16分）1. n-i，rj+1=rj2. mid=(low+high)/2，rmid.key>

10、k四、算法簡答題（每題 6 分，共24分）1. DEBCA2. E=(1,5),(5,2),(5,3),(3,4),W=103. ASL=(1*1+2*2+3*4)/7=17/74. ASL1=7/6，ASL2=4/3五、算法設(shè)計題（每題12分，共24分）1. 設(shè)計判斷兩個二叉樹是否相同的算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judgebitree(bitree *bt1,bitree *bt2) if (bt1=0 && bt2=0) return(1); e

11、lse if (bt1=0 | bt2=0 |bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild);2. 設(shè)計兩個有序單鏈表的合并排序算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data<hb-