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

1、數(shù)據(jù)結(jié)構(gòu)模擬試題08一、單項(xiàng)選擇題（每題 2 分，共20分）1數(shù)據(jù)的最小單位是（ ）。(A) 數(shù)據(jù)項(xiàng)(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個(gè)長度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jì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è)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（ ）。(A) O(log2n)(B)

3、O(1)(C) O(n2)(D) O(n)6設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(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個(gè)元素，則用二分查找查找元素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)，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（ ）。(A) abed

4、fc(B) acfebd(C) aebdfc(D) aedfcb9設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（ ）。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(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è)有一個(gè)順序共享?xiàng)0：

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

6、歷序列為_，后序遍歷序列為_。6 設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為_，有_個(gè)葉子結(jié)點(diǎn)。7 設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的_，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的_。8 設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，kn)是堆，則對(duì)i=1，2，n/2而言滿足的條件為_。三、算法填空題（每題 8 分，共16分）1. 下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiā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. 下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiā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（如下圖所示），給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。3. 設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長度。4. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長度。五、算法設(shè)計(jì)題（每題12分，共24分）1 設(shè)計(jì)判斷兩個(gè)二叉樹是

9、否相同的算法。2 設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。5數(shù)據(jù)結(jié)構(gòu)模擬試題08參考答案一、單項(xiàng)選擇題（每題 2 分，共20分）1A2B3A4A5D6B7B8B9C10C二、填空題（每小題2分，共16分）1. top1+1=top22. 可以隨機(jī)訪問到任一個(gè)頂點(diǎn)的簡單鏈表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è)計(jì)題（每題12分，共24分）1. 設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。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è)計(jì)兩個(gè)有序單鏈表的合并排序算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data<hb-