大連理工2008計算機專業課真題完整版---《數據結構與離散數學》

aijiuyigezi123

從考研論壇上得到了很多幫助，但作出的貢獻卻很少，感覺有點慚愧，這次也做點貢獻。
今年參加了大工的考試，但卻從未想過要考上，因為基本沒準備什么，純粹是為了混點經驗。
大工的準考證還不錯，背面都是空白，考試的時候閑著也是閑著，于是就將試題偷偷的抄在了背面，于是就有了這份真題。
雖然說高校不再賣往年試題了，但總有人會弄到手的，因此就會產生新的不公平，因此我就將今年的試題免費送給大家參考參考。
但仔細想想，如果我將這套試題一份份的賣出去，自己也可以賺點錢，但考慮到大家考研都不容易，尤其是如果看到沒有專業課試題心理總會覺得不踏實，所以賺不賺錢都無所謂了，大家公平的去競爭才是最好的。
試題里面有可能還有點錯誤，還請大家指正。
如果明年的準考證還是這樣，希望還有人能將真題帶給大家。
摸到出題規律考高分也許是有點不好，但如果不公平，那就更不好了。
很少發帖，有點羅嗦，望見諒。
最后祝大家過年好！

aijiuyigezi123

數據結構部分

一、選擇題
1、        線性表的————運算中，順序存儲結構比例鏈式存儲結構好。
A、        插入   B、刪除   C、按號查找   D、按元素值查找
2、        此程序的復雜度為————
for(int i=0；i<m; i++)
   for(int j=0;j<n; j++)
     A[j]=i*j;
A 、O(m2)     B、  O(n2)  C、 O (m*n)  D、 O (m+n)
3、在待排數據已基本有序的情況下，————效率最高。
A、  直接選擇排序  B、  直接插入排序  C、  快速排序  D、  歸并排序
4、n個英文單詞，每個單詞長度基本相等，為m，當n>>50,m<5時，時間復雜度最佳的為————：
A、  快速排序  B、歸并排序  B、基數排序  B、直接插入排序
5、順序查找長度為n的順序表，查找成功的平均檢索長度為————：
A、n   B、n/2  B、(n-1)/2   D、(n+1)/2
6、一顆二叉樹，頭序序列為ABCDEFG，中序序列為CBDAEGF，后序為————
A、CDBGFEA  B、CDBFGEA  C、CDBAGFE   D、BCDAGFE
7、一顆度為3的樹，度為3的節點為三個，度為2的節點為1個，度為1的節點1個，度為0的節點————個。
  A、6   B、7  C、8  D、9
8、m階B—樹中，某一節點插入一個新關鍵字引起破裂，則該節點原有關鍵字————個。
  A、|—m/2—|      B、|—m/2—|-1    C、m  D、m-1   E、|—m/2—|  F、|—m/2—|-1
9、兩個長度為n的遞增有序表，合并成一個長度為2n的遞增有序表，最少需要進行關鍵字比較————次。
  A、1  B、n-1  C、n  D、2n
10、有向圖G, n個頂點，鄰接矩陣存儲于二維數組中，頂點i的度為————。
   A、(i=0 n-1)∑A[j]   B、(j=0 n-1)∑A[j]   C、(i=0 n-1)∑A[j]+(j=0 n-1)∑A[j]   D、(j=0 n-1)∑(A[j]+A[j])
二、問答題
1、        （6）n階對稱陣（aij）n×n，采用壓縮存儲存放于一維數組F[m]中，從F[0]開始存儲，給出矩陣的壓縮存儲方式及任一矩陣元素aij（0<=i,j<=n-1）的地址計算公式，并求算m。
2、        （5）順序隊列如何解決假溢出問題。
3、        （8）已知一組關鍵字（10，26，14，25，17，36，37，44，27，34，60）設哈希函數H（x）=x%13，表長m=13，請寫出用線性探測法處理沖突構造所得的哈希表。并求出在等概率情況下，查找成功時的平均檢索長度。
4、        （6）給定一個由n個關鍵字不同的記錄構成的序列，你能否用比2n-3少的比較次數找出n個元素中的最大值和最小值？如果有，請描述你的方法。最快需要多少次比較？（無需寫算法）
三  、用類C語言完成設計：
1、        （15）什么是堆？設計算法判定給定的存于數組r[]中的n個數據是否為堆。
2、        （15）設u、v是有向圖的兩個頂點，設計算法判讀有向圖中是否存在從頂點u到v的長度為k的簡單路徑。要求給出圖的存儲形式及其類型定義。
3、        （10）設二叉樹以二叉鏈表形式存放。一顆二叉樹的繁茂程度定義為各層節點數的最大值與樹的高度的乘積。試設計一個高效算法，求二叉樹的繁茂程度。




離散數學部分

1、        （10）求出下列公式的主析取范式，再由主析取范式求出主合取范式：
（（pVq）∧(p→q)）>(q→p)
2、        （8）判斷下式類型（永真，可滿足式，永假）并解釋說明：
（ " x）（ $y）F(x，y)( $ x)( "y)F(x,y)   
3、        （10）符號化下列命題，并使用推理規則證明：
每個領導小組成員都是干部并且是專家，有些成員是老同志，所以有些成員是老干部。
4、        （9）求關系R的自反、對稱和傳遞閉包，并畫出相應的關系圖。
R={<1,2><2,1><2,2><2,3><4,3>}
5、        （10）設f和g都是<G1,*>到<G2，O×>的群同態，且H1={x|x ∈G1∧f(x)=g(x)}
試證<H1,*>是<G1,*>的子群
6、        （10）群<G,*>中子群<H,*>的左陪集關系C HL={<a,b>|a,b∈G∧b -1 *a∈H}是G中的等價關系。
7、        （10）已知一顆無向樹T有三個3度節點，一個2度節點，其余的都是1度節點。
1）        T中有幾個1度節點？給出計算過程。
2）        試畫出兩棵滿足上述度數要求的非同構的無向樹。
8、（8）證明：在至少有2個人的人群中，至少有2個人，他們有相同的朋友數。

aijiuyigezi123

這個顯示效果太差了，我還是附上一個Word格式的吧

[ 本帖最后由 aijiuyigezi123 于 2008-1-20 22:53 編輯 ]

shabbylee

好人，謝謝你，真的

zhenghu1226

呵呵，你倒挺有意思的，不會做題目倒也不著急，還索性把題目抄下來與眾研友分享，境界甚高吶！當年我也只是憑記憶把幾個算法的大概描述傳了上來，比起你來，不值一提啊！佩服

telnetor

算法的題啊。。我全暈了。。。傷心中……無緣了！！

zhouheng1212

數據結構部分

一、選擇題
1、 線性表的 ———— 運算中，順序存儲結構比例鏈式存儲結構好。
A、 插入 B 、刪除 C 、按號查找 D 、按元素值查找
2、 此程序的復雜度為 ————
for(int i=0 ; i<m; i++)
for(int j=0;j<n; j++)
A[j]=i*j;
A 、 O(m2) B 、 O(n2) C 、 O (m*n) D 、 O (m+n)
3 、在待排數據已基本有序的情況下， ———— 效率最高。
A 、 直接選擇排序 B 、 直接插入排序 C 、 快速排序 D 、 歸并排序
4 、 n 個英文單詞，每個單詞長度基本相等，為 m ，當 n>>50,m<5 時，時間復雜度最佳的為 ———— ：
A 、 快速排序 B 、歸并排序 B 、基數排序 B 、直接插入排序
5 、順序查找長度為 n 的順序表，查找成功的平均檢索長度為 ———— ：
A 、 n    B 、 n/2      C、 (n-1)/2          D 、 (n+1)/2
6 、一顆二叉樹，頭序序列為 ABCDEFG ，中序序列為 CBDAEGF ，后序為 ————
A 、 CDBGFEA         B 、 CDBFGEA         C 、 CDBAGFE          D 、 BCDAGFE
7 、一顆度為 3 的樹，度為 3 的節點為三個，度為 2 的節點為 1 個，度為 1 的節點 1 個，度為 0 的節點 ———
— 個。
A 、 6 B 、 7 C 、 8 D 、 9
8 、 m 階 B— 樹中，某一節點插入一個新關鍵字引起破裂，則該節點原有關鍵字 ———— 個。
A、|—m/2—|      B、|—m/2—|-1    C、m  D、m-1   E、|—m/2—|  F、|—m/2—|-1
9 、兩個長度為 n 的遞增有序表，合并成一個長度為 2n 的遞增有序表，最少需要進行關鍵字比較 ———— 次。
A 、 1 B 、 n-1 C 、 n D 、 2n
10 、有向圖 G, n 個頂點，鄰接矩陣存儲于二維數組中，頂點 i 的度為 ———— 。
A、(i=0 n-1)∑A[j]   B、(j=0 n-1)∑A[j]   C、(i=0 n-1)∑A[j]+(j=0 n-1)∑A[j]   D、(j=0 n-1)
∑(A[j]+A[j])
二、問答題
1、 （ 6 ） n 階對稱陣（ aij ） n × n ，采用壓縮存儲存放于一維數組 F[m] 中，從 F[0] 開始存儲，給出矩陣
的壓縮存儲方式及任一矩陣元素 aij （ 0<=i,j<=n-1 ）的地址計算公式，并求算 m 。
2、 （ 5 ）順序隊列如何解決假溢出問題。
3、 （ 8 ）已知一組關鍵字（ 10 ， 26 ， 14 ， 25 ， 17 ， 36 ， 37 ， 44 ， 27 ， 34 ， 60 ）設哈希函數
H （ x ） =x%13 ，表長 m=13 ，請寫出用線性探測法處理沖突構造所得的哈希表。并求出在等概率情況下，查找成功
時的平均檢索長度。
4、 （ 6 ）給定一個由 n 個關鍵字不同的記錄構成的序列，你能否用比 2n-3 少的比較次數找出 n 個元素中的最大
值和最小值？如果有，請描述你的方法。最快需要多少次比較？（無需寫算法）
三 、用類 C 語言完成設計：
1、 （ 15 ）什么是堆？設計算法判定給定的存于數組 r[] 中的 n 個數據是否為堆。
2、 （ 15 ）設 u 、 v 是有向圖的兩個頂點，設計算法判讀有向圖中是否存在從頂點 u 到 v 的長度為 k 的簡單路
徑。要求給出圖的存儲形式及其類型定義。
3、 （ 10 ）設二叉樹以二叉鏈表形式存放。一顆二叉樹的繁茂程度定義為各層節點數的最大值與樹的高度的乘積。試
設計一個高效算法，求二叉樹的繁茂程度。

離散數學部分

1、 （ 10 ）求出下列公式的主析取范式，再由主析取范式求出主合取范式：
（（pVq）∧(p→q)）&szlig;>(q→p)
2、 （ 8 ）判斷下式類型（永真，可滿足式，永假）并解釋說明：
（ " x）（ $y）F(x，y)à( $ x)( "y)F(x,y)
3、 （ 10 ）符號化下列命題，并使用]
推理規則證明：

每個領導小組成員都是干部并且是專家，有些成員是老同志，所以有些成員是老干部。
4、 （ 9 ）求關系 R 的自反、對稱和傳遞閉包，并畫出相應的關系圖。
R={<1,2><2,1><2,2><2,3><4,3>}
5、（10）設f和g都是<G1,*>到<G2，O×>的群同態，且H1={x|x ∈G1∧f(x)=g(x)}
試證<H1,*>是<G1,*>的子群
6、  （ 10 ）群<G,*>中子群<H,*>的左陪集關系C HL={<a,b>|a,b∈G∧b -1 *a∈H}是G中的等價關系。
7、 （ 10 ）已知一顆無向樹 T 有三個 3 度節點，一個 2 度節點，其余的都是 1 度節點。
1） T 中有幾個 1 度節點？給出計算過程。
2） 試畫出兩棵滿足上述度數要求的非同構的無向樹。
8 、（ 8 ）證明：在至少有 2 個人的人群中，至少有 2 個人，他們有相同的朋友數。

wuzoujing

牛哥！！！！！厲害！！

tanzhipeng

算法的題嚴習題集都出現過，每年都這樣，所以今后的考研人真要注意嚴習題的重要性了。

BAPER_DUT

佩服你的記憶力 我考研后啥也沒記住