數(shù)據(jù)結(jié)構(gòu)模擬2.doc

系 專業(yè) 班級(jí) 姓名 考號(hào) （密 封 線 內(nèi) 不 要 答 題） 南陽(yáng)理工學(xué)院 課程: 數(shù)據(jù)結(jié)構(gòu)(A卷)評(píng)卷人（簽名） 復(fù)核人（簽名） 題號(hào)一（20）二（30）三（50）合 計(jì)得分 一、單項(xiàng)選擇題：（每題2分，共20分）1、數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指( D ) A.數(shù)組、鏈表、樹(shù)、圖形結(jié)構(gòu) B.線性表、鏈表、棧隊(duì)列、數(shù)組廣義表 C.線性結(jié)構(gòu)、鏈表、樹(shù)、圖形結(jié)構(gòu) D.集合、線性結(jié)構(gòu)、樹(shù)、圖形結(jié)構(gòu) 2.下列關(guān)于棧和隊(duì)列的敘述中，不正確的是( C ) 。A.它們是n個(gè)結(jié)點(diǎn)的有窮序列 B.都可以為空。 C.每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前趨和一個(gè)后繼 D.結(jié)點(diǎn)間的邏輯關(guān)系是1:1的聯(lián)系 3、.若進(jìn)棧序列為a,b,c,d,進(jìn)棧過(guò)程每個(gè)元素只能進(jìn)棧出棧一次，則不可能的一個(gè)出棧序列是（ B ）。A.c,d,b,a B. a,d,b,c C. b,d,c,a D. c,b,a,d 4利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ C ）。A指向最左孩子 B指向最右孩子 C空 D非空5、一個(gè)有序表為9，12，34，45，62，75，82，95，100，利用折半查找查找key=100時(shí)需要_A_次比較后查找成功。A. 4 B. 3 C. 2 D. 56、已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓?fù)湫蛄惺牵ˋ ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V77、假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為200,它的最小高度 8_A_ 。A. 8 B. 10 C. 7 D. 118、 一個(gè)n*n的三角矩陣經(jīng)過(guò)壓縮后所占的空間是（C ）An+1/2 Bn*(nl)/2 Cn*(nl)/2 Dn*n/2 9、在對(duì)一組記錄(20,40,96,100,15,72,140,45,68)按從小到大進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄交換的次數(shù)為（D ） A.6 B.5 C.3 D.410. n個(gè)頂點(diǎn)，e條邊的無(wú)向圖采用鄰接表存儲(chǔ)時(shí)，所分配的弧結(jié)點(diǎn)數(shù)為（ C ）個(gè)。An B. n+e C. 2e D. e二、填空題（每空2分，共30分）1. 設(shè)a、b、c,d都是串名，akexue，bjiaoyu，cfangfa。則求聯(lián)接操作CONCAT(&d,SUB(a,3,3)， SUB(c,3,2)結(jié)果為 _xueng_ 。2. 一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次，（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是_ 。3. 有一組葉子結(jié)點(diǎn)的權(quán)值為WG=7，19，2，6，32，3，21，10，則所建Huffman樹(shù)的樹(shù)高是_ 6 ，帶權(quán)路徑長(zhǎng)度WPL為_(kāi) 。系 專業(yè) 班級(jí) 姓名 考號(hào) （密 封 線 內(nèi) 不 要 答 題） 8566101512781115bacdifegh4. n個(gè)頂點(diǎn)的強(qiáng)連通圖，其弧的條數(shù)至少為_(kāi)n_ 。n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的條數(shù)至少為_(kāi)n-1_ 。5. 設(shè)二維數(shù)組A0.30,0.20, 每個(gè)元素占有4 個(gè)存儲(chǔ)單元, 存儲(chǔ)起始地址為200.如按行優(yōu)先順序存儲(chǔ),則元素 A25,18的存儲(chǔ)地址為_(kāi)2372 _。6. 廣義表(a,(a,b),d,e,(i,j),k)的長(zhǎng)度是 5 ，表尾是_ _ (a,b),d,e,(i,j),k) 。7. 串的兩種最基本的存儲(chǔ)方式是_定長(zhǎng)存儲(chǔ)_ 、_堆存儲(chǔ)_ 。 8. 循環(huán)隊(duì)列的引入，目的是為了克服_假溢出_ 。9. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則入隊(duì)時(shí)rear=_(front+1)%n _ 。10.已知一無(wú)向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖，如要得到的序列為abecd，則需要采用的是_深度_ 遍歷方法；如要得到的序列為abcde，需要采用的是_廣度_ 遍歷方法。三、應(yīng)用題。（共50分）1、已知下面是一個(gè)工程的AOE網(wǎng)絡(luò)，請(qǐng)按要求回答下面的問(wèn)題。（10分）（1）若能順利進(jìn)行則請(qǐng)計(jì)算從工程開(kāi)始到結(jié)束需要的時(shí)間（4分）（2）請(qǐng)畫(huà)出此AOE網(wǎng)絡(luò)工程圖的關(guān)鍵路徑。（6分）1、（1）416515acieh（2）15ABCDEFGHIVE08662118292641VL0116721193026412、已知一棵二叉樹(shù)的先序遍歷序列為：abcdefgh，。中序遍歷序列為：cdfehgba請(qǐng)畫(huà)出這棵二叉樹(shù)并寫(xiě)出它的后序遍歷的序列。（10分：其中畫(huà)出樹(shù)8分，寫(xiě)出序列2分）系 專業(yè) 班級(jí) 姓名 考號(hào) （密 封 線 內(nèi) 不 要 答 題）abdcegfh 后序序列為：f h g e d b a3、對(duì)下列關(guān)鍵字序列進(jìn)行快速排序(從小至大)key= (48, 88, 65, 95, 50, 13, 27, 62)要求:（1）描述快速排序的算法思想。（4分）（2）畫(huà)出排序過(guò)程示意圖。（6分）（1）一次快速排序是通過(guò)選擇一個(gè)支點(diǎn)，把一個(gè)無(wú)序的序列劃分為兩個(gè)序列，左側(cè)序列小于支點(diǎn)，右側(cè)序列大于支點(diǎn)，然后再分別對(duì)兩個(gè)序列進(jìn)行下一次快速排序，直至序列長(zhǎng)度=1結(jié)束?；舅枷胝_為4分第一趟：（27，13），48，（95，50，65，88，62）第二趟：13，27，48，（62，50，65，88），95第三趟：13，27，48，50，62，（65，88），95第四趟：13，27，48，50，62，65，88，95排序過(guò)程正確為6分，無(wú)過(guò)程不得分。4、已知一組關(guān)鍵字為（19,14,23,01,68,20,84,27,55,11,28,78）按哈希函數(shù) H(Key)=Key MOD 13和線性探測(cè)再散列處理沖突的方法在地址空間A0.15中構(gòu)造哈希表。（10分）解：H(KEY)=KEY MOD 13 處理沖突方法為：H(KEY)=(H(KEY)+Di) MOD M (M=16)H(19)=6 H(14)=1 H(23)=10H (01)=1(沖突) H(01)=2 H(68)=3 H(20)=7H(84)=6(沖突) H(84)=7 H(27)=1(沖突) H(27)=4H(55)=3(沖突) H(55)=5 H(11)=11 H(28)=15 H(78)=078140168275