華東交通大學(xué)2011-2012.1數(shù)據(jù)結(jié)構(gòu)試卷

1、承諾：我將嚴(yán)格遵守考場紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿承擔(dān)由此引起的一切后果。專業(yè) 班級 學(xué)號 學(xué)生簽名： 華東交通大學(xué)20112012學(xué)年第一學(xué)期考試卷試卷編號：（ A ）卷 數(shù)據(jù)結(jié)構(gòu) 課程 課程類別：必 閉卷 考試日期： 2012.1 題號一二三四五六七八九十總分累分人簽名題分2030428100得分考生注意事項：1、本試卷共 4 頁，總分100分，考試時間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。3、答案必須寫在答題紙上，考試結(jié)束時請將答題紙與試卷分開上交，試卷、答題紙、草稿

2、紙都必須交回。得分評閱人 一、選擇題(每題 2 分，共 20 分) 1. 計算機算法必須具備輸入、輸出（ ）5個特性。A可行性、可移植性和可擴充性B. 有窮性、確定性、可行性 C. 確定性、有窮性和穩(wěn)定性D. 可讀性、穩(wěn)定性和安全性2.在長度為n的順序表的第i個元素（1=inext=s; s-next=p-next; Bs-next=p-next; p-next=s;Cp-next=s; p-next=s-next; D. p-next=s-next; p-next=s;4. 判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A隊列 B線性表 C棧 D雙向鏈表5包含2012個頂

3、點的連通圖最少有（ ）條邊。A. 2011B. 2012C. 2013D. 20146. 在有序表4，15，26，27，38，64，81中折半查找38的比較次數(shù)為（ ）。A1 B2 C3 D4 7. 線索鏈表中，若結(jié)點p的RTag=1，則p-rchild指向（ ）。A. 左孩子 B. 右孩子 C. 前驅(qū) D. 后繼8. 對完全二叉樹按層序從1開始編號，編號為100的結(jié)點是編號為50的結(jié)點的（ ）。A. 左孩子 B. 右孩子C. 雙親D. 根結(jié)點9下圖AOE網(wǎng)絡(luò)中，要完成該工程需要（ ）時間。A. 43 B.18 C. 31 D. 3510順序查找的時間復(fù)雜度為（ ）A O(n/2) BO(n)

4、 CO(1) DO(log2n) 得分評閱人二、填空題(每題 2 分，共 30 分)1數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是算法的 (1) 和空間復(fù)雜度。2. 鏈接存儲的特點是利用 (2) 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。3. 假設(shè)有5行4列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A00的地址為1000，按行優(yōu)先存儲時元素A23的地址是 (3) 。4帶頭結(jié)點的單鏈表L中，L-next-next表示第 （4） 個數(shù)據(jù)元素。5若用一個大小為8的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear的值為 (5) ，front的

5、值為 (6) 。6. SubString(HAPPYNEWYEAR, 6, 3）= （7） 。7一棵具有267個結(jié)點的完全二叉樹，它的深度為 (8) ，有 (9) 個葉子結(jié)點。8以下代碼片段中，k+的執(zhí)行次數(shù)為 (10) 。for (int i=0; in; i+) for (int j=0; jn; j+) k+;9若一棵二叉樹具有7個度為2的結(jié)點，3個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是_ (11) 。10右圖的一個拓?fù)渑判蛐蛄袨锳 （12） EF。11. 帶頭結(jié)點的循環(huán)鏈表中最后一個結(jié)點的指針域指向 （13） 。填空題10圖12. 順序表第 (14) 個數(shù)據(jù)元素的存儲位置稱為基地址。13.

6、 具有3個結(jié)點的二叉樹有 （15） 種不同形態(tài)。得分評閱人三、綜合題 （每題6分，共42分）1進(jìn)棧順序為12345，問能否得到45231和32451的出棧序列？以push（X）表示進(jìn)棧和以pop（X）表示出棧的操作序列，說明為什么不能或如何能得到。2. 已知一棵二叉樹的后序序列為IGDBEHFCA,中序序列為DIGBAECFH,直接畫出此二叉樹并畫出對應(yīng)的森林。3. 用教材中給出的數(shù)值轉(zhuǎn)換算法將十進(jìn)制數(shù)2012轉(zhuǎn)換成八進(jìn)制數(shù)，并畫出轉(zhuǎn)換過程中棧的變化情況。4給定下列網(wǎng)G: 寫出用克魯斯卡爾算法構(gòu)造最小生成樹過程中每一步選擇的邊。5假設(shè)用于通信的電文由6個字母A,B,C,D,E,F組成，字母在電

7、文中出現(xiàn)的頻率分別為0.17, 0.12, 0.05, 0.28, 0.35, 0.03。 試為這6個字母設(shè)計哈夫曼樹（權(quán)值小的作為左子樹）。6記錄的關(guān)鍵字序列為：56，90，27，67，56，10，88，試構(gòu)造一棵二叉排序樹，并寫出其構(gòu)造過程。7利用迪杰斯特拉算法依次求出下圖中從頂點v0到其他各頂點間的最短路徑。得分評閱人四、算法題 （共8分）1. 實現(xiàn)帶頭結(jié)點的單鏈表L 中，刪除第i個元素，并由e返回其值。 （1）用編程語言定義單鏈表的存儲結(jié)構(gòu)（3分） （2）用編程語言定義函數(shù)實現(xiàn)上述功能（5分）承諾：我將嚴(yán)格遵守考場紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿承擔(dān)由此引起的一切后果。專業(yè) 班級 學(xué)號 學(xué)生簽名： 華東交通大學(xué)20112012學(xué)年第一學(xué)期考試卷 試卷編號：（ A ）卷 數(shù)據(jù)結(jié)構(gòu) 課程 課程類別：必 閉卷 考試日期：2012.1 題號一二三四五六七八九十總分累分人簽名題分2030428100得分得分評閱人 一、選擇題（每題2 分，共20分）12345678910得分評閱人 二、填空題（每空2分，共30分） 123456