山東大學2004年數據結構考研試題

來源：時間：2007-06-06 14:34:22

2004年山東大學碩士研究生入學考試數據結構試題

一、簡答題：
1、10分（1）數據結構和數據類型的區別，一個好的數據結構類型有哪幾個標準？
（2）順序和鏈式存取的特點是什么，什么時候順序存取有優勢？
2、12分 g（m，n）= 0 (m=0,n>=0)
= g(m-1,2n) n (m>=0,n>=0)
寫出遞歸算法并畫出 g(5,2)的棧的變化。
3、8分求下列算法里@區域的時間執行頻度和整個算法最時間復雜度。
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)的單鏈表的存儲表示，做一下結構說明。
(2) 執行插入刪除運算得出a(x) b(x)的存儲表示，利用a(x)和b(x)原有的空間。
5、6分有中序線索2叉樹序列cbedahgijf,后續序列：cedbhjigfa,畫出前序、中序和后序的線索二叉樹。
6、6分樹的度為m，度為1的結點數為N1, 度為2的結點數為N2, 度為m的結點數為Nm,
求樹的葉子結點數。
7、8分無向圖G=（V，E），G的各頂點的度>=2，證明這個無向圖中一定含有回路。
8、10分求關鍵路徑。
9、8分平衡2叉樹中的插入元素調整平衡的過程。
10、8分，什么是哈希表？沖突可能與哪些因素有關？為什么？
11、8分有5000個無序列的元素，如果要快速選擇最大的10個元素，那么在快速、堆、歸并、基數、希爾排序中哪個最好，為什么？
12、10分 n個不同的英語單詞排序，長度均為m,n>>50,m<5,那種排序方式最佳？為什么？

二、算法設計題目：
1、8分寫折半查找（2分法）的遞歸算法
2、8分三叉堆（同去年的題目）
3、10分設計選舉人得票數，按得票數輸出，一張選票只能選一個被選舉人，一共有n個被選舉人，m張選票。
4、8分 P是中序線索2叉樹的非根接點，寫出不用棧刪除P的子樹的算法。
5、12分寫出2叉中序非遞歸的算法。

結束

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

②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。

: 有用

25人覺得有用

閱讀全文

山東大學2004年數據結構考研試題

2019考研VIP資料免費領取