數(shù)據(jù)結(jié)構(gòu)試題2009秋本科A

1、一 填空題（共20分，每空1分）1設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data,next），next為指針域。已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需執(zhí)行一下語(yǔ)句：（ py-next = px-next ；）（ px-next = py ）。2設(shè)無(wú)向圖G的頂點(diǎn)數(shù)為n，圖G最少有（ n-1 ）邊；最多有（n(n-1)/2 ）邊。若G為有向圖，有n個(gè)頂點(diǎn)，則圖G最少有（ n-1）邊；最多有（n(n-1) ）邊。3設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過(guò)push，push，pop，push，pop，push，push后，輸出序列是（ 5,

2、4,1 ）。4由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為（ ）5由a，b，c三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有（ 5 ）種不同的結(jié)構(gòu)。6在線性表的散列存儲(chǔ)中，處理沖突有（ ）和（ ）方法。7在對(duì)一組記錄（50，40，95，20，15，70，60，45，80）進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄的交換的次數(shù)為（ 6 ），在整個(gè)排序過(guò)程中共需進(jìn)行（ 8 ）趟就可以將排序完成。8數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（ ）和（）以及它們之間的相互關(guān)系。9. 散列法要解決的兩個(gè)關(guān)鍵問(wèn)題是（ 散列函數(shù) ）和（ 沖突 ）。10.外部排序需要考慮的三個(gè)關(guān)鍵問(wèn)題分別是（多路歸并以減少歸并次數(shù)）、（并行操

3、作的緩沖區(qū)處理盡量使輸入與輸出與CPU工作重疊）和（初始并歸段的生成）。二判斷題（對(duì)的填，錯(cuò)的填，共10分，每題1分）1在線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（ ）2在鏈?zhǔn)酱鎯?chǔ)的棧的頭部必須要設(shè)頭結(jié)點(diǎn)。（ ）3在二叉樹中插入結(jié)點(diǎn)，則該項(xiàng)二叉樹便不再是二叉樹。（ ）4由二叉樹結(jié)點(diǎn)的先序序列和后序序列可以唯一確定一棵二叉樹。（ ）5樹的父鏈表示就是用數(shù)組表示樹的存儲(chǔ)結(jié)構(gòu)。（ ）6任何二叉樹都唯一對(duì)應(yīng)一個(gè)森林，反之亦然。（ ）7順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。( )8用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列。( )9算法分析的目的是分析算法的易讀性（ ）。10一組記錄的關(guān)鍵字為（4

4、6,79,56,38,40,84）,則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為40,38,46,56,79,84（ ）。三選擇題（共10分，每題1分）1快速分類在_的情況下不利于發(fā)揮其長(zhǎng)處。A. 待分類的數(shù)據(jù)量太大 B. 待分類的數(shù)據(jù)相同值過(guò)多C. 待分類的數(shù)據(jù)已基本有序 D. 待分類的數(shù)據(jù)值差過(guò)大.2已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為 。A39 B52 C111 D1193設(shè)森林中有三棵樹，第一、第二和第三棵樹中的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3。那么在由該森林轉(zhuǎn)化成二叉樹中根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是 。Am1+m2

5、Bm2+m3 Cm3+m1 Dm1+m2+m34 設(shè)結(jié)點(diǎn)x和y是二叉樹中任意的兩個(gè)結(jié)點(diǎn)。在該二叉樹的前序遍歷序列中x在y之前，而在其后序遍歷序列中x在y之后，則x和y的關(guān)系是 。Ax是y的左兄弟 Bx是y的右兄弟 Cx是y的祖先 Dx是y的后裔5采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷類似于二叉樹的A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷6使用DFS算法遞歸地遍歷一個(gè)無(wú)環(huán)有向圖，并在退出遞歸時(shí)輸出相應(yīng)頂點(diǎn)，這樣得到的頂點(diǎn)序列是 。 A逆拓?fù)溆行?B拓?fù)溆行?C無(wú)序的 D都不是7散列函數(shù)有共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 概率取其值域的每一個(gè)值。A最大 B最小 C平均 D同等8對(duì)長(zhǎng)度為10的順序表進(jìn)行查

6、找，若查找前面5個(gè)元素的概率相同，均為1/8。查找后面5個(gè)元素的概率相同，均為3/40，則查找到表中任一元素的平均查找長(zhǎng)度為 。 A5.5 B5 C39/8 D4/39若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序方法只能是 。A起泡排序 B插入排序 C選擇排序 D二路歸并排序10堆是一種有用的數(shù)據(jù)結(jié)構(gòu)，例如排序碼序列 就是一個(gè)堆。A16，72，31，23，94，53 B94，53，31，72，16，23C16，53，23，94，31，72 D16，31，23，94，53，72四、簡(jiǎn)答題（共20分，每題5分 ）1什么是線性表？線

7、性表的兩種存儲(chǔ)結(jié)構(gòu)(順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu))各有哪些優(yōu)缺點(diǎn)?2輸入23, 25, 28, 10, 9, 16, 12, 18, 13, 20，給出構(gòu)造平衡二叉樹的過(guò)程。3已知下圖所示的無(wú)向圖，試畫出（1）以D為搜索起點(diǎn)的先深生成樹；（2）以D為搜索起點(diǎn)的先廣生成樹。4有一份電文中共使用五個(gè)字符:a，b，c，d，e，它們的出現(xiàn)頻率依次為8，14，10，4，18，請(qǐng)構(gòu)造出相應(yīng)的哈夫曼(Huffman)樹(約定左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)),求出每個(gè)字符的哈夫曼編碼。五綜合應(yīng)用題（共40分）1已知一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。假設(shè)該鏈表只給出了表頭指針l

8、ist，在不改變鏈表的前提下請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能有效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的域的值，并返回1，否則只返回0.要求：（1）描述該算法的基本思想；（2）描述該算法的詳細(xì)實(shí)現(xiàn)步驟；（3）根據(jù)算法的基本設(shè)計(jì)思想和詳細(xì)實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法，關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。（10分）2. 給出二叉樹的數(shù)據(jù)結(jié)構(gòu)定義，設(shè)計(jì)算法，實(shí)現(xiàn)二叉樹的層序遍歷（可以使用書中定義的ADT操作）。（10分）3.試設(shè)計(jì)一個(gè)算法， 判斷一個(gè)無(wú)向圖G是否為一棵樹。若是一棵樹，則算法返回1，否則返回0。(10分)4設(shè)順序表中的元素依次為017，094，154，170，275

9、，503，509，512，553，612，677，765，897，908。試畫出對(duì)其進(jìn)行折半查找時(shí)的判定樹，并計(jì)算查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。（10分）一、名詞解釋（每名詞3分，共15分）1、ADTADT包括數(shù)據(jù)元素，數(shù)據(jù)關(guān)系以及相關(guān)操作2、線性表線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結(jié)構(gòu)簡(jiǎn)單，便于實(shí)現(xiàn)和操作。3、滿二叉樹：除葉節(jié)點(diǎn)外其余節(jié)點(diǎn)都有兩個(gè)孩子節(jié)點(diǎn)的二叉樹4、拓?fù)渑判驅(qū)o(wú)環(huán)路有向圖排成一個(gè)線性序列，使得當(dāng)從定點(diǎn)i到j(luò)存在一條邊時(shí)，則在線性序列中將i排在j的前面5、HASH表根據(jù)關(guān)鍵碼

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

11、14)_插入操作則在表的另一端進(jìn)行。3、 對(duì)無(wú)向圖進(jìn)行先深搜索的結(jié)果，把圖中所有邊分成(15)_和(16)_兩類。(15)從先深編號(hào)(17)_的結(jié)點(diǎn)指向先深編號(hào)(18)_的結(jié)點(diǎn)，(16)從先深編號(hào)(19)_的結(jié)點(diǎn)指向先深編號(hào)(20)_的結(jié)點(diǎn)。而對(duì)有向圖進(jìn)行先深搜索和先深編號(hào)形成先深生成森林，圖中所有邊被分成(21)_、(22)_、(23)_和（24）_四類。4、 在帶權(quán)的有向圖中，用結(jié)點(diǎn)表示（25）_事件，邊表示（26）_活動(dòng)，（27）邊上的權(quán)值表示活動(dòng)所持續(xù)的時(shí)間，把這樣的有向圖關(guān)于邊的活動(dòng)網(wǎng)，簡(jiǎn)稱AOE網(wǎng)。5、 磁盤文件的歸并排序主要解決以下三個(gè)方面的問(wèn)題，以此提高歸并的效率。(28）多路

12、歸并以減少歸并次； (29)并行操作的緩存區(qū)處理使輸入輸出盡可能的與CPU工作重疊； (30)初始?xì)w并段的生成_；三、簡(jiǎn)要回答下列問(wèn)題（每問(wèn)題5分，共40分）1、 設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為0，試證明該二叉樹的總分支數(shù)為2(n0-1)，其中，n0為度為0（葉子）結(jié)點(diǎn)的數(shù)目。2、 已知圖的存儲(chǔ)結(jié)構(gòu)，給出圖的深度優(yōu)先（DFS）和廣度優(yōu)先（BFS）序列。1ABCDEFG244213650123456 3、下面哪一個(gè)方法可以判斷出一個(gè)有向圖中是否有環(huán)（回路），為什么？ (1)深度優(yōu)先遍歷，(2)拓樸排序，(3)求最短路徑，(4)求關(guān)鍵路徑 4、 試求按關(guān)鍵字序列（12，1，4，3，7，8，1O，2）插

13、入生成的二叉排序樹和平衡二叉樹。5、求最小生成樹6、 假設(shè)字符a,b,c,d,e,f的使用頻度分別是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è)源點(diǎn)為A, 頂點(diǎn)A-E依次編號(hào)為1-5。步驟集合SwD2(B)D3(C)D4(D)D5(E)初態(tài)112345四、算法設(shè)計(jì)（共30分）1、 已知任意排列的線性鏈表，結(jié)點(diǎn)的數(shù)據(jù)類型為整形，表頭結(jié)點(diǎn)為Head。設(shè)

14、計(jì)算法實(shí)現(xiàn)鏈表就地排序，重新整理該鏈表為升序序列的鏈表。（此題8分）要求：給出結(jié)點(diǎn)類型定義，假設(shè)鏈表已建立。2、 已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，設(shè)計(jì)算法實(shí)現(xiàn)二叉樹按層序遍歷，即從第一層到最后一層，每層從左到右順序輸出二叉樹中的每個(gè)結(jié)點(diǎn)，同時(shí)給出每個(gè)結(jié)點(diǎn)所在層號(hào)及二叉樹的高度。（此題10分）3、自定義圖的鄰接表存儲(chǔ)結(jié)構(gòu)，并在此結(jié)構(gòu)上實(shí)現(xiàn)計(jì)算每個(gè)頂點(diǎn)入度和出度的算法。 要求：（1）給出結(jié)構(gòu)類型定義，并進(jìn)行簡(jiǎn)要說(shuō)明； （2）結(jié)構(gòu)類型中有存放每個(gè)頂點(diǎn)的入度和出度的空間； （2）實(shí)現(xiàn)計(jì)算每個(gè)頂點(diǎn)入度和出度的算法； 注：假設(shè)按照你所定義結(jié)構(gòu)的鄰接表已經(jīng)存在，不需要實(shí)現(xiàn)建立鄰接表的算法。 （此題12分）

15、一、 名詞總結(jié)：ADT：抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型和在該模型上定義的操作的集合線性表： 線性表是由n(n0)個(gè)相同類型的元素組成的有序集合。棧：線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，也就是在對(duì)線性表的操作加以限制后，形成的一種新的數(shù)據(jù)結(jié)構(gòu)。是限定只在表尾進(jìn)行插入和刪除操作的線性表。棧又稱為后進(jìn)先出的線性表。隊(duì)列：將線性表的插入和刪除操作分別限制在表的兩端進(jìn)行，和棧相反，隊(duì)列是一種先進(jìn)先出的線性表。串：線性表的一種特殊形式，表中每個(gè)元素的類型為字符型，是一個(gè)有限的字符序列。 廣義表：由零個(gè)原子，或若干個(gè)原子或若干個(gè)廣義表組成的有窮序列。 樹：1、一個(gè)結(jié)點(diǎn)x組成的集x是一株樹(Tree)，這個(gè)

16、結(jié)點(diǎn)x也是這株樹的根。2、假設(shè)x是一個(gè)結(jié)點(diǎn)，T1，T2，Tk是 k 株互不相交的樹，我們可以構(gòu)造一株新樹：令x為根，并有k條邊由x指向樹T1，T2，Tk。這些邊也叫做分支，T1，T2，Tk稱作根x的樹之子樹。 二叉樹：有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集合或者是空集，或者是由一個(gè)根結(jié)點(diǎn)和兩株互不相交的二叉樹組成，其中一株叫根的做左子樹，另一棵叫做根的右子樹。 滿二叉樹：深度為k且有2k 1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。 完全二叉樹：深度為 k 的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為 k 的滿二叉樹中編號(hào)從 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)，稱之為完全二叉樹。 線索二叉樹：若結(jié)點(diǎn)p有左孩子，則p-lc

17、hild指向其左孩子結(jié)點(diǎn)，否則令其指向其（中序）前驅(qū)。若結(jié)點(diǎn)p有右孩子，則p-rchild指向其右孩子結(jié)點(diǎn)，否則令其指向其（中序）后繼。 堆：如果一棵完全二叉樹的任意一個(gè)非終端結(jié)點(diǎn)的元素都不小于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹為最大堆。同樣，如果一棵完全二叉樹的任意一個(gè)非終端結(jié)點(diǎn)的元素都不大于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹為最小堆。 選擇樹：一棵選擇樹是一棵二叉樹，其中每一個(gè)結(jié)點(diǎn)都代表該結(jié)點(diǎn)兩個(gè)兒子中的較小者。這樣，樹的根結(jié)點(diǎn)就表示樹中最小元素的結(jié)點(diǎn)。 二叉排序樹：二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1、若它的左子

18、樹非空，則左子樹上的所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。2、若它的右子樹非空，則右子樹上的所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值。3、它的左右子樹分別為二叉排序樹。 圖：一個(gè)圖G=（V，E）是一個(gè)由非空的有限集 V和一個(gè)邊集E所組成的。若E中的每條邊都是頂點(diǎn)的有序?qū)Γ╲ , w），就說(shuō)該圖是有向圖（directed graph，digraph）。若E中的每條邊是兩個(gè)不同頂點(diǎn)無(wú)序?qū)?，就說(shuō)該圖是無(wú)向圖，其邊仍表示成（v, w）。 開放樹：連通而無(wú)環(huán)路的無(wú)向圖稱作開放樹。 最小生成樹：設(shè)G=( V, E )是一個(gè)連通圖，E中每一條邊(u, v)的權(quán)為C(u, v)，也叫做邊長(zhǎng)。圖G的一株生成樹(spa

19、nning tree)是連接V中所有結(jié)點(diǎn)的一株開放樹。將生成樹中所有邊長(zhǎng)之總和稱為生成樹的價(jià)(cost)。使這個(gè)價(jià)最小的生成樹稱為圖G的最小生成樹。 無(wú)向圖雙連通分量：設(shè) Vi 是 Ei 中各邊所連接的點(diǎn)集（1ik）, 每個(gè)圖Gi = ( Vi , E i ) 叫做 G 的一個(gè)雙連通分量。 雙連通圖：若對(duì)V中每個(gè)不同的三元組v,w,a；在v和w之間都存在 一條不包含 a 的路，就說(shuō)G是雙連通的 強(qiáng)連通性：設(shè)G =（V, E）是一個(gè)有向圖，稱頂點(diǎn)v ,wV是等價(jià)的，要么v = w；要么從頂點(diǎn) v 到 w 有一條有向路 ，并且從頂點(diǎn) w 到 v 也有一條有向路。 拓?fù)渑判颍航o定一個(gè)無(wú)環(huán)路有向圖G=

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