數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A(可編輯優(yōu)質(zhì)文檔)_第1頁
數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A(可編輯優(yōu)質(zhì)文檔)_第2頁
數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A(可編輯優(yōu)質(zhì)文檔)_第3頁
已閱讀5頁,還剩9頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A (可編輯優(yōu)質(zhì)文檔)(可以直接使用,可編輯 完整版資料,歡迎下載)填空題(共20分,每空1 分)1 設單鏈表的結(jié)點結(jié)構(gòu)為(data,next ), next為指針域。已知指針指針py指向 data 為y的新結(jié)點,若將結(jié)點y插入結(jié)點x之后,px指向單鏈表中 data為x的結(jié)點,則需執(zhí)行一下語句:(py-> next =px->n ext;)(px->next = py2設無向圖G的頂點數(shù)為n,有n個頂點,則圖 G最少有(n-1 )邊;最多有(n-1)邊;最多有(n(n-1)圖G最少有(n(n-1)/2邊。)邊。若G為有向圖,3 .設有一空棧,現(xiàn)有輸入

2、序列1, 2, 3, 4, 5,經(jīng)過 push, push, pop , push, pop , push, push 后,輸岀序列是(5,4,1)4. 由帶權(quán)為3, 9, 6 , 2, 5的5個葉子結(jié)點構(gòu)成一棵哈夫曼樹,則帶權(quán)路徑長度為()5由a, b, c三個結(jié)點構(gòu)成的二叉樹,共有(5 )種不同的結(jié)構(gòu)。6在線性表的散列存儲中,處理沖突有()和()方法。7 在對一組記錄(50, 40, 95 , 20, 15, 70 , 60, 45, 80)進行冒泡排序時,第一趟需進行相鄰記錄的交換的次數(shù)為(6),在整個排序過程中共需進行(8)趟就可以將排序完成。8 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的()和()以及它們

3、之間的相互關(guān)系。9. 散列法要解決的兩個關(guān)鍵問題是(散列函數(shù))和(沖突)。10. 外部排序需要考慮的三個關(guān)鍵問題分別是(多路歸并以減少歸并次數(shù))、(并行操作的緩沖區(qū)處理盡量使輸入與輸岀與 CPU工作重疊)和(初始并歸段的生成)。二. 判斷題(對的填V,錯的填x,共10分,每題1分)1 在線性結(jié)構(gòu)中,每個結(jié)點都有一個直接前驅(qū)和一個直接后繼。(X )2 在鏈式存儲的棧的頭部必須要設頭結(jié)點。()3 在二叉樹中插入結(jié)點,則該項二叉樹便不再是二叉樹。()4由二叉樹結(jié)點的先序序列和后序序列可以唯一確定一5樹的父鏈表示就是用數(shù)組表示樹的存儲結(jié)構(gòu)。6任何二叉樹都唯一對應一個森林,反之亦然。7 順序存儲方式只能

4、用于存儲線性結(jié)構(gòu)。()8 用循環(huán)鏈表作為存儲結(jié)構(gòu)的隊列就是循環(huán)隊列。9 算法分析的目的是分析算法的易讀性()10. 組記錄的關(guān)鍵字為(46,79,56,38,40,84)的一次劃分結(jié)果為40,38,46,56,79,84(三. 選擇題(共10分,每題1分)棵二叉樹。()()()(),則利用快速排序的方法,以第一個記錄為基準元素得到)。1 快速分類在 的情況下不利于發(fā)揮其長處。A. 待分類的數(shù)據(jù)量太大B. 待分類的數(shù)據(jù)相同值過多C. 待分類的數(shù)據(jù)已基本有序D. 待分類的數(shù)據(jù)值差過大2 已知一棵完全二叉樹的第6層(設根為第1層)有8個葉結(jié)點,則該完全二叉樹的結(jié)點個數(shù)最多B . 52C. 111D

5、. 1193設森林中有三棵樹,第一、第二和第三棵樹中的結(jié)點個數(shù)分別為 成二叉樹中根結(jié)點的右子樹上的結(jié)點個數(shù)是。m1、m2和m3。那么在由該森林轉(zhuǎn)化A . m1+m2B . m2+m3C . m3+m1D . m1+m2+m3x在y之前,而在其后序遍4. 設結(jié)點x和y是二叉樹中任意的兩個結(jié)點。在該二叉樹的前序遍歷序列中 歷序列中x在y之后,則x和y的關(guān)系是 。A . x是y的左兄弟B . x是y的右兄弟C . x是y的祖先D . x是y的后裔5. 采用鄰接表存儲的圖的廣度優(yōu)先遍歷類似于二叉樹的A .先序遍歷B .中序遍歷C .后序遍歷D .層次遍歷6使用 DFS算法遞歸地遍歷一個無環(huán)有向圖,并在

6、退出遞歸時輸出相應頂點,這樣得到的頂點序列C .無序的D .都不是概率取其值域的每一個值C .平均D .同等A .逆拓撲有序B .拓撲有序7.散列函數(shù)有共同的性質(zhì),即函數(shù)值應當以A .最大B .最小8 .對長度為10的順序表進行查找,若查找前面5個元素的概率相同,均為1/8。查找后面5個元素的概率相同,均為3/40,則查找到表中任一元素的平均查找長度為 。A . 5.5B . 5C . 39/8D . 4/39 .若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果,則該排序方法只能是 。A .起泡排序B .插入排序C .選擇排序D .二路歸并

7、排序10 .堆是一種有用的數(shù)據(jù)結(jié)構(gòu),例如排序碼序列 就是一個堆A . 16,72,31,23,94,53B. 94, 53, 31, 72, 16, 23C. 16, 53, 23, 94, 31, 72D. 16,31,23,94,53,72四、簡答題(共20分,每題5分)1 什么是線性表?線性表的兩種存儲結(jié)構(gòu)(順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu))各有哪些優(yōu)缺點?2 .輸入23, 25, 28, 10, 9, 16, 12, 18, 13, 20,給岀構(gòu)造平衡二叉樹的過程3已知下圖所示的無向圖,試畫岀(1)以D為搜索起點的先深生成樹; (2)以D為搜索起點的先廣生成樹。8,14,10,4,18,請構(gòu)

8、造岀相),求出每個字符的哈夫曼編碼。4. 有一份電文中共使用五個字符:a,b,c,d,e,它們的岀現(xiàn)頻率依次為應的哈夫曼(Huffman)樹(約定左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)五. 綜合應用題(共40分)1 已知一個帶表頭結(jié)點的單鏈表,結(jié)點的結(jié)構(gòu)為(data,link )。假設該鏈表只給出了表頭指針 list,在不改變鏈表的前提下請設計一個盡可能有效的算法,查找鏈表中倒數(shù)第k個位置上的結(jié)點(k為正數(shù))。若查找成功,算法輸岀該結(jié)點的域的值,并返回1,否則只返回0.要求:(1)描述該算法的基本思想;(2)描述該算法的詳細實現(xiàn)步驟;(3)根據(jù)算法的基本設計思想和詳細實現(xiàn)步驟,采用程序設計語

9、言描述算法,關(guān)鍵之處請給岀簡要注釋。(10 分)ADT操作)。(101,否則返回 0。 (10 分 )2. 給出二叉樹的數(shù)據(jù)結(jié)構(gòu)定義,設計算法,實現(xiàn)二叉樹的層序遍歷(可以使用書中定義的 分)3. 試設計一個算法, 判斷一個無向圖 G 是否為一棵樹。若是一棵樹,則算法返回 4設順序表中的元素依次為 017 ,094 ,154,170 ,275 ,503 ,509,512,553,612,677,765 ,897 ,908。 試畫出對其進行折半查找時的判定樹, 并計算查找成功的平均查找長度和查找不成功的平均查找長度。 ( 10 分)數(shù)據(jù)結(jié)構(gòu)考試題型:1. 名詞解釋 15 分(每題 3 分,共 5

10、題)2. 選擇 20 分(每題 2 分,共 10 題)3. 簡答 30 分(每題 5 分,共 6 題)4. 算法 35 分 (共 3 題) 名詞解釋考察樹中的名詞比較多。例如 AVL 樹,數(shù)據(jù)結(jié)構(gòu)的定義得看看。歸墟的群共享 里那份總結(jié)有所有所需名詞解釋選擇題有 2 個排序的,穩(wěn)定性的可能占一個,緒論中也會出選擇題,算法的復雜度算是 一個選擇題簡答題中拓撲排序 (課本 P147 48)單源最短路徑 (課本 P155 4-10)可能作為簡答題, 也可能是算法題 哈夫曼樹 最小生成樹算法(復習一下實驗可能會有很大的收獲)1) 鏈表2 ) 樹(據(jù)猜測考層序)3) 圖 (圖的構(gòu)建,最小生成樹,單源最短路

11、徑) 其余重點:哈希表(平均失敗、成功長度)07 年考試題中 關(guān)鍵路徑不考, kmp 不考,課本中帶星號的內(nèi)容不考,作業(yè)題中可能會考一點內(nèi)容 圖中關(guān)于是否有環(huán)路得仔細了解、名詞解釋 (每名詞 3 分,共 15 分)1、ADT2、線性表線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系,即除了第一個和最后一個數(shù)據(jù)元素之外,其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結(jié)構(gòu)簡單,便于實現(xiàn)和操作。3、滿二叉樹:除葉節(jié)點外其余節(jié)點都有兩個孩子節(jié)點的二叉樹4、拓撲排序?qū)o環(huán)路有向圖排成一個線性序列,使得當從定點 i至U j存在一條邊時,則在線性序列中將i排在j的前面5、HASH 表根據(jù)關(guān)鍵碼直接訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說

12、它通過將關(guān)鍵碼值映射到一個表中的一個位置來訪問記錄,以加快查找速度。這個映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表二、填空題(每空0.5分,共15分)1、 線性表的存儲結(jié)構(gòu)包括(1)_靜態(tài)存儲_、(2)動態(tài)存儲和(3) _靜態(tài)鏈表三種方式。樹的存儲結(jié)構(gòu)可歸納為(4)雙親表示法、(5)孩子表示法_和(6)左右鏈表示法三種方法。圖的存儲結(jié)構(gòu)包括(7)鄰接矩陣和(8)鄰接鏈表兩種方式。2、 (9)棧是一種特殊形式的線性表,對于它,所有的 (10)插入和(11刪除操作都在表的一端進行。(12)隊列是另一種形式的線性表,對于它,所有的(13) 刪除操作在表的一端進行,而(14) 插入操作則在表的另一

13、端進行。3、 對無向圖進行先深搜索的結(jié)果,把圖中所有邊分成(15) 和(16) 兩類。(15)從先深編號(17) 的結(jié)點指向先深編號(18) 的結(jié)點,(16)從先深編號(19) 的結(jié)點指向先深編號(20) 的結(jié)點。而對有向圖進行先深搜索和先深編號形成先深生成森林,圖中所有邊被分成(21)、(22)、(23) 和(24) 四類。4、 在帶權(quán)的有向圖中,用結(jié)點表示(25) _事件,邊表示(26) _活動,(27)邊上的權(quán)值表示活動所持續(xù)的時間,把這樣的有向圖關(guān)于邊的活動網(wǎng),簡稱AOE網(wǎng)。5、磁盤文件的歸并排序主要解決以下三個方面的問題,以此提高歸并的效率。(28 )多路歸并以減少歸并次;(29)并

14、行操作的緩存區(qū)處理使輸入輸出盡可能的與CPU工作重疊;(30)初始歸并段的生成_;三、 簡要回答下列問題(每問題5分,共40分)1、設二叉樹中度為1的結(jié)點數(shù)為0,試證明該二叉樹的總分支數(shù)為2(n 0-1),其中,n。為度為0 (葉子)結(jié)點的數(shù)目。1H2、已知圖的存儲結(jié)構(gòu),給出圖的深度優(yōu)先( DFS和廣度優(yōu)先(BFS序列3、下面哪一個方法可以判斷出一個有向圖中是否有環(huán)(回路),(1)深度優(yōu)先遍歷,(2)拓樸排序,(3)求最短路徑,(4)求關(guān)鍵路徑4、試求按關(guān)鍵字序列(12,1,4, 3,7,8,10, 2)插入生成的二叉排序樹和平衡二叉樹5、求最小生成樹6、假設字符 a,b,c,d,e,f的使用

15、頻度分別是 0.07,0.09,0.12,0.22,0.23,0.27,寫出 a,b,c,d,e,f 的 Huffman (哈夫曼)編碼。7、一棵二叉樹的先序和中序序列分別如下,畫岀該二叉樹先序:A B C D E F G H I J中序:C B E D A G H F J I8、求單源最短路徑,設源點為A,頂點A-E依次編號為1-5步驟集合SwD2(B)D3(C)D4(D)D5(E)初態(tài)112345四、算法設計(共30分)1、已知任意排列的線性鏈表,結(jié)點的數(shù)據(jù)類型為整形,表頭結(jié)點為Head。設計算法實現(xiàn)鏈表就地排序,重新整理該鏈表為升序序列的鏈表。(此題8分)要求:給岀結(jié)點類型定義,假設鏈表

16、已建立。序輸出二叉樹中的每個結(jié)點,同時給出每個結(jié)點所在層號及二叉樹的高度。(此題 10 分)3、自定義圖的鄰接表存儲結(jié)構(gòu),并在此結(jié)構(gòu)上實現(xiàn)計算每個頂點入度和出度的算法。要求:( 1)給出結(jié)構(gòu)類型定義,并進行簡要說明;( 2)結(jié)構(gòu)類型中有存放每個頂點的入度和出度的空間;( 2)實現(xiàn)計算每個頂點入度和出度的算法;注:假設按照你所定義結(jié)構(gòu)的鄰接表已經(jīng)存在,不需要實現(xiàn)建立鄰接表的算法。(此題 12 分)名詞總結(jié):ADT :抽象數(shù)據(jù)型是一個數(shù)學模型和在該模型上定義的操作的集合 線性表:線性表是由n(n0)個相同類型的元素組成的有序集合。棧 :線性表的一種特殊形式,是一種限定性數(shù)據(jù)結(jié)構(gòu),也就是在對線性表的

17、操作加以限制后,形成的一種新的 數(shù)據(jù)結(jié)構(gòu)。是限定只在表尾進行插入和刪除操作的線性表。棧又稱為后進先出的線性表。隊列: 將線性表的插入和刪除操作分別限制在表的兩端進行,和棧相反,隊列是一種先進先出的線性表。串: 線性表的一種特殊形式,表中每個元素的類型為字符型,是一個有限的字符序列。廣義表: 由零個原子,或若干個原子或若干個廣義表組成的有窮序列。樹:1、一個結(jié)點x組成的集X是一株樹仃ree),這個結(jié)點x也是這株樹的根。2、假設x是一個結(jié)點,T1 , T2,,Tk是k株互不相交的樹,我們可以構(gòu)造一株新樹:令x為根,并有k條邊由x指向樹T1,T2,Tk。這些邊也叫做分支,T1,T2,Tk稱作根x的樹

18、之子樹。二叉樹: 有限個結(jié)點的集合,這個集合或者是空集,或者是由一個根結(jié)點和兩株互不相交的二叉樹組成,其中一 株叫根的做左子樹,另一棵叫做根的右子樹。滿二叉樹: 深度為 k 且有 2k 1 個結(jié)點的二叉樹稱為滿二叉樹。完全二叉樹: 深度為 k 的,有 n 個結(jié)點的二叉樹, 當且僅當其每個結(jié)點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結(jié)點一一對應,稱之為完全二叉樹。線索二叉樹:若結(jié)點p有左孩子,則p->lchild指向其左孩子結(jié)點,否則令其指向其(中序)前驅(qū)。若結(jié)點 p有右 孩子,則 p->rchild 指向其右孩子結(jié)點,否則令其指向其(中序)后繼。堆: 如果一棵完全二叉樹的

19、任意一個非終端結(jié)點的元素都不小于其左兒子結(jié)點和右兒子結(jié)點(如果有的話)的元 素,則稱此完全二叉樹為最大堆。 同樣, 如果一棵完全二叉樹的任意一個非終端結(jié)點的元素都不大于其左兒子 結(jié)點和右兒子結(jié)點(如果有的話)的元素,則稱此完全二叉樹為最小堆。選擇樹: 一棵選擇樹是一棵二叉樹,其中每一個結(jié)點都代表該結(jié)點兩個兒子中的較小者。這樣,樹的根結(jié)點就表 示樹中最小元素的結(jié)點。二叉排序樹: 二叉排序樹或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹:1、若它的左子樹非空,則左子樹上的所有結(jié)點的值均小于它的根結(jié)點的值。2、若它的右子樹非空,則右子樹上的所有結(jié)點的值均大于或等于它的根結(jié)點的值。3、它的左右子樹分別為二

20、叉排序樹。圖:一個圖G= ( V,E)是一個由非空的有限集V和一個邊集E所組成的。若E中的每條邊都是頂點的有序?qū)?v , w),就說該圖是有向圖(directed graph,digraph) o若E中的每條邊是兩個不同頂點無序?qū)?,就說該圖 是無向圖,其邊仍表示成( v, w)。開放樹: 連通而無環(huán)路的無向圖稱作開放樹。最小生成樹:設G=( V, E )是一個連通圖,E中每一條邊(u, v)的權(quán)為C(u, v),也叫做邊長。圖 G的一株生成樹(spanning tree)是連接V中所有結(jié)點的一株開放樹。將生成樹中所有邊長之總和稱為生成樹的價(cost)。使這個價最小的生成樹稱為圖G的最小生成樹

21、。無向圖雙連通分量: 設Vi是Ei中各邊所連接的點集( K i< k),每個圖Gi = ( Vi , E i )叫做G的一個 雙連通分量。雙連通圖:若對V中每個不同的三元組 v,w,a;在v和w之間都存在一條不包含 a 的路,就說 G 是雙連通的強連通性:設G = (V, E)是一個有向圖,稱頂點 v ,w V是等價的,要么v = w ;要么從頂點v到w有一條有 向路 ,并且從頂點 w 到 v 也有一條有向路。拓撲排序:給定一個無環(huán)路有向圖 G=(V,E),各結(jié)點的編號為v=(1,2,,。要求對每一個結(jié)點i重新進行編號, 使得若i是j的前導,則有Labeli<labelj。即拓撲分

22、類是將無環(huán)路有向圖排成一個線性序列,使當 從結(jié)點 i 到結(jié)點 j 存在一條邊,則在線性序列中,將 i 排在 j 的前面。AOE 網(wǎng): 在帶權(quán)的有向圖中,用結(jié)點表示事件,用邊表示活動,邊上權(quán)表示活動的開銷(如持續(xù)時間),則稱此有向圖為邊表示活動的網(wǎng)絡 ,簡稱 AOE 網(wǎng)。關(guān)鍵路徑: 在 AOE 網(wǎng)中,由于有些活動可以并行,所以完成工程的最短時間是從源點到匯點的最大路徑長度。因此,把從源點到匯點具有最大長度的路徑稱為關(guān)鍵路徑。查找表: 由同一類型的數(shù)據(jù)元素(或紀錄)構(gòu)成的集合。關(guān)鍵字: 數(shù)據(jù)元素中某一數(shù)據(jù)項的值,用以表示一個數(shù)據(jù)元素。AVL 樹: AVL 樹或者是一顆空二叉樹,或者具有如下性質(zhì)的二叉查找樹:其左子樹和右子樹都是高度平衡的二叉樹,且左子樹和右子樹高度之差的絕對值不超過1。B-樹:B-樹是一種非二叉的查找樹除了要滿足查找樹的特性,還要滿足以下結(jié)構(gòu)特性:一棵m階的B-樹:(1)樹的根

溫馨提示

  • 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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論