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

命題教師命題教師胡春玲共一5頁,第_1_頁合肥學(xué)院2013至2014學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計 課程考試(A)卷系—級專業(yè)學(xué)號姓名題號一一二四五六七八九十總分得分閱卷一、選擇題：(2分X15=30分) 大題得分.棧和隊列的共同特點是(A.棧和隊列的共同特點是(A)。A、只允許在端點處插入和刪除元素C、都是先進先出 D、沒有共同點.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？A、隊列 B、棧.下面程序的時間復(fù)雜為(B)。for(i=1,s=0;i<=n;i++){t=1A、O(n)B、O(n2)C、O(n3)B、都是先進后出(D)C、線性表 D、二叉樹;for(j=1;j<=i;j++)t=t*j;s=s+t;}D、O(n4)4.在一個單鏈表中，已知執(zhí)行(B)0A.s->next=p->next;q結(jié)點是p結(jié)點的前趨結(jié)點，若在4.在一個單鏈表中，已知執(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),則以第一個記錄關(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è)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為(D)。A、O(log2n) B、O(1)C、O(n2)D、O(n).設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有(A)條邊才能確保是一個連通圖。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)},則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為(A)。A、abedfcB、acfebdC、aebdfcD、aedfcb.設(shè)散列表長m=14，散列函數(shù)H(K)=K%11,已知表中已有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、9.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為(B)。A、第i行非0元素的個數(shù)之和 B、第i歹I」非0元素的個數(shù)之和C、第i行0元素的個數(shù)之和D、第i列0元素的個數(shù)之和.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為(D)0

A、top=top+1B、top=top-1C、top->next=top;D、top=top->next.二叉樹的第K層的結(jié)點數(shù)最多為（D）。A、2k-1 B、2K+1 C、2K-1+1 D、2k-1.設(shè)有向無環(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個數(shù)據(jù)元素，則在第數(shù)據(jù)元素個數(shù)是 n-i+1 。45,18,26,54,92),則由這組記錄關(guān)鍵字C.后序遍歷 D.層次遍歷大題得分i個位置上插入一個數(shù)據(jù)元素需要移動表中.設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的新結(jié)點X,則在p后進行插入操作的語句片列為(s->next=p->next;p->next=s)(設(shè)結(jié)點的指針域為next)o.設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后的結(jié)果的是122427351826。.設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是 A[i][j]=1。.設(shè)二叉排序樹的高度為h,則在該樹中查找關(guān)鍵字key最多需要比較 h次。.設(shè)一組初始記錄關(guān)鍵字序列(k1,k2,……,kn)是小根堆,則對61,2,…，n/2而言滿足的條件為_kiwk2i且kiWk2i+1(2i+1<n)。.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。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）;}.若要對某二叉排序樹進行遍歷，保證輸出所有結(jié)點的值序列有序排列，應(yīng)對該二叉排序大題得分樹采用中序遍歷法。三、應(yīng)用題：(5分X5=25分)1.設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。小題得分

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

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