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

來(lái)源：時(shí)間：2007-06-06 14:35:35

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

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

結(jié)束

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

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

: 有用

25人覺(jué)得有用

閱讀全文

制服一区字幕精品|一二三区欧洲视频|国产无遮挡裸体女|好吊色91青青草|色欲TV亚洲国产|私人高清强伦中文字幕|国产在线自慰欧美综合图区|色欲av成人一区二区三区在线观看|九九九久久精品亚洲视频久久精品|亚洲无码中文在线

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

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