數據結構模擬2.docVIP

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