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

1、2007年山東齊魯工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題A卷一、填空題（每空 2 分，共 10 分）1、廣義表(a),a)的表頭為 （1） ，表尾為 （2） 。2、 已知二維數(shù)組 M，每個(gè)元素的存儲(chǔ)占 3 個(gè)單元，行下標(biāo) i 的范圍從 1 到 8，列下標(biāo) j 的范圍從 1 到 10，從首地址 SA 開始連續(xù)存放在存儲(chǔ)器內(nèi)，若按行優(yōu)先存儲(chǔ)，則元素 M85的地址是 （3） 。3、深度為 h（h1）的完全二叉樹至少有 （4）個(gè)結(jié)點(diǎn)。4、從有序表3,6,9,13,21,37,50,78,90中，用二分法檢索出 13 需要 （5） 次比較。二、簡(jiǎn)要回答下列問題（共 88 分）1、（5 分）有 3 個(gè)元素，其入棧次序?yàn)?/p>

2、：A，B，C，寫出各種可能的出棧次序。2、（5 分）樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？3、（5 分）快速排序是在所有情況下排序速度最快嗎？為什么？4、（5 分）如果通信字符 a,b,c,d 出現(xiàn)頻度分別為：7，5，2，4。請(qǐng)畫出哈夫曼樹并給出相應(yīng)的哈夫曼編碼。5、 已知一棵二叉樹如圖 1 所示，要求：(1) （6 分）寫出此二叉樹的先序、中序、后序遍歷序列；（6 分）對(duì)此二叉樹進(jìn)行中序線索化；（4 分）將此二叉樹變換為森林；（2 分）用先序遍歷該森林，寫出遍歷后的結(jié)點(diǎn)序列。6、 已知一無向圖如圖 2 所示，要求：（4 分）給出該圖的鄰接矩陣；（4 分）依據(jù)該圖的鄰接矩陣，寫出從頂點(diǎn) 1 出發(fā)

3、對(duì)圖進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的頂點(diǎn)序列；（6 分）寫出用克魯斯卡爾（Kruskal）算法構(gòu)造該圖的最小生成樹的過程。7、設(shè)哈希表長(zhǎng)度 13, 哈希函數(shù)為 H （ K ） =K MOD 13 ， 給定的鍵值序列為13,41,15,44,06,68,12,25,38,64,19,49，用鏈地址法處理沖突。要求：（12 分）構(gòu)造哈希表；（4 分）什么是同義詞？列出該哈希表中的同義詞；（2 分）求出在等概率情況下，查找成功的平均查找長(zhǎng)度。8、 給定一組關(guān)鍵字序列（52，70，33，65，24，56，48，92，86，37），要求：（10 分）根據(jù)該序列創(chuàng)建一棵二叉排序樹，畫出得到的二叉排序樹

4、。（4 分）寫出對(duì)該序列進(jìn)行快速排序的第一趟的結(jié)果。（4 分）將該序列調(diào)整為一個(gè)小頂堆，畫出得到的小頂堆。（注意事項(xiàng)：以下算法設(shè)計(jì)題建議采用類 C 語言書寫，并對(duì)主要數(shù)據(jù)類型給出聲明。所寫算法應(yīng)結(jié)構(gòu)清晰、簡(jiǎn)明易懂，加上必要的注釋）三、算法設(shè)計(jì)題（共 52 分）1、斐波那契數(shù)列 Fn 定義如下：F0=0,F1=1,Fn=Fn-1+Fn-2,n=2,3,。分別書寫：（6 分）求解 Fn 的遞歸算法；（8 分）求解 Fn 的非遞歸算法。2、（12 分）設(shè)有一個(gè)由正整數(shù)構(gòu)成的單鏈表 L(帶頭結(jié)點(diǎn))，編寫算法刪除 L 中值等于 x 的所有結(jié)點(diǎn)。3、（10 分）已知含有 n（n1）個(gè)整數(shù)的數(shù)組 A，編寫算法輸出 A 的前 k（k1） 個(gè)最大的元素，并分析算法的時(shí)間復(fù)雜度。4、（10 分）已知二叉樹 T 采用二叉鏈表表示，