數(shù)據(jù)結(jié)構(gòu)自測題答案.doc

第1章 緒論 一、選擇題12345678CCADABCC二、填空題1. 4種基本結(jié)構(gòu)是：集合、 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 、 圖狀結(jié)構(gòu) 。2. 樹形結(jié)構(gòu)中元素的關(guān)系是 一對多 ，圖形結(jié)構(gòu)中元素的關(guān)系是 多對多 。3. 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素的存儲位置與其 邏輯順序 是對應(yīng)的。4. 算法效率的度量方法有：事后統(tǒng)計方法和 事前分析估算方法 。5. 好算法應(yīng)達(dá)到的目標(biāo)： 正確性 、 可讀性 、 健壯性 、 執(zhí)行時間短 、 存儲量低 。6. 抽象數(shù)據(jù)類型可細(xì)分為3種： 原子類型 、 固定聚合類型 和 可變聚合類型 。7. 抽象數(shù)據(jù)類型的定義包括： 數(shù)據(jù)對象的定義 、 數(shù)據(jù)關(guān)系的定義 、基本操作的定義 。三、判斷題1234567891011五、應(yīng)用題1. 按增長率從小到大的順序排列下列各函數(shù)： (2/3)n ，n ，n2 ，n!2. 寫出以下各函數(shù)的功能，并求出其時間復(fù)雜度。(1) 功能是判斷n是否為素數(shù) ，時間復(fù)雜度為O(n ) 。(2) 功能是計算1!+2!+n! ，時間復(fù)雜度為O(n ) 。(3) 功能是計算1!+2!+n! ，時間復(fù)雜度為O(n2 ) 。六、算法題1. 編寫算法計算1!+2!+n!，并使算法的時間復(fù)雜度為O(n)。算法思想：用循環(huán)實現(xiàn)階乘的累加求和，注意在求n!時，使用前一次循環(huán)中已經(jīng)求出的(n-1)!的結(jié)果。double factorial(int n) int i; double p=1, sum=0; for( i=1; iMAXINT（0kn）時，應(yīng)進(jìn)行出錯處理。算法思想：先判斷n的取值是否合法，若非法則直接退出程序，若n 合法則繼續(xù)計算2i，在計算2i時，需要判斷2i的值是否大于MAXINT/2，這個條件其實就是判斷2i+1的值是否大于MAXINT#define arrsize 100#define MAXINT 65535void calculate(int a , int n) int i; if(narrsize) printf(n error!n); exit(-1); a0=1; printf(a0=%dn, a0); for(i=1; iMAXINT/2 ) printf(“i=%d, ERROR!n”, i+1)； break; 第2章 線性結(jié)構(gòu)一、選擇題1234567891011121314151617ABCADBBACACBBBDCD二、填空題1. 需向后移動_n-i+1_個元素。2. 應(yīng)采用_順序_存儲結(jié)構(gòu)。3. 有n個結(jié)點的單鏈表，在x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_O(n)_。4可以將線性鏈表分成_單鏈表_和多重鏈表。5鏈接存儲的特點是利用_指針_來表示數(shù)據(jù)元素之間的邏輯關(guān)系。6. 順序存儲結(jié)構(gòu)是通過_ 物理位置相鄰_表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過_指針_表示元素之間的關(guān)系的。7. 循環(huán)單鏈表的最大優(yōu)點是：_從任一結(jié)點出發(fā)都可訪問到鏈表中每一個元素_。8. 帶頭結(jié)點的單循環(huán)鏈表L，L為空表的條件是：_ L-next=L_。三、判斷題12345678四、簡答題1. 對線性表中的插入操作，分別寫出順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)下的時間復(fù)雜度。答： O(n), O(1)2. 線性結(jié)構(gòu)的特點是什么？答：在數(shù)據(jù)元素的非空有限集中，(1)存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素; (2)存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素; (3)除第一個之外，集合中的每個元素均只有一個前驅(qū); (4) 除最后一個之外，集合中每個元素均只有一個后繼3. 說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭結(jié)點之間的根本區(qū)別；頭結(jié)點與首元結(jié)點的關(guān)系。答：在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義（有些情況下也可存放鏈表的長度、用做監(jiān)視哨等），有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。4. 在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點出發(fā)訪問到任何一個結(jié)點?答：在單鏈表中不能從當(dāng)前結(jié)點（若當(dāng)前結(jié)點不是第一結(jié)點）出發(fā)訪問到任何一個結(jié)點，鏈表只能從頭指針開始，訪問到鏈表中每個結(jié)點。在雙鏈表中求前驅(qū)和后繼都容易，從當(dāng)前結(jié)點向前到第一結(jié)點，向后到最后結(jié)點，可以訪問到任何一個結(jié)點。*5. 順序表在插入或刪除元素時一般需要移動元素，如果想不移動多個元素就實現(xiàn)插入和刪除，應(yīng)該如何處理？答：插入元素時，直接將新元素插在第n+1個位置；刪除第i個元素時，將第n個元素補(bǔ)到第i個位置。五、算法題1、利用線性表的基本操作(教材P19)，實現(xiàn)在線性表A中刪除在線性表B中出現(xiàn)的元素。#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct int *elem;int length;int listsize;SqList;void Delete(SqList &A, SqList B) /線性表A、B已存在 B_len=ListLength(B); for(i=1; i=B_len; i+) GetElem(B, i, e); / 用e返回B中第i 個元素的值 n= LocateElem(A, e, equal); / n為e在A中的位序 if ( n!=0) ListDelete(A, n, e ); /刪除A中第n個元素 2、編寫算法，將一個有n個非零元素的線性表A拆分成兩個線性表，其中大于零的元素存放線性表B中，小于零的元素存放在線性表C中。#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct int *elem;int length;int listsize;SqList;void separate(SqList A, SqList &B, SqList &C) /線性表A已存在，B和C不存在 InitList(B); InitList(C); na=A.length; nb=nc=0; for(i=0; i0 ) B.elemnb=A.elemi; nb+; else C.elemnc=A.elemi; nc+; B.length=nb; C.length=nc;3、分別基于線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)（帶頭結(jié)點），實現(xiàn)以下操作：(1) 從線性表中刪除具有給定值x的所有元素。(2) 從線性表中刪除其值在有給定值s與t之間的所有元素，其中要求s=t ，若s或t不合理，或線性表為空，則顯示出錯信息并退出程序。(3) 假設(shè)線性表的元素按遞增順序排列，刪除表中所有大于s且小于t的所有元素（若存在這樣的元素），要求s0; i-) /從后面開始刪除，可以減少元素的移動次數(shù) if (L.elemi-1 = x ) for( int j=i; jt ) printf( ”s, t的值不合理!n”); return ; for( int i=L.length; i0; i-) /從后面開始刪除 if (L.elemi-1 = s & L.elemi-1=t ) for( int j=i; jt ) printf( ”s, t的值不合理!n”); return; for( int i=0; iL.length & L.elemis; i+) /尋找值大于等于s的第1個元素 ； /注意循環(huán)體為空語句 if ( i=L.length ) printf(”線性表中所有元素值都小于s!n”); return ; for( int j=i; jL.length & L.elemj=t; j+)； /尋找值大于t的第1個元素 for( int n=i, k=j; kL.length; n+, k+) L.elemn=L.elemk; L.length=L.length-(j-i); (4) void Delete_same(SqList &L) /L為有序表 if( L.length=0) printf(線性表為空!n); return; for( int i=0; iL.length; i+) while( iL.length-1 & L.elemi!=L.elemi+1 ) i+; /尋找重復(fù)元素 if(i=L.length-1) break; for( int j=i+1; L.elemj=L.elemi; j+); /尋找與第i個元素不相同的元素 for( int t=i+1, k=j; knext; q=L; while (p!=NULL ) if(p-data!=x) q=p; p=p-next; else q-next = p-next; free(p);p=q-next; (2)void ListDelete_st(LinkList &L, int s, int t) /刪除值在st之間的元素 LinkList p,q; if(L=NULL) printf(鏈表為空！n); return; p = L-next; q=L; while (p!=NULL ) if (p-data=s & p-datanext = p-next; free(p); p=q-next; else q=p; p=p-next; (3) void Delete_st(LinkList &L, int s, int t) / 在有序單鏈表L中，刪除值在st之間的結(jié)點 LinkList p, q, p1, p2; if(L=NULL) printf(鏈表為空！n); return ; p = L-next; while(p!=NULL & p-datanext; / p指向該元素，q指向p的前驅(qū)結(jié)點 if(p=NULL) printf(鏈表中所有元素值都小于s!n); return ; while(p!=NULL & p-datanext; p1=q-next; q-next = p; /刪除值在st之間的所有結(jié)點 while(p1!=p) /循環(huán)釋放st之間的所有結(jié)點的空間 p2=p1; p1=p1-next; free(p2); (4) void Delete_same(LinkList &L) / 在有序單鏈表L中，刪除值相同的多余結(jié)點 LinkList p,q; if(L=NULL) printf(鏈表為空！n); return ; p = L-next; while(p!=NULL & p-next!=NULL) q=p-next; if(p-data!=q-data) p=p-next; else p-next=q-next; free(q); p=p-next; *4、設(shè)有一個不帶頭結(jié)點的非空單鏈表，編寫遞歸算法實現(xiàn)以下操作：(1) 求鏈表中的結(jié)點個數(shù) (2) 求鏈表中的最大整數(shù)（設(shè)鏈表結(jié)點的數(shù)據(jù)域中存放的是整型數(shù)據(jù)）typedef struct LNode int data;Struct LNode *next;Lnode, *LinkList;(1) int Num(LinkList L) / 鏈表L已存在 if( L-next=NULL ) return 1; else return (1+Num( L-next); (2) void Max(LinkList L,int &m) / 鏈表L已存在，找到的最大整數(shù)存在m中 int n; if( L-next=NULL ) m=L-data; else Max( L-next, n); m= L-datan?L-data:n; 第3章 棧和隊列一、選擇題1234567891011BCBBADCADDC二、填空題1. 棧和隊列都是 線性 結(jié)構(gòu)，對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 。不允許插入和刪除運算的一端稱為 棧底 。3. 在具有n個單元的循環(huán)隊列中，隊滿時共有 n-1 個元素。4. 向棧中插入元素的操作是先 存入元素 ，后 移動棧頂指針 。5. 帶表頭結(jié)點的空循環(huán)鏈表的長度等于 0 。6. 設(shè)循環(huán)隊列Qmaxsize的隊頭指針為front，隊尾指針為rear，則該隊列的隊滿條件是 Q.front=(Q.rear+1)%maxsize 。三、判斷題1234567891011四、簡答題1.說明線性表、棧與隊的異同點。答：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：運算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運算，因而是后進(jìn)先出表LIFO；隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2.設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。答：至少有14種。 全進(jìn)之后再出情況，只有1種：4，3，2，1 進(jìn)3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab則不是回文。假設(shè)一字符序列已存入計算機(jī)，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲，可以實現(xiàn)，靠循環(huán)變量從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進(jìn)先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ斣O(shè)置到數(shù)組末尾，然后直接用POP動作實現(xiàn)。若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部入棧后再依次輸出。4. 順序隊列的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿、隊空的辦法有三： 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空； 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法，即隊頭指針、隊尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。判斷循環(huán)隊列隊空標(biāo)志是： f=rear 隊滿標(biāo)志是：f=(r+1)%N5. 設(shè)循環(huán)隊列的容量為40（序號從0到39）， 現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11，rear=19; front=19，rear=11；問這兩種情況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、算法閱讀題1. 答：輸出為“stack”。2. 答：輸出為“char”。3. 答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進(jìn)行逆置。六、算法題1. 試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文”。int PalindromeTest(void) /判別輸入的字符串是否回文序列,是則返回1,否則返回0 InitStack(S); InitQueue(Q); /同時使用棧和隊列兩種結(jié)構(gòu)while(c=getchar()!=) Push(S,c); EnQueue(Q,c); while(!StackEmpty(S) Pop(S,a); DeQueue(Q,b); if(a!=b) return 0; return 1; 2. 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，只設(shè)一個指向隊尾結(jié)點的尾指針，不設(shè)頭指針，分別寫出入隊列和出隊列的算法。typedef struct node ElemType data; Struct node *next; *LinkQueue;void EnQueue(LinkQueue &rear, ElemType e) LinkQueue s; s=(Qnode *) malloc(sixeof(Qnode); s-data=e; s-next=rear-next; rear-next=s; rear=s;void DeQueue(LinkQueue &rear, ElemType &e) LinkQueue h, p; if ( rear=rear-next ) printf(“隊空”); return; h=rear-next; p=h-next; e=p-data; if ( p=rear ) rear=h; h-next=p-next; free(p);第6章 樹和二叉樹一、選擇題1234567891011121314CABCADCBCACDAB二、填空題1. 可能最大高度是 n ，葉結(jié)點數(shù)為 1 ，可能最小高度是 ，葉結(jié)點數(shù)為 n2+1。2. 一棵完全二叉樹有12個葉結(jié)點，則該樹最多有 24 個結(jié)點。答：n0=12， n2=n0-1=11， n=n0+n2+1=12+11+1=243. 先序序列為ABDCEF，中序序列為DBAECF，則后序序列為 DBEFCA 。4. 二叉樹的層次遍歷需要使用 隊列 輔助才能實現(xiàn)。 5. 設(shè)二叉樹有n個結(jié)點，則二叉鏈表中空指針數(shù)為 n+1 。6. 由3個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 7. 一棵深度為6的滿二叉樹有 31 個分支結(jié)點和 32 個葉子。答：滿二叉樹沒有度為1的結(jié)點，分支結(jié)點數(shù)就是度為2的結(jié)點數(shù)。n1+n2=0+ n2= n0-1=31， 26-1 =328 一棵具有257個結(jié)點的完全二叉樹，它的深度為 9 。答：用 log2(n) +1= 8.xx +1=99. 設(shè)一棵完全二叉樹有700個結(jié)點，則共有 350 個葉子結(jié)點。答：因n=n0+n2+1, n2=n0-1, 所以 n=2*n0, n0n/2350 10. 設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 500 個葉子結(jié)點，有 499 個度為2的結(jié)點，有 1 個結(jié)點只有非空左子樹，有 0 個結(jié)點只有非空右子樹。答：n0n/2500，n2=n0-1=499。 最后一個結(jié)點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹不可能有左空右不空的情況，所以非空右子樹數(shù)0.11. 一棵有n(n1)個結(jié)點的k叉樹，可能的最大深度為 n ，可能的最小深度為 2 。答：當(dāng)k=1(單叉樹)時應(yīng)該最深，深度n（層）；當(dāng)k=n-1（n-1叉樹）時應(yīng)該最淺，深度2（層），但不包括n=0或1時的特例情況。三、判斷題12345678910111211. 正確。用二叉鏈表存儲包含n個結(jié)點的二叉樹，結(jié)點共有2n個鏈域。由于二叉樹中，除根結(jié)點外，每一個結(jié)點有且僅有一個雙親，所以只有n-1個結(jié)點的鏈域存放指向非空子女結(jié)點的指針，還有n+1個空指針。）12. n0=n/26，再求n2=n0-1=5四、應(yīng)用題1. 在一棵度為4的樹中，有20個度為4的結(jié)點， 10個度為3的結(jié)點， 1個度為2的結(jié)點，10個度為1的結(jié)點，請計算樹中度為0的結(jié)點個數(shù)。(寫出計算過程)答：因 n=n0+n1+n2+n3+n4, 總分支數(shù)e=n-1, e= n0+n1+n2+n3+n4-1, e=4*n4+3*n3+2*n2+n1 n0=e-n1-n2-n3-n4+1=(4-1)*n4+(3-1)*n3+(2-1)*n2+1=3*20+2*10+1*1+1=822. 一棵二叉樹有1024個結(jié)點，有葉子結(jié)點465個，度為2和度為1的結(jié)點各有多少個。答：因n0=n2+1，所以n2=465-1=464，n1=1024-465-464=953. 請畫出一棵先序序列和中序序列相同的二叉樹（注：空樹和只有根結(jié)點的樹除外）。答：右單枝樹的先序序列與中序序列相同abc4. 已知二叉樹的層次遍歷序列為ABCDEFG，中序序列為DBFEGAC，請畫出該樹。ACBEDGF5. 給定如圖所示二叉樹T，請畫出與其對應(yīng)的中序線索二叉樹。解：要遵循中序遍歷的軌跡來畫出每個前驅(qū)和后繼。2825 3340 60 08 54 55中序遍歷序列：55 40 25 60 28 08 33 5482540555560330854NULLNULL 2825 33 40 60 08 54 556. 試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A7. 把如圖所示的樹轉(zhuǎn)化成二叉樹。 五、算法題1. 借助于棧實現(xiàn)二叉樹的非遞歸中序遍歷算法。（可以直接使用棧的基本操作）typedef struct BiTNode char data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree; /定義二叉鏈表的存儲結(jié)構(gòu)void Inorder(BiTree T) SqStack S; BiTree p=T; InitStack(S); do while(p!=NULL) Push(S,p); p=p-lchild; if (!StackEmpty(S) Pop(S, p); printf(%c , p-data); p=p-rchild; while(p!=NULL | ! StackEmpty(S) ); 2. 設(shè)二叉樹以二叉鏈表做存儲結(jié)構(gòu)，編寫遞歸算法實現(xiàn)以下功能：(1) 統(tǒng)計二叉樹中度為1的結(jié)點個數(shù) (2) 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)(3) 計算二叉樹的高度(4) 刪除二叉樹中所有的葉子結(jié)點(5) 求指定結(jié)點的父結(jié)點(指定二叉樹中某個結(jié)點的值)typedef struct BiTNode char data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree; /定義二叉鏈表的存儲結(jié)構(gòu)(1) int Degree1(BiTree T) /計算度為1的結(jié)點個數(shù) if (T=NULL) return 0; if( (T-lchild!=NULL & T-rchild=NULL) | (T-lchild=NULL & T-rchild!=NULL) return 1; return Degree1(T-lchild)+Degree1(T-rchild); (2) int leaves(BiTree T) /計算葉子結(jié)點的個數(shù) if (T=NULL) return 0; if( T-lchild=NULL & T-rchild=NULL) return 1; return leaves(T-lchild)+leaves(T-rchild);(3) int Height(BiTree T) /計算二叉樹的高度 int Lh, Rh, h; if (T=NULL) return 0; Lh=Height(T-lchild);Rh=Height(T-rchild);h=LhRh?Lh: Rh;return(h+1);(4) void del_leaves(BiTree &T) /刪除所有葉子結(jié)點 if (T=NULL) return; if( T-lchild=NULL & T-rchild=NULL) free(T); T=NULL; else del_leaves(T-lchild); del_leaves(T-rchild); (5) void parent(BiTree T,BiTree &p,char x) /求指定結(jié)點值為x的父結(jié)點 if (T=NULL) p=NULL; if( T-lchild!=NULL & T-lchild-data=x | T-rchild!=NULL & T-rchild-data=x) p=T; if(T-lchild!=NULL) parent(T-lchild,p,x); if(T-rchild!=NULL) parent(T-rchild,p,x);3. 設(shè)二叉樹以二叉鏈表做存儲結(jié)構(gòu)，利用先序遍歷求先序序列中的第k個結(jié)點。BiTree search_k(BiTree T, int &count, int k) /count必須是引用參數(shù) BiTree p;if (T) count+; if(count=k) return T; if( p=search_k(T-lchild, count, k) return p; if( p=search_k(T-rchild, count, k) return p;return NULL;4. 設(shè)二叉樹以二叉鏈表做存儲結(jié)構(gòu)，編寫算法判斷一個二叉樹是否是完全二叉樹。算法思想：利用層次遍歷，讓二叉樹的結(jié)點逐層入隊列，如果中間出現(xiàn)空結(jié)點，則說明該樹不是完全二叉樹。算法返回1表示是完全二叉樹，返回0表示不是完全二叉樹int CompleteBiTree(BiTree T) LinkQueue Q; int flag=0;if(T=NULL) return 1;InitQueue(Q);EnQueue(Q,T); while( !QueueIsEmpty(Q) ) DeQueue(Q,T); if(T=NULL) flag=1;elseif(flag) return 0;else EnQueue(Q,T-lchild); EnQueue(Q,T-rchild); DestroyQueue(Q);return 1;第7章 圖一、選擇題123456789101112131415161718CBBCCBADCDACADAADA二、填空題1. 圖的存儲結(jié)構(gòu)最常用的有 鄰接矩陣 、 鄰接表 ，遍歷圖的方法有： 深度優(yōu)先遍歷 、 廣度優(yōu)先遍歷 等。2. 有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i的 出度 。3. 如果n個頂點的圖是一個環(huán)，則它有 n 棵生成樹。 4. n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復(fù)雜度為 O(n2) 。5. n個頂點e條邊的圖，若采用鄰接表存儲，則空間復(fù)雜度為 O(n+e) 。6. 設(shè)有一稀疏圖G，則G采用 鄰接表 存儲較省空間。7. 設(shè)有一稠密圖G，則G采用 鄰接矩陣 存儲較省空間。8. 圖的逆鄰接表存儲結(jié)構(gòu)只適用于 有向 圖。9. 圖的深度優(yōu)先遍歷序列 不是 惟一的。10. n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復(fù)雜度為 O(n2) ；若采用鄰接表存儲時，該算法的時間復(fù)雜度為 O(n+e) 。11. n個頂點e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復(fù)雜度為 O(n2) ；若采用鄰接表存儲，該算法的時間復(fù)雜度為 O(n+e) 。12. Prim算法求具有n個頂點e條邊的圖的最小生成樹的時間復(fù)雜度為 O(n2) ；用克魯斯卡爾(Kruskal)算法的時間復(fù)雜度是 O(elog2e) 。13. 若要求一個稀疏圖G的最小生成樹，最好用 克魯斯卡爾(Kruskal) 算法來求解。14. 若要求一個稠密圖G的最小生成樹，最好用 普里姆(Prim) 算法來求解。15. 用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度 遞增 的次序來得到最短路徑的。16. 求最短路徑的Dijkstra算法的時間復(fù)雜度是 O(n2) 。17. 拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有 0 個前驅(qū)頂點的過程來完成的。三、判斷題123456789四、簡答題1. 50個頂點、15條邊的有向圖的鄰接矩陣有多少個矩陣元素？該矩陣是否是稀疏矩陣？答：50*50=2500 有2500個矩陣元素，15/2500=0.0060.05 該矩陣是稀疏矩陣2.有n個頂點的無向圖最多有幾條邊，最少有幾條邊；如果該圖是連通圖，則該圖最多有幾條邊，最少有幾條邊？答：無向圖最多有n(n-1)/2邊，最少有0條邊。無向連通圖最多有n(n-1)/2邊，最少有n-1條邊。3. 有n個頂點的有向圖最多有幾條邊，最少有幾條邊；如果該圖是強(qiáng)連通圖，則該圖最多有幾條邊，最少有幾條邊？答：有向圖最多有n(n-1)邊，最少有0條邊。強(qiáng)連通圖最多有n(n-1)邊，最少有n條邊。4、對下面所示的有向圖，請回答：該圖是強(qiáng)連通圖嗎？若不是，請畫出其強(qiáng)連通分量。答：該圖不是強(qiáng)連通圖。有6個強(qiáng)連通分量，即各個頂點。 五、應(yīng)用題1. 已知如圖所示的有向圖，請給出該圖的:（1） 每個頂點的入/出度；（2） 鄰接矩陣；（3） 鄰