鄭州輕工業(yè)學(xué)院09-10學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)試題(B卷)

1、請畫出該二叉樹，并寫出其先序遍歷序列（7分）20092010學(xué)年第二學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)試題 B一、單項選擇題（每道選擇題只有一個正確答案；共15小題，每小題2分，共30分）1 數(shù)據(jù)結(jié)構(gòu)是【】。A. 種數(shù)據(jù)類型B 數(shù)據(jù)的存儲結(jié)構(gòu)C 一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2. 線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址【】。A.必須是不連續(xù)的B. 連續(xù)與否均可 C 必須是連續(xù)的 D 和頭結(jié)點的存儲地址相連續(xù)3. 若線性表最常用的操作是存取第 i個元素及其前驅(qū)元素的值，則采用【】存儲方式最節(jié)省時間。A單鏈表 B 雙向鏈表 C 單循環(huán)鏈表 D 順序表4. 設(shè)棧S和隊

2、列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g 依次進入棧S。若每個元素出棧后立即進入隊列Q且7個元素出隊的順序是b,d,c,f,e,a,g ，則棧S的容量至少是【 】。 A . 1 B . 2 C . 3 D . 45. 為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩存區(qū)， 主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是【】。A 棧B 隊列 C 樹 D 圖6排序算法的穩(wěn)定性是指【】。A 經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對位置不變B經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對位置不變C算法的排序性能與

3、被排序元素的數(shù)量關(guān)系不大D算法的排序性能與被排序元素的數(shù)量關(guān)系密切7 在下列排序方法中，【】的比較次數(shù)與記錄的初始排列狀態(tài)無關(guān)。A.直接插入排序 B.起泡排序 C.快速排序 D.簡單選擇排序&在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系【】。A.不一定相同B .都相同C.都不相同D .互為逆序9二維數(shù)組A89按行優(yōu)先順序存儲，若數(shù)組元素A23的存儲地址為1087,A47的存儲地址為1153,則數(shù)組元素A67的存儲地址為【】。A. 1207 B . 1209 C . 1211 D. 121310. 若從二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序，則該二叉樹

4、是【】。A .二叉排序樹B .哈夫曼樹C .堆D . AVL樹11. 棧中元素的進出原則是【】。A.先進先出 B.后進先出C.棧空則進D.棧滿則出12. 數(shù)組Q 20用來表示一個循環(huán)隊列，f為當(dāng)前隊列頭元素的位置，r為隊尾元素的后一位置，若隊列的長度和隊頭指針值分別為13和17,則當(dāng)前尾指針的值為【】。A.8B . 9C . 10D. 1113. 若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是【】A.9B . 11 C. 15 D .不確定14. 一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是【】。A. Jogn +1 B . logn+1C . IljognD .

5、 logn-115. 引入二叉線索樹的目的是【】。A加快查找結(jié)點的前驅(qū)或后繼的速度B為了能在二叉樹中方便的進行插入與刪除C. 為了能方便的找到雙親D .使二叉樹的遍歷結(jié)果唯一二、應(yīng)用題（共5題，共計50分）1. 已知一棵二叉樹的中序遍歷結(jié)果為GDHBAEC,后序遍歷結(jié)果為 GHDBEIFCA3. 已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點的結(jié)構(gòu)為:依此鄰接表：（1）寫出從頂點 C出發(fā)進行深度優(yōu)先搜索的遍歷序列；（2）寫出從頂點 C出發(fā)進行廣度度優(yōu)先搜索的遍歷序列；（3） 按照PRIM算法畫出從頂點 C出發(fā)求最小生成樹的過程。（15分）4. 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符（a, b, c

6、, d, e, f ,g, h），其概率分別為 0.05， 0.29，0.07，0.08，0.14，0.23，0.03，0.11，試畫出對 應(yīng)的編碼Huffman樹（請按照左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的 次序構(gòu)造），求每種字符的 Huffman編碼。（12分）5 .設(shè)哈希（Hash）表的地址范圍為 017,哈希函數(shù)為：H （ K）= K MOD 16。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：（10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49）造出Hash表，試回答下列問題：（11分）（1）畫出哈希表的示意圖；（2）若查找關(guān)鍵字6

7、3,需要依次與哪些關(guān)鍵字進行比較？（3）若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？（4）假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。四、編程題（每題 10分，共20分）1.設(shè)有一個單向循環(huán)鏈表結(jié)構(gòu)，first是指向頭結(jié)點的指針。（1 ）請編寫一個算法，將此鏈表中數(shù)據(jù)最小的結(jié)點從鏈表中刪除。（2）請分析你的算法的時間復(fù)雜度。2. 給出算法分別求出二叉樹的葉結(jié)點、度數(shù)為1的結(jié)點、度數(shù)為2的結(jié)點的個數(shù)。一個處處像別人表明自己優(yōu)秀的，恰恰證明了他（她）并不優(yōu)秀，或者說缺什么，便炫耀什么。對生活飽有熱情，滿足與一些小確幸，也要經(jīng)得起誘惑，耐得住寂寞，內(nèi)心始終如孩童般的純真。要知道，你走的

8、每一步，都是為了遇見更好的自己，都是為了不辜負所有的好年華。一個真實的人，一定也是個有擔(dān)當(dāng)?shù)?。不論身處何地，居于何種逆境，他（她）們都不會畏懼坎坷和暴風(fēng)雨的襲擊。因為知道活著的意義，就是真實的直面風(fēng)浪。生而為人，我們可以失敗，卻不能敗的沒有風(fēng)骨，甚至連挑戰(zhàn)的資格都不敢有。人當(dāng)如玉，無骨不去其身。生于塵，立于世，便該有一顆寬厚仁德之心，便有一份容天下之事的氣度。一個真實的人，但是又不會過于執(zhí)著。因為懂得，水至清則無魚，人至察則無徒的道理。完美主義者最大的悲哀，就是活得不真實，不知道審時度勢，適可而止。一扇窗，推開是艷陽天，關(guān)閉，也要安暖向陽。不煩不憂，該來的就用心珍惜，坦然以對；要走的就隨它去，

9、無怨無悔。人活著，就是在修行，最大的樂趣，就是從痛苦中尋找快樂。以積極的狀態(tài)，過好每一天，生活不完美，我們也要向美而生。一個真實的人，一定是懂愛的。時光的旅途中，大多數(shù)都是匆匆擦肩的過客。只有那么微乎其微的人，才可以相遇，結(jié)伴同行。而這樣的結(jié)伴一定又是基于志趣相投，心性相近的品性。最好的愛，不是在于共富貴，而是可以共患難，就像一對翅膀，只有相互擁抱著才能飛翔。愛似琉璃，正是因為純粹干凈，不沾染俗世的美。懂愛的人，一定是真實的人。正是因為懂得真愛的不易，所以更是以真面目面對彼此，十指緊扣，甘愿與愛的人把世間各種風(fēng)景都看透，無論風(fēng)雨，安暖相伴。一個真實的人，定然是有著大智慧的。人生在世，什么都追求好，追求完美，雖然這是一種積極的思想，卻會很累，不僅自己累，身