數(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[i][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[i][j] B、(j=0 n-1)∑A[i][j] C、(i=0 n-1)∑A[i][j]+(j=0 n-1)∑A[i][j] D、(j=0 n-1)∑(A[i][j]+A[j][i])
二、問(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ě)算法）
三 、用類(lèi) 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ǔ)形式及其類(lèi)型定義。
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 ）判斷下式類(lèi)型（永真，可滿足式，永假）并解釋說(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ù)
你的位置：
中國(guó)研究生信息網(wǎng)-復(fù)習(xí)指導(dǎo)_歷年試題
減小字體
增大字體