【正文】 , BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7．在隊(duì)列的順序存儲結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲的空間大?。閙axnum。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動元素的方法。將隊(duì)頭、隊(duì)尾看作是一個首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。 int j。 q=qnext。 while((ji) amp。j++。 free(s)?！?p=L。}3．設(shè)單循環(huán)鏈表的頭指針為head，類型為LinkList。 q=head。 p=pnext。 struct node *next,*prior。 p=headnext。amp。 pprior=q。 p=headnext。p=pnext。 qnext=p。 while (p!=NULL) if((pdata=min) || (pdata=max)) { q=p。p=qnext。rearnext=p。}}（2）刪除（即出隊(duì)）算法：delete(LinkList *rear){ //設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif (rear= =NULL) //空隊(duì) printf(underflow\n)。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ){ int i。 i0 amp。 // 比較并移動元素 (*L).elem[ i ] =x。 2. 一個子串在包含它的主串中的位置是指（ ）。A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。 二、填空題1. 計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是___________，第二種是___________________。5. 空串是指___________________，空格串是指___________________。習(xí)題3參考答案一、單項(xiàng)選擇題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è)計(jì)題1．算法描述為：int delete(r,s,t,m) //從串的第m個字符以后刪除長度為t的子串char r[ ]。i=m。j++)r[st+j]=r[j]。LinkString find(s,t)LinkString *s, *t。 while((pt!=NULL)amp。 else { ps=psnext。 +[i*n+j1]*k +[(i1)*n+j1]*k+[(j1)*n+i1]*k +[j*n+i1]*k2. 已知二維數(shù)組A1010中，元素a20的地址為560，每個元素占4個字節(jié)，則元素a10的地址為（ ）。 6. 廣義表A=（a），則表尾為（ ）。 10. 假定在數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。 14. 一個廣義表的表頭總是一個（ ）。2. 對于一個二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?，則任一元素A[i][j]相對于A[0][0]的地址為______________。6. 已知廣義表A=((a,b,c),(d,e,f))，則運(yùn)算head(tail(tail(A)))=____________。（其中：c1≤d1,c2≤d2,c3≤d3）10. 數(shù)組A[1…10，2…6，2…8]以行優(yōu)先的順序存儲，設(shè)第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。（ ）4. 對于不同的特殊矩陣應(yīng)該采用不同的存儲方式。（ ）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）習(xí)題4參考答案一、單項(xiàng)選擇題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.√習(xí)題5一、單項(xiàng)選擇題1. 在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)數(shù)為（ ）個。A. 2 B. 4 C. 6 D. 85. 用順序存儲的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號為結(jié)點(diǎn)（ ）。A. plc=NULL B. pltag=1 C. pltag=1 且plc=NULL D. 以上都不對9. 設(shè)n , m 為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（ ）。A. 二叉樹是特殊的樹B. 二叉樹等價(jià)于度為2的樹C. 完全二叉樹必為滿二叉樹D. 二叉樹的左右子樹有次序之分13. 任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（ ）。 （?。?. 二叉樹的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。 （?。?. 樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。 （?。?0. 樹的子樹是無序的。4. 由帶權(quán)為3，9，6，2，5的5個葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為___。8. 一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_____，最大值為______。12. 對于一棵具有n個結(jié)點(diǎn)的二叉樹，若一個結(jié)點(diǎn)的編號為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號為________，右孩子結(jié)點(diǎn)的編號為________，雙親結(jié)點(diǎn)的編號為________。16. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有______________和_______________兩種。20. 本節(jié)中我們學(xué)習(xí)的樹的存儲結(jié)構(gòu)有_____________、___________和___________。8. 假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二叉樹的后序遍歷序列。2. 給定一棵用二叉鏈表表示的二叉樹，其中的指針t指向根結(jié)點(diǎn)，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結(jié)點(diǎn)按從左至右的次序訪問。習(xí)題5參考答案一、單項(xiàng)選擇題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（或?i/2?）13. 2n，n1，n+114. 帶權(quán)路徑長度最小15. 結(jié)點(diǎn)數(shù)為0，只有一個根結(jié)點(diǎn)的樹16. 二叉鏈表，三叉鏈表17. 雙親結(jié)點(diǎn)18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 1，RChild20. 孩子表示法，雙親表示法，長子兄弟表示法四、應(yīng)用題1. 解答：根據(jù)給定的邊確定的樹如圖515所示。（2）編號為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號是((n2)/m)+1。6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點(diǎn)的二叉樹。假設(shè)該完全二叉樹的結(jié)點(diǎn)以層次為序，按照從上到下，同層從左到右順序編號，存放在一個一維數(shù)組R[1..n]中，且用一個有足夠大容量為maxlen的順序棧作輔助存儲，算法描述如下：preorder (R) //先序遍歷二叉樹Rint R[n]。 //s棧置空root=1。 stop++。 stop?！　nt rear,front。do { front=front%maxsize+1。 que[rear]=tlchild。 //隊(duì)列為空時(shí)結(jié)束}}3. 解答：設(shè)該線索二叉樹類型為bithptr，包含5個域：lchild，ltag，data，rchild，rtag。srtag=1。while(qltag= =0) //查找p所指結(jié)點(diǎn)中序后繼，即為其右子樹中最左下的結(jié)點(diǎn) q=qlchild。}slchild=p。parentjudge(t,n)BiTree *t。BiTree *parent。 //初始化隊(duì)列 rear=1。 if((tlchilddata= =n)|| (trchilddata= =n)) //結(jié)點(diǎn)n有雙親 { parent=t。 que[rear]=tlchild。 //隊(duì)空時(shí)結(jié)束 if (parent = =NULL) printf(“結(jié)點(diǎn)不存在”)。A. n B. e C. n+e D. 2e 4. 在一個具有n個頂點(diǎn)的無向完全圖中，所含的邊數(shù)為(　　)。A. 0 B. 1 C. n D. n+1 8. 若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點(diǎn)，則必須調(diào)用( )次深度優(yōu)先搜索遍歷的算法。e C. e D. 2180。e 12. 在一個具有n個頂點(diǎn)和e條邊的無向圖的鄰接表中，邊結(jié)點(diǎn)的個數(shù)為( )。A. n B. 2n C. e D. 2e 14. 在一個無權(quán)圖的鄰接表表示中，每個邊結(jié)點(diǎn)至少包含( )域。A. 每個頂點(diǎn)的入度等于出度 B. 每個頂點(diǎn)的度等于其入度與出度之和C. 每個頂點(diǎn)的入度為0 D. 每個頂點(diǎn)的出度為0 18. 在一個有向圖的鄰接表中，每個頂點(diǎn)單鏈表中結(jié)點(diǎn)的個數(shù)等于該頂點(diǎn)的( )。A. 1,2,5,4,3 B. 1,2,3,4,5C. 1,2,5,3,4 D. 1,4,3,2,5 22. 若一個圖的邊集為{1,2,1,4,2,5,3,1,3,5,4,3}，則從頂點(diǎn)1開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( )。A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e二、填空題 1. 在一個圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的________倍。 5. 表示圖的兩種存儲結(jié)構(gòu)為__________和__________。 9. 對于一個具有n個頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小至少為________180。 12. 對于一個具有n個頂點(diǎn)和e條邊的無向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度分別為________和________。 16. 圖的________優(yōu)先搜索遍歷算法是一種遞歸算法，圖的________優(yōu)先搜索遍歷算法需要使用隊(duì)列。20. 假定一個有向圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，對該圖進(jìn)行拓?fù)渑判虻玫降捻旤c(diǎn)序列為________。 注：每一種序列都是唯一的，因?yàn)槎际窃诖鎯Y(jié)構(gòu)上得到的。 6. 已知圖613所示的一個網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹的產(chǎn)