(論文)東北大學(xué)2000年數(shù)據(jù)結(jié)構(gòu)試題

東北大學(xué)2000年數(shù)據(jù)結(jié)構(gòu)試題 1 （20分） 簡要回答下列問題 （注意：請將答案寫在答題紙上，并注明題號） （3分） 內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢。 （5分） 假設(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（哈夫曼）編碼。 （4分） 一棵共有n個結(jié)點的樹，其中所有分枝結(jié)點的度均為k，求該樹中葉子結(jié)點的子數(shù)。 （4分） 圖1表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的代價，如何選擇能溝通每個城市且總代價最省的n-1條線路，畫出所有可能的選擇。（4分） 在起泡（汽泡）排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動，試舉例說明之?？焖倥判蜻^程中有沒有這種現(xiàn)象？ 2 （15分） 設(shè)有一個由正整數(shù)組成的無序（向后）單鏈表，編寫完成下列功能的算法： 找出最小值結(jié)點，且打印該數(shù)值； 若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換； 若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除； 3 （14分） 解答下列問題： (4分） 將算術(shù)表達式 (a+b)+c*(d+e)+f)*(g+h) 轉(zhuǎn)化為二叉樹； (10分） 假設(shè)一個僅包含二元運算符的算術(shù)表達式以二叉鏈表形式存儲在二叉樹BT中，寫出計算該算術(shù)表達式值的算法。 4（21） 解答下列問題： （5分） 畫出有向圖的十字鏈表存儲結(jié)構(gòu)中頭結(jié)點和表結(jié)點的結(jié)點結(jié)構(gòu)。 (4分） 下面哪一個方法可以判斷出一個有向圖中是否有環(huán)（回路）？ (1)深度優(yōu)先遍歷 (2)拓樸排序 (3)求最短路徑 (4)求關(guān)鍵路徑 (12分） 假設(shè)一個有向圖g已經(jīng)以十字鏈表形式存儲在內(nèi)中，試寫一個判斷該有向圖中是否有環(huán)（回路）的算法。 5（15分） 寫出刪除二叉排序樹bt中值為x的結(jié)點的算法（二叉排序樹以二叉鏈表形式存儲，刪除后仍然保持二叉排序性質(zhì)）。 6（15分） 設(shè)有大小不等的n個數(shù)據(jù)組（n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi)，每個數(shù)據(jù)占一個存儲單元，數(shù)據(jù)組的首地址由數(shù)組s給出（如下圖所示），試編寫將新數(shù)據(jù)