數(shù)據(jù)結(jié)構(gòu)試卷A卷及答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)試卷A卷及答案計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2023年春季學(xué)期2023級(jí)計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程本科《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷（A卷、閉卷）

一、選擇題（單項(xiàng)選擇題，每題3分，共33分）

1．已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA，則該二叉樹的后序序列為。A．BCDEAFB．ABDCEFC．DBACEFD．DABECF

2．在11個(gè)元素的有序表A[1…11]中進(jìn)行折半查找（?(low?high)/2?），查找元素A[11]時(shí)，被比較的元素的下標(biāo)依次是。

A．6，8，10，11B．6，9，10，11C．6，7，9，11D．6，8，9，11

3．由元素序列（27，16，75，38，51）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點(diǎn)最近且平衡因子的絕對(duì)值為2的結(jié)點(diǎn)）為。

A．27B．38C．51D．75

4．利用逐點(diǎn)插入法建立序列（50，72，43，85，75，20，35，45，65，30）對(duì)應(yīng)的二叉排序樹以后，查找元素30要進(jìn)行次元素間的比較。

A．4B．5C．6D．75．循環(huán)鏈表的主要優(yōu)點(diǎn)是。

A．不再需要頭指針了B．已知某個(gè)結(jié)點(diǎn)的位置后，很簡(jiǎ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ǔ)在散列表A[0…6]中，若采用線性探測(cè)方法解決沖突，則在該散列表上進(jìn)行等概率查找時(shí)查找成功的平均查找長(zhǎng)度為。

A．1．5B．1．7C．2．0D．2．3

7．由權(quán)值為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為。A．23B．37C．44D．46

8．在最好和最壞狀況下的時(shí)間繁雜度均為O（nlogn）且穩(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．a(chǎn)ebdcfB．a(chǎn)bedfcC．a(chǎn)edfcbD．a(chǎn)cfdeb10．置換-選擇排序的功能是。

A．產(chǎn)生初始?xì)w并段B．選出最大的元素C．產(chǎn)生有序文件D．置換某個(gè)記錄11．ISAM和VSAM文件屬于。

A．索引順序文件B．索引非順序文件C．順序文件D．散列文件

二、填空題(1~8每空2分，9~12每空1分，共20分）

1．下面程序段的時(shí)間繁雜度為。Sum=1;For(i=0;sumrchild==p)//右子樹不存在或已被訪問,訪問之{⑤;//訪問根結(jié)點(diǎn)Pop(S,p);//退棧

p=t;}//p指向已被訪問的結(jié)點(diǎn)else{t=t->rchild;//t指向右子樹

tag=0;}//設(shè)置未被訪問的標(biāo)記}

}while(⑥);returnOK;}

四、解答題（共20分）

1．（6分）已知模式串p=’cbcaacbcbc’，求出p的next數(shù)組值和nextval數(shù)組值。j模式串pNext[j]1c2b3c4a5a6c7b8c9b10cNextval[j]2．（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ò)，解答以下問題。(1)求每個(gè)事件的最早開始時(shí)間Ve[i]和最遲開始時(shí)間Vl[i]。VeVlell-e1①2③3②4④5⑤6⑥(2)求每個(gè)活動(dòng)的最早開始時(shí)間e()和最遲開始時(shí)間l()。(3)確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。

(4)這個(gè)工程最早可能在什么時(shí)間終止。五、算法設(shè)計(jì)題（9分）

完成以下算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。voidLinkList_reverse(Linklist為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2Linklistp,q,s;

p=L->next;q=p->next;s=q->next;p->next=NULL;

3

2023年春季學(xué)期2023級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科

《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷（A卷、閉卷）

試題答案及評(píng)分標(biāo)準(zhǔn)

一、選擇題（單項(xiàng)選擇題，每題3分，共33分）1B2B3D4B5D6C7C8D9A10A11A

二、填空題(1~8每空2分，9~12每空1分，共20分）O(n)

69269堆排序鏈?zhǔn)交鶖?shù)排序快速排序二路歸并排序14O(tu+nu)O(nu)(b，c，d)11(2n)!nC2或n2n?1n?1(n!)

三、算法填空題(每空3分，共18分）

1．①M(fèi).data[t].j②num[col-1]③++cpot[col]2．④t=t->lchild⑤Visit(t->data)⑥!StackEmpty(S)

四、解答題（共20分）

1．(6分)j2．(共6分)模式串p階B-樹為：

Next[j]Nextval[j]1c002b113c104a225a116c107b218c309b4410c30(1)(2分)3

(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?來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。

(1)每個(gè)事件的最早開始時(shí)間Ve[i]和最遲開始時(shí)間Vl[i]

4

Vlell-e①0017172③15150003②1919151504④2937192785⑤38386⑥4343Ve0(2)每個(gè)活動(dòng)的最早開始時(shí)間e()和最遲開始時(shí)間l()191901527122937838380(3)關(guān)鍵活動(dòng)為：，，，；加速這些活動(dòng)可使整個(gè)工程提前完成；由所有關(guān)鍵活動(dòng)構(gòu)成的圖：（關(guān)鍵路徑為：）

1

1534219556(4)此工程最早完成時(shí)間為43。

五、算法設(shè)計(jì)題（9分）

試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。

voidLinkList_reverse(Linklist為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2Linklistp,q,s;

p=L->next;q=p->next;s=q->next;p->next=NULL;解：

while(s->next)