1、 院（系） 班級 姓名 學號 裝訂線 專業(yè)數(shù)據(jù)結構（C語言描述）期末試卷（ 學年 第 學期）題號總分得分一、填空(10分)1、一個m階B-樹中，每個結點最少有( ceil(m/2) )個兒子結點,m階B+樹中每個結點(除根外)最多有( m )個兒子結點.2、n(n0)個結點構成的二叉樹，葉結點最多有( floor(n+1)/2) )個，最少有( 1 )個。若二叉樹有m個葉結點，則度為2的結點有( m-1 )個。3、順序查找方法適用于存儲結構為( 順序表和線性鏈表 )的線性表，使用折半查找方法的條件是(查找表為順序存貯的有序表 )4、廣義表A=( )，(a，(b，c)，d)的表尾Gettail(

2、A)為( (a,(b,c),d) )5、直接插入排序，起泡排序和快速排序三種方法中，( 快速排序 )所需的平均執(zhí)行時間最??；( 快速排序 )所需附加空間最大。二、選擇(10分)1、倒排文件的主要優(yōu)點是：( C )A、便于進行插入和刪除 B、便于進行文件的合并C、能大大提高基于非主關鍵字數(shù)據(jù)項的查找速度 D、易于針對主關鍵字的逆向檢索2 下面程序段的時間復雜性為( C )y=0;while(n=(y+1)*(y+1) y+;A、O(n) B、O(n2) C、 O(sqrt(n) D、 O(1)3、若從二叉樹的任一結點出發(fā)到根的路徑上所經過的結點序列按其關鍵字有序，則該二叉樹是( C )A、二叉排

3、序樹 B、哈夫曼樹 C、堆 D、AVL樹4、棧和隊列都是（ B ）A、順序存儲的線性結構 B、限制存取點的線性結構C、鏈式存儲的線性結構 D、限制存取點的非線性結構5、用順序查找方法查找長度為n的線性表時，在等概率情況下的平均查找長度為（ D ）A、n B、n/2 C、(n-1)/2 D、(n+1)/2三、簡答（30分）1、已知一棵二叉樹的前序掃描序列和中序掃描序列分別為ABCDEFGHIJ和BCDAFEHJIG，試給出該二叉樹的后序序列并繪出該二叉樹對應的森林。解：后序序列為：DCBFJIHGEA2、若對序列（7，3，1，8，6，2，4，5）按從小到大排序，請寫出起泡排序的第一趟結果和堆排序

4、的初始堆。解：冒泡：3 1 7 6 2 4 5 8堆：8 7 4 5 6 2 1 33、某通訊系統(tǒng)只可能有A、B、C、D、E、F 6種字符，其出現(xiàn)的概率分別是0.1、0.4、0.04、0.16、0.19、 0.11，試畫出相應的哈夫曼樹，并設計哈夫曼編碼。解：編碼：A:1011 B:0 C:1010 D:110 E:111 F:1004、在二叉平衡檢索樹（AVL樹）的調整中，將最靠近新插入點的不平衡結點調整平衡后，樹中是否還會有不平衡結點？為什么？解：不會再有不平衡點。因為插入結點發(fā)生不平衡現(xiàn)象后，會改變以“靠近新插入點的不平衡結點”為根的子樹（即最小不平橫樹）的高度加1，經過調整后使最小不平

5、衡樹的整體高度又恢復到原來的值，所以不會對原平衡樹的其他部分造成危害，因此不會再有不平衡點。5、指定Hash函數(shù)H(k)=3*k mod 11及線性探測開地址法處理沖突，試在010的散列空間中對關鍵字序列（22，41，53，46，30，13，01，67）構造Hash表，并求在等查找概率下查找成功的平均查找長度。解：插入元素后的分布情況：0123456789102241300153461367ASL = (1+1+1+1+2+2+2+6)/8=2.0四、（10分）下圖是帶權的有向圖G的鄰接矩陣表示，請給出：1、其鄰接表存儲結構2、按Floyd算法求所有頂點對之間最短距離的矩陣變化過程。 V1 V

6、2 V3 V4V1| 0 1 4V2|092V3| 3 5 0 8V4| 6 0解：Floyd算法執(zhí)行過程中矩陣的變化情況為（從左到右）：0 1 4 0 9 23 4 0 7 6 00 1 10 3 0 9 23 4 0 6 6 00 1 10 312 0 9 23 4 0 69 10 6 00 1 9 311 0 8 23 4 0 69 10 6 0五、（12分） 設雙鏈表結點結構為 llink data rlink，請設計算法將其中P所指結點與其rlink所指結點位置互換的算法。解： typedef struct DLNode ElemType data; struct DLNode *l

7、link,*rlink;DLNode,*DLinkList;/思想：將P-rlink先從鏈表中刪除掉，然后再插入到P前Status SwapANode(DLNode *&P) /結點存在嗎? if(!P | !(P-rlink)return ERROR; q = P-rlink; /刪除q結點 if(!q-rlink) P-rlink = NULL; else P-rlink = q-rlink; q-rlink-llink = P; /將q結點插入到P結點前面 if(!P-llink) q-llink = NULL; q-rlink = P; P-llink = q; else q-llin

8、k = P-llink; q-rlink = P; P-llink-rlink = q; P-llink = q; return OK;六、（13分） 若有一棵二叉樹的存儲結構為二叉鏈表，T指向根結點，請寫出一個非遞歸算法判定其是否為二叉排序數(shù)。解：解法一：#define TRUE 1#define FALSE 0typedef int BOOL;typedef struct BTreeNode ElemType data; struct BTreeNode *lchild,*rchild;BTreeNode,*BTree;/我是將教材P130的中序非遞歸遍歷方法改的/注釋沒寫，大家看書上的吧

9、BOOL IsBST(BTree T) if(!T) return TRUE; InitStack(S); x = T-data; Push(S,T); while(!StackEmpty(S) while(GetTop(S,p) & p) Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p); if(x p-data) return FALSE; x = p-data; Push(S,p-rchild); / if / while return TRUE;另解：/我的另外一個解法,根據(jù)longeli的思想/Author: Ritchie

10、/ Date: 2002-10-12typedef int ElemType;typedef struct BiTreeNode ElemType data; struct BTreeNode *lchild,*rchild;BiTreeNode,*BiTree;/功能：判斷二叉樹T是否為二叉排序樹,如果是返回TRUE,否則返回 FALSE/思想：判斷T中的結點是否符合要求,按層序進行判斷,一旦不符合就返回Status IsBST(BiTree T) if (!T) return TRUE; /空樹是BST InitQueue(Q); EnQueue(Q,T); while(!QueueEmp

11、ty(Q) DeQueue(Q,t); /左右孩子先入隊 if(t-lchild) EnQueue(Q,t-lchild); if(t-rchild) EnQueue(Q,t-rchild); if(t-lchild & t-lchild) / 左右子樹不為空且不滿足BST的條件，返回FALSE if(t-lchild-data=t-data)|(t-rchild-datadata) return FALSE; else if (t-lchild & (t-lchild-data = t-data) /右子樹為空的情況 return FALSE; else if(t-rchild & (t-r

12、child-data data) /左子樹為空的情況 return FALSE; DestroyQueue(Q); return TRUE;用遞歸的方式做也有兩三種做法，這兒就不列舉了。七、（15分） 下表列出了某工序之間的優(yōu)先關系和各工序所需時間，要求：（1）畫出AOE網（2）列出各事件的最早、最晚發(fā)生時間（3）找出該AOE網中的關鍵路徑，并回答完成該工程所需要的最短時間。工序代號所需時間先驅工序工序代號所需時間先驅工序A15無H15G、IB10無I120EC50A、BJ60ID8BK15F、IE15C、DL30H、J、KF40BM20LG300E解：(1) AOE圖如下(需要添加虛線才可以

13、畫出圖，我就是在這兒被迷惑住的，第一次看到這樣的題目)（2）各事件的最早最遲發(fā)生時間:事件編號1234567891011ve(i)01510655080200380395425445vl(i)015576538080335380395425445(3)通過上表不用求出活動的最早最遲開始時間就可以看出關鍵路徑為：1，2，4，6，8，9，10，11完成工程所需的最短時間為：4451. 算法的計算量的大小稱為計算的（ ）?！颈本┼]電大學2000 二、3 （20/8分）】A效率 B. 復雜性 C. 現(xiàn)實性 D. 難度2. 算法的時間復雜度取決于（ ）【中科院計算所 1998 二、1 （2分）】A問題的

14、規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計算機算法指的是（1），它必須具備（2） 這三個特性。(1) A計算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調度方法(2) A可執(zhí)行性、可移植性、可擴充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 【南京理工大學 1999 一、1（2分） 【武漢交通科技大學 1996 一、1（ 4分）】4一個算法應該是（ ）。【中山大學 1998 二、1（2分）】A程序 B問題求解步驟的描述 C要滿足五個基本特性 DA和C. 5. 下面關于算法說法錯誤的是（ ）【南京理工大學 2000 一、1（1.5分

15、）】A算法最終必須由計算機程序實現(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的1下述哪一條是順序存儲結構的優(yōu)點？（ ）【北方交通大學 2001 一、4（2分）】A存儲密度大 B插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結構的存儲表示2下面關于線性表的敘述中，錯誤的是哪一個？（ ）【北方交通大學 2001 一、14（2分）】A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線

16、性表是具有n個（ ）的有限序列（n0）。 【清華大學 1998 一、4（2分）】A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項 E信息項4若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。【哈爾濱工業(yè)大學 2001 二、1（2分）】A順序表 B雙鏈表 C帶頭結點的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間?！灸祥_大學 2000 一、3】A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，

17、則選用( )最節(jié)省時間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結點的雙循環(huán)鏈表【合肥工業(yè)大學 2000 一、1（2分）】7若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用（ ）存儲方式最節(jié)省運算時間?！颈本├砉ご髮W 2000 一、1（2分）】A單鏈表 B雙鏈表 C 單循環(huán)鏈表 D帶頭結點的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ ）. 【北京理工大學 2001 六、2（2分）】A 內存地址 B數(shù)組下標 C下一元素地址 D左、右孩子地址9. 鏈表不具有的特點是（ ） 【福州大學 1998 一、8 (2分)】A插入、刪除不需要移動元素 B可隨

18、機訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比10. 下面的敘述不正確的是（ ）【南京理工大學 1996 一、10（2分）】A線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比B. 線性表在鏈式存儲時，查找第i個元素的時間同i的值無關C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關1. 對于棧操作數(shù)據(jù)的原則是（ ）?！厩鄭u大學 2001 五、2（2分）】A. 先進先出 B. 后進先出 C. 后進后出 D. 不分順序2. 在作進棧運算時,應先判別棧是否( ),在作退棧運算時應先判別棧是否( )。當棧中

19、元素為進棧運算時發(fā)生上溢,則說明該棧的最大容量為( )。為了增加內存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內存空間時,應將兩棧的 ( )分別設在這片內存空間的兩端,這樣,當( )時，才產生上溢。 , : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長度 B. 深度 C. 棧頂 D. 棧底: A. 兩個棧的棧頂同時到達?？臻g的中心點.B. 其中一個棧的棧頂?shù)竭_?？臻g的中心點.C. 兩個棧的棧頂在?？臻g的某一位置相遇.D. 兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底.【上海海運學院 1997 二、1（5分）】【上

20、海海運學院 1999 二、1（5分）】3. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i0）個(（2）)的集合T1，T2， ，m，每個集合又都是樹，此點T稱為Ti的父結點，Ti稱為T的子結點（1im）。一個結點的子結點個數(shù)稱為該結點的( （3） )。二叉樹與樹是兩個不同的概念，二叉樹也是點的有限集合，它(（4）)根結點?？梢园褬涞母Y點的層數(shù)定義為1，其他結點的層數(shù)等于其父結點所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結點數(shù)小于2的結點中的任意兩個，它們所在的層數(shù)分別為Ki和Kj，當關系式Ki-Kj1一定成立時，則稱T為一棵（(5)）。供選擇的答案：（1）

21、(4) A. 有0個或1個 B. 有0個或多個 C. 有且只有一個 D. 有1個或1個以上（2） A. 互不相交 B.允許相交 C.允許葉結點相交 D.允許樹枝結點相交（3） A. 權 B.維數(shù) C.次數(shù) D.序（5） A. 豐滿樹 B.查找樹 C.平衡樹 D.完全樹 【上海海運學院1999二、2(5分）】8若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)是（ ）A9 B11 C15 D不確定 【北京工商大學2001一.7(3分)】9在一棵三元樹中度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點數(shù)為2個，則度為0的結點數(shù)為（ ）個A4 B5 C6 D7 【哈爾濱

22、工業(yè)大學 2001 二、2 （2分）】10設森林F中有三棵樹，第一，第二，第三棵樹的結點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是（ ）?！颈狈浇煌ù髮W 2001 一、16 （2分）】AM1 BM1+M2 CM3 DM2+M311具有10個葉結點的二叉樹中有（ ）個度為2的結點，【北京航空航天大學2000 一、5（2分)】A8 B9 C10 Dll12一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是（ ）【西安交通大學 1996 三、2 (3分)】A 250 B 500 C254 D505 E以上答案都不對 13. 設給定權值總數(shù)有n 個，其哈夫曼樹的結

23、點總數(shù)為( ) 【福州大學 1998 一、5 (2分)】A不確定 B2n C2n+1 D2n-114. 有n個葉子的哈夫曼樹的結點總數(shù)為（ ）?！厩鄭u大學 2002 二、1 （2分）】A不確定 B2n C2n+1 D2n-115若度為m的哈夫曼樹中，其葉結點個數(shù)為n，則非葉結點的個數(shù)為（ ）?！局锌圃河嬎闼?999一、2（2分）】An-1 Bn/m-1 C(n-1)/(m-1)D n/(m-1)-1 E(n+1)/(m+1)-116. 有關二叉樹下列說法正確的是（ ）【南京理工大學 2000 一、11 （1.5分）】A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結點的度為2

24、 D二叉樹中任何一個結點的度都為217二叉樹的第I層上最多含有結點數(shù)為（ ）【中山大學1998二、7 （2分）】【北京理工大學 2001 六、5（2分）】A2I B 2I-1-1 C 2 I-1D2I -118. 一個具有1025個結點的二叉樹的高h為（ ）【南京理工大學 1999 一、19 （2分）】A11 B10 C11至1025之間 D10至1024之間19一棵二叉樹高度為h,所有結點的度或為0，或為2，則這棵二叉樹最少有( )結點A2h B2h-1 C2h+1 Dh+1 【南京理工大學2001一、11(1.5分）】 20對于有n 個結點的二叉樹, 其高度為（ ）【武漢交通科技大學 19

25、96 一、5 (4分)】Anlog2n Blog2n Clog2n|+1 D不確定1圖中有關路徑的定義是（ ）?！颈狈浇煌ù髮W 2001 一、24 （2分）】A由頂點和相鄰頂點序偶構成的邊所形成的序列 B由不同頂點所形成的序列C由不同邊所形成的序列 D上述定義都不是2設無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En 2【清華大學 1998 一、5 （2分）】【西安電子科技大 1998 一、6 （2分）】【北京航空航天大學 1999 一、7 （2分）】3一個n個頂點的連通無向圖，其邊的個數(shù)至少為（ ）。【浙江大學 1999 四、4 (

26、4分)】An-1 Bn Cn+1 Dnlogn；4要連通具有n個頂點的有向圖，至少需要（ ）條邊?！颈本┖娇蘸教齑髮W 2000 一、6(2分）】An-l Bn Cn+l D2n5n個結點的完全有向圖含有邊的數(shù)目（）?！局猩酱髮W 1998 二、9 （2分）】An*n n（n） Cn2 Dn*（nl）6一個有n個結點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量。A0 B1 Cn-1 Dn【北京郵電大學 2000 二、5 （20/8分）】7在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍?！竟枮I工業(yè)大學 2001 二、

27、3 （2分）】A1/2 B2 C1 D48用有向無環(huán)圖描述表達式(A+B)*（A+B）/A），至少需要頂點的數(shù)目為( )?！局猩酱髮W1999一、14】A5 B6 C8 D9 9用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是( )。A逆拓撲有序 B拓撲有序 C無序的 【中科院軟件所 1998】10下面結構中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）。A鄰接矩陣 B逆鄰接表 C鄰接多重表 D十字鏈表 E鄰接表1.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為( )?！颈本┖娇蘸教?/p>

28、大學 2000 一、8 （2分）】 A (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為( ) 【南京理工大學1998一、7（2分A（N+1）/2 B. N/2 C. N D. （1+N）*N /23順序查找法適用于查找順序存儲或鏈式存儲的線性表，平均比較次數(shù)為（1）,二分法查找只適用于查找順序存儲的有序表，平均比較次數(shù)為（2）。 在此假定N為線性表中結點數(shù)，且每次查找都是成功的?！鹃L沙鐵道學院 1997 四、3 (4分)】A.N+1 B.2log 2N C.logN D.N/2 E.Nlog 2N F.N

29、 24. 下面關于二分查找的敘述正確的是 ( ) 【南京理工大學 1996 一、3 （2分）】 A. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 C. 表必須有序，而且只能從小到大排列B. 表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型 D. 表必須有序，且表只能以順序方式存儲5. 對線性表進行二分查找時，要求線性表必須（ ）【燕山大學 2001 一、5 （2分）】A.以順序方式存儲 B.以順序方式存儲,且數(shù)據(jù)元素有序 C.以鏈接方式存儲 D.以鏈接方式存儲,且數(shù)據(jù)元素有序6適用于折半查找的表的存儲方式及元素排列要求為( ) 【南京理工大學 1997 一、6 （2分）】A鏈接方式存儲，元素無序 B鏈接方式存儲，元素有序C順序方式存儲，元素無序 D順序方式存儲，元素有序7. 用二分（對半）查找表的元素的速度比用順序法( ) 【南京理工大學 1998 一、11 （2分）】 A 必然快 B. 必然慢 C. 相等 D. 不能確定8當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情況下要快 D. 取決于表遞增還是遞減【南京理工大學 1997 一、7 （2分）】9. 具有12個關鍵字的有序表，折半查找的平均查找長度（ ）【中山大學 1998 二、10 （2分）】A. 3.1 B. 4 C. 2.