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

合肥學(xué)院2013至2014學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程考試（A）卷系級(jí)專業(yè)學(xué)號(hào)姓名題號(hào)一二三四五六七八九十總分得分閱卷大題得分一、選擇題：（2分×15=30分）1． 棧和隊(duì)列的共同特點(diǎn)是(A)。A、只允許在端點(diǎn)處插入和刪除元素B、都是先進(jìn)后出C、都是先進(jìn)先出D、沒(méi)有共同點(diǎn)2． 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D)A、隊(duì)列B、棧C、線性表D、二叉樹3．下面程序的時(shí)間復(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(n) B、O(n2) C、O(n裝訂線4．在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行（B）。A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q5.設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（C）。 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，806．設(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)7.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有(A)條邊才能確保是一個(gè)連通圖。A、5B、6C、7D、88．設(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、abedfc B、acfebd C、aebdfc D、aedfcb9.設(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、910.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（B）。 A、第i行非0元素的個(gè)數(shù)之和 B、第i列非0元素的個(gè)數(shù)之和 C、第i行0元素的個(gè)數(shù)之和 D、第i列0元素的個(gè)數(shù)之和命題教師胡春玲共5頁(yè)，第命題教師胡春玲共5頁(yè)，第1頁(yè) A、top=top+1 B、top=top-1 C、top->next=top; D、top=top->next12.二叉樹的第K層的結(jié)點(diǎn)數(shù)最多為(D)。A、2k-1B、2K+1C、2K-1+1D、2k-113.設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ˋ）。 A、1，2，3，4 B、2，3，4，1 C、1，4，2，3 D、1，2，4，314.設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（A）。 A、4 B、5 C、6 D、715.圖的深度優(yōu)先遍歷類似于二叉樹的(A)。A.先序遍歷 B.中序遍歷 C.后序遍歷 D.層次遍歷大題得分二、填空題：（2分×10=20分）1．設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則在第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中數(shù)據(jù)元素個(gè)數(shù)是n-i+1。2．設(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）。3. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是122427351826。4．設(shè)某無(wú)向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是A[i][j]=1。5. 設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較h次。6. 設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是小根堆，則對(duì)i=1，2，…，n/2而言滿足的條件為ki≤k2i且ki≤k2i+1(2i+1≤n)。7. 下面程序段的功能是實(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);}8．若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出所有結(jié)點(diǎn)的值序列有序排列，應(yīng)對(duì)該二叉排序樹采用______中序_遍歷法。大題得分三、應(yīng)用題：（5分×5=25分）1． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。小題得分共共5頁(yè)，第2頁(yè)小題得分2．請(qǐng)畫出下圖的鄰接矩陣和鄰接表。裝裝訂線3． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給小題得分出構(gòu)造過(guò)程。4． 設(shè)有無(wú)向圖G，要求給出用普里姆算法構(gòu)造最小生成樹和所走過(guò)的邊的集合。小題得分共共5頁(yè)，第3頁(yè)5、 假設(shè)一棵二叉樹的先序序列是ABCDEFGHIJ和中序序列是CDBFEAIHGJ,請(qǐng)畫出該樹。小題得分大題得分四、算法閱讀題：（12分）小題得分1、LinkListmynote(LinkListL)（7分）{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針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；}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,a1）小題得分2．voidABC(BTNode*BT)（5分）{ifBT{ABC(BT->left);ABC(BT->right);visit(BT);}}該算法的功能是：后序遍歷二叉樹遞