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

1、計算機科學與技術(shù)、網(wǎng)絡(luò)工程本科數(shù)據(jù)結(jié)構(gòu)期末考試試卷一、選擇題（單選題，每小題3分，共33分）1已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA，則該二叉樹的后序序列為 。 ABCDEAF BABDCEF CDBACEF DDABECF2在11個元素的有序表A111中進行折半查找（），查找元素A11時，被比較的元素的下標依次是 。 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é)點最近且平衡因子的絕對值為2的結(jié)點）為 。 A27 B38 C51 D7

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

3、由權(quán)值為9，2，5，7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為 。 A23 B37 C44 D468在最好和最壞情況下的時間復雜度均為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）。對該圖進行深度優(yōu)先遍歷，下面不能得到的序列是 。 Aaebdcf Babedfc Caedfcb Dacfdeb10置換-選擇排序的功能是 。 A產(chǎn)生初始歸并段 B選出最大的元素 C產(chǎn)生有序文件 D置換某個記錄 11ISAM和

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

5、)，A22存放位置在676(10)，每個元素占一個空間，則A33(10)存放的位置為 【7】 。(腳注(10)表示用10進制表示)7 若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總的結(jié)點數(shù)是 【8】 。8給定一組關(guān)鍵字49，38，65，97，76，13，27，49，以下用了4種不同的排序方法分別得到了第一趟排序后的結(jié)果，請指出各自對應的排序方法。（每空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)置算法/稀疏矩陣的三元組順序表存儲表示#define MAXSIZE 12500 /非零元個數(shù)最大為12500typedef struct int i,j; /行號,列號 ElemType e; /非零元Triple;typedef struct Triple dataMAXSIZE+1; /三元組表0號不用 int mu,nu,tu; /總行數(shù),總列數(shù),非零元總個數(shù)TSMatrix;#define MAXCOL 50status FastTransposeSMatrix(TSMatrix M,TSMatrix &a

7、mp;T)/采用三元組表存儲表示,求稀疏矩陣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中每一列含非零元個數(shù) cpot1=1; /求第col列中第一個非零元在T.data中的序號 for (col=2; col<=M.nu; +col) /后一列第一個非零元在Tdata中的序號等于cpotcol=

8、cpotcol-1+ ; / 前一列的序號+前一列非零元個數(shù) for (p=1; p<=M.tu; +p) col=M.datap.j; /M中第p行的列號域值賦給col q=cpotcol; /M中的第col列非零元在T.data中的恰當位置賦給q T.dataq.i=M.datap.j; /M中的第p行復制到T中的第q行 T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; ; /M中第col列下一個非零元在Tdata中的位置應增1 return OK;2后序遍歷二叉樹非遞歸算法Status PostOrderTraverse1(BiTree t,Sta

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

10、; /p指向已被訪問的結(jié)點else t=t->rchild; /t指向右子樹tag=0; /設(shè)置未被訪問的標記 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分）試對右圖所示的AOE網(wǎng)絡(luò)，解答下列問題。

11、(1) 求每個事件的最早開始時間Vei和最遲開始時間Vli。1 2 3 4 5 6 VeVl (2) 求每個活動的最早開始時間e( )和最遲開始時間l( )。<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6><5, 6> e ll-e (3) 確定哪些活動是關(guān)鍵活動。畫出由所有關(guān)鍵活動構(gòu)成的圖，指出哪些活動加速可使整個工程提前完成。(4) 這個工程最早可能在什么時間結(jié)束。五、算法設(shè)計題（9分）完成以下算法，對單鏈表實現(xiàn)就地逆置。void LinkList_rever

12、se(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2 Linklist p,q,s; p=L->next; q=p->next; s=q->next; p->next=NULL;試題答案及評分標準一、選擇題（單選題，每小題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快速排序二路歸并排序堆排序鏈式基數(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分) 按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l - e = 0? 來確定

14、關(guān)鍵活動，從而確定關(guān)鍵路徑。(1) 每個事件的最早開始時間Vei和最遲開始時間Vli 2 3 4 5 6 Ve 0 15 19 29 38 43 Vl 0 15 19 37 38 43 (2) 每個活動的最早開始時間e( )和最遲開始時間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)鍵活動為：<1, 3>，<3, 2>，<2, 5>，<5, 6>；加速這些活動可使整個工程提前完成；由所有關(guān)鍵活動構(gòu)成的圖：（關(guān)鍵路徑為：<1, 3><3, 2><2, 5><5, 6>）(4) 此工程最早完成時間為43。五、算法設(shè)計題（9分） 試寫一算法，對單鏈表實現(xiàn)就地逆置。void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2 Linklist