算法與數(shù)據(jù)結(jié)構(gòu)試卷

1、、選擇題(10*2%=20%)1.代碼段 for (j=1; j=1; k/=2)count+;A、O(n2)B、O(nlogn)C、O(logn)D、O(n)對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，下列敘述正確的 A。A、第i行上的非零元素個(gè)數(shù)和第i列上的非零元素個(gè)數(shù)一定相等B、矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)C、第i行與第i列上的非零元素的總數(shù)等于頂點(diǎn)vi的度數(shù)D、矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù)循環(huán)雙鏈表中在p所指結(jié)點(diǎn)之后插入結(jié)點(diǎn)s的操作是 DA、p-next=s; s-prior=p; p-next-prior=s; s-next=p-nextB、p-next=s; p-next-prior

2、=s; s-prior=p; s-next=p-nextC、s-prior=p; s-next=p-next; p-next=s; p-next-prior=sD、s-prior=p; s-next=p-next; p-next-prior=s; p-next=s4個(gè)元素a1, a2, a3和a4依次通過(guò)一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)如圖，棧頂一棧底tA、a4，a3，a2，不可能的出棧順序是a1B、 a3, a2, a4, a1C、a3，a1，a4，a2 D、a3，a4，a2，a1 TOC o 1-5 h z 下列四種排序方法中，不穩(wěn)定的方法是D。A、插入排序B、冒泡排序C、歸并排序D、選擇排

3、序單個(gè)結(jié)點(diǎn)二叉樹(shù)的高度為0，所有含有15個(gè)結(jié)點(diǎn)的二叉樹(shù)中，最小高度DA、6B、5C、4D、3 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要B_條邊。A、nB、n-1C、n/2D、n+1 快速排序法的運(yùn)行效率取決于D。A、要排序的數(shù)據(jù)量B、要排序的數(shù)據(jù)中含有相同值的比例C、要排序的數(shù)據(jù)的局部有序性D、劃分過(guò)程的對(duì)稱性二叉樹(shù)若用順序存儲(chǔ)結(jié)構(gòu)(數(shù)組)存放，則下列四種運(yùn)算中白最容易實(shí)現(xiàn)。A、先序遍歷二叉樹(shù)B、判斷兩個(gè)結(jié)點(diǎn)是否位于同一層C、層次遍歷二叉樹(shù)D、根據(jù)結(jié)點(diǎn)的值查找其存儲(chǔ)位置 模式串ABBCABABDBABBC的前綴函數(shù)為CA、 00001212000121C、 000012120012

4、34B、 10000120001212D、 10000120012345二、填空題(15*2%=30%)1、已知某棵二叉樹(shù)按中序遍歷所得到的結(jié)點(diǎn)序列為DCBGEAHFIJK,按后序遍歷所得到的 結(jié)點(diǎn)序列為DCEGBFHKJIA，該二叉樹(shù)按前序遍歷所得到的結(jié)點(diǎn)序列為ABCDGEIHFJK2、一個(gè)nxn的下三角矩陣A中的元素a (iNj, 1Wi, jWn)按行存于一個(gè)一維數(shù)組B1.n (n+1)/2中，對(duì)其中的任一元素aij,若在B中的位置為k,則k=j+(i-1)i/23、設(shè)一棵完全二叉樹(shù)具有988個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有494個(gè)葉子結(jié)點(diǎn)，有493 個(gè)度為2的結(jié)點(diǎn)，有 1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，

5、有一0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。4、向一個(gè)有127個(gè)元素的有序線性表(數(shù)組實(shí)現(xiàn))中插入一個(gè)隨機(jī)的新元素并依然保持有序性，平均要移動(dòng)635個(gè)元素。5、設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1, a2, a3, a4, a5和a6依次通過(guò)一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3, a5, a4, a6, a2, a1則 棧S至少應(yīng)該能容納4個(gè)元素。6、順序循環(huán)隊(duì)列中，設(shè)隊(duì)頭指針為front ,隊(duì)尾指針為rear ,隊(duì)中最多可有MAX個(gè)元素， 則元素入隊(duì)列時(shí)隊(duì)尾指針的變化為(rear+1)%MAX；元素出隊(duì)列時(shí)隊(duì)頭指針的變化為 (front+1)%MAX。若采用少用一個(gè)存儲(chǔ)單元的

6、方法區(qū)分隊(duì)滿與隊(duì)空問(wèn)題，則可用 (rear+1)%MAX=front表示隊(duì)滿的判別條件。7、 在輸入已經(jīng)有序的情況下，整個(gè)冒泡排序算法需要執(zhí)行n(n-1)/2次元素比較操作。8、設(shè)一個(gè)閉散列表的容量為m,用線性探測(cè)法解決沖突，要插入一個(gè)鍵值，若插入成功，至多要進(jìn)行m-1次檢測(cè)。0 1 09、用鄰接矩陣A = 1 0 1表示一張圖，如果該圖是有向圖，共 4條邊；若是 0 1 0無(wú)向圖，則共有_ 2一條邊。三、簡(jiǎn)答題(28%)1、(5分)設(shè)下列二叉樹(shù)是與某森林對(duì)應(yīng)的二叉樹(shù)，回答下列問(wèn)題。森林中有幾棵樹(shù)？每一棵樹(shù)的根結(jié)點(diǎn)標(biāo)號(hào)分別是什么？每一棵樹(shù)中有幾個(gè)結(jié)點(diǎn)？森林中共有幾個(gè)葉子結(jié)點(diǎn)？解答：(1) 3

7、(2 分)A C F (1 分)6 2 3(1 分)6(1 分)2、（6分）用Prim算法（初始頂點(diǎn)集S = 7）構(gòu)造出下圖的一棵最小生成樹(shù)，請(qǐng)用圖示法畫出其構(gòu)造過(guò)程。圖解：（每圖1分）（1）（6分）已知序列17, 31, 13, 11, 20, 35, 25, 8,請(qǐng)將上述序列初始建為一個(gè)極小 化堆，并給出輸出前兩個(gè)最小關(guān)鍵字后重建的堆。（要求畫出初始建堆和兩次調(diào)整后堆的示 意圖）。圖解:（每圖2分）4. （5 分）設(shè)有一組關(guān)鍵字10 100 32 45 58 126 3 29 200 400 0散列表大小 hashSize=13, 表項(xiàng)下標(biāo)從0到12,散列函數(shù)h（x）采用先將關(guān)鍵碼各位數(shù)字

8、折疊相加，再用%hashSize將 相加的結(jié)果映像到表中的辦法，采用二次散列技術(shù)（h2i-1（x）=|h（x）+i2|%hashsize, h2i（x）=|h（x）-i2|%hashsize解決沖突，畫出相應(yīng)的閉散列表，并指出每一個(gè)產(chǎn)生沖突的關(guān)鍵 碼分別產(chǎn)生了多少次沖突。解答：（每項(xiàng)包括位置和沖突次數(shù)0.5分）下標(biāo)關(guān)鍵字沖突次數(shù)0580110021001330440005320620037894501012611129012095. （6分）已知如圖所示的有向圖，請(qǐng)按照Dijkstra算法找出頂點(diǎn)A到所有其它頂點(diǎn)的最短 路徑。（要求給出具體迭代過(guò)程）解答：(每迭代0.5分，每個(gè)頂點(diǎn)距離0.5分

9、)迭代SUDistBDistCDistDDistEDistFDistG初始A-5388881A,CC531010882A,C,BB53108863A,C,B,GG53107864A,C,B,G,EE5397865A,C,B,G,E,FF5397866A,C,B,G,E,F,DD539786A-B： 5AC： 3AB G E D： 9AB G E： 7AB G EF： 8AB G： 6四、程序填空題(共6分)1、(6分)下列算法實(shí)現(xiàn)在中序線索二叉樹(shù)中求結(jié)點(diǎn)p的前驅(qū)，請(qǐng)?jiān)诳瞻滋幪钊胝_的語(yǔ)句 或表達(dá)式。ThreadedNode *Predecessor( ThreadedNode *p ) Thr

10、eadedNode *q;if ( (1) p-LeftThread )return (p-LeftChild);elseq=p-LeftChild;while ( (2) !q-RightThread)(3)q=q-RightChild ;return(q);/Predecessor五、算法設(shè)計(jì)題(共16分)1、(8分)二叉搜索樹(shù)預(yù)先假設(shè)搜索是基于一個(gè)關(guān)鍵字的。如果我們想要執(zhí)行或者基于關(guān)鍵 字keyl或者基于關(guān)鍵字key2的查找，可以使用一種類似于二叉樹(shù)的結(jié)構(gòu)一2-d樹(shù)。但是 在一棵2-d樹(shù)中，偶數(shù)層用keyl進(jìn)行分叉，奇數(shù)層用key2進(jìn)行分叉(根結(jié)點(diǎn)層數(shù)為0)。圖 中就是一棵2-d樹(shù)的示例

11、，以名(first name)和姓(last name)作為兩個(gè)關(guān)鍵字對(duì)二戰(zhàn)以 后的美國(guó)總統(tǒng)進(jìn)行查找?？偨y(tǒng)的姓名是按照年代順序插入的(Truman、Eisenhower、Ford、 Carter、Reagan、Bush、Clinton)。請(qǐng)根據(jù)上述描述，編寫實(shí)現(xiàn)2-d樹(shù)的插入操作。算法設(shè)計(jì)思想：從根結(jié)點(diǎn)開(kāi)始，從上往下搜索元素X合適的插入位置，搜索過(guò)程中，記錄當(dāng)前結(jié)點(diǎn)current 所在層次(根結(jié)點(diǎn)層次為0)，若current的層次為奇數(shù)時(shí)，用key2進(jìn)行比較，當(dāng)current-key2x-key2，則搜索current的左子樹(shù)，否則搜索其右子樹(shù)；同理，若current 的層次為偶數(shù)時(shí)，用key

12、1進(jìn)行比較，當(dāng)current-key1x-key1,則搜索current的左子樹(shù)， 否則搜索其右子樹(shù)。搜索過(guò)程中要記錄當(dāng)前結(jié)點(diǎn)current的父結(jié)點(diǎn)，以便找到一個(gè)空指針的 時(shí)候，可以直接在這個(gè)位置插入新的結(jié)點(diǎn)，并將元素x存儲(chǔ)在這個(gè)新結(jié)點(diǎn)中。算法設(shè)計(jì)題酌情給分2、(8分)現(xiàn)有一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)和一個(gè)雙向連接表，每一個(gè)連接A-B表示文件可以在計(jì)算 機(jī)A和B之間傳送，如果存在M個(gè)連接和N臺(tái)計(jì)算機(jī)，設(shè)計(jì)一個(gè)有效的算法幫助判定能否 將一個(gè)文件從網(wǎng)絡(luò)上任意一臺(tái)計(jì)算機(jī)發(fā)送到任意的另外一臺(tái)計(jì)算機(jī)上。要求：算法時(shí)間復(fù)雜性為O(M+N)算法設(shè)計(jì)思想：將每一臺(tái)計(jì)算機(jī)視為某一張無(wú)向圖G中的結(jié)點(diǎn)，每一個(gè)連接A-B表示結(jié) 點(diǎn)A和B之間存在一條邊?？赏ㄟ^(guò)圖的連通性判斷是否能將一個(gè)文件從網(wǎng)絡(luò)上任意一臺(tái)計(jì) 算機(jī)發(fā)送到任意的另外一臺(tái)計(jì)算機(jī)上。由于這樣的一張圖具有N個(gè)結(jié)點(diǎn)和M條邊，為了滿 足時(shí)間復(fù)雜性的要求，采用鄰接表的方式實(shí)現(xiàn)圖，并對(duì)圖進(jìn)行深度優(yōu)先搜索也可以初始將每一臺(tái)計(jì)算看