《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)》期末試卷

1、專業(yè)數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)期末試卷( 一 學(xué)年第 學(xué)期)題號(hào)總分得分一、填空(10分)1、一個(gè)m階B-樹中，每個(gè)結(jié)點(diǎn)最少有(ceil(m/2)個(gè)兒子結(jié)點(diǎn) 四階8+樹中每個(gè)結(jié)點(diǎn)(除根外) 最多有(m )個(gè)兒子結(jié)點(diǎn).2、n(n>0)個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，葉結(jié)點(diǎn)最多有(floor(n+1)/2)個(gè)，最少有(1)個(gè)。若二叉樹有m個(gè)葉結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)有(m-1 )個(gè)。3、順序查找方法適用于存儲(chǔ)結(jié)構(gòu)為(順序表和線性鏈表)的線性表，使用折半查找方法的條件是(查找表為順序存貯的有序表)4、廣義表 A=( ) , (a, (b, c), d)的表尾 Gettail(A)為(a,(b,c),d)5、直接插

2、入排序，起泡排序和快速排序三種方法中，(快速排序)所需的平均執(zhí)行時(shí)間最小；(快速排序)所需附加空間最大。二、選擇(10分)1、倒排文件的主要優(yōu)點(diǎn)是：(C )A、便于進(jìn)行插入和刪除B、便于進(jìn)行文件的合并C、能大大提高基于非主關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)的查找速度D、易于針對(duì)主關(guān)鍵字的逆向檢索2下面程序段的時(shí)間復(fù)雜性為(C )班)系(院y=0;while(n>=(y+1)*(y+1) y+;A、O(n) B、O(n2) C、O(sqrt(n) D、O(1)3、若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是(C )A、二叉排序樹B、哈夫曼樹C、堆D、AVL樹4、棧和隊(duì)列都是(

3、 B )A、順序存儲(chǔ)的線性結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)B、限制存取點(diǎn)的線性結(jié)構(gòu)D、限制存取點(diǎn)的非線性結(jié)構(gòu)5、用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，在等概率情況下的平均查找長(zhǎng)度為(A、n B、n/2 C、（n-1）/2 D、（n+1）/2三、簡(jiǎn)答(30分)ABCDEFGHIJ 和 BCDAFEHJIG ,1、已知一棵二叉樹的前序掃描序列和中序掃描序列分別為 試給出該二叉樹的后序序列并繪出該二叉樹對(duì)應(yīng)的森林。解：后序序列為：DCBFJIHGEA0.16、0.19、2、若對(duì)序列(7, 3, 1, 8, 6, 2, 4, 5)按從小到大排序，請(qǐng)寫出起泡排序的第一趟結(jié)果 和堆排序的初始堆。解：冒泡：3 1

4、 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.11，試畫出相應(yīng)的哈夫曼樹，并設(shè)計(jì)哈夫曼編碼。F:1004、在二叉平衡檢索樹(AVL樹)的調(diào)整中，將最靠近新插入點(diǎn)的不平衡結(jié)點(diǎn)調(diào)整平衡后, 樹中是否還會(huì)有不平衡結(jié)點(diǎn)？為什么？解： 不會(huì)再有不平衡點(diǎn)。因?yàn)椴迦虢Y(jié)點(diǎn)發(fā)生不平衡現(xiàn)象后，會(huì)改變以靠近新插入點(diǎn)的不平衡結(jié)點(diǎn) ”為根的子樹(即最小不平橫樹)的高度加1,經(jīng)過(guò)調(diào)整后使最小不平衡樹的整體高度又恢復(fù)到原來(lái)的值，所以不會(huì)對(duì)原平衡樹 的其他部分造成危害，因此不會(huì)再有不平衡點(diǎn)。5、指定Has

5、h函數(shù)H(k)=3*k mod 11及線性探測(cè)開地址法處理沖突，試在010的散列空間中對(duì)關(guān)鍵字序列(22, 41, 53, 46, 30, 13, 01, 67)構(gòu)造Hash表，并求在等查找概率下 查找成功的平均查找長(zhǎng)度。解：插入元素后的分布情況：0123456789102241300153461367ASL = （1+1 + 1 + 1+2+2+2+6）/8=2.0四、（10分）下圖是帶權(quán)的有向圖 G的鄰接矩陣表示，請(qǐng)給出:1、其鄰接表存儲(chǔ)結(jié)構(gòu)2、按Floyd算法求所有頂點(diǎn)對(duì)之間最短距離的矩陣變化過(guò)程。V1V2V3V4V1|01oo4V2|oo092V3|3508V4|oooo60解：Flo

6、yd算法執(zhí)行過(guò)程中矩陣的變化情況為（從左到右）01oo401103011030193oo092oo09212092110823407340634063406oooo60oooo609106091060五、(12分)設(shè)雙鏈表結(jié)點(diǎn)結(jié)構(gòu)為llink data rlink ,請(qǐng)?jiān)O(shè)計(jì)算法將其中P所指結(jié)點(diǎn)與其rlink所指結(jié)點(diǎn)位置互換的算法。解：typedef struct DLNodeElemType data;struct DLNode *llink,*rlink;DLNode,*DLinkList;/思想：將P->rlink先從鏈表中刪除掉，然后再插入到P前Status SwapANode(D

7、LNode *&P)/ 結(jié)點(diǎn)存在嗎？if(!P | !(P->rlink)return ERROR;q = P->rlink;/ 刪除q結(jié)點(diǎn)if(!q->rlink)P->rlink = NULL;else P->rlink = q->rlink;q->rlink->llink = P;/將q結(jié)點(diǎn)插入到P結(jié)點(diǎn)前面if(!P->llink)q->llink = NULL;q->rlink = P;P->llink = q; else q->llink = P->llink;q->rlink = P;

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

9、ee 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/ whilereturn TRUE; 另解 ：/ 我的另外一個(gè)解法, 根據(jù) longeli 的思想/Aut

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

11、ile(!QueueEmpty(Q)DeQueue(Q,t);/ 左右孩子先入隊(duì)if(t->lchild) EnQueue(Q,t->lchild);if(t->rchild) EnQueue(Q,t->rchild);if(t->lchild && t->lchild)/左右子樹不為空且不滿足 BST 的條件，返回 FALSEif(t->lchild->data>=t->data)|(t->rchild->data< t->data)return FALSE; else if (t->l

12、child && (t->lchild->data >= t->data) / 右子樹為空的情況 return FALSE; else if(t->rchild && (t->rchild->data < t->data) / 左子樹為空的情況 return FALSE;DestroyQueue(Q);return TRUE;用遞歸的方式做也有兩三種做法，這兒就不列舉了。七、(15分)下表列出了某工序之間的優(yōu)先關(guān)系和各工序所需時(shí)間，要求:(1)畫出AOE網(wǎng)(2)列出各事件的最早、最晚發(fā)生時(shí)間(3)找出該AOE

13、網(wǎng)中的關(guān)鍵路徑，并回答完成該工程所需要的最短時(shí)間。工序代號(hào)所需時(shí)間先驅(qū)工序工序代號(hào)所需時(shí)間先驅(qū)工序A15無(wú)H15G、IB10無(wú)I120EC50A、BJ60ID8BK15F、IE15C、DL30H、J、KF40BM20LG300E解：(1) AOE圖如下(需要添加虛線才可以畫出圖，我就是在這兒被迷惑住的，第一次看到這樣的(2)各事件的最早最遲發(fā)生時(shí)間事件編號(hào)1234567891011ve(i)01510655080200380395425445vl(i)015576538080335380395425445(3)通過(guò)上表不用求出活動(dòng)的最早最遲開始時(shí)間就可以看出關(guān)鍵路徑為:1 , 2, 4, 6,

14、 8, 9, 10, 11完成工程所需的最短時(shí)間為：4451. 算法的計(jì)算量的大小稱為計(jì)算的（ ） 。 【北京郵電大學(xué)2000 二、 3 （ 20/8 分） 】A 效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2. 算法的時(shí)間復(fù)雜度取決于（ ） 【中科院計(jì)算所1998 二、 1 （ 2 分） 】A 問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài)C. A 和 B3. 計(jì)算機(jī)算法指的是（1 ） ，它必須具備（2）這三個(gè)特性。（1） A 計(jì)算方法B. 排序方法 C. 解決問(wèn)題的步驟序列 D. 調(diào)度方法（2） A 可執(zhí)行性、可移植性、可擴(kuò)充性B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性D. 易讀性、穩(wěn)

15、定性、安全性【南京理工大學(xué) 1999 一、 1 （ 2 分） 【武漢交通科技大學(xué) 1996 一、 1（ 4 分） 】4 一個(gè)算法應(yīng)該是（ ） 。 【中山大學(xué)1998 二、 1（ 2 分） 】A .程序B .問(wèn)題求解步驟的描述 C .要滿足五個(gè)基本特性D . A和C.5. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ ） 【南京理工大學(xué) 2000 一、 1（ 1.5 分） 】A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性D. 以上幾個(gè)都是錯(cuò)誤的1 下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ ） 【北方交通大學(xué)2001 一、 4 （ 2 分） 】

16、A.存儲(chǔ)密度大 B.插入運(yùn)算方便C.刪除運(yùn)算方便 D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2下面關(guān)于線性表的敘述中， 錯(cuò)誤的是哪一個(gè)？ （ ） 【北方交通大學(xué)2001 一、 14（ 2 分） 】A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D 線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3線性表是具有n 個(gè)（ ）的有限序列（ n>0）。 【清華大學(xué)1998 一、 4（2分） 】A 表元素 B 字符 C 數(shù)據(jù)元素D 數(shù)據(jù)項(xiàng) E 信息項(xiàng)4若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)

17、行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間?！竟枮I工業(yè)大學(xué) 2001 二、 1（ 2 分） 】A 順序表 B 雙鏈表C 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D 單循環(huán)鏈表5某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 【南開大學(xué) 2000 一、3】A 單鏈表 B 僅有頭指針的單循環(huán)鏈表C 雙鏈表D 僅有尾指針的單循環(huán)鏈表6設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用 （ ）最節(jié)省時(shí)間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表【合肥工業(yè)大學(xué) 2000 一、 1 （ 2 分） 】7若某表最常用的操

18、作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！颈本├砉ご髮W(xué) 2000 一、 1 （ 2 分） 】A 單鏈表 B 雙鏈表 C 單循環(huán)鏈表D 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ ） . 【北京理工大學(xué) 2001 六、 2（ 2 分） 】A.內(nèi)存地址 B.數(shù)組下標(biāo)C.下一元素地址D.左、右孩子地址9. 鏈表不具有的特點(diǎn)是（ ） 【福州大學(xué) 1998 一、 8 （2 分）】A.插入、刪除不需要移動(dòng)元素B.可隨機(jī)訪問(wèn)任一元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性長(zhǎng)度成正比10. 下面的敘述不正確的是（） 【南京理工大學(xué)1996 一、 10

19、（ 2 分） 】i 個(gè)元素的時(shí)間同i 個(gè)元素的時(shí)間同i 個(gè)元素的時(shí)間同i 個(gè)元素的時(shí)間同i 的值成正比i 的值無(wú)關(guān)i 的值成正比i 的值無(wú)關(guān)A.線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第C. 線性表在順序存儲(chǔ)時(shí)，查找第D. 線性表在順序存儲(chǔ)時(shí)，查找第1. 對(duì)于棧操作數(shù)據(jù)的原則是（ ） 。 【青島大學(xué) 2001 五、 2（ 2 分） 】A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否（ ）,在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否（ ）。當(dāng)棧中元素為進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為 （ ） 。為了增加內(nèi)存空間的利用率和減少溢出的可能

20、性, 由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 （ ）分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng) （ ） 時(shí)，才產(chǎn)生上溢。, : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長(zhǎng)度 B. 深度 C. 棧頂 D. 棧底 : A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) .B. 其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn).C. 兩個(gè)棧的棧頂在棧空間的某一位置相遇.D. 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.【上海海運(yùn)學(xué)院 1997 二、 1 （ 5 分） 】 【上海海運(yùn)學(xué)院 1999 二、 1（ 5 分） 】3. 一個(gè)棧的輸入序列為123

21、n,若輸出序列的第一個(gè)元素是n,輸出第i （1<=i<=n）個(gè)元素是（A. 不確定 B. n-i+1 C. i D. n-i【中山大學(xué) 1999 一、 9（1 分）】4 .若一個(gè)棧的輸入序列為1,2,3，,n,輸出序列的第一個(gè)元素是i,則第j個(gè)輸出元素是（）。A. i-j-1 B. i-j C. j-i+1 D. 不確定的【武漢大學(xué) 2000 二、3】5 .若已知一個(gè)棧的入棧序列是1,2,3,n,其輸出序列為 p 1,p 2,p 3 ,pN,若p N是n,則 pi 是（ ）。A. i B. n-i C. n-i+1 D. 不確定【南京理工大學(xué)2001 一、1 （ 1.5 分）】6.

22、 有六個(gè)元素6， 5， 4 ， 3 ， 2， 1 的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6【北方交通大學(xué)2001 一、3 （ 2 分） 】7. 設(shè)棧的輸入序列是1 ， 2， 3， 4,則（）不可能是其出棧序列。 【中科院計(jì)算所2000 一、10（2 分）A. 1 ，2， 4，3，B. 2， 1 ， 3，4，C. 1 ， 4， 3，2，D. 4，3， 1 ，2，E. 3， 2， 1，4，8. 一個(gè)棧的輸入序列為 1 2 3 4 5 ，則下列序列中不可能是棧的輸出序列的是

23、（ ） 。A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2【南開大學(xué) 2000 一、 1】【山東大學(xué)2001 二、 4 （1 分 ）】【北京理工大學(xué) 2000 一、 2（ 2分） 】9. 設(shè)一個(gè)棧的輸入序列是1，2 ， 3 ， 4，5,則下列序列中，是棧的合法輸出序列的是（） 。A. 5 1 2 3 4B. 4 51 3 2 C. 43 12 5 D. 3 2 15 4【合肥工業(yè)大學(xué)2001 一、1（ 2 分） 】10. 某堆棧的輸入序列為a, b, c , d,下面的四個(gè)序列中，不可能是它的輸出序列的是（）。A. a ， c ， b ，

24、d B. b, c ， d， a C. c, d， b, a D. d, c ， a， b1. 已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E ， 后綴形式為 ABC*+DE/- ， 其前綴形式為 （ ）A -A+B*C/DE B. -A+B*CD/E C -+*ABC/DE D. -+A*BC/DE【北京航空航天大學(xué) 1999 一、 3 （ 2分）】2. 算術(shù)表達(dá)式a+b* （c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）【中山大學(xué)1999 一、5】A ab+cde/* B abcde/+*+ C abcde/*+ D abcde*/+3. 設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖） ，它所表示的算術(shù)表達(dá)

25、式是（ ）【南京理工大學(xué) 1999 一、 20（ 2 分） 】A. A*B+C/（D*E）+（F-G） B. （A*B+C）/（D*E）+（F-G）C. （A*B+C）/（D*E+（ F-G） ） D. A*B+C/D*E+F-G4. 設(shè)樹 T 的度為4，其中度為1， 2， 3 和 4 的結(jié)點(diǎn)個(gè)數(shù)分別為 4， 2， 1， 1 則 T 中的葉子數(shù)為（ ）A 5 B 6 C 7 D 8【南京理工大學(xué) 2000 一、 8 （ 1.5 分） 】5. 在下述結(jié)論中，正確的是（ ） 【南京理工大學(xué) 1999 一、 4 （ 1 分） 】只有一個(gè)結(jié)點(diǎn)的二叉樹的度為 0; 二叉樹的度為 2； 二叉樹的左右子樹可

26、任意交換;深度為 K 的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A B C D 6. 設(shè)森林F對(duì)應(yīng)的二叉樹為 B,它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ ）A m-n B m-n-1 C n+1 D 條件不足，無(wú)法確定 【南京理工大學(xué) 2000 一、 17（ 1.5分） 】7. 樹是結(jié)點(diǎn)的有限集合，它（ （1 ） ）根結(jié)點(diǎn)，記為 T 。其余結(jié)點(diǎn)分成為 m （ m>0 ）個(gè) （ 2） ） 的集合T1, T2,，T m,每個(gè)集合又都是樹，此點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（iwiwm）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的 （ （ 3）

27、。二叉樹與樹是兩個(gè)不同的概念，二叉樹也是點(diǎn)的有限集合，它 （4） ）根結(jié)點(diǎn)?？梢园褬涞母Y(jié)點(diǎn)的層數(shù)定義為 1，其他結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)所在層數(shù)加上1 。令 T 是一棵二叉樹， Ki 和 Kj 是T中子結(jié)點(diǎn)數(shù)小于2的結(jié)點(diǎn)中的任意兩個(gè)，它們所在的層數(shù)分別為入Ki和入Kj ,當(dāng)關(guān)系式入Ki-入Kj | w 1 一定成立時(shí)，則稱 T為一棵（5）。供選擇的答案：（ 1 ） （4） A. 有 0 個(gè)或 1 個(gè) B. 有 0 個(gè)或多個(gè) C. 有且只有一個(gè)D. 有 1 個(gè)或 1 個(gè)以上（2） A.互不相交B.允許相交C.允許葉結(jié)點(diǎn)相交D.允許樹枝結(jié)點(diǎn)相交（3） A.權(quán)B.維數(shù)C.次數(shù)D.序（5）A.豐滿樹B

28、.查找樹C.平衡樹D.完全樹【上海海運(yùn)學(xué)院1999二、2（5分）】8 若一棵二叉樹具有10 個(gè)度為 2 的結(jié)點(diǎn)， 5 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)個(gè)數(shù)是（ ）A 9 B 11 C 15 D 不確定 【北京工商大學(xué) 2001 一.7（3分）】9 在一棵三元樹中度為3 的結(jié)點(diǎn)數(shù)為 2 個(gè)，度為 2 的結(jié)點(diǎn)數(shù)為1 個(gè)，度為 1 的結(jié)點(diǎn)數(shù)為 2 個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)A. 4 B. 5 C. 6 D. 7【哈爾濱工業(yè)大學(xué)2001二、2 （2分）】10 .設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1, M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）。【北

29、方交通大學(xué) 2001 一、16 （2分）】A. M1 B. M1+M2 C. M3 D , M2+M311 .具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（）個(gè)度為2的結(jié)點(diǎn)，【北京航空航天大學(xué) 2000 、5 （2分）】A. 8 B. 9 C. 10 D. ll12.一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是 （）【西安交通大學(xué) 1996三、2 （3分）】A. 250 B. 500 C. 254 D. 505 E.以上答案都不對(duì)13 .設(shè)給定權(quán)值總數(shù)有 n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為 （）【福州大學(xué)1998 、5 （2分）】A,不確定 B. 2n C. 2n+1 D. 2n-114 .有n個(gè)葉子的哈

30、夫曼樹的結(jié)點(diǎn)總數(shù)為（）?！厩鄭u大學(xué)2002二、1 （2分）】A,不確定 B. 2n C, 2n+1 D. 2n-115 .若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為（）?！局锌圃河?jì)算所 1999 一、2 （2 分）】A. n-1 Bl n/m -1 Cl（n-1）/（m-1） D.n/（m-1） -1 El （n+1）/（m+1） -116 .有關(guān)二叉樹下列說(shuō)法正確的是（）【南京理工大學(xué) 2000 、11 （1.5分）】A.二叉樹的度為2 B. 一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為217 .二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為

31、（）【中山大學(xué)1998二、7 （2分）】【北京理工大學(xué) 2001六、5 （2分）】A. 2IB. 2I-1-1C. 2 I-1D. 2I -118. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高 h為（）【南京理工大學(xué)1999 一、19 （2分）】A. 11 B. 10 C. 11 至 1025 之間 D. 10 至 1024 之間19. 一棵二叉樹高度為 h,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這棵二叉樹最少有（）結(jié)點(diǎn)A. 2h B. 2h-1 C. 2h+1 D, h+1 【南京理工大學(xué) 2001 、11（1.5 分）】20.對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹，其高度為（）【武漢交通科技大學(xué)1996 一、5 （4分）

32、】A. nlog2nB. log2nC. log2n|+1D.不確定1 圖中有關(guān)路徑的定義是（） 。 【北方交通大學(xué) 2001 一、 24 （ 2 分） 】A 由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B 由不同頂點(diǎn)所形成的序列C.由不同邊所形成的序列D.上述定義都不是2 .設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有（）條邊。A n-1 B n（n-1）/2 C n（n+1）/2 D 0 E n 2【清華大學(xué) 1998 一、 5 （ 2 分） 】 【西安電子科技大1998 一、 6 （ 2 分） 】【北京航空航天大學(xué) 1999 一、 7 （ 2 分） 】3 一個(gè) n 個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少

33、為（ ） 。 【浙江大學(xué) 1999 四、 4 （4 分）】A n-1 B n C n+1 D nlogn ；4 要連通具有n 個(gè)頂點(diǎn)的有向圖，至少需要（ ）條邊。 【北京航空航天大學(xué) 2000 一、 6（2分） 】A n-l B n C n+l D 2n5 n 個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（ ） 。 【中山大學(xué)1998 二、 9 （ 2 分） 】A. n*n B . n（n+l） C. n/2 D. n* （n l）6 一個(gè)有 n 個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通分量。A 0 B 1 C n-1 D n【北京郵電大學(xué) 2000 二、 5 （ 20/8 分） 】7 在一個(gè)

34、無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍。 【哈爾濱工業(yè)大學(xué) 2001 二、 3 （ 2 分） 】A 1/2 B 2 C 1 D 48 用有向無(wú)環(huán)圖描述表達(dá)式（A+B）* （A+B ） /A ） ，至少需要頂點(diǎn)的數(shù)目為 （ ）。 【中山大學(xué)1999 一、14】A 5 B 6 C 8 D 99 用 DFS 遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS 算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是 （ ） 。A.逆拓?fù)溆行駼.拓?fù)溆行駽.無(wú)序的 【中科院軟件所 1998】10下面結(jié)構(gòu)中最適于表示稀疏無(wú)向圖的是（） ，適于表示稀疏有向圖的

35、是（ ） 。A.鄰接矩陣 B.逆鄰接表C.鄰接多重表 D.十字鏈表E.鄰接表1 .若查找每個(gè)記錄的概率均等， 則在具有 n 個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL 為（ ） 。 【北京航空航天大學(xué) 2000 一、 8 （ 2 分） 】A（n-1）/2 B. n/2 C. （n+1）/2 D. n2 . 對(duì) N 個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為 （ ） 【南 京理工大學(xué) 1998 一、 7 （ 2 分A （N+1 ） /2 B. N/2 C. N D. （ 1+N） *N /23 順序查找法適用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表，平

36、均比較次數(shù)為（ （ 1） ） ,二分法查找只適用于查找順序存儲(chǔ)的有序表，平均比較次數(shù)為（ （ 2） ） 。 在此假定 N 為線性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的。 【長(zhǎng)沙鐵道學(xué)院 1997四、 3 （4 分）】A.N+1 B.2log 2N C.logN D.N/2 E.Nlog 2N F.N 24. 下面關(guān)于二分查找的敘述正確的是（ ） 【南京理工大學(xué) 1996 一、 3 （ 2 分） 】A. 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)C. 表必須有序，而且只能從小到大排列B. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型D. 表必須有序，且表只能以順序方式存儲(chǔ)5. 對(duì)線性表進(jìn)行二分

37、查找時(shí)，要求線性表必須（ ） 【燕山大學(xué)2001 一、 5 （ 2 分） 】A. 以順序方式存儲(chǔ) B. 以順序方式存儲(chǔ) ,且數(shù)據(jù)元素有序C. 以鏈接方式存儲(chǔ)D. 以鏈接方式存儲(chǔ) , 且數(shù)據(jù)元素有序6. 適用于折半查找的表的存儲(chǔ)方式及元素排列要求為 （ ） 【南京理工大學(xué) 1997 一、 6 （ 2 分） 】A 鏈接方式存儲(chǔ)，元素?zé)o序B 鏈接方式存儲(chǔ)，元素有序C.順序方式存儲(chǔ)，元素?zé)o序D .順序方式存儲(chǔ)，元素有序7. 用二分 （對(duì)半） 查找表的元素的速度比用順序法（ ） 【南京理工大學(xué) 1998 一、 11 （ 2 分） 】A 必然快 B. 必然慢 C. 相等 D. 不能確定8當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找