東北大學(xué)1999數(shù)據(jù)結(jié)構(gòu)考研試題
來源：
時間：2007-06-06 14:35:38
1999年考研試題
一、（27分）回答下列各題：
1．已知一棵滿二叉樹的結(jié)點個數(shù)為2040之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？（3分）
2．設(shè)有五對角矩陣A=(aij)20*20，按特殊矩陣壓縮存儲的方式將其五條對角線上的元素存于數(shù)組[-10：m]中，計算元素A[15，16]的存儲位置。（4分）
3．以至一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），用鏈地址法解決沖突。假設(shè)裝填因子a=0.75散列函數(shù)的形式為H（K）=K MOD P，回答下列問題：
（1）、構(gòu)造出散列函數(shù)；（3分）
（2）、計算出等概率情況下查找成功的平均查找長度；（3分）
（3）、計算出等概率情況下查找失敗的平均查找長度；（3分）
4、判別一下序列是否為堆，若不是，則把他調(diào)整為堆。
（1）（100，86，48，73，35，39，42，57，66，21）（4分）
（2）（12，70，33，65，24，56，48，92，86，33）（4分）
5、設(shè)有1000個無序的元素，希望用最大的速度挑選出其中前十個最大的元素，在以下的方法中采用哪一種最好？為什么？（3分）
（快速排序，歸并排序，堆排序，基數(shù)排序，shell排序）
二、（10分）兩個正數(shù)序列A=a1,a2,a3,…..am和B=b1,b2,b3,…bn已經(jīng)存入兩個單鏈表中，設(shè)計一個算法，判別序列B是否是序列A的子序列。
三、（12分）編寫算法判別二叉樹是否為平衡二叉樹。
四、（13分）編寫一算法，利用葉子結(jié)點中的空指針域?qū)⑺腥~子結(jié)點鏈接為一個帶頭結(jié)點的雙鏈表，算法返回頭結(jié)點的地址。
五、（18分）對于一個使用鄰接表存儲的有向圖G，可以利用深度優(yōu)先遍歷方法，對該圖中結(jié)點進行拓撲排序。其基本思想是：在遍歷過程中，每訪問一個頂點，就將其鄰接到的頂點的入度減一，并對其未訪問的、入度為0的鄰接到的頂點進行遞歸。
（1）給出完成上述功能的圖的鄰接表定義（結(jié)構(gòu)）：（4分）
（2）定義在算法中使用的全局輔助數(shù)組。（4分）
（3）寫出在遍歷圖的同時進行拓撲排序的算法：（10分）
六、（20分）回答下列問題：
（1）、試找出滿足下列條件的二叉樹（4分）
1》先序序列與后序序列相同 2》中序序列與后序序列相同
3》先序序列與中序序列相同 4》中序序列與層次遍歷序列相同
（2）、已知一棵二叉樹的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，畫出這棵二叉樹。（4分）
（3）已知一棵二叉樹的中序序列和后序序列，寫一個建立該二叉樹的二叉鏈表存儲結(jié)構(gòu)的算法。（12分）
結(jié)束
特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；
②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。
閱讀全文
招生服務(wù)平臺始創(chuàng)于1999年
打開微信掃一掃，關(guān)注育路教育官方微信
