計算機學院數(shù)據(jù)結(jié)構(gòu)歷年試題

1、PAGE PAGE 3華南師范大學試卷（A卷） 考試科目： 數(shù)據(jù)結(jié)構(gòu) 考試日期：2003.1.16 成績： 系級班別：2001級本科 學生姓名： 學號： 一、選擇題（10分）1.在內(nèi)排序中,不論待排序記錄的初始狀態(tài)如何，其時間復雜性一樣的是( ). A插入排序B二分法插入排序 C快速排序D冒泡排序2.根據(jù)n個元素建立一棵二叉排序樹，其時間復雜度大致為（ ） A. O(n) B.O(nlogn) C.O(logn) D.O(n2)3設(shè)一個具有t個非零元素的m*n大小的稀疏矩陣采用順序存儲結(jié)構(gòu)（即三元組存儲結(jié)構(gòu)），其轉(zhuǎn)置矩陣的普通轉(zhuǎn)置算法的時間復雜度為（ ） A.O(m) B.O(n) C.O(n

2、*m) D.O(m*t) E.O(n*t)4. 在堆排序的過程中，需要對n個記錄建立初始堆。假設(shè)將這n個記錄存放于數(shù)組 A0.n-1中，則在建立初始堆時，最先進行堆調(diào)整的結(jié)點的編號是（ ）A.n div 2 B. n div 2 +1 C. n div 2-1 D. (n-1) div 25.下面算法的時間復雜度為（ ） function f ( n:integer):integer;begin if ( n=0) or ( n=1 ) then return 1 else return n*f(n-1);end. A. O(1) B.O(n) C.O(n2) D.O(n!)二、填空題（10分

3、）1.在堆排序的過程中，對n個記錄建立初始堆需要進行 次篩選運算，由初始堆到堆排序結(jié)束，需要對樹根結(jié)點進行 次篩選運算。2.假設(shè)一個循環(huán)隊列的元素存放于m1.max+1中，則判斷隊滿的條件為 。3.設(shè)A是一個線性表（a0,a1,.an），采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均沒插入一個元素需要移動的元素個數(shù)為 ；若元素插入在ai與ai+1之間（0in-1）的概率為(n-i)/(n*(n+1)/2),則平均每插入一個元素所要移動的元素個數(shù)是 。4.在散列表的查找算法中，平均查找長度與表的 無關(guān)，只與所選取的 、 、 有關(guān)。5通過取表頭HEAD運算和取表尾TAIL運算從廣義表L=(a,b),(

4、),(c,(d)中提取出 c 的表達式是。三、應用解答題（25分）1設(shè)有三對角矩陣A（n*n）,將其三條對角線（即三條對角線是指主對角線和與其相鄰的上下兩條對角線）上的元素逐行地存于數(shù)組B1.x中，使得Bk=aij，則: (1)x的值等于多少。 (2)試用i,j表示k的下標變換公式。 (3)若將該三條對角線上的元素存于數(shù)組C-1.1,1.n中，使得Cu,v=aij，試用i,j表示u,v下標變換的公式。2.選取哈希函數(shù)H(k)= (3k) mod 11。用線性探測開放定址法處理沖突。試在0 10的散列地址空間中對關(guān)鍵字序列（11，19，53，24，30，13，12，56）構(gòu)造哈希表。并分別求在等

5、概率情況下查找成功和不成功時的平均查找長度。3.在設(shè)計電話目錄管理系統(tǒng)時，什么樣的數(shù)據(jù)結(jié)構(gòu)最適合？為什么？4.已知樹的前序遍歷序列為：ABECFGH，后序遍歷序列為：EBFGCHA，試問能否構(gòu)造出唯一的樹？如果不可以則請說明原因。如果可以則請把該樹的樹形畫出來。四、算法填空題（15分）1.下面的程序段是輸出二叉樹的算法：將以二叉鏈式存儲結(jié)構(gòu)存儲的二叉樹以廣義表的形式輸出。struct btreenode struct btreenode *lchild; int data; struct btreenode *rchild;void printbtree(struct btreenode *b

6、t)if ( bt!=NULL) / 遞歸結(jié)束條件：二叉樹為空則結(jié)束遞歸，不空則做 cout ; if ( ) cout(; /輸出左括號 ；if ( ) coutrchild); / 輸出右子樹cout); /輸出右括號 五、算法設(shè)計題（40分）1.設(shè)計一個遞歸算法來將二叉樹的前序序列中倒數(shù)第k個結(jié)點輸出。假定二叉樹用二叉鏈表表示。要求算法的時間復雜度為O(k)。并說明你的算法達到了這個要求。2.設(shè)有單鏈表HL為： 請寫一個時間復雜度為O(n)的算法, 將HL改造為如下所示的單鏈表. 3.請設(shè)計一個遞歸算法：判別一棵二叉樹是否為二叉排序樹。要求算法的時間復雜度最佳。4.請設(shè)計一個遞歸算法：判別兩個廣義表是否