【正文】 4. 已知一個無向圖的鄰接表如圖612(b)所示，試寫出從頂點0出發(fā)分別進行深度優(yōu)先和廣度優(yōu)先搜索遍歷得到的頂點序列。 注：每一種序列都是唯一的，因為都是在存儲結(jié)構(gòu)上得到的。 18. 若一個連通圖中每個邊上的權(quán)值均不同，則得到的最小生成樹是________（唯一/不唯一）的。 14. 一個圖的邊集為{(a,c),(a,e),(b,e),(c,d),(d,e)}，從頂點a出發(fā)進行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。 10. 對于具有n個頂點和e條邊的有向圖和無向圖，在它們對應(yīng)的鄰接表中，所含邊結(jié)點的個數(shù)分別為________和________。 7. 圖中的一條路徑長度為k，該路徑所含的頂點數(shù)為________。 3. 假定一個有向圖的頂點集為{a,b,c,d,e,f}，邊集為{a,c, a,e, c,f, d,c, e,b, e,d}，則出度為0的頂點個數(shù)為________，入度為1的頂點個數(shù)為________。A. n B. n1 C. n+1 D. 2180。A. A,B,C,F,D,E B. A,C,F,D,E,BC. A,B,D,C,F,E D. A,B,D,F,E,C 20. 若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點A開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為( )。A. k1 B. k2 C. k1k2 D. k1+k2 16. 對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)逆鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為( )。e C. e D. 2180。A. n B. n180。A. n B. n+1 C. n1 D. 2n 10. 在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個數(shù)為( )。A. n B. n(n1) C. n(n1)/2 D. n(n+1)/2 6. 在一個無向圖中，若兩頂點之間的路徑長度為k，則該路徑上的頂點數(shù)為( )。A. s B. s1 C. s+1 D. n 2. 在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂點的度數(shù)之和為(　　)。 que[rear]=trchild。 printf(“parent”,tdata)。 //根結(jié)點進隊 do { front=front%maxsize+1。if (t)if (tdata= =n)printf(“no parent!”)。{ BiTree *que[maxnum]。}4. 解答：利用一個隊列來完成，設(shè)該隊列類型為指針類型，最大容量為maxnum。srtag=0。prtag=0。{ BiThrNode *q。 que[rear]=trchild。 printf(tdata)。 //置空隊列rear=1。算法中的front為隊頭指針，rear為隊尾指針。 root=2*root。amp。SqStack *s。10. 解答：構(gòu)造而成的哈夫曼樹如圖517所示。（4）編號為n的結(jié)點有右兄弟的條件是(n1)%m≠0。2. 解答：度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹不能交換。習題5參考答案一、單項選擇題1. C 2. B 3. C 4. D 5. B 6. D 7. C 8. B 9. B 10. B 11. A 12. D 13. A 14. B 15. A二、判斷題1. 2.√ 3. 4.√ 5. 6.√ 7.√ 8.√ 9. 10.三、填空題1. 3，4，6，1，1，2，A，F(xiàn)，G2. n+13. 完全，最大，n4. 555. 中序6. 2n，n1，n+17. n2+18. 2k1，2k1，2k19. 510. 2h111. 單支樹，完全二叉樹12. 2i，2i+1，i/2（或235。2. 給定一棵用二叉鏈表表示的二叉樹，其中的指針t指向根結(jié)點，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結(jié)點按從左至右的次序訪問。8. 假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二叉樹的后序遍歷序列。20. 本節(jié)中我們學習的樹的存儲結(jié)構(gòu)有_____________、___________和___________。16. 二叉樹的鏈式存儲結(jié)構(gòu)有______________和_______________兩種。12. 對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i(1≤i≤n)，則它的左孩子結(jié)點的編號為________，右孩子結(jié)點的編號為________，雙親結(jié)點的編號為________。8. 一棵深度為k的滿二叉樹的結(jié)點總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點總數(shù)的最小值為_____，最大值為______。4. 由帶權(quán)為3，9，6，2，5的5個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為___。 （?。?0. 樹的子樹是無序的。 （?。?. 樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。 （?。?. 二叉樹的前序遍歷中，任意結(jié)點均處在其子女結(jié)點之前。A. 二叉樹是特殊的樹B. 二叉樹等價于度為2的樹C. 完全二叉樹必為滿二叉樹D. 二叉樹的左右子樹有次序之分13. 任何一棵二叉樹的葉子結(jié)點在先序、中序和后序遍歷序列中的相對次序（ ）。A. plc=NULL B. pltag=1 C. pltag=1 且plc=NULL D. 以上都不對9. 設(shè)n , m 為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是（ ）。A. 2 B. 4 C. 6 D. 85. 用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R[1..n]，結(jié)點R[i]若有左孩子，其左孩子的編號為結(jié)點（ ）。（ ）習題4參考答案一、單項選擇題1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 二、填空題1. 線性結(jié)構(gòu)，順序結(jié)構(gòu)，以行為主序，以列為主序2. in+j個元素位置3. 5，34.（（0，2，2），（1，0，3），（2，2，1），（2，3，5））5. n(n+1)/26. e7. 418. head(head(tail(Ls)))9.（dc+1）（dc+1）（dc+1）10. 913三、判斷題1. 2.√ 3.√ 4.√ 5. 6. 7.√ 8. 9. 10.√ 11.√ 12.√ 13. 14.√ 15.√習題5一、單項選擇題1. 在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（ ）個。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（ ）4. 對于不同的特殊矩陣應(yīng)該采用不同的存儲方式。（其中：c1≤d1,c2≤d2,c3≤d3）10. 數(shù)組A[1…10，2…6，2…8]以行優(yōu)先的順序存儲，設(shè)第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。6. 已知廣義表A=((a,b,c),(d,e,f))，則運算head(tail(tail(A)))=____________。2. 對于一個二維數(shù)組A[m][n]，若按行序為主序存儲，則任一元素A[i][j]相對于A[0][0]的地址為______________。 14. 一個廣義表的表頭總是一個（ ）。 10. 假定在數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。 6. 廣義表A=（a），則表尾為（ ）。 +[i*n+j1]*k +[(i1)*n+j1]*k+[(j1)*n+i1]*k +[j*n+i1]*k2. 已知二維數(shù)組A1010中，元素a20的地址為560，每個元素占4個字節(jié)，則元素a10的地址為（ ）。 else { ps=psnext。 while((pt!=NULL)amp。LinkString find(s,t)LinkString *s, *t。j++)r[st+j]=r[j]。i=m。習題3參考答案一、單項選擇題1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空題1. 固定長度，設(shè)置長度指針2. 兩個串的長度相等，對應(yīng)位置的字符相等3. “BCDEDE”4. 含n個字符的有限序列 （n≥0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計題1．算法描述為：int delete(r,s,t,m) //從串的第m個字符以后刪除長度為t的子串char r[ ]。5. 空串是指___________________，空格串是指___________________。 二、填空題1. 計算機軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是___________，第二種是___________________。A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。 2. 一個子串在包含它的主串中的位置是指（ ）。 // 比較并移動元素 (*L).elem[ i ] =x。 i0 amp。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ){ int i。}}（2）刪除（即出隊）算法：delete(LinkList *rear){ //設(shè)循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) //空隊 printf(underflow\n)。rearnext=p。p=qnext。 while (p!=NULL) if((pdata=min) || (pdata=max)) { q=p。 qnext=p。p=pnext。 p=headnext。 pprior=q。amp。 p=headnext。 struct node *next,*prior。 p=pnext。 q=head。}3．設(shè)單循環(huán)鏈表的頭指針為head，類型為LinkList?！?p=L。 free(s)。j++。 while((ji) amp。 q=qnext。 int j。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動元素的方法。6．共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7．在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大小）為maxnum。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。2．線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。7. 假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運算的算法：（1）向循環(huán)鏈隊列插入一個元素值為x的結(jié)點；（2）從循環(huán)鏈隊列中刪除一個結(jié)點。5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。3. 設(shè)計將帶表頭的鏈表逆置算法。 qnext=NULL。 L=Lnext。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無頭結(jié)點的單鏈表L