合肥學(xué)院期末考試卷試題及答案

1、 合肥學(xué)院20 13 至20 14 學(xué)年第 2 學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計 課程考試（ A ）卷 系 級 專業(yè) 學(xué)號 姓名 題號一二三四五六七八九十總 分得分閱卷大題得分一、選擇題：（2分×15=30分）1棧和隊列的共同特點是( A )。A、只允許在端點處插入和刪除元素 B、都是先進(jìn)后出 C、都是先進(jìn)先出 D、沒有共同點2以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)( D )A、 隊列 B、 棧 C、 線性表 D、 二叉樹3下面程序的時間復(fù)雜為（ B ）。for（i=1，s=0； i<=n； i+） t=1；for(j=1；j<=i；j+) t=t*j；s=s+t；裝 訂 線A、 O(

2、n)B、 O(n2)C、 O(n3)D、 O(n4)4在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行（B ）。 As->next=p->next; p->next=s Bq->next=s; s->next=pCp->next=s->next; s->next=p Dp->next=s; s->next=q5. 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（ C ）。A、 40，42，45，55，80，83B、 42，40，

3、45，80，85，88C、 42，40，45，55，80，85D、 42，40，45，85，55，806設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（ D ）。A、 O(log2n)B、 O(1)C、 O(n2)D、 O(n)7. 設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有( A )條邊才能確保是一個連通圖。A、5 B、6 C、7 D、88設(shè)連通圖G中的邊集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（ A ）。A、 abedfc B、 acfebdC、

4、 aebdfcD、 aedfcb9. 設(shè)散列表長m=14,散列函數(shù)H（K）=K11，已知表中已有4個結(jié)點：r(15)=4; r(38)=5; r(61)=6；r(84)=7，其他地址為空，如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點地址是( D )。 A、 8 B 、3 C、 5 D 、910. 設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為（ B ）。A、 第i行非0元素的個數(shù)之和B、 第i列非0元素的個數(shù)之和C、 第i行0元素的個數(shù)之和 D、 第i列0元素的個數(shù)之和命題教師 胡春玲 共 5 頁，第 1 頁11.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序

5、列為（ D ）。A、 top=top+1 B、 top=top-1C、 top->next=top;D、 top=top->next 12. 二叉樹的第K層的結(jié)點數(shù)最多為( D )。A、2k-1 B、2K+1 C、2K-1 +1 D、 2k-113. 設(shè)有向無環(huán)圖G中的有向邊集合E=<1，2>，<2，3>，<3，4>，<1，4>，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?A ）。A、 1，2，3，4B、 2，3，4，1C、 1，4，2，3D、1，2，4，314. 設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，9

6、2)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ A）。A、 4B、 5C、 6D、 715.圖的深度優(yōu)先遍歷類似于二叉樹的( A )。 A.先序遍歷 B.中序遍歷 C.后序遍歷 D.層次遍歷大題得分二、填空題：（2分×10=20分）1設(shè)順序線性表中有n個數(shù)據(jù)元素，則在第i個位置上插入一個數(shù)據(jù)元素需要移動表中 數(shù)據(jù)元素個數(shù)是 n-i+1 。2設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則在p后進(jìn)行插入操作的語句序列為（ s->next=p->next ; p->next=s ）（設(shè)結(jié)點的指針域為next）。3.設(shè)有一組初始關(guān)鍵字序列為(24，3

7、5，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是 12 24 27 35 18 26 。4設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是 Aij=1 。5.設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較 h 次。6.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，kn)是小根堆，則對i=1，2，n/2而言滿足的條件為 kik2i 且kik2i+1(2i+1n) 。7.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordint key; int others;int bisearch(st

8、ruct record r , int k) int low=0,mid,high=n-1; while(low<=high) mid=(low+high)/2 ; if(rmid.key=k) return(mid+1); else if( k<L->rmid.key ) high=mid-1;else low=mid+1; return(0);8若要對某二叉排序樹進(jìn)行遍歷，保證輸出所有結(jié)點的值序列有序排列，應(yīng)對該二叉排序樹采用_中序_遍歷法。大題得分三、應(yīng)用題：（5分×5=25分）1設(shè)一棵樹T中邊的集合為(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))

9、，(C，G)，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。小題得分共 5 頁，第 2 頁小題得分2請畫出下圖的鄰接矩陣和鄰接表。裝 訂 線 3設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給小題得分出構(gòu)造過程。 4設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹和所走過的邊的集合。小題得分共 5 頁，第 3 頁5、假設(shè)一棵二叉樹的先序序列是ABCDEFGHIJ和中序序列是CDBFEAIHGJ,請畫出該樹。小題得分大題得分四、算法閱讀題：（12分）小題得分1、LinkList mynote(LinkList L) （7

10、分） /L是不帶頭結(jié)點的單鏈表的頭指針 if(L&&L->next) q=L；L=L>next；p=L； S1： while(p>next) p=p>next； S2： p>next=q；q>next=NULL； return L; 請回答下列問題：（1）說明語句S1的功能。 查詢鏈表的尾結(jié)點（2）說明語句組S2的功能。 將第一個結(jié)點連接到鏈表的尾部，作為新的尾結(jié)點（3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。返回的線性表為：（a2,a3,an,a1）小題得分2void ABC(BTNode * BT) （5分） if BT ABC (BT->left); ABC