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