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

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

2、54利用逐點(diǎn)插入法建立序列（50，72，43，85，75，20，35，45，65，30）對(duì)應(yīng)的二叉排序樹以后，查找元素30要進(jìn)行 次元素間的比較。 A4 B5 C6 D75循環(huán)鏈表的主要優(yōu)點(diǎn)是 。 A不再需要頭指針了 B 已知某個(gè)結(jié)點(diǎn)的位置后，很容易找到它的直接前驅(qū)結(jié)點(diǎn)C在進(jìn)行刪除后，能保證鏈表不斷開 D 從表中任一結(jié)點(diǎn)出發(fā)都能遍歷整個(gè)鏈表6已知一個(gè)線性表（38，25，74，63，52，48），假定采用散列函數(shù)h（key）=key%7計(jì)算散列地址，并散列存儲(chǔ)在散列表A06中，若采用線性探測(cè)方法解決沖突，則在該散列表上進(jìn)行等概率查找時(shí)查找成功的平均查找長(zhǎng)度為 。 A15 B17 C20 D237

3、由權(quán)值為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為 。 A23 B37 C44 D468在最好和最壞情況下的時(shí)間復(fù)雜度均為O（nlogn）且穩(wěn)定的排序方法是 。 A基數(shù)排序 B快速排序 C堆排序 D歸并排序9無向圖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)先遍歷，下面不能得到的序列是 。 Aaebdcf Babedfc Caedfcb Dacfdeb10置換-選擇排序的功能是 。 A產(chǎn)生初始?xì)w并段 B選出最大的元素 C產(chǎn)生有序文件 D置換某個(gè)記錄 11ISAM和

4、VSAM文件屬于 。A索引順序文件 B索引非順序文件 C順序文件 D散列文件二、填空題(18每空2分，912每空1分，共20分）1下面程序段的時(shí)間復(fù)雜度為 【1】 。Sum=1; For (i=0; sum<n; i+) sum+=i;2稀疏矩陣快速轉(zhuǎ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ù)元素依次按a1，a2，an的順序壓入棧中，共有【5】 種出棧序列。5含有4個(gè)結(jié)點(diǎn)的不相似的二叉樹有 【6】 棵。6設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10

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

6、38，49，49【12】三、算法填空題(每空3分,共18分）1 稀疏矩陣快速轉(zhuǎn)置算法/稀疏矩陣的三元組順序表存儲(chǔ)表示#define MAXSIZE 12500 /非零元個(gè)數(shù)最大為12500typedef struct int i,j; /行號(hào),列號(hào) ElemType e; /非零元Triple;typedef struct Triple dataMAXSIZE+1; /三元組表0號(hào)不用 int mu,nu,tu; /總行數(shù),總列數(shù),非零元總個(gè)數(shù)TSMatrix;#define MAXCOL 50status FastTransposeSMatrix(TSMatrix M,TSMatrix &a

7、mp;T)/采用三元組表存儲(chǔ)表示,求稀疏矩陣M的轉(zhuǎn)置矩陣T int numMAXCOL, 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è)非零元在Tdata中的序號(hào)等于cpotcol=

8、cpotcol-1+ ; / 前一列的序號(hào)+前一列非零元個(gè)數(shù) for (p=1; p<=M.tu; +p) col=M.datap.j; /M中第p行的列號(hào)域值賦給col q=cpotcol; /M中的第col列非零元在T.data中的恰當(dāng)位置賦給q T.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è)非零元在Tdata中的位置應(yīng)增1 return OK;2后序遍歷二叉樹非遞歸算法Status PostOrderTraverse1(BiTree t,Sta

9、tus (*Visit)(TElemType e)/后序遍歷二叉樹T非遞歸算法,對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit一次且僅一次. BiTree p; SqStack S; int tag; InitStack(S); do while (t) Push(S,t); ; p=NULL; /p指向當(dāng)前結(jié)點(diǎn)的前一個(gè)已訪問的結(jié)點(diǎn) tag=1; /設(shè)置t的訪問標(biāo)記為已訪問過 while (!StackEmpty(S)&&tag) t=GetTop(S); /取棧頂元素if (t->rchild=p) /右子樹不存在或已被訪問,訪問之 ; /訪問根結(jié)點(diǎn)Pop(S,p); /退棧 p=t

10、; /p指向已被訪問的結(jié)點(diǎn)else t=t->rchild; /t指向右子樹tag=0; /設(shè)置未被訪問的標(biāo)記 while( ); return OK;四、解答題（共20分）1（6分）已知模式串p=cbcaacbcbc，求出p的next數(shù)組值和nextval數(shù)組值。j12345678910模式串pcbcaacbcbcNextjNextvalj2（6分）已知一組關(guān)鍵字為21，33，12，40，68，59，25，51，(1) 試依次插入關(guān)鍵字生成一棵3階的B-樹；(2) 在生成的3階B-樹中依次刪除40和12，畫出每一步執(zhí)行后B-樹的狀態(tài)。3（8分）試對(duì)右圖所示的AOE網(wǎng)絡(luò)，解答下列問題。

11、(1) 求每個(gè)事件的最早開始時(shí)間Vei和最遲開始時(shí)間Vli。1 2 3 4 5 6 VeVl (2) 求每個(gè)活動(dòng)的最早開始時(shí)間e( )和最遲開始時(shí)間l( )。<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6><5, 6> e ll-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)就地逆置。void LinkList_rever

12、se(Linklist &L)/鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2 Linklist p,q,s; p=L->next; q=p->next; s=q->next; p->next=NULL;試題答案及評(píng)分標(biāo)準(zhǔn)一、選擇題（單選題，每小題3分，共33分）1234567891011BBDBDCCDAAA二、填空題(18每空2分，912每空1分，共20分）【1】【2】【3】【4】【5】【6】O()O(tu+nu)O(nu)(b，c，d)14【7】【8】【9】【10】【11】【12】69269快速排序二路歸并排序堆排序鏈?zhǔn)交鶖?shù)排序三、算法填空題(每空3分，共18

13、分）1 M.datat.j numcol-1 +cpotcol2 t=t->lchild Visit(t->data) !StackEmpty(S)四、解答題（共20分）1 (6分)j12345678910模式串pcbcaacbcbcNextj0112112343Nextvalj01021010402(共6分) (1) (2分) 3階B-樹為：(2) （4分） 刪除40后B-樹的狀態(tài) 刪除12后B-樹的狀態(tài)3(8分) 按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間Ve和最遲允許開始時(shí)間Vl。然后再計(jì)算各個(gè)活動(dòng)的最早可能開始時(shí)間e和最遲允許開始時(shí)間l，根據(jù)l - e = 0? 來確定

14、關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。(1) 每個(gè)事件的最早開始時(shí)間Vei和最遲開始時(shí)間Vli 2 3 4 5 6 Ve 0 15 19 29 38 43 Vl 0 15 19 37 38 43 (2) 每個(gè)活動(dòng)的最早開始時(shí)間e( )和最遲開始時(shí)間l( )<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6><5, 6> e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0(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>）(4) 此工程最早完成時(shí)間為43。五、算法設(shè)計(jì)題（9分） 試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2 Linklist