【正文】 將算法補(bǔ)充完整。 while(islenamp。jtlen) if(j==1||sdata[i]==tdata[j]){ i++。 } else j= 。 else return(1)。int index_bf(sqstring*s,sqstring *t,int start){ int i=start1,j=0。amp。j++。j=0。 else return 1。int function(SqString *s1,SqString *s2){ int i。is1lengthamp。is1length。 return s1lengths2length。int fun(sqstring *s,sqstring *t,int start){ int i=start1,j=0。amp。j++。j=0。 else return 1。A. 1和1 B. 1和3 C. 1和2 D. 2和3廣義表((a),a)的表尾是（ B ）。A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列表 C. 三元組和十字鏈表 D. 散列表和十字鏈表一個(gè)非空廣義表的表頭（ D ）。A. 1175 B. 1180 C. 1205 D. 1210廣義表G=(a,b(c,d,(e,f)),g)的長(zhǎng)度是（ A ）。A. 正確 B. 錯(cuò)誤 C. 無法確定 D. 以上均不對(duì)廣義表(a,b,c)的表尾是（ B ）。A. 建立和刪除 B. 索引和修改 C. 查找和修改 D. 查找與索引對(duì)一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（ D ）。A. 13　 B. 33 C. 18 D. 401設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B[1,n(n1)/2]中，對(duì)下三角部分中任一元素ai,j(i=j)，在一維數(shù)組B的下標(biāo)位置k的值是（ B ）。A. a B. (a) C. b D. ((a))1稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ C ）。A. B. C. D. 1以下有關(guān)廣義表的表述中，正確的是（ A ）。A. 的 B. e C. (e) D. （e,f）二、判斷題（ ）廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度。（√ ）稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（√ ）廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。廣義表運(yùn)算式HEAD(TAIL((a,b,c),(x,y,z)))的結(jié)果是： (x,y,z) 。稀疏矩陣的壓縮存儲(chǔ)方式有： 和 。答案：第六章 樹一、選擇題二叉樹的深度為k，則二叉樹最多有（ C ）個(gè)結(jié)點(diǎn)。A. R[2i1] B. R[2i+1] C. R[2i] D. R[2/i]設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（ B ）。A. adbce B. decab C. debac D. abcde在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（A）。A. 能 B. 不能某二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為（ C ）。A. 67　 B. 68 C. 69 D. 70將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（ A ）。A. abcd+　 B. abc+*d C. abc*+d D. +*abcd1對(duì)某二叉樹進(jìn)行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是（ B ）。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)1表達(dá)式A*(B+C)/(DE+F)的后綴表達(dá)式是（ C ）。A. tleft==NULL　 B. tltag==1 C. tltag==1amp。tleft==NULL D. 以上都不對(duì)1任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。 A. 15 B. 16 C. 17 D. 471在下列情況中，可稱為二叉樹的是（ B ）。A. R[2i1] B. R[2i+1] C. R[2i] D. R[2/i]1下面說法中正確的是（ ）。A. 先序序列 B. 中序序列 C. 后序序列 D. 層序序列 2按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（ C ）種。A. 51 B. 23 C. 53 D. 74二、判斷題（ ）存在這樣的二叉樹，對(duì)它采用任何次序的遍歷，結(jié)果相同。（ ）對(duì)于任意非空二叉樹，要設(shè)計(jì)其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對(duì)該二叉樹采用三叉鏈表。（√ ）一個(gè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹，它的高度是235。＋1。三、填空題具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 235。+1 。在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0= N2+1 。四、代碼填空題函數(shù)InOrderTraverse(Bitree bt)實(shí)現(xiàn)二叉樹的中序遍歷，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 printf(“%c”,btdata)。 } }函數(shù)depth實(shí)現(xiàn)返回二叉樹的高度，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 else{ hl=depth(tlchild)。 if( hlhr ) return hl+1。 } }寫出下面算法的功能。 if(bt==NULL) t=NULL。 tdata=btdata。 t2=function(btright)。 tright=t1。 }答案：交換二叉樹結(jié)點(diǎn)左右子樹的遞歸算法寫出下面算法的功能。 function(prchild)。}}答案：二叉樹后序遍歷遞歸算法五、綜合題假設(shè)以有序?qū),c表示從雙親結(jié)點(diǎn)到孩子結(jié)點(diǎn)的一條邊，若已知樹中邊的集合為{a,b,a,d,a,c,c,e,c,f,c,g,c,h,e,i,e,j,g,k},請(qǐng)回答下列問題：（1）哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？（2）哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？（3）哪些結(jié)點(diǎn)是k的祖先？（4）哪些結(jié)點(diǎn)是j的兄弟？（5）樹的深度是多少？。假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：。答案：已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案： WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69已知權(quán)值集合為{5,7,2,3,6,9}，要求給出哈夫曼樹，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。畫出二叉樹的形態(tài)。答案： 有一分電文共使用5個(gè)字符。1畫出與下圖所示的森林相對(duì)應(yīng)的二叉樹，并指出森林中的葉子結(jié)點(diǎn)在二叉樹中具有什么特點(diǎn)。 答案：先序：FDBACEGIHJ 中序：ABCDEFGHIJ 后序：ACBEDHJIGF六、編程題編寫求一棵二叉樹中結(jié)點(diǎn)總數(shù)的算法。（以先序遍歷的方法為例）void count_preorder(Bitree *t, int *n) { if(t!=NULL){*n++。count_preorder(tlchild)。A. n B. n2 C. n1 D. (n1)2如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（ ）。A. 從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑　 B. 從源點(diǎn)到匯點(diǎn)的最短路徑 C. 最長(zhǎng)的回路 D. 最短的回路下面（ ）可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。 A. 第i行非無窮的元素之和　 B. 第i列非無窮的元素個(gè)數(shù)之和C. 第i行非無窮且非0的元素個(gè)數(shù) D. 第i行與第i列非無窮且非0的元素之和采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類似于二叉樹的（ ）。A. 對(duì)稱矩陣 B. 零矩陣 C. 上三角矩陣 D. 對(duì)角矩陣當(dāng)利用大小為N的數(shù)組存儲(chǔ)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度是（ ）。A. 順序存儲(chǔ)結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) C. 索引存儲(chǔ)結(jié)構(gòu) D. 散列存儲(chǔ)結(jié)構(gòu)下面有向圖所示的拓?fù)渑判虻慕Y(jié)果序列是（ ）。 A. 頂點(diǎn)序列 B. 邊序列 C. 權(quán)值總和 D. 邊的條數(shù) 1在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。V2,E1205。A. G1是G2的子圖 B. G2是G1的子圖 C. G1是G2的連通分量 D. G2是G1的連通分量1已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)（ ）。 B. 有一個(gè) C. 一定有多個(gè) D. 有一個(gè)或多個(gè)1在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。A. 連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程 B. 圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征 C. 非連通圖不能用深度優(yōu)先搜索法 D. 圖的遍歷要求每一頂點(diǎn)僅被訪問一次1帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度為A中：（ ）。的元素之和 B. 第i列非165。且非0的元素個(gè)數(shù) D. 第i列非165。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層次遍歷一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有（ ）條邊。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v22關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。 A. 連通分量是無向圖中的極小連通子圖 B. 強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖 C. 在一個(gè)有向圖的拓?fù)湫蛄兄腥繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧a,b D. 對(duì)有向圖G，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖2假設(shè)有向圖含n個(gè)頂點(diǎn)及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點(diǎn)個(gè)數(shù)為（ ）。A. 有向圖 B. 無向圖 C. 強(qiáng)連通圖 D. 完全圖2為便于判別有向圖中是否存在回路，可借助于（ ）。A. 只有一棵　 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在2已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（ ）。A. k1　 B. k2 C. k1+k2 D. k1k2一個(gè)具有8個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和的差等于（ ）。A. 通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù) B. 與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù) C. 與該頂點(diǎn)連通的頂點(diǎn)數(shù) D. 通過該頂點(diǎn)的回路數(shù)二、填空題n個(gè)頂點(diǎn)的連通圖至少有 邊。答案：極小連通子圖一個(gè)圖的 表示法是惟一的。答案：深度優(yōu)先搜索在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于 。答案：拓?fù)渑判蛞阎粋€(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 。已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 。三、判斷題圖的連通分量是無向圖的極小連通子圖。O圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。O存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。O從源點(diǎn)到終點(diǎn)的最短路徑是唯一的。O圖的生成樹是惟一的。 typedef struct{ int vexnum,arum。 int arcs[N][N]。void funtion(int i,graph *g){ int j。 visited[i]=TRUE。jgvexnum。amp。 }答案：實(shí)現(xiàn)圖的深度優(yōu)先遍歷算法五、綜合題已知圖G的鄰接矩陣如下所示：（1）求從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列；（2）根據(jù)prim算法，求圖G從頂點(diǎn)1出發(fā)的最小生成樹，要求表示出其每一步生成過程。答案：(1)廣度優(yōu)先遍歷序列：