數(shù)據(jù)結(jié)構(gòu)與算法模擬題.doc

學(xué)號(hào)： 姓名：數(shù)據(jù)結(jié)構(gòu)與算法模擬題一、填空題：（共15分）（每空一分）1. 按照排序時(shí)，存放數(shù)據(jù)的設(shè)備，排序可分為 內(nèi)部 排序和 外部 排序。2. 圖的常用的兩種存儲(chǔ)結(jié)構(gòu)是 鄰接矩陣存儲(chǔ) 和 鄰接表面存儲(chǔ) 。3. 數(shù)據(jù)結(jié)構(gòu)中的三種基本的結(jié)構(gòu)形式是 x線性結(jié)構(gòu) 和 樹形結(jié)構(gòu) 、 圖形結(jié)構(gòu) 。4. 一個(gè)高度為6的二元樹，最多有 63 個(gè)結(jié)點(diǎn)。5. 線性查找的時(shí)間復(fù)雜度為： ，折半查找的時(shí)間復(fù)雜度為： 、堆分類的時(shí)間復(fù)雜度為： 。6. 在采用散列法進(jìn)行查找時(shí)，為了減少?zèng)_突的機(jī)會(huì)，散列函數(shù)必須具有較好的隨機(jī)性，在我們介紹的幾種散列函數(shù)構(gòu)造法中，隨機(jī)性最好的是隨機(jī)數(shù) 法、最簡(jiǎn)單的構(gòu)造方法是 除留余數(shù)法 。7. 線性表的三種存儲(chǔ)結(jié)構(gòu)是：數(shù)組、 鏈表 、 靜態(tài)鏈表 。二、回答下列問(wèn)題：（共30分）1. 現(xiàn)有如右圖的樹，回答如下問(wèn)題：A） 根結(jié)點(diǎn)有：6B） 葉結(jié)點(diǎn)有：5C） 具有作大度的結(jié)點(diǎn)：9和10D） 結(jié)點(diǎn)o的祖先是：0和2E） 結(jié)點(diǎn)o的后代是：102. 棧存放在數(shù)組Am中，棧底位置是m-1。試問(wèn)：A） ?？盏臈l件是什么？B） 棧滿的條件是什么？ 3. 數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)型的區(qū)別與聯(lián)系：4. 已知一株非空二元樹，其先根與中根遍歷的結(jié)果為：先根：ABCDEFGHI 中跟：CBEDAGFHI 將此二元樹構(gòu)造出來(lái)。5. 分析下列程序的運(yùn)行時(shí)間：A) void mystery(int n)int i, j, k; for(i=1; in; i+) for(j=i+1; j=n; j+) for(k=1; k=j; k+)some statement requiring O(1) time; B）void podd(int n) int I, j, x, y; for(I=1; I=n; I+) if( odd(I ) ) for(j=I; j=n; j+) x=x+1; for(j=1; j=I; j+) y=y+1; 6. 已知數(shù)學(xué)表達(dá)式是(3+b)sin(x+5)a/x2，求該表達(dá)式的波蘭表示法的前綴和后綴表示（要求給出過(guò)程）。三、實(shí)現(xiàn)下列算法：（共0分）1. 在指針實(shí)現(xiàn)的線性表L中，實(shí)現(xiàn)在線性表L 中刪除關(guān)鍵字為x的結(jié)點(diǎn)。(共7分)2.3. 設(shè)有如下圖的雙向環(huán)形鏈表L=(a, b, c, d) 。請(qǐng)寫出將該表轉(zhuǎn)換為L(zhǎng)=(b, a, c, d)的簡(jiǎn)單操作。（共7分）abcdLL D RLL 4. 在線索二元樹中，由結(jié)點(diǎn)P求其先根順序的后繼。（共8分）先根：ABCDEFGHI 中跟：CBEDAGFHI 將此二元樹構(gòu)造出來(lái)。遍歷的基本方法：先左子樹后右子樹。1,先根遍歷可以確定根節(jié)點(diǎn)為A,2,依據(jù)1步，可以在中根遍歷中確定左子樹為：CBED,右為：GFHI3,在可以重復(fù)1,2步。就可以得到結(jié)果。 A B FC D G H I4, O(n3)+O(1)5. 在二元查找樹F中，實(shí)現(xiàn)插入記錄R。（共8分）四、對(duì)下面的帶權(quán)連通無(wú)向圖，用Prim（普里姆）算法，構(gòu)造一株最小生成樹。畫出構(gòu)造過(guò)程的每一步。（12分）jklmop1028161222251418n24五、設(shè)要分類的數(shù)據(jù)存放在數(shù)組A31415