東北大學2001年數(shù)據(jù)結(jié)構(gòu)考研試題

來源：時間：2007-06-06 14:35:35

東北大學
2001 年碩士學位研究生試題(f)
一．簡要回答下列問題：
1．在執(zhí)行某個排序算法的過程中，出現(xiàn)了排序關(guān)鍵字朝著最終排序相反方向的移動，從而認為該算法是不穩(wěn)定的。這種說法對么？為什么？
2．從一棵二叉排序樹中刪除兩個元素后，該二叉排序樹的形態(tài)是否與兩個元素的刪除次序有關(guān)？為什么？
3．如在內(nèi)存中存放一個完全二叉樹，在樹上只進行下面兩個操作： 1> 尋找某個結(jié)點的雙親； 2:> 尋找某個結(jié)點的的兒子；請問應(yīng)該用何種結(jié)構(gòu)來存儲二叉樹。
4．有字符串次序為 3*-y-a/y^2，利用棧，給出將次序改為3y-*ay^/-的操作步驟。（可用X代表掃描該字符串過程中順序去一個字符進棧的操作，用s代表從棧中取一個字符的出棧操作。例如:abc變?yōu)閎ca 的操作步驟為XXSXSS）.
5．寫出廣義表 B=(a,b) =(a,(b,c(d,e))), D=(a,B,C), E=((a,b),E) 的存儲結(jié)構(gòu)（任意一種存儲方法均可）
6．有n 個葉子結(jié)點的哈夫曼樹的結(jié)點總數(shù)是多少？
二設(shè)有一個正整數(shù)序列組成的單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試寫能實現(xiàn)下列功能的算法：（要求用最少的時間和最少的空間）
1：確定在序列中比正整數(shù)大的數(shù)有幾個（相同的數(shù)只計算一個，如（20，20，17，16，15，15，11，10 ，8，7，7，5，4））中比10大的數(shù)有5個）；
2：在單鏈表將比正整數(shù)小的數(shù)x小的數(shù)將按遞減次序排列；
3：將正整數(shù)x大的偶數(shù)從單鏈表刪除。
三設(shè)t是一個滿二叉數(shù)，編寫一個將t的先序序列轉(zhuǎn)換為后續(xù)序列的遞歸算法。
四解答下列問題：
1：畫出下列給出二叉數(shù)的后續(xù)線索二叉數(shù)；
2：寫出后序線索二叉數(shù)的非遞歸遍歷算法。

五再有向圖g中，如果r到g中的每個節(jié)點都有路徑可達，則稱結(jié)點r為
g的根結(jié)點，編寫一個算法完成下列功能：
1：建立有向圖的鄰接表存儲結(jié)構(gòu)；
2：判斷有向圖g是否有根，若有，則打印出所有的根結(jié)點的值。
六．對下面的關(guān)鍵字集（30，15，21，40，25，26，36，37）若查找表的裝添因子為0.8采用線性再散列方法解決沖突，做：1>設(shè)計哈希表函數(shù)： 2:>畫出哈希表； 3>計算查找成功和查找失敗的平均查找長度； 4>寫出哈希表中某個數(shù)據(jù)元素刪除的算法。

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責任；

②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。

: 有用

25人覺得有用

閱讀全文

奶昔直播官方版-奶昔直播直播视频在线观看免费版下载-奶昔直播安卓版本免费安装

東北大學2001年數(shù)據(jù)結(jié)構(gòu)考研試題

2019考研VIP資料免費領(lǐng)取