五邑大學(xué)-數(shù)據(jù)結(jié)構(gòu)A卷(附參考答案)

試卷編號(hào)試卷編號(hào)命題人： 審核人： 試卷分類（A卷或B卷） A五邑大學(xué)試卷及參考答案與評(píng)分標(biāo)準(zhǔn)學(xué)期： 至 學(xué)年度 第 1 學(xué)期課程： 數(shù)據(jù)結(jié)構(gòu) 課程代號(hào)： 0800310使用班級(jí)： 姓名： 學(xué)號(hào)：一、、 單項(xiàng)選擇題小題，每小題2分，共20分）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空元素e1,e2,e3,e4,e5,e6依次通過棧一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2,e4,e3,e6,e5,e1，則棧S的容至應(yīng)該是（ B A．2 B．3 C．4 D．6由4個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹該樹的總結(jié)點(diǎn)是（D 。A．4 B．5 C．6 D．7具有具有n個(gè)葉子節(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)對(duì)于長(zhǎng)度為m（m>1）的指定序列，通過初始為空的一個(gè)棧、一個(gè)隊(duì)列后，錯(cuò)誤的敘述是1:1,隊(duì)列第2句：一個(gè)入棧序列可能對(duì)應(yīng)多個(gè)出站隊(duì)列1:n（ D 。A．若入棧和入隊(duì)列的序列相同，則出棧序列和出隊(duì)序列可能相同B．若入棧和入隊(duì)列的序列相同，則出棧序列和出隊(duì)序列可以互為逆序C1:11:n(n≥1)D1:n(n1:1,隊(duì)列第2句：一個(gè)入棧序列可能對(duì)應(yīng)多個(gè)出站隊(duì)列1:n在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指結(jié)點(diǎn)后繼結(jié)，則執(zhí)行（A 。p=q->next; C．p=q->next; p->next=q->next;

p=q->next; q->next=p;D．q->next=q->next->next; q->next=q;題號(hào)題號(hào)得分一二三四五六七八九十總分假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的產(chǎn)；子女之間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ B 。樹 B．圖 C．線性表 D．集合設(shè)數(shù)組S[n]作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S[n]全滿時(shí)才不能進(jìn)進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是（A 。第1頁(yè)共6頁(yè)A．S1的棧底位置為0，S2的棧底位置為n-1B．S1的棧底位置為0，S2的棧底位置為n/2C．S1的棧底位置為0，S2的棧底位置為nD．S1的棧底位置為0，S2的棧底位置為1下面說法中不正確的是（ D 。A．對(duì)稱矩陣只須存放包括主對(duì)角線在內(nèi)的下（或上）三角的元素即B．對(duì)角矩陣只須存放非零元素即可C．稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)（）與線性表長(zhǎng)度）成正比為5個(gè)使用頻率不等的字符設(shè)哈夫曼編，不可能的方案是（A 。A．100，11，10，1，0 C．000，001，010，011，1 D．001，000，01，11，10已知一棵二叉樹的結(jié)點(diǎn)數(shù)為n,若該二叉樹無度為1的結(jié)點(diǎn)，則該二叉樹的葉子結(jié)點(diǎn)數(shù)為（ Ｄ 。 P109 二叉樹的性質(zhì)A．n B．n-1 C．(n-1)/2 D．(n+1)/2滿二叉樹：葉子結(jié)點(diǎn)：n0=（n（結(jié)點(diǎn)數(shù)）+1）/2二叉樹：葉子結(jié)點(diǎn)度為2的節(jié)點(diǎn)則：n0=n2+1求單源最短路徑的迪杰斯特拉（Dijkstra）算法是按（ Ｂ ）的順序求源點(diǎn)到各頂?shù)淖疃搪窂降?。路徑長(zhǎng)度遞減 B．路徑長(zhǎng)度遞增 C．頂點(diǎn)編號(hào)遞減 D．頂點(diǎn)編號(hào)遞減二、得分 （8分）試給出下面稀疏矩陣A的三元組表示。下標(biāo)從0開始。021048214233306４５２515前7行：5分 后3行3分 （非零個(gè)數(shù)）1得分（8分）1點(diǎn)v和廣度優(yōu)先。1第2頁(yè)共6頁(yè)圖1V[6]={v1,v2,v3,v4,v5,v6}DFS:v1v2v3v5v4v6BFS:v1v2v4v6v3v5 2

arc[6][6]=

0 1 0 1 0 11 0 1 1 1 010 1 0 0 1 0 1 0 0 1 10 1 1 1 0 0 0 0 1 0 0四、得分 (8分)圖2是一個(gè)無向網(wǎng)圖，請(qǐng)按Kruskal算法給出求最小生成樹的過程。圖2解：a b a b a b a d d 1 d 1 d 132 e f e f e f e 2 c 2 初始狀態(tài) (b) 邊(b,d)加入 (c)邊(e,f)加入 (d)邊(a,c)加入a b a 5 d 1 d 13 5 3 5c e 2

c e 2 f(e)邊(b,f)加入 (f)邊(a,b)加入(a)和(d)2分，其余各步個(gè)1分五、得分 （8分）試由權(quán)值為291215623的五個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹并求其帶權(quán)路徑長(zhǎng)度。解：6 12 15 23 29 15 18 23 29 23 29 33頁(yè)共6頁(yè)共6第3

15 186 1233 15 18 23

8529 33 52

44步每步1分6 12

15 18 23 296 12 得分（8分）已知模式T=”abaabcab,對(duì)應(yīng)的next[0..7]的值。next0 1 2 3 4 5 6 7-1 0 0 1 1 2 0 1一個(gè)1分得分七、 （8分）為便于存儲(chǔ)和處理一般樹結(jié)構(gòu)形式的信息，常采用孩子—兄弟表示法將其轉(zhuǎn)換成二叉樹（左孩子關(guān)系表示父子、右孩子關(guān)系表示兄弟換成對(duì)應(yīng)的二叉樹是。11 1232 3 4 2 3 45 45 6 圖3

5 6 7 6 7422分

加線 (b)去線 (c)層次調(diào)整八、得分 （8分）已知某二叉樹的中序、層序序列分別為DBAFCEFDEBCA，構(gòu)造該二叉樹，并給出該二叉樹的后序序列。評(píng)分：二叉樹構(gòu)造：5分，后序遍歷序列：3第4頁(yè)共6頁(yè)得分九、 （8分）用容量為n的順序表（n：0~3）表示一個(gè)循環(huán)隊(duì)列Q，Q.front為隊(duì)頭元素的前一個(gè)位置為隊(duì)尾元素位置，填寫循環(huán)隊(duì)列Q在下列運(yùn)算中隊(duì)列和尾變化的情況。得分初始狀態(tài)Q.front0Q.rear0E1進(jìn)隊(duì)（隊(duì)尾rear+1）01出隊(duì)（隊(duì)頭rear+1）11E2進(jìn)隊(duì)12E3進(jìn)隊(duì)13出隊(duì)23E4進(jìn)隊(duì)（循環(huán)：01230）20十、得分 算法設(shè)計(jì)題（2小題，每小題8分，共16分）structnode{ intdata;structnodelchild,rchild;};設(shè)計(jì)算法按前序遍歷次序