數(shù)據(jù)結(jié)構(gòu)期末試題及答案

1、電腦科學(xué)與技術(shù)、網(wǎng)絡(luò)工程本科數(shù)據(jù)結(jié)構(gòu)期末考試試卷一、選擇題單項(xiàng)選擇題，每題3分，共33分1 .已知某二叉樹(shù)的中序、層序序列分別為DBAFCE、FDEBCA,則該二叉樹(shù)的后序序列為。A.BCDEAFB.ABDCEFC.DBACEFD.DABECF2 .在11個(gè)元素的有序表A111中進(jìn)行折半查找（lowhigh）/2，查找元素A11時(shí)，被比較的元素的下標(biāo)依次是。A.6,8,10,11B.6,9,10,11C.6,7,9,11D,6,8,9,113 .由元素序列27,16,75,38,51構(gòu)造平衡二叉樹(shù)，則首次出現(xiàn)的最小不平衡子樹(shù)的根即離插入結(jié)點(diǎn)最近且平衡因子的絕對(duì)值為2的結(jié)點(diǎn)為。A.27B.38C

2、.51D.754 .利用逐點(diǎn)插入法建立序列50,72,43,85,75,20,35,45,65,30對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素30要進(jìn)行次元素間的比較。A.4B.5C.6D.75.循環(huán)鏈表的主要優(yōu)點(diǎn)是 。A.不再需要頭指針了 直接前驅(qū)結(jié)點(diǎn)C.在進(jìn)行刪除后，能保證鏈表不斷開(kāi) 鏈表B.已知某個(gè)結(jié)點(diǎn)的位置后，很容易找到它的D.從表中任一結(jié)點(diǎn)出發(fā)都能遍歷整個(gè)7.由權(quán)值為 9, 2, 5, 為。A. 23B. 37C. 44D. 466.已知一個(gè)線性表38,25,74,63,52,48，假定采用散列函數(shù)hkey=key%7計(jì)算散列地址，并散列存儲(chǔ)在散列表A06中，假設(shè)采用線性探測(cè)方法解決沖突，則在該

3、散列表上進(jìn)行等概率查找時(shí)查找成功的平均查找長(zhǎng)度為。B.1.7C.2.0D,2.37的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度8 .在最好和最壞情況下的時(shí)間復(fù)雜度均為Onlogn且穩(wěn)定的排序方法是。A.基數(shù)排序B.快速排序C.堆排序D.歸并排序9 .無(wú)向圖G=（V,E）,其中V=a,b,c,d,e,f,E=（a,b）,a,e，（a,c）,b,e，c,f，（f,d）,e,d。對(duì)該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列是。A.aebdcfB.abedfcC.aedfcbD.acfdeb10 .置換-選擇排序的功能是。A.產(chǎn)生初始?xì)w并段B.選出最大的元素C.產(chǎn)生有序文件D.置換某個(gè)記錄11.I

4、SAM和VSAM文件屬于。A.索引順序文件B.索引非順序文件C.順序文件D.散列文件二、填空題（18每空2分，912每空1分，共20分1 .下面程序段的時(shí)間復(fù)雜度為L(zhǎng)1J。Sum=1;For（i=0;sum<n;i+）sum+=i;2 .稀疏矩陣快速轉(zhuǎn)置算法(見(jiàn)第三題第1小題)的時(shí)間復(fù)雜度為【2】,空間復(fù)雜度為【3】。3 .對(duì)廣義表A=(a,(b,c,d)的運(yùn)算head(rail(A)的結(jié)果是4。4 .將n個(gè)數(shù)據(jù)元素依次按al,a2,，an的順序壓入棧中，共有【5種出棧序列。5 .含有4個(gè)結(jié)點(diǎn)的不相似的二叉樹(shù)有【6】棵。6 .設(shè)有一個(gè)二維數(shù)組Amn,假設(shè)A00存放位置在644(10),A

5、22存放位置在676(10),每個(gè)元素占一個(gè)空間，則A33(10)存放的位置為【7】。(腳注(10)表示用10進(jìn)制表本)7 .假設(shè)某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總的結(jié)點(diǎn)數(shù)是18】。8 .給定一組關(guān)鍵字49,38,65,97,76,13,27,49),以下用了4種不同的排序方法分別得到了第一趟排序后的結(jié)果，請(qǐng)指出各自對(duì)應(yīng)的排序方法。每空1分A趟排序后的結(jié)果排序方法27,38,13,49,76,97,65,491【9】38,49,65,97,13,76,27,491【10】49；76,65,49,38,13,27,97【11】113,65,76,97,27,38,

6、49,491【12】三、算法填空題(每空3分，共18分1.稀疏矩陣快速轉(zhuǎn)置算法/稀疏矩陣的三元組順序表存儲(chǔ)表示#defineMAXSIZE12500非零元個(gè)數(shù)最大為12500typedefstructinti,j;行號(hào)，列號(hào)ElemTypee;非零元Triple;typedefstructTripledataMAXSIZE+1;三元組表.0號(hào)不用intmu,nu,tu;總行數(shù)，總列數(shù)，非零元總個(gè)數(shù)TSMatrix;#defineMAXCOL50statusFastTransposeSMatrix(TSMatrixM,TSMatrix&T)采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T.

7、intnumMAXCOL,cpotMAXCOL,col,t,p,q;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col<=M.nu;+col)numcol=0;for(t=1;t<=M.tu;+t)+num;求M中每一列含非零元個(gè)數(shù)cpot1=1;求第col列中第一個(gè)非零元在T.data中的序號(hào)for(col=2;col<=M.nu;+col)后一列第一個(gè)非零元在T.data中的序號(hào)等于cpotcol=cpotcol-1+;/前一列的序號(hào)+前一列非零元個(gè)數(shù)for(p=1;p<=M.tu;+p)col=M.datap.j

8、;/M中第p行的列號(hào)域值賦給colq=cpotcol;/M中的第col列非零元在T.data中的恰當(dāng)位置賦給qT.dataq.i=M.datap.j;M中的第p行復(fù)制到T中的第q行T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;/M中第col列下一個(gè)非零元在T.data中的位置應(yīng)增1returnOK;2.后序遍歷二叉樹(shù)非遞歸算法StatusPostOrderTraverse1(BiTreet,Status(*Visit)(TElemTypee)后序遍歷二叉樹(shù)T非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit一次且僅一次BiTree p; SqStack S; int

9、 tag; InitStack(S); do while (t) Push(S,t);p=NULL;/ptag=1;/while (!StackEmpty(S)&&tag)t=GetTop(S); / if (t->rchild=p) /；/Pop(S,p);/p=t;/pelse t=t->rchild;/ttag=0;/while( )；return OK; 四、解答題共20分1指向當(dāng)前結(jié)點(diǎn)的前一個(gè)已訪問(wèn)的結(jié)點(diǎn)設(shè)置t的訪問(wèn)標(biāo)記為已訪問(wèn)過(guò)取棧頂元素右子樹(shù)不存在或已被訪問(wèn)，訪問(wèn)之訪問(wèn)根結(jié)點(diǎn)退棧指向已被訪問(wèn)的結(jié)點(diǎn)指向右子樹(shù)設(shè)置未被訪問(wèn)的標(biāo)記j12345678910模式

10、串pcbcaacbcbcNextjNextvalj1.6分已知模式串p='cbcaacbcbc',求出p的next數(shù)組彳I和nextval數(shù)組值。2.6分已知一組關(guān)鍵字為21,33,12,40,68,59,25,51,(1)試依次插入關(guān)鍵字生成一棵3階的B-樹(shù)；(2)在生成的3階B-樹(shù)中依次刪除40和12,畫出每一步執(zhí)行后B-樹(shù)的狀態(tài)。3.8分試對(duì)右圖所示的AOE網(wǎng)絡(luò)，解答以下問(wèn)題。(1)求每個(gè)事件的最早開(kāi)始時(shí)間Vei和最遲開(kāi)始時(shí)間Vli。123456VeVl(2)求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e()和最遲開(kāi)始時(shí)間1()。<1,2><1,3><3,2&g

11、t;<2,4><2,5><3,5><4,6><5,6>ell-e(3)確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。(4)這個(gè)工程最早可能在什么時(shí)間結(jié)束。五、算法設(shè)計(jì)題9分完成以下算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。voidLinkList_reverse(Link1ist&L)鏈表的就地逆置；為簡(jiǎn)化算法，假設(shè)表長(zhǎng)大于2Linklistp,q,s;p=L->next;q=p->next;s=q->next;p->next=NULL;試題答案及評(píng)分標(biāo)準(zhǔn)、選擇題單項(xiàng)選擇題

12、，每題3分，共33分1234567891011BBDBDCCDAAA、填空題(18每空2分，912每空1分，共20分【1】【3】【4】【5】【6】O(vn)O(tu+nu)O(nu)(b,c,d)1Cn或1(2n)!n12nn1(n!)214【7】【8】【9】【10】【11】【12】69269快速排序二路歸并排序堆排序鏈?zhǔn)交鶖?shù)排序三、算法填空題(每空3分，共18分1. M.datat.jnumcol-1+cpotcol2. t=t->lchildVisit(t->data)！StackEmpty(S)四、解答題共20分1.(6分)j12345678910模式串pcbcaacbcbc

13、Nextj0112112343Nextvalj0102101040刪除40后B-樹(shù)的狀態(tài)刪除12后B-樹(shù)的狀態(tài)3. (8分)按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間2.(共6分)(1)(2分)3階B-樹(shù)為:(4)此工程最早完成時(shí)間為43。Ve和最遲允許開(kāi)始時(shí)間V1。然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間1,根據(jù)1-e=0?來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。(1)每個(gè)事件的最早開(kāi)始時(shí)間Vei和最遲開(kāi)始時(shí)間V1i23456Ve01519293843Vl01519373843(2)每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e()和最遲開(kāi)始時(shí)間1()<1,2><1,3>&l

14、t;3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938l170152719273738l-e1700801280(3)關(guān)鍵活動(dòng)為：<1,3>,<3,2>,<2,5>,<5,6>加速這些活動(dòng)可使整個(gè)工程提前完成；由所有關(guān)鍵活動(dòng)構(gòu)成的圖：關(guān)鍵路徑為：<1,3><3,2><2,5><5,6>五、算法設(shè)計(jì)題9分試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。voidLinkList_reverse(Link1ist&L)鏈表的就地逆置；為簡(jiǎn)化算法，假設(shè)表長(zhǎng)大于2Linklist