寧波大學2022年數(shù)據(jù)結(jié)構(gòu)與算法考研真題

寧波大學2022年[數(shù)據(jù)結(jié)構(gòu)與算法]考研真題選擇題1.采用鏈式存儲結(jié)構(gòu)表示數(shù)據(jù)時，相鄰的數(shù)據(jù)元素的存儲地址（）。A.一定不連續(xù)B.不一定連續(xù)C.一定連續(xù)D.部分連續(xù)，部分不連續(xù)2.在一個單鏈表中，若*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;3.用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中結(jié)點，使j沿鏈移動的操作為()。A.j=j->nextB.j=r[j].nextC.j=j+1D.j=r[j]->next4.向一個棧頂指針為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;5.已知一個推入堆棧的字符序列順序是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,e6.循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)7.在一個具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊空的條件是（）。A.front==(rear+1)%n B.front==rearC.front==0 D.(front+1)%n==rear 8.對順序存儲的線性表，設其長度為n，在任何位置上插入或刪除操作都是等概念的，插入一個元素時平均要移動表中的（）個元素。A.(n－1)/2B.nC.n/2D.(n＋1)/29.對廣義表A=（（a,(b)）,(c,()),d）執(zhí)行操作gettail(gethead(gettail(A)))的結(jié)果是：（）。A.（）B.（（））C.dD.(d)10.構(gòu)造哈希表的關鍵字的輸入序列為(25,21,30,13,4,43,35,64,5,17,2,8)，哈希函數(shù)H(key)=key%15，采用鏈地址法解決沖突。查找64的關鍵字比較次數(shù)是（）。A.1B.2C.4D.311.下圖是一個二叉樹后序遍歷的結(jié)果是（）。A、abcdefB、cfabdeC、dbaecfD、cbfade12.現(xiàn)有以下按前序和中序遍歷二叉樹的結(jié)果：前序：GAHFDBCE中序：AHGBDCFE，該二叉樹的后序遍歷序列為()。A.GHABCDEFB.HABCDEFGC.ABCDEFGHD.HABCGDEF13.一棵完全二叉樹的第6層（設根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是（）。A.39B.119C.111D.23914.一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）。A.是一棵滿二叉樹B.所有的結(jié)點均無右孩子C.所有的結(jié)點均無左孩子D.只有一個葉子結(jié)點15.任何一個連通圖的最小生成樹()。A．只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在

填空題1.已知某二叉樹的先序遍歷次序為abcdefg，中序遍歷次序為badcgfe，則該二叉樹的后序遍歷次序為____________，層次遍歷次序為___________。2.對于長度為n的關鍵字有序的線性表，若進行順序查找，則平均時間復雜度為________；若采用二分法查找，則平均時間復雜度為________；3.在一棵度為3的樹中，度為3的結(jié)點個數(shù)為3，度為2的結(jié)點個數(shù)為2，度為1的結(jié)點個數(shù)為1，則度為0的結(jié)點個數(shù)為________。4.在一棵m階B-樹中，除根結(jié)點外非葉結(jié)點至少有________棵子樹，至多有________棵子樹。5.分別采用堆排序、快速排序、冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是________算法，最費時間的是________算法6.如圖所示的有向無環(huán)圖可以排出________種不同的拓撲序列。7.給定一組數(shù)據(jù){6，2，7，10，3，12}，以它構(gòu)造一棵哈夫曼樹，則樹高為__________，帶權(quán)路徑長度WPL的值為__________。8.已知一組待排序的記錄關鍵字初始排列如下：56268635751977584842；則快速排序一趟排序的結(jié)果是，希爾排序（初始步長為3）一趟排序的結(jié)果是。簡答題1.按關鍵字13、24、37、90、53、34的次序構(gòu)造一棵平衡二叉樹，回答以下問題：（1）該平衡二叉樹的高度是多少？ （2）其根節(jié)點的關鍵字是什么？（3）其中經(jīng)過了哪些調(diào)整？（指出調(diào)整名稱和次數(shù)）2.根據(jù)下圖G以及它的存儲，分別寫出廣度和深度遍歷結(jié)果。設第一個訪問結(jié)點是1。3.下圖所示的AOE網(wǎng)絡用于描述一項工程，其中的頂點表示事件，邊代表一次活動，邊上的權(quán)值表示完成該活動所需的時間，試回答以下問題：(1)完成整個工程所需的總時間是多少？(2)給出整個工程的關鍵活動和關鍵路徑。4.設散列表的長度為13，散列函數(shù)為H（k）=k%13，給定的關鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。01234567891011125.下圖表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設線路花費的代價，如何選擇能溝通每個城市且總代價最省的n-1條線路，畫出所有可能的選擇。6.已知關鍵字序列（60，20，31，1，5，44，55，61，200），寫出對它進行第一趟快速排序（以第一個關鍵字為基準）后的序列的值，并指出它的穩(wěn)定性.7.請給出Dijkstra最短路徑算法的主要步驟，如果加權(quán)圖如下所示，請計算從頂點1到其它所有頂點的最短路徑，給出算法具體執(zhí)行過程中頂點集合的擴展情況。如果有些弧上加權(quán)為負，請問Dijkstra算法是否還能正常運行？為什么？如果不能正常運行請給出解決方法。8.已知關鍵字序列在R[1..8]中的初始狀態(tài)為R487033652456129212345678寫出在將它調(diào)整為大根堆的過程中每一次篩選后R的狀態(tài)。算法設計題1.請設計合理算法，在O(n)時間復雜度條件下，將中綴式a+3*b+4*(c-d)轉(zhuǎn)化為對應的后綴表式并計算出表達式的值，若a=1，b=2，c=4，d=3，給出計算結(jié)果。2.假設二叉樹采用二叉鏈存儲結(jié)構(gòu)進行存儲，每個結(jié)點有data、lchild和rchild三個域。設計一個算法，計算一棵給定二叉樹中節(jié)點值為x的節(jié)點個數(shù)（注意在一棵二叉樹中可能存在相同節(jié)點值的節(jié)點），并給出