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

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

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