數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-5

數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題

(20分)1．?dāng)?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)，則以增量趟希爾排序結(jié)束后前 4條記錄關(guān)鍵字為（ ）。

d=4

的一40，50，20，95(B)15，40，60，2015，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)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（ ）。15，25，35，50，20，40，80，85，36，7015，25，35，50，80，20，85，40，70，3615，25，35，50，80，85，20，36，40，7015，25，35，50，80，20，36，40，70，854．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（ ）。(A)“STRUCTURE” (B)“DATA”(C)“ASTRUCTUR”

(D)“DATASTRUCTURE”5．設(shè)一個有序的單鏈表中有則該操作的時間復(fù)雜度為（

n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，）。(A)O(log2n)

(B)O(1)

(C)O(n2)

(D)O(n)6．設(shè)一棵 m叉樹中度數(shù)為結(jié)點數(shù)為 Nm，則N0=（

0的結(jié)點數(shù)為）。

N0，度數(shù)為

1的結(jié)點數(shù)為

Nl，??，度數(shù)為

m的(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)abedfc(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為基準(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二、填空題(共20分)設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為 n，則判斷共享棧滿的條件是 ____________________。2. 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是 ____________________。3.

設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出隊列，所以又把隊列稱為_________表。5.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。6.設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為________，有__________個葉子結(jié)點。設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點 i的__________。設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，??，kn)是堆，則對i=1，2，?，n/2而言滿足的條件為_______________________________。下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j<_____________;j++)if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}if(exchange==0)return；}}下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){________________________________;if(r[mid].key==k)return(mid+1);elseif(____________)high=mid-1;elselow=mid+1;}return(0);}三、應(yīng)用題(32分)設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。4. 設(shè)散列表的長度為 8，散列函數(shù) H(k)=kmod7，初始記錄關(guān)鍵字序列為 (25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。四、算法設(shè)計題 (28分)1．設(shè)計判斷兩個二叉樹是否相同的算法。2．設(shè)計兩個有序單鏈表的合并排序算法。數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案一、選擇題1．A2．B3．A4．A5．D6．B7．B8．B9．C10．C二、填空題top1+1=top2可以隨機訪問到任一個頂點的簡單鏈表i(i+1)/2+j-1FILO，F(xiàn)IFOABDECF，DBEAFC，DEBFCA8，64出度，入度ki<=k2i&&ki<=k2i+1n-i，r[j+1]=r[j]mid=(low+high)/2，r[mid].key>k三、應(yīng)用題DEBCAE={(1,5),(5,2),(5,3),(3,4)},W=10ASL=(1*1+2*2+3*4)/7=17/7ASL1=7/6，ASL2=4/3四、算法設(shè)計題設(shè)計判斷兩個二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;i