大連理工2008計(jì)算機(jī)專業(yè)課真題完整版---《數(shù)據(jù)結(jié)構(gòu)與離散數(shù)學(xué)》

aijiuyigezi123

從考研論壇上得到了很多幫助，但作出的貢獻(xiàn)卻很少，感覺(jué)有點(diǎn)慚愧，這次也做點(diǎn)貢獻(xiàn)。
今年參加了大工的考試，但卻從未想過(guò)要考上，因?yàn)榛緵](méi)準(zhǔn)備什么，純粹是為了混點(diǎn)經(jīng)驗(yàn)。
大工的準(zhǔn)考證還不錯(cuò)，背面都是空白，考試的時(shí)候閑著也是閑著，于是就將試題偷偷的抄在了背面，于是就有了這份真題。
雖然說(shuō)高校不再賣往年試題了，但總有人會(huì)弄到手的，因此就會(huì)產(chǎn)生新的不公平，因此我就將今年的試題免費(fèi)送給大家參考參考。
但仔細(xì)想想，如果我將這套試題一份份的賣出去，自己也可以賺點(diǎn)錢，但考慮到大家考研都不容易，尤其是如果看到?jīng)]有專業(yè)課試題心理總會(huì)覺(jué)得不踏實(shí)，所以賺不賺錢都無(wú)所謂了，大家公平的去競(jìng)爭(zhēng)才是最好的。
試題里面有可能還有點(diǎn)錯(cuò)誤，還請(qǐng)大家指正。
如果明年的準(zhǔn)考證還是這樣，希望還有人能將真題帶給大家。
摸到出題規(guī)律考高分也許是有點(diǎn)不好，但如果不公平，那就更不好了。
很少發(fā)帖，有點(diǎn)羅嗦，望見(jiàn)諒。
最后祝大家過(guò)年好！

aijiuyigezi123

數(shù)據(jù)結(jié)構(gòu)部分

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




離散數(shù)學(xué)部分

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

aijiuyigezi123

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

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

shabbylee

好人，謝謝你，真的

zhenghu1226

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

telnetor

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

zhouheng1212

數(shù)據(jù)結(jié)構(gòu)部分

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

離散數(shù)學(xué)部分

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

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

wuzoujing

牛哥！?。。?！厲害??！

tanzhipeng

算法的題嚴(yán)習(xí)題集都出現(xiàn)過(guò)，每年都這樣，所以今后的考研人真要注意嚴(yán)習(xí)題的重要性了。

BAPER_DUT

佩服你的記憶力 我考研后啥也沒(méi)記住