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

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

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

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

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

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

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

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

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