山東大學(xué)2004年數(shù)據(jù)結(jié)構(gòu)考研試題
來源：
時(shí)間：2007-06-06 14:34:22
2004年 山東大學(xué)碩士研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題
一、簡答題：
1、10分 （1）數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的區(qū)別，一個(gè)好的數(shù)據(jù)結(jié)構(gòu)類型有哪幾個(gè)標(biāo)準(zhǔn)？
（2）順序和鏈?zhǔn)酱嫒〉奶攸c(diǎn)是什么，什么時(shí)候順序存取有優(yōu)勢(shì)？
2、12分 g（m，n）= 0 (m=0,n>=0)
= g(m-1,2n) n (m>=0,n>=0)
寫出遞歸算法并畫出 g(5,2)的棧的變化。
3、8分 求下列算法里@區(qū)域的 時(shí)間執(zhí)行頻度和整個(gè)算法最時(shí)間復(fù)雜度。
X=0,y=0;
For (i-1;i ;i<=n) {
If odd(i)
@{ for(j=i;j ;j<=n) x ;
For(j=i;j ;j<=i) y ; }
}
4、10分 a(x)=7 3x 9x^8 5x^17 b(x)=8x 22x^7-9x^8
(1) 畫出a(x)和b(x)的單鏈表的存儲(chǔ)表示，做一下結(jié)構(gòu)說明。
(2) 執(zhí)行插入刪除運(yùn)算得出a(x) b(x)的存儲(chǔ)表示，利用a(x)和b(x)原有的空間。
5、6分 有中序線索2叉樹序列cbedahgijf,后續(xù)序列：cedbhjigfa,畫出前序、中序和后序的線索二叉樹。
6、6分 樹的度為m，度為1的結(jié)點(diǎn)數(shù)為N1, 度為2的結(jié)點(diǎn)數(shù)為N2, 度為m的結(jié)點(diǎn)數(shù)為Nm,
求樹的葉子結(jié)點(diǎn)數(shù)。
7、8分 無向圖G=（V，E），G的各頂點(diǎn)的度>=2，證明這個(gè)無向圖中一定含有回路。
8、10分 求關(guān)鍵路徑。
9、8分 平衡2叉樹中的插入元素調(diào)整平衡的過程。
10、8分，什么是哈希表？沖突可能與哪些因素有關(guān)？為什么？
11、8分 有5000個(gè)無序列的元素，如果要快速選擇最大的10個(gè)元素，那么在快速、堆、歸并、基數(shù)、希爾排序中哪個(gè)最好，為什么？
12、10分 n個(gè)不同的英語單詞排序，長度均為m,n>>50,m<5,那種排序方式最佳？為什么？
二、算法設(shè)計(jì)題目：
1、8分 寫折半查找（2分法）的遞歸算法
2、8分 三叉堆（同去年的題目）
3、10分 設(shè)計(jì)選舉人得票數(shù)，按得票數(shù)輸出，一張選票只能選一個(gè)被選舉人，一共有n個(gè)被選舉人，m張選票。
4、8分 P是中序線索2叉樹的非根接點(diǎn)，寫出不用棧刪除P的子樹的算法。
5、12分 寫出2叉中序非遞歸的算法。
結(jié)束
特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；
②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系我們溝通解決。
閱讀全文
招生服務(wù)平臺(tái)始創(chuàng)于1999年
打開微信掃一掃，關(guān)注育路教育官方微信
