2005年山東齊魯工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題

1、2005年山東齊魯工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題一、填空（每空 2 分，共 10 分）1、廣義表（a），a）的表頭為 （1） ，表尾為（2） 。2、具有n（n>1）個(gè)結(jié)點(diǎn)的滿二叉樹，其非葉子結(jié)點(diǎn)數(shù)為 （3） 。3、從有序表3,6,9,13,21,37,50,78,90中，用二分法檢索出 37 需要 （4） 次比較。4、一棵m 階B樹中，每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)外）最少為 （5） 棵子樹。二、選擇題（每空 2 分，共 20 分）1、在有n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為 （1）。A不確定B2nC2n+1D2n­1 2、一個(gè)隊(duì)列的入對序列是 1 2 3 4 5，則隊(duì)列的輸出序列為 （2）

2、 。A5 4 3 2 1B1 2 3 4 5C4 3 5 1 2D4 5 3 2 13、 二維數(shù)組M 中，每個(gè)元素是占 6 個(gè)存儲(chǔ)單元，行下標(biāo) i 的范圍從 0 到 8，列下標(biāo)j 的范圍從 1 到 10，則 M 按行優(yōu)先存儲(chǔ)時(shí)元素 M85的起始地址與M 按列優(yōu)先存儲(chǔ)時(shí)元素 （3） 的起始地址相同。AM 85BM310CM58DM094、森林的先序遍歷序列等同于其對應(yīng)的二叉樹的 （4） 遍歷序列。A先序B中序C后序D層次5、在圖的廣度優(yōu)先遍歷中，需采用 （5）以存儲(chǔ)已被訪問過的頂點(diǎn)。A數(shù)組B鏈表C棧D隊(duì)列6、具有n 個(gè)頂點(diǎn)的有向圖最多有 （6）條邊。AnBn(n1)Cn(n+1)D n27、關(guān)鍵

3、路徑是指 AOE(Activity On Edge)網(wǎng)中 （7）。A. 最長的回路B. 最短的回路C.從源點(diǎn)到匯點(diǎn)(結(jié)束頂點(diǎn))的最長路徑D.從源點(diǎn)到匯點(diǎn)(結(jié)束頂點(diǎn))的最短路徑8、順序查找方法適合于存儲(chǔ)結(jié)構(gòu)是 （8）的線性表。A散列存儲(chǔ)B順序存儲(chǔ)或者鏈接存儲(chǔ) C壓縮存儲(chǔ)D索引存儲(chǔ)9、以下序列中不符合堆定義的是（9）。A(102，87，100，79，82，62) B(102，100，87，79，82，62) C(62，82，79，87，100，102) D(102，87，79，82，62，100)10、 在待排序列基本有序的前提下，效率最高的排序方法是 (10)。A.直接插入排序B.選擇排序C.快

4、速排序D.歸并排序三、簡答（共 40 分）1、（10 分）假設(shè)用于通訊的電文僅由 a,b,c,d,e,f 6 個(gè)字母組成，各字母在電文中出現(xiàn)的頻率分別為（2，3，5，7，11，4），試為這 6 個(gè)字母設(shè)計(jì)哈夫曼編碼。2、（10 分）給定關(guān)鍵字序列47，50，32，13，21，89，首先創(chuàng)建二叉排序樹，然后從二叉排序樹中依次刪除關(guān)鍵字值是 13、47 的結(jié)點(diǎn)。（要求畫出創(chuàng)建的二叉排序樹和依次刪除 13、47 結(jié)點(diǎn)后的二叉排序樹狀態(tài)）。3、（8 分）選取哈希函數(shù) H（key）=key MOD 11，用開放地址法的線性探測再散列方法處理沖突，其沖突后求下一地址的函數(shù)為：Hi=（H（key）+di）M

5、OD 14，其中di=1,2,3.。試在 013 的散列地址空間內(nèi)對關(guān)鍵字序列（03，38，61，84，49，14）造哈希表，并分別求找出 49、14 所需的比較次數(shù)。4、（12 分）給出一組關(guān)鍵字 T（12，2，16，30，8，28，4，10，20，6，18），寫出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。(1)直接插入排序(2)起泡排序(3)快速排序（選第一個(gè)記錄為樞軸記錄）四、（共 20 分）已知一棵二叉樹如右圖 1。1、 （8 分）寫出對此二叉樹分別進(jìn)行先序、中序、后序、圖 1層次遍歷后的結(jié)點(diǎn)序列2、（9 分）畫出此二叉樹的中序線索化樹3、（3 分）將此二叉樹轉(zhuǎn)化為森林五、（共 18

6、 分）已知一網(wǎng)右圖 2 所示。請給出：1、（4 分）該網(wǎng)的鄰接矩陣。2、（6 分）從頂點(diǎn) 1 出發(fā)對網(wǎng)進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列和廣度優(yōu)先生成樹。2、 （8 分）求出該網(wǎng)的一棵最小生成樹。圖2（注意事項(xiàng)：以下算法設(shè)計(jì)題建議采用類C 語言書寫，并對主要數(shù)據(jù)類型給出聲明）六、（算法設(shè)計(jì)題，共 42 分）1、（14 分）已知存儲(chǔ)整型元素的帶頭結(jié)點(diǎn)的單鏈表，L 是其頭指針。(1)設(shè)計(jì)算法輸出L 中值最小的元素。(2)設(shè)計(jì)算法輸出L 的表長2、（18 分）已知含有 n 個(gè)整型元素的線性表按遞增有序存放于數(shù)組 A100的前 n個(gè)位置上（n<90）。 (1)編寫算法求線性表中n 個(gè)元素的乘積。(2)編寫算法向線性表插