完整word版,合肥學(xué)院期末考試卷及答案,推薦文檔

命題教師命題教師胡春玲共一5頁(yè),第_1_頁(yè)合肥學(xué)院2013至2014學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) 課程考試(A)卷系—級(jí)專業(yè)學(xué)號(hào)姓名題號(hào)一一二四五六七八九十總分得分閱卷一、選擇題：(2分X15=30分) 大題得分.棧和隊(duì)列的共同特點(diǎn)是(A.棧和隊(duì)列的共同特點(diǎn)是(A)。A、只允許在端點(diǎn)處插入和刪除元素C、都是先進(jìn)先出 D、沒有共同點(diǎn).以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？A、隊(duì)列 B、棧.下面程序的時(shí)間復(fù)雜為(B)。for(i=1,s=0;i<=n;i++){t=1A、O(n)B、O(n2)C、O(n3)B、都是先進(jìn)后出(D)C、線性表 D、二叉樹;for(j=1;j<=i;j++)t=t*j;s=s+t;}D、O(n4)4.在一個(gè)單鏈表中，已知執(zhí)行(B)0A.s->next=p->next;q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在4.在一個(gè)單鏈表中，已知執(zhí)行(B)0A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=p5.設(shè)一組初始記錄關(guān)鍵字序列為C.p->next=s->next;s->next=p5.設(shè)一組初始記錄關(guān)鍵字序列為(45,基準(zhǔn)而得到一趟快速排序的結(jié)果是(45為80,55,40,42,85),則以第一個(gè)記錄關(guān)鍵字C45為A、 40,42,45, 55, 80, 83 B、 42,40,45, 80, 85, 88C、42,40,45, 55, 80, 85 D、42,40,45, 85, 55, 80.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為(D)。A、O(log2n) B、O(1)C、O(n2)D、O(n).設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有(A)條邊才能確保是一個(gè)連通圖。A、5 B、6 C、7 D、8.設(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)。A、abedfcB、acfebdC、aebdfcD、aedfcb.設(shè)散列表長(zhǎng)m=14，散列函數(shù)H(K)=K%11,已知表中已有4個(gè)結(jié)點(diǎn)：r(15)=4;r(38)=5;r(61)=6;r(84)=7,其他地址為空，如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是(D)。A、8 B、3 C、5 D、9.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為(B)。A、第i行非0元素的個(gè)數(shù)之和 B、第i歹I」非0元素的個(gè)數(shù)之和C、第i行0元素的個(gè)數(shù)之和D、第i列0元素的個(gè)數(shù)之和.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為(D)0

A、top=top+1B、top=top-1C、top->next=top;D、top=top->next.二叉樹的第K層的結(jié)點(diǎn)數(shù)最多為（D）。A、2k-1 B、2K+1 C、2K-1+1 D、2k-1.設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,4>},則下列屬于該有向圖G的一■種拓?fù)渑判蛐蛄械氖牵ˋ）。A、1,2,3,4B、2,3,4,1 C、 1,4,2,3D、1,2,4,3.設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,.設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,生成的二叉排序樹的深度為(A)。A、4B、5C、6D、7.圖的深度優(yōu)先遍歷類似于二叉樹的(A)。A.先序遍歷 B.中序遍歷二、填空題：(2分X10=20分)1.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則在第數(shù)據(jù)元素個(gè)數(shù)是 n-i+1 。45,18,26,54,92),則由這組記錄關(guān)鍵字C.后序遍歷 D.層次遍歷大題得分i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的新結(jié)點(diǎn)X,則在p后進(jìn)行插入操作的語(yǔ)句片列為(s->next=p->next;p->next=s)(設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext)o.設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后的結(jié)果的是122427351826。.設(shè)某無(wú)向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是 A[i][j]=1。.設(shè)二叉排序樹的高度為h,則在該樹中查找關(guān)鍵字key最多需要比較 h次。.設(shè)一組初始記錄關(guān)鍵字序列(k1,k2,……,kn)是小根堆,則對(duì)61,2,…，n/2而言滿足的條件為_kiwk2i且kiWk2i+1(2i+1<n)。.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(_k<L->r[mid].key )high=mid-1;elselow=mid+1;}return（0）;}.若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出所有結(jié)點(diǎn)的值序列有序排列，應(yīng)對(duì)該二叉排序大題得分樹采用中序遍歷法。三、應(yīng)用題：(5分X5=25分)1.設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。小題得分

共5頁(yè)，第2共5頁(yè)，第2頁(yè)2.請(qǐng)畫出下圖的鄰接矩陣和鄰接表小題得分.設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給小題得分出構(gòu)造過(guò)程小題得分.設(shè)有無(wú)向圖G,要求給出用普里姆算法構(gòu)造最小生成樹和所走過(guò)的邊的集合。64

645、假設(shè)一棵二叉樹的先序序列是ABCDEFGHIJ和中序序列是CDBFEAIHGJ,請(qǐng)畫出該樹小題得分共5頁(yè),第3頁(yè)四、算法閱讀題：(12分)1、四、算法閱讀題：(12分)1、LinkListmynote(LinkListL)(7分){//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針大題得分小題得分if(L&&L->next){S1:S2:S1:S2:while(p—>next)p=p—>next；p—>next=q；q—>next=NULL;}returnL;}請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1的功能。 查詢鏈表的尾結(jié)點(diǎn)(2)說(shuō)明語(yǔ)句組S2的功能。將第一個(gè)結(jié)點(diǎn)連接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)設(shè)鏈表表示的線性表為(a1,a2,…,an),寫出算法執(zhí)行后的返回值所表示的線性表。返回的線性表為：(a2,a3,…an,a。小題得分2.voidABC(BTNode*BT) (5分){ifBT{ABC(BT->left