大學(xué)計算機《數(shù)據(jù)結(jié)構(gòu)》試卷及答案(九)

大學(xué)計算機《數(shù)據(jù)結(jié)構(gòu)》試卷及答案一、選擇題(30分)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)，則以增量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é)果為()。(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,85函數(shù)substr(“DATASTRUCTURE”，5,9)的返回值為()。(A)“STRUCTURE” (B)“DATA”(C)“ASTRUCTUR” (D)“DATASTRUCTURE”設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為()。(A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N[, ,度數(shù)為m的結(jié)點數(shù)為Nm,則N0=()。(A)叫+比+ +Nm (B)1+N2+2N3+3N4+ +(m-1)Nm(C)N2+2N3+3N4+ +(m-1)Nm(D)2Nl+3N2+ +(m+1)Nm設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較()次。(A)25(B)10(A)25(B)10(C)7(D)1設(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)aedfcb設(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二、填空題(共30分)1. 設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧項指針topi的初值為-1,第二個棧頂指針top2的初值為n,則判斷共享棧滿的條件是在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是設(shè)有一個n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素)存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有 個數(shù)據(jù)元素。棧的插入和刪除只能在棧的棧頂進行,后進棧的元素必定先出棧,所以又把棧稱為 表；隊列的插入和刪除運算分別在隊列的兩端進行,先進TOC\o"1-5"\h\z隊列的元素必定先出隊列,所以又把隊列稱為 表。設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為 ,中序遍歷序列為 ,后序遍歷序列為 。設(shè)一棵完全二叉樹有128個結(jié)點,則該完全二叉樹的深度為 ,有 個葉子結(jié)點。元素個數(shù)之和等于頂點i的 ，第i列中所有非零元素個數(shù)之和等于頂點i的 。設(shè)一組初始記錄關(guān)鍵字序列(匕，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；}}10.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){ 3if(r[mid].key==k)return(mid+1);elseif( )high=mid-1;elselow=mid+1;}return(0);三、應(yīng)用題（24分）設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。3. 設(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è)計題（16分）設(shè)計判斷兩個二叉樹是否相同的算法。設(shè)計兩個有序單鏈表的合并排序算法。參考答案一、選擇題1．A 2．B3．A4．A5．D6．B 7．B8．B9．C10．C二、填空題top1+1=top2可以隨機訪問到任一個頂點的簡單鏈表i(i+1)/2+j-1FILO，F(xiàn)IFOABDECF，DBEAFC，DEBFCA8，648.9.7.8.9.ki<=k2i&&ki<=kn-i，r[j+1]=r[j]10.mid=(low+high)/2，r[mid].key>k三、應(yīng)用題1.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è)計題1.設(shè)計判斷兩個二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));2.設(shè)計兩個有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->da