北大數(shù)據(jù)結(jié)構(gòu)與算法期末考試模擬試卷

1、2014年春季北大數(shù)據(jù)結(jié)構(gòu)與算法b期末考試模擬試卷（本試卷只是給同學(xué)們看看考題形式和范圍，難度與真實(shí)考卷稍有差別）學(xué)號(hào)_ 姓名_ 教師/教室_（注：如未標(biāo)明，本試卷題中的下標(biāo)、位置都從0開(kāi)始計(jì)數(shù)）一、 填空題（共32分）1. 設(shè)有字符串變量string a = “this”, b=“is”, c=“just”, d=“atest”，請(qǐng)計(jì)算下列表達(dá)式：（1）a+b+d=_“thisisatest”_；（2）d.indexof(“t”) = _2_；（求字符在字符串中的第一個(gè)位置）（3）b.strlength() = _2_（4）d.substr(1,2) = _“t” _（注：1為起始下標(biāo)，2為

2、子串長(zhǎng)度）【4分】2. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_(kāi)n_次；若查找失敗，則比較關(guān)鍵字的次數(shù)最多為_(kāi)n_，最少為_(kāi)n_次?！?分】3. 在散列函數(shù)h（key）=key%p中，p值最好取_質(zhì)數(shù)（或素?cái)?shù)）_。【1分】4. 對(duì)于下圖鄰接表所對(duì)應(yīng)的有向圖，試寫(xiě)出：【2分】(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷結(jié)果_1, 2, 3, 4, 5_；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷結(jié)果_1, 2, 3, 4, 5 _； 5. 當(dāng)圖中各條邊上的權(quán)值 _都相等_ 時(shí)，寬度優(yōu)先搜索算法可用來(lái)解決單源最短路徑問(wèn)題？【2分】6. 一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)有_0_個(gè)度為1的結(jié)點(diǎn)、有_(n

3、-1)/2個(gè)分支 （非終端）結(jié)點(diǎn)；該滿二叉樹(shù)的深度最大為_(kāi)(n-1)/2 _, 最小為 int(log2n)或ëlog2nû。（獨(dú)根樹(shù)深度為0）【4分】7. 對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 線性結(jié)構(gòu) ， 樹(shù)形結(jié)構(gòu) ， 圖形結(jié)構(gòu) ，_集合_四種。【2分】8. 下面程序段的時(shí)間復(fù)雜度為_(kāi)o(n)_。(n>1) 大o表示法 【2分】 sum=1； for (i=0;sum<n;i+) sum+=1;9.對(duì)于最大堆 65 43 59 24 37 48 57 12 23 28 5 3，刪除掉最大元素后，堆中元素為59,43,57,24,37,48,3,12,2

4、3,28,5【2分】10. 從空二叉樹(shù)開(kāi)始，嚴(yán)格按照二叉搜索樹(shù)的插入算法（不進(jìn)行旋轉(zhuǎn)平衡），逐個(gè)插入關(guān)鍵碼 18,73,10,5,68,99,27,41,51,32,25 構(gòu)造出一棵二叉搜索樹(shù)，該二叉樹(shù)轉(zhuǎn)換為森林，則該森林的層次遍歷序列為 _18 73 99 10 68 5 27 41 51 25 32_【4分】對(duì)于的二叉樹(shù)為11. 用s表示入棧操作，x表示出棧操作，若元素入棧的順序?yàn)?2345，為了得到13542出棧順序，相應(yīng)的s和x的操作串為_(kāi)sxssxssxxx_?！?分】二、 單選題（18分，每題2分，最后兩題每題4分）1. 對(duì)初始狀態(tài)為遞增的表按遞增順序排序，最省時(shí)間的是（ c ）算

5、法。 a. 基數(shù)排序 b. 桶排 c. 直接插入排序 d. 歸并排序2. 一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（a）。an-1 bn cn+1 dnlogn；3 線性表（ a1,a2,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜度為（ c ）ao（i） bo（1） co（n） do（i-1）4. 使用prim算法從結(jié)點(diǎn)0出發(fā)求下圖的最小生成樹(shù)，依次寫(xiě)出每次被加入到最小生成樹(shù)中邊的編號(hào)，下面正確的答案是（b）。a. (0, 2) (3, 5) (1, 4) (2, 5) (1, 2) b. (0, 2) (2, 5) (3, 5) (1, 2) (1, 4)c. (0, 2) (3,

6、 5) (1, 4) (1, 2) (2, 5) b. (0, 2) (1, 2) (1, 4) (2, 5) (3, 5)5一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最多有（ d ）個(gè)連通分量。a0 b1 cn-1 dn6. 用二分（對(duì)半）查找法檢索元素速度比用順序法( d ) ?！?分】a 必然快 b. 必然慢 c. 相等 d. 不能確定7. 已知一算術(shù)表達(dá)式的中綴形式為 a+b*c-d/e，后綴形式為abc*+de/-，其前綴形式為( d )?！?分】a-a+b*c/de b. -a+b*cd/e c-+*abc/de d. -+a*bc/de8對(duì)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟處理（對(duì)

7、應(yīng)于排序算法中一層循環(huán)或一層遞歸算法）后，數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15；則采用的是（ c ）排序。【4分】a. 選擇 b. 快速 c. 希爾（shell） d. 冒泡三、 簡(jiǎn)答題（30分，每題10分）1. 試問(wèn)由二叉樹(shù)的中序序列和后序序列是否能唯一的建立二叉樹(shù)，請(qǐng)說(shuō)明理由；若能，對(duì)中序序列dbeafgc和后序序列debgfca構(gòu)造二叉樹(shù)。答：（1）給定二叉樹(shù)結(jié)點(diǎn)的后序序列和對(duì)稱序（中序）序列，可以唯一確定該二叉樹(shù)。因?yàn)楹笮蛐蛄械淖詈笠粋€(gè)元素是根結(jié)點(diǎn)，該元素將二叉樹(shù)中序序列分成兩部分，左邊（設(shè)有l(wèi)個(gè)元素）表示左子樹(shù)，若左邊無(wú)元素，則說(shuō)明左子樹(shù)為空；右邊（設(shè)有r個(gè)元素）是右子樹(shù)，

8、若為空，則右子樹(shù)為空。根據(jù)后序遍歷中“左子樹(shù)右子樹(shù)根”的順序，則后序序列中由從第1元素開(kāi)始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹(shù)；由后序序列l(wèi)個(gè)元素后面r個(gè)元素序列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹(shù)。（2）中序序列dbeafgc和后序序列debgfca構(gòu)造的二叉樹(shù)如下圖2設(shè)一組數(shù)據(jù)為1,14,27,29,55,68,10,11,23，現(xiàn)采用的散列函數(shù)是h(key)=key % 13，沖突用鏈地址法解決，設(shè)散列表的大小為13(下標(biāo)為012)，試畫(huà)出插入上述數(shù)據(jù)后的散列表。答：3. 設(shè)t是一棵二叉樹(shù)，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度數(shù)皆為2，若 t中有6個(gè)葉結(jié)點(diǎn)，試問(wèn)：（1）t樹(shù)的

9、最大深度kmax=?最小可能深度kmin=?（假定獨(dú)根二叉樹(shù)深度為0）（2）t樹(shù)中共有多少非葉結(jié)點(diǎn)？（3）若葉結(jié)點(diǎn)的權(quán)值分別為1,2,3,4,5,6。請(qǐng)畫(huà)出一棵哈曼夫樹(shù)，并計(jì)算該哈曼夫樹(shù)的帶權(quán)路徑長(zhǎng)度wpl。答：1）t樹(shù)的最大深度kmax=5（除根外，每層均是兩個(gè)結(jié)點(diǎn)）t樹(shù)的最小深度kmin=3（具有6個(gè)葉子的完全二叉樹(shù)是其中的一種形態(tài)）（2）非葉子結(jié)點(diǎn)數(shù)是5。（n2=n0-1） （3）哈夫曼樹(shù)見(jiàn)下圖，其帶權(quán)路徑長(zhǎng)度wpl=51四、 算法填空題（20分，第一題10分，第2題10分）1. 下面是求二叉樹(shù)高度（獨(dú)根樹(shù)高度是1）的遞歸算法，試補(bǔ)充完整二叉樹(shù)的兩指針域?yàn)閘child與rchild, 算

10、法中p為二叉樹(shù)的根，lh和rh分別為以p為根的二叉樹(shù)的左子樹(shù)和右子樹(shù)的高，hi為以p為根的二叉樹(shù)的高，hi最后返回。int height(bintree *p)inthi, lh, rh;if (_p _)/ p!=null 也對(duì) if (p->lchild=null) lh=_0_; else lh=_height(p->lchild)_;if (p->rchild=null) rh=_0_; else rh=_ height(p->rchild) _;if (lh>rh) hi=_lh+1_；else hi=_rh+1_; else hi=_0_;return

11、 hi;/ 題目中結(jié)構(gòu)已經(jīng)給定，就應(yīng)該按照題目要求來(lái)/ 如果根據(jù)給定的題目結(jié)構(gòu)填入其他內(nèi)容也正確的話，那么就是正確的。)2對(duì)單鏈表（帶頭結(jié)點(diǎn)）中元素按插入方法實(shí)現(xiàn)非遞增序列的排序的c語(yǔ)言描述算法如下，其中l(wèi)為鏈表頭結(jié)點(diǎn)指針。請(qǐng)?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。typedef struct node int data; struct node *next; linknode,*link;void insertsort(link l) link p,q,r,u;p=l->next; _l->next = null_;/ l->next = null這一句是需要的，因?yàn)閜指向待插入結(jié)點(diǎn)，l后來(lái)一直指向排好序的鏈表。/ 第二層while循環(huán)實(shí)際上是在l所指向的有序表中查找p應(yīng)該插入的位置。 while(_p != null _) r=l; q=l->next; while(q != null && q->data <= p-&