



全文預覽已結(jié)束
下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
系 專業(yè) 班級 姓名 考號 (密 封 線 內(nèi) 不 要 答 題) 南陽理工學院 課程: 數(shù)據(jù)結(jié)構(gòu)(A卷)評卷人(簽名) 復核人(簽名) 題號一(20)二(30)三(50)合 計得分 一、單項選擇題:(每題2分,共20分)1、數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指( D ) A.數(shù)組、鏈表、樹、圖形結(jié)構(gòu) B.線性表、鏈表、棧隊列、數(shù)組廣義表 C.線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu) D.集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu) 2.下列關(guān)于棧和隊列的敘述中,不正確的是( C ) 。A.它們是n個結(jié)點的有窮序列 B.都可以為空。 C.每一個結(jié)點有且僅有一個前趨和一個后繼 D.結(jié)點間的邏輯關(guān)系是1:1的聯(lián)系 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利用二叉鏈表存儲樹,則根結(jié)點的右指針是( 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、假定一棵二叉樹的結(jié)點數(shù)為200,它的最小高度 8_A_ 。A. 8 B. 10 C. 7 D. 118、 一個n*n的三角矩陣經(jīng)過壓縮后所占的空間是(C )An+1/2 Bn*(nl)/2 Cn*(nl)/2 Dn*n/2 9、在對一組記錄(20,40,96,100,15,72,140,45,68)按從小到大進行冒泡排序時,第一趟需進行相鄰記錄交換的次數(shù)為(D ) A.6 B.5 C.3 D.410. n個頂點,e條邊的無向圖采用鄰接表存儲時,所分配的弧結(jié)點數(shù)為( C )個。An B. n+e C. 2e D. e二、填空題(每空2分,共30分)1. 設a、b、c,d都是串名,akexue,bjiaoyu,cfangfa。則求聯(lián)接操作CONCAT(&d,SUB(a,3,3), SUB(c,3,2)結(jié)果為 _xueng_ 。2. 一個深度為k的,具有最少結(jié)點數(shù)的完全二叉樹按層次,(同層次從左到右)用自然數(shù)依此對結(jié)點編號,則編號最小的葉子的序號是_ 。3. 有一組葉子結(jié)點的權(quán)值為WG=7,19,2,6,32,3,21,10,則所建Huffman樹的樹高是_ 6 ,帶權(quán)路徑長度WPL為_ 。系 專業(yè) 班級 姓名 考號 (密 封 線 內(nèi) 不 要 答 題) 8566101512781115bacdifegh4. n個頂點的強連通圖,其弧的條數(shù)至少為_n_ 。n個頂點的連通無向圖,其邊的條數(shù)至少為_n-1_ 。5. 設二維數(shù)組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)現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖,如要得到的序列為abecd,則需要采用的是_深度_ 遍歷方法;如要得到的序列為abcde,需要采用的是_廣度_ 遍歷方法。三、應用題。(共50分)1、已知下面是一個工程的AOE網(wǎng)絡,請按要求回答下面的問題。(10分)(1)若能順利進行則請計算從工程開始到結(jié)束需要的時間(4分)(2)請畫出此AOE網(wǎng)絡工程圖的關(guān)鍵路徑。(6分)1、(1)416515acieh(2)15ABCDEFGHIVE08662118292641VL0116721193026412、已知一棵二叉樹的先序遍歷序列為:abcdefgh,。中序遍歷序列為:cdfehgba請畫出這棵二叉樹并寫出它的后序遍歷的序列。(10分:其中畫出樹8分,寫出序列2分)系 專業(yè) 班級 姓名 考號 (密 封 線 內(nèi) 不 要 答 題)abdcegfh 后序序列為:f h g e d b a3、對下列關(guān)鍵字序列進行快速排序(從小至大)key= (48, 88, 65, 95, 50, 13, 27, 62)要求:(1)描述快速排序的算法思想。(4分)(2)畫出排序過程示意圖。(6分)(1)一次快速排序是通過選擇一個支點,把一個無序的序列劃分為兩個序列,左側(cè)序列小于支點,右側(cè)序列大于支點,然后再分別對兩個序列進行下一次快速排序,直至序列長度=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排序過程正確為6分,無過程不得分。4、已知一組關(guān)鍵字為(19,14,23,01,68,20,84,27,55,11,28,78)按哈希函數(shù) H(Key)=Key MOD 13和線性探測再散列處理沖突的方法在地址空間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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 鋼筋圖紙教學課件
- 2025年三季度重慶云陽縣事業(yè)單位招聘工作人員304人筆試歷年典型考題及考點剖析附帶答案詳解
- 無煙教育活動方案
- 春季踏春活動方案
- 【黃山】2025年安徽黃山市消防救援支隊招聘政府專職消防隊員60人筆試歷年典型考題及考點剖析附帶答案詳解
- 新開淘寶店活動方案
- 旺季刮刮卡活動方案
- 早點店優(yōu)惠活動方案
- 數(shù)獨校本訓練活動方案
- 無人售賣運營活動方案
- 滁州瑞芬生物科技有限公司年產(chǎn)1.5萬噸赤蘚糖醇項目環(huán)境影響報告書
- THMDSXH 003-2023 電商產(chǎn)業(yè)園區(qū)數(shù)字化建設與管理指南
- 新建ICU鎮(zhèn)痛、鎮(zhèn)靜藥物應用幻燈片
- 2020年上海市中考語數(shù)英物化五科試卷及答案
- 橡膠和基材的粘接
- GB/T 10610-2009產(chǎn)品幾何技術(shù)規(guī)范(GPS)表面結(jié)構(gòu)輪廓法評定表面結(jié)構(gòu)的規(guī)則和方法
- GA/T 935-2011法庭科學槍彈痕跡檢驗鑒定文書編寫規(guī)范
- 湖北省黃石市基層診所醫(yī)療機構(gòu)衛(wèi)生院社區(qū)衛(wèi)生服務中心村衛(wèi)生室信息
- DB44-T 2163-2019山地自行車賽場服務 基本要求-(高清現(xiàn)行)
- 工傷責任保險單
- 圍堰施工監(jiān)理實施細則
評論
0/150
提交評論