2019年寧波大學(xué)信息科學(xué)與工程學(xué)院碩士自命題科目真題916數(shù)據(jù)結(jié)構(gòu)與算法

寧波大學(xué)2019年碩士研究生招生考試初試試題(A卷)(答案必須寫在考點提供的答題紙上)科目代碼：916總分值：150科目名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 一、選擇題：(共30分，每題2分)TOC\o"1-5"\h\z采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示數(shù)據(jù)時，相鄰的數(shù)據(jù)元素的存儲地址( )。A.一定不連續(xù) B.不一定連續(xù)C.一定連續(xù) D.部分連續(xù)，部分不連續(xù)在一個單鏈表中，若*p節(jié)點不是最后節(jié)點，在*p之后插入節(jié)點*s,則執(zhí)行( )。A.s->next=p;p->next=s; B.s->next=p->next;p->next=s;C.s->next=p->next;p=s; D.p->next=s;s->next=p;用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中結(jié)點，使j沿鏈移動的操作為( )。A.j=j->next B.j=r[j].next C.j=j+l D.j=r[j]->next向一個棧頂指針為HS的鏈棧(帶頭結(jié)點)中插入一個s所指結(jié)點時，則執(zhí)行( )。A.s->next=HS;HS=s; B. HS->next=s;C.s->next=HS->next;HS->next=s; D. s->next=HS;HS=HS->next;已知一個推入堆棧的字符序列順序是a,b,c,d,e,下列哪個字符序列是不能通過堆棧操作得到的字符序列( )。A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e循環(huán)隊列存儲在數(shù)組A[0..m]中，貝9入隊時的操作為( )。A.rear=rear+1 B. rear=(rear+1)mod(m-1)C.rear=(rear+1)modm D. rear=(rear+1)mod(m+1)在一個具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針,則判斷隊空的條件是( )。A.front==(rear+1)%n B.front==rearC.front==0 D.(front+1)%n==rear對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概念的，插入一個元素時平均要移動表中的( )個元素。A.(n—1)/2B.n C.n/2 D.(n+1)/2TOC\o"1-5"\h\z對廣義表A=((a,(b)),(c,()),d)執(zhí)行操作gettail(gethead(gettail(A)))的結(jié)果是：( )。A.() B.(()) C.d D.(d)構(gòu)造哈希表的關(guān)鍵字的輸入序列為(25,21,30,13,4,43,35,64,5,17,2,8)，哈希函數(shù)H(key)=key%15，采用鏈地址法解決沖突。查找64的關(guān)鍵字比較次數(shù)是( )。A.1 B.2 C.4 D. 3（答案必須寫在考點提供的答題紙上）科目代碼：916總分值：150科目名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 TOC\o"1-5"\h\z下圖是一個二叉樹后序遍歷的結(jié)果是（ ）。A、abcdef B、cfabdeC、dbaecf D、cbfade現(xiàn)有以下按前序和中序遍歷二叉樹的結(jié)果：前序:GAHFDBCE中序:AHGBDCFE，該二叉樹的后序遍歷序列為（ ）。A.GHABCDEF B.HABCDEFGC.ABCDEFGH D.HABCGDEF一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是（ ）。A.39 B.119 C.111 D.239一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）。A.是一棵滿二叉樹 B.所有的結(jié)點均無右孩子C.所有的結(jié)點均無左孩子 D.只有一個葉子結(jié)點TOC\o"1-5"\h\z任何一個連通圖的最小生成樹（ ）。A?只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在二、填空題：（共28分，每空2分）已知某二叉樹的先序遍歷次序為abcdefg，中序遍歷次序為badcgfe，則該二叉樹的后序遍歷次序為 ，層次遍歷次序為 。對于長度為n的關(guān)鍵字有序的線性表，若進(jìn)行順序查找，則平均時間復(fù)雜度為 ；若采用二分法查找，則平均時間復(fù)雜度為 ;3?在一棵度為3的樹中，度為3的結(jié)點個數(shù)為3,度為2的結(jié)點個數(shù)為2,度為1的結(jié)點個數(shù)為1，則度為0的結(jié)點個數(shù)為 。在一棵m階B-樹中，除根結(jié)點外非葉結(jié)點至少有 棵子樹，至多有 棵子樹。

（答案必須寫在考點提供的答題紙上）科目代碼：916總分值：150科目名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 分別采用堆排序、快速排序、冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是 算法，最費時間的是 算法如圖所示的有向無環(huán)圖可以排出 種不同的拓?fù)湫蛄小?gI1TTTLL?gI1TTTLL給定一組數(shù)據(jù)｛6，2，7，10，3,12｝，以它構(gòu)造一棵哈夫曼樹，則樹高為 ，帶權(quán)路徑長度WPL的值為 。已知一組待排序的記錄關(guān)鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42；則快速排序一趟排序的結(jié)果是 ，希爾排序（初始步長為3）一趟排序的結(jié)果是 。三、簡答題：（共52分）按關(guān)鍵字13、24、37、90、53、34的次序構(gòu)造一棵平衡二叉樹，回答以下問題：（8分）（1） 該平衡二叉樹的高度是多少？（2） 其根節(jié)點的關(guān)鍵字是什么？（3） 其中經(jīng)過了哪些調(diào)整？（指出調(diào)整名稱和次數(shù)）根據(jù)下圖G以及它的存儲，分別寫出廣度和深度遍歷結(jié)果。設(shè)第一個訪問結(jié)點是1。（6分）—H2I gI4卩皿|—5I1TTJLL]—>13IH-H5

（答案必須寫在考點提供的答題紙上）科目代碼：916總分值：150科目名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 下圖所示的AOE網(wǎng)絡(luò)用于描述一項工程，其中的頂點表示事件，邊代表一次活動，邊上的權(quán)值表示完成該活動所需的時間，試回答以下問題：（6分）（1） 完成整個工程所需的總時間是多少？（2） 給出整個工程的關(guān)鍵活動和關(guān)鍵路徑。4.設(shè)散列表的長度為13,散列函數(shù)為H（k）=k%13，給定的關(guān)鍵碼序列為19，14，23,01，68，20，84，27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。（5分）0 1 2 3 4 5 6 7 8 9 10 11 125.下圖表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的代價,如何選擇能溝通每個城市且總代價最省的n-1條線路，畫出所有可能的選擇。（7分）6.已知關(guān)鍵字序列（60,20，31，1，5,44,55,61，200），寫出對它進(jìn)行第一趟快速排序（以第一個關(guān)鍵字為基準(zhǔn)）后的序列的值，并指出它的穩(wěn)定性（6分）（答案必須寫在考點提供的答題紙上）科目代碼：916總分值：150科目名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 7.請給出Dijkstra最短路徑算法的主要步驟，如果加權(quán)圖如下所示，請計算從頂點1到其它所有頂點的最短路徑，給出算法具體執(zhí)行過程中頂點集合的擴展情況。如果有些弧上加權(quán)為負(fù)，請問Dijkstra算法是否還能正常運行？為什么？如果不能正常運行請給出解決方法。（8分）8.已知關(guān)鍵字序列在R[1..8]中的初始狀態(tài)為48703365245612921 2 3 4 5 6 7 8寫出在將它調(diào)整為大根堆的過程中每一次篩選后R的狀態(tài)。（6分）四、算法設(shè)計題：（共40分）1?請設(shè)計合理算法，在O（n）時間復(fù)雜度條件下，將中綴式a+3*b+4*（c-d）轉(zhuǎn)化為對應(yīng)的后綴表式并計算出表達(dá)式的值，若a=1，b=2，c=4，d=3，給出計算結(jié)果。（15分）假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)進(jìn)行存儲，每個結(jié)點有data、lchild和rchild三個域。設(shè)計一個算法，計算一棵給定二叉樹中節(jié)點值為x的節(jié)點個數(shù)（注意在一棵二叉樹中可能存在相同節(jié)點值