鄭州輕工業(yè)學院09-10學年第2學期數據結構試題(B卷)

1、請畫出該二叉樹，并寫出其先序遍歷序列（7分）20092010學年第二學期期末考試數據結構試題 B一、單項選擇題（每道選擇題只有一個正確答案；共15小題，每小題2分，共30分）1 數據結構是【】。A. 種數據類型B 數據的存儲結構C 一組性質相同的數據元素的集合D.相互之間存在一種或多種特定關系的數據元素的集合2. 線性表采用鏈式存儲時，結點的存儲地址【】。A.必須是不連續(xù)的B. 連續(xù)與否均可 C 必須是連續(xù)的 D 和頭結點的存儲地址相連續(xù)3. 若線性表最常用的操作是存取第 i個元素及其前驅元素的值，則采用【】存儲方式最節(jié)省時間。A單鏈表 B 雙向鏈表 C 單循環(huán)鏈表 D 順序表4. 設棧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. 為解決計算機主機與打印機之間速度不匹配問題，通常設置一個打印數據緩存區(qū)， 主機將要輸出的數據依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數據。該緩沖區(qū)的邏輯結構應該是【】。A 棧B 隊列 C 樹 D 圖6排序算法的穩(wěn)定性是指【】。A 經過排序之后，能使值相同的數據保持原順序中的相對位置不變B經過排序之后，能使值相同的數據保持原順序中的絕對位置不變C算法的排序性能與

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

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

5、 logn-115. 引入二叉線索樹的目的是【】。A加快查找結點的前驅或后繼的速度B為了能在二叉樹中方便的進行插入與刪除C. 為了能方便的找到雙親D .使二叉樹的遍歷結果唯一二、應用題（共5題，共計50分）1. 已知一棵二叉樹的中序遍歷結果為GDHBAEC,后序遍歷結果為 GHDBEIFCA3. 已知帶權圖的鄰接表如下所示，其中邊表結點的結構為:依此鄰接表：（1）寫出從頂點 C出發(fā)進行深度優(yōu)先搜索的遍歷序列；（2）寫出從頂點 C出發(fā)進行廣度度優(yōu)先搜索的遍歷序列；（3） 按照PRIM算法畫出從頂點 C出發(fā)求最小生成樹的過程。（15分）4. 已知某系統(tǒng)在通信聯(liá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，試畫出對 應的編碼Huffman樹（請按照左子樹根結點的權小于等于右子樹根結點的權的 次序構造），求每種字符的 Huffman編碼。（12分）5 .設哈希（Hash）表的地址范圍為 017,哈希函數為：H （ K）= K MOD 16。K為關鍵字，用線性探測法再散列法處理沖突，輸入關鍵字序列：（10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49）造出Hash表，試回答下列問題：（11分）（1）畫出哈希表的示意圖；（2）若查找關鍵字6

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

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

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