1裝訂線(xiàn)裝訂線(xiàn)內(nèi)不要答題題號(hào)一二三分?jǐn)?shù)人1、考生進(jìn)入考場(chǎng)后，按照監(jiān)考老師安排隔位就座，將學(xué)生證放人1、考生進(jìn)入考場(chǎng)后，按照監(jiān)考老師安排隔位就座，將學(xué)生證放在桌面上。無(wú)學(xué)生證者不能參加考試；遲到超過(guò)15分鐘不得入場(chǎng)。在考試開(kāi)始30分鐘后方可交卷出場(chǎng)。2、除必要的文具和主考教師允許的工具書(shū)、參考書(shū)、計(jì)算器以外，其它所有物品（包括空白紙張、手機(jī)、或有存儲(chǔ)、編程、查詢(xún)功能的電子用品等）不得帶入座位，已經(jīng)帶入考場(chǎng)的必須放在監(jiān)考人員指定的位置。3、考試使用的試題、答卷、草稿紙由監(jiān)考人員統(tǒng)一發(fā)放，考試結(jié)束時(shí)收回，一律不準(zhǔn)帶出考場(chǎng)。若有試題印制問(wèn)題請(qǐng)向監(jiān)考教師?出，不得向其他考生?前答完試卷，應(yīng)舉手示意請(qǐng)監(jiān)考人員收卷后方可離開(kāi)；交卷后不得在考場(chǎng)內(nèi)逗留或在附近高聲交談。未交卷擅自離開(kāi)考場(chǎng)，不得重新進(jìn)入考場(chǎng)答卷?？荚嚱Y(jié)束時(shí)間到，考生立即停止答卷，在座位上等待監(jiān)考人員收卷清點(diǎn)后，方可離4、考生要嚴(yán)格遵守考場(chǎng)規(guī)則，在規(guī)定時(shí)間內(nèi)獨(dú)立完成答卷。不準(zhǔn)交頭接耳，不準(zhǔn)偷看、夾帶、抄襲或者有意讓他人抄襲答題內(nèi)容，不準(zhǔn)接傳答案或者試卷等。凡有違紀(jì)作弊者，一經(jīng)發(fā)現(xiàn)，當(dāng)場(chǎng)取消其考試資格，并根據(jù)《北京大學(xué)本科考試工作與學(xué)術(shù)規(guī)范條例》及相關(guān)規(guī)定嚴(yán)肅處理。5、考生須確認(rèn)自己填寫(xiě)的個(gè)人信息真實(shí)、準(zhǔn)確，并承擔(dān)信息填寫(xiě)錯(cuò)誤帶來(lái)的一切責(zé)任與后果。學(xué)校倡議所有考生以北京大學(xué)學(xué)生的榮譽(yù)與誠(chéng)信答卷，共同維護(hù)北京大學(xué)的學(xué)術(shù)聲譽(yù)。2得分第一題填空題（每空1分，共8分）1.設(shè)無(wú)向圖G=(V,E)中V={1,2,3,4,5,6,7}，E={(1,2),(1,3),(2,3),(4,5),(3,6),(4,7),(5,7)}。則圖G包含的不同生成森林的個(gè)數(shù)為。注釋?zhuān)浩渲腥魞蓚€(gè)生成森林的邊集不同，則認(rèn)為它們是不同的生成森林。2.若對(duì)下面的無(wú)向圖以1為起點(diǎn)運(yùn)行單源最短路徑的Dijkstra算法，則在Dijkstra算法的過(guò)程中，每一步依次被選出的頂點(diǎn)依次是。若忽略邊權(quán)，以6為起點(diǎn)進(jìn)行一次廣度優(yōu)先周游，將得到一棵廣度優(yōu)先搜索的生成樹(shù)。設(shè)僅包含一個(gè)結(jié)點(diǎn)的樹(shù)高度為1，則該生成樹(shù)的高度為_(kāi)_，樹(shù)的最深層結(jié)點(diǎn)集合為。3.用某種排序方法對(duì)序列（25,84,21,47,15,27,68,35,20）進(jìn)行排序時(shí)，若序列的變化情況如下，則所采用的排序方法為。25,84,21,47,15,27,68,35,2020,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,844.假設(shè)Shell排序的增量序列是(2k,2k-1,…,2,1)，其中k=[log2n]。若待排序序列是正序的（已經(jīng)排好）或逆序的，則Shell排序的時(shí)間復(fù)雜度分別是___5.設(shè)輸入的關(guān)鍵碼滿(mǎn)足k1>k2>…>kn，緩沖區(qū)大小為m。在n=150,m=25的情況下，用最小值堆進(jìn)行置換-選擇排序方法可產(chǎn)生初始?xì)w并段的個(gè)數(shù)為。36.假定有一棵B+樹(shù)，它的內(nèi)部結(jié)點(diǎn)可以存儲(chǔ)多達(dá)20個(gè)子結(jié)點(diǎn)，葉結(jié)點(diǎn)可以存儲(chǔ)多達(dá)15條記錄（本題中的B+樹(shù)把所有記錄存放在葉結(jié)點(diǎn)上）。那么2層的B+樹(shù)能夠存儲(chǔ)的最多記錄個(gè)數(shù)和最少記錄個(gè)數(shù)分別為、。得分第二題簡(jiǎn)要和辨析題（每小題3分，共15分）1.設(shè)d是帶權(quán)無(wú)向圖G的相鄰矩陣，G的任意兩個(gè)頂點(diǎn)之間至多只有1條邊，若i=j，則d[i][j]=0；若i與j之間有邊權(quán)為w的邊，則d[i][j]=w；若i與j之間無(wú)邊，則d[i][j]=+∞;下面有一段用于求無(wú)向圖中任意兩點(diǎn)間最短路徑的偽代碼：forj←1tondofork←1tondod[i][j]←min(d[i][j],d[i][k]+d[k][j]);請(qǐng)判斷這段偽代碼的正確性。若正確，請(qǐng)給出證明；若錯(cuò)誤，請(qǐng)分析錯(cuò)誤原因并修正。2.請(qǐng)畫(huà)出往下圖的5階B樹(shù)中插入一個(gè)關(guān)鍵碼420后得到的B樹(shù)，以及再刪除關(guān)鍵碼40后得到的B樹(shù)。并請(qǐng)分別分析插入和刪除時(shí)的讀寫(xiě)頁(yè)塊次數(shù)。（假設(shè)刪除關(guān)鍵碼時(shí)，如果需要從兄弟結(jié)點(diǎn)借關(guān)鍵碼的話(huà)，先查看左邊的、再查看右邊的兄弟。在操作之前B樹(shù)所有的結(jié)點(diǎn)頁(yè)塊均在外存，在插入和刪除過(guò)程中，新近被訪(fǎng)問(wèn)過(guò)的外存磁盤(pán)塊都被緩沖在內(nèi)存緩沖區(qū)中，不必重新訪(fǎng)外，abcdef是對(duì)各個(gè)結(jié)點(diǎn)的標(biāo)記）4）3.已知一個(gè)線(xiàn)性表(38，25，74，63，52，48)，采用的散列函數(shù)為H(Key)=Keymod7，將元素散列到表長(zhǎng)為7的散列表中存儲(chǔ)。(1)若采用線(xiàn)性探查的沖突解決策略，則在該散列表上進(jìn)行等概率成功查找的平均查找長(zhǎng)度為多少？請(qǐng)寫(xiě)出計(jì)算過(guò)程。(2)若采用拉鏈法解決沖突，則在該散列表上進(jìn)行等概率成功查找的平均查找長(zhǎng)度為多少？請(qǐng)寫(xiě)出計(jì)算過(guò)程。4.廣義表A=abcad，e（1）畫(huà)出其一種存儲(chǔ)結(jié)構(gòu)圖；（2）寫(xiě)出表的長(zhǎng)度與深度；（3）用求頭部，尾部的方式求出e。5.對(duì)于順序輸入的關(guān)鍵碼{1,2,3,4,5,6,7}（1）嚴(yán)格遵循AVL樹(shù)的操作規(guī)定，畫(huà)出所得到的AVL樹(shù)。（2）嚴(yán)格遵循紅黑樹(shù)的操作規(guī)定，畫(huà)出所得到的紅黑樹(shù)。得分第三題算法填空題（每空1分，共7分）1.下面的代碼實(shí)現(xiàn)了一種計(jì)數(shù)排序：對(duì)每個(gè)待排序記錄，掃?整個(gè)序列統(tǒng)計(jì)比它小的記錄個(gè)數(shù)count，count即是該記錄在序列中的正確位置。template<classRecord>voidSort(RecordArray[],intn){intcurIndex=0;//待排下標(biāo)while(curIndex<n){//需要一直進(jìn)行，直到已經(jīng)遍歷了整個(gè)數(shù)組intcount=0;//統(tǒng)計(jì)比Array[curIndex]小的值的個(gè)數(shù)for()//空缺1if(Array[j]<Array[curIndex])5 ___;//空缺2swap(Array,curIndex,count);/*如果curIndex不用移動(dòng)，考慮下一個(gè)位置；否則，繼續(xù)考慮該位置（因?yàn)槠渌麤](méi)排序的值交換過(guò)來(lái)了）*/if(curIndex==count)____;//空缺3}}2.考慮用雙向鏈表來(lái)實(shí)現(xiàn)一個(gè)有序表，使得能在這個(gè)表中進(jìn)行正向和反向檢索。若指針p總是指向最后成功檢索到的結(jié)點(diǎn)，檢索可以從p所指結(jié)點(diǎn)出發(fā)沿任一方向進(jìn)行。根據(jù)這種情況編寫(xiě)一個(gè)函數(shù)search(head,p,key)，檢索具有關(guān)鍵碼key的結(jié)點(diǎn)，并相應(yīng)地修改p。boolsearch(LinkNode*head,LinkNode*&p,intkey){if(head==NULL)returnfalse;if(p==NULL)p=head;LinkNode*temp=p;while()//空缺4 //空缺5while()//空缺6 //空缺7if(temp->value==key){p=temp;returntrue;}elsereturnfalse;}得分1.一個(gè)具有n個(gè)有序數(shù)據(jù)的線(xiàn)性表，后面又插入了f(n)個(gè)無(wú)序數(shù)據(jù)。針對(duì)下列a)f(n)=O(1)b)f(n)=O(logn)c)f(n)=，6給出對(duì)這樣n+f(n)個(gè)數(shù)據(jù)的排序算法，并分析時(shí)間復(fù)雜度。注釋?zhuān)翰恍枰獙?xiě)具體算法，簡(jiǎn)單說(shuō)一下算法思路就可以。方案二，4分2.營(yíng)業(yè)額統(tǒng)計(jì)TurnoverTiger最近被公司升任為營(yíng)業(yè)部經(jīng)理，他上任后接受公司交給的第一項(xiàng)任務(wù)便是統(tǒng)計(jì)并分析公司成立以來(lái)的營(yíng)業(yè)情況。Tiger拿出了公司的賬本，賬本上記錄了公司成立以來(lái)每天的營(yíng)業(yè)額。分析營(yíng)業(yè)情況是一項(xiàng)相當(dāng)復(fù)雜的工作。由于節(jié)假日，大減價(jià)或者是其他情況的時(shí)候，營(yíng)業(yè)額會(huì)出現(xiàn)一定的波動(dòng)，當(dāng)然一定的波動(dòng)是能夠接受的，但是在某些時(shí)候營(yíng)業(yè)額突變得很高或是很低，這就證明公司此時(shí)的經(jīng)營(yíng)狀況出現(xiàn)了問(wèn)題。經(jīng)濟(jì)管理學(xué)上定義了一種最小波動(dòng)值來(lái)衡量這種情況：該天的最小波動(dòng)值=min{|該天以前某一天的營(yíng)業(yè)額-該天的營(yíng)業(yè)額|}當(dāng)最小波動(dòng)值越大時(shí)，就說(shuō)明營(yíng)業(yè)情況越不穩(wěn)定。而分析整個(gè)公司的從成立到現(xiàn)在營(yíng)業(yè)情況是否穩(wěn)定，只需要把每一天的最小波動(dòng)值加起來(lái)就可以了。你的任務(wù)就是編寫(xiě)一個(gè)程序幫助Tiger來(lái)計(jì)算這一個(gè)值。注釋?zhuān)旱谝惶斓淖钚〔▌?dòng)值為第一天的營(yíng)業(yè)額。數(shù)據(jù)范圍：天數(shù)n≤32767，每天的營(yíng)業(yè)額ai≤1,000,000。最后結(jié)果T≤231。?示：題目的意思非常明確，關(guān)鍵是要每次讀入一個(gè)數(shù)，并且在前面輸入的數(shù)中找到一個(gè)與該數(shù)相差最小的一個(gè)。我們很容易想到O(n2)的算法：每次讀入一個(gè)數(shù)，再將前面輸入的數(shù)一次查找一遍，求出與當(dāng)前數(shù)的最小差值，記入總結(jié)果T。但由于本題中n很大，這樣的算法是不可能在時(shí)限內(nèi)出解的。而如果使用線(xiàn)段樹(shù)記錄已經(jīng)讀入的數(shù)，就需要記下一個(gè)2M的大數(shù)組，空間消耗太大。紅黑樹(shù)與AVL樹(shù)雖然在時(shí)間效率、空間復(fù)雜度上都比較優(yōu)秀，但過(guò)高的編程復(fù)雜度卻讓人望而卻步。建議采用伸展樹(shù)。（1）?述采用伸展樹(shù)求解本問(wèn)題的基本算法思路；（2）利用一下的伸展樹(shù)基本函數(shù)，寫(xiě)出主要算法框架。伸展樹(shù)是一種自平衡的BST，數(shù)據(jù)結(jié)構(gòu)如structTreeNode{intdata;TreeNode*father,*left,*right;可以用的函數(shù)為：voidzag(TreeNode*y);//對(duì)稱(chēng)的左旋(zag)和右旋(z