數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A(可編輯優(yōu)質(zhì)文檔)

1、數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A （可編輯優(yōu)質(zhì)文檔）（可以直接使用，可編輯 完整版資料，歡迎下載）填空題（共20分，每空1 分）1 設(shè)單鏈表的結(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設(shè)無向圖G的頂點數(shù)為n,有n個頂點，則圖 G最少有（n-1 ）邊；最多有（n-1）邊；最多有（n（n-1）圖G最少有（n(n-1)/2邊。）邊。若G為有向圖,3 .設(shè)有一空棧，現(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 在鏈?zhǔn)酱鎯Φ臈５念^部必須要設(shè)頭結(jié)點。（）3 在二叉樹中插入結(jié)點，則該項二叉樹便不再是二叉樹。（）4由二叉樹結(jié)點的先序序列和后序序列可以唯一確定一5樹的父鏈表示就是用數(shù)組表示樹的存儲結(jié)構(gòu)。6任何二叉樹都唯一對應(yīng)一個森林，反之亦然。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分）棵二叉樹。（）（）（）（）,則利用快速排序的方法，以第一個記錄為基準(zhǔn)元素得到）。1 快速分類在 的情況下不利于發(fā)揮其長處。A. 待分類的數(shù)據(jù)量太大B. 待分類的數(shù)據(jù)相同值過多C. 待分類的數(shù)據(jù)已基本有序D. 待分類的數(shù)據(jù)值差過大2 已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多B . 52C. 111D

5、. 1193設(shè)森林中有三棵樹，第一、第二和第三棵樹中的結(jié)點個數(shù)分別為 成二叉樹中根結(jié)點的右子樹上的結(jié)點個數(shù)是。m1、m2和m3。那么在由該森林轉(zhuǎn)化A . m1+m2B . m2+m3C . m3+m1D . m1+m2+m3x在y之前，而在其后序遍4. 設(shè)結(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、退出遞歸時輸出相應(yīng)頂點，這樣得到的頂點序列C .無序的D .都不是概率取其值域的每一個值C .平均D .同等A .逆拓?fù)溆行駼 .拓?fù)溆行?.散列函數(shù)有共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以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)頻率依次為應(yīng)的哈夫曼（Huffman）樹（約定左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)五. 綜合應(yīng)用題（共40分）1 已知一個帶表頭結(jié)點的單鏈表，結(jié)點的結(jié)構(gòu)為（data,link ）。假設(shè)該鏈表只給出了表頭指針 list，在不改變鏈表的前提下請設(shè)計一個盡可能有效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點（k為正數(shù)）。若查找成功，算法輸岀該結(jié)點的域的值，并返回1,否則只返回0.要求：（1）描述該算法的基本思想；（2）描述該算法的詳細(xì)實現(xiàn)步驟；（3）根據(jù)算法的基本設(shè)計思想和詳細(xì)實現(xiàn)步驟，采用程序設(shè)計語

9、言描述算法，關(guān)鍵之處請給岀簡要注釋。（10 分）ADT操作）。（101，否則返回 0。 （10 分 ）2. 給出二叉樹的數(shù)據(jù)結(jié)構(gòu)定義，設(shè)計算法，實現(xiàn)二叉樹的層序遍歷（可以使用書中定義的 分）3. 試設(shè)計一個算法， 判斷一個無向圖 G 是否為一棵樹。若是一棵樹，則算法返回 4設(shè)順序表中的元素依次為 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)定性的可能占一個，緒論中也會出選擇題，算法的復(fù)雜度算是 一個選擇題簡答題中拓?fù)渑判?（課本 P147 48）單源最短路徑 （課本 P155 4-10）可能作為簡答題， 也可能是算法題 哈夫曼樹 最小生成樹算法（復(fù)習(xí)一下實驗可能會有很大的收獲）1） 鏈表2 ） 樹（據(jù)猜測考層序）3） 圖 （圖的構(gòu)建，最小生成樹，單源最短路

11、徑） 其余重點：哈希表（平均失敗、成功長度）07 年考試題中 關(guān)鍵路徑不考， kmp 不考，課本中帶星號的內(nèi)容不考，作業(yè)題中可能會考一點內(nèi)容 圖中關(guān)于是否有環(huán)路得仔細(xì)了解、名詞解釋 （每名詞 3 分，共 15 分）1、ADT2、線性表線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結(jié)構(gòu)簡單，便于實現(xiàn)和操作。3、滿二叉樹：除葉節(jié)點外其余節(jié)點都有兩個孩子節(jié)點的二叉樹4、拓?fù)渑判驅(qū)o環(huán)路有向圖排成一個線性序列，使得當(dāng)從定點 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)初始?xì)w并段的生成_;三、 簡要回答下列問題(每問題5分，共40分)1、設(shè)二叉樹中度為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、假設(shè)字符 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、求單源最短路徑，設(shè)源點為A,頂點A-E依次編號為1-5步驟集合SwD2(B)D3(C)D4(D)D5(E)初態(tài)112345四、算法設(shè)計（共30分）1、已知任意排列的線性鏈表，結(jié)點的數(shù)據(jù)類型為整形，表頭結(jié)點為Head。設(shè)計算法實現(xiàn)鏈表就地排序，重新整理該鏈表為升序序列的鏈表。（此題8分）要求：給岀結(jié)點類型定義，假設(shè)鏈表

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

17、操作加以限制后，形成的一種新的 數(shù)據(jù)結(jié)構(gòu)。是限定只在表尾進行插入和刪除操作的線性表。棧又稱為后進先出的線性表。隊列： 將線性表的插入和刪除操作分別限制在表的兩端進行，和棧相反，隊列是一種先進先出的線性表。串： 線性表的一種特殊形式，表中每個元素的類型為字符型，是一個有限的字符序列。廣義表： 由零個原子，或若干個原子或若干個廣義表組成的有窮序列。樹：1、一個結(jié)點x組成的集X是一株樹仃ree)，這個結(jié)點x也是這株樹的根。2、假設(shè)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é)點的二叉樹， 當(dāng)且僅當(dāng)其每個結(jié)點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結(jié)點一一對應(yīng)，稱之為完全二叉樹。線索二叉樹：若結(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)路的無向圖稱作開放樹。最小生成樹：設(shè)G=( V, E )是一個連通圖，E中每一條邊(u, v)的權(quán)為C(u, v)，也叫做邊長。圖 G的一株生成樹(spanning tree)是連接V中所有結(jié)點的一株開放樹。將生成樹中所有邊長之總和稱為生成樹的價(cost)。使這個價最小的生成樹稱為圖G的最小生成樹

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

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