|
2008年大連理工大學數據結構與離散數學考研試題
| 數據結構部分 一、選擇題 1、 線性表的 ———— 運算中，順序存儲結構比例鏈式存儲結構好。 A、 插入 B 、刪除 C 、按號查找 D 、按元素值查找 2、 此程序的復雜度為 ———— 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 、在待排數據已基本有序的情況下， ———— 效率最高。 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[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]) 二、問答題 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 個人，他們有相同的朋友數 |