【正文】 [j]){ i++。 } if(j=tlen) return itlen+1。A. a B. (a) C. () D. ((a))稀疏矩陣的常見壓縮存儲(chǔ)方法有（ C ）兩種。A. 3 B. 4 C. 7 D. 8采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲(chǔ)，若要完成對(duì)三元組表進(jìn)行轉(zhuǎn)置，只要將行和列對(duì)換，這種說法（ B ）。A. 表達(dá)變得簡單 B. 對(duì)矩陣元素的存取變得簡單 C. 去掉矩陣中的多余元素 D. 減少不必要的存儲(chǔ)空間的開銷1設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每元素占1個(gè)地址空間，則a85的地址為（ B ）。A. 二維數(shù)組和三維數(shù)組　 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表1假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對(duì)應(yīng)的45的稀疏矩陣是（注：矩陣的行列下標(biāo)均從1開始）（ B ）。（ 錯(cuò) ）一個(gè)稀疏矩陣采用三元組表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把mu和nu的值進(jìn)行互換，則完成了矩陣轉(zhuǎn)置。三、填空題已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0])，則A[i][j]的地址是Loc(A[0][0])+(i*N+j)*k 。四、綜合題現(xiàn)有一個(gè)稀疏矩陣，請(qǐng)給出它的三元組表。A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孫設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（ D ）。A. 3　 B. 2 C. 4 D. 5若以{4,5,6,7,8}作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（ C ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC1樹最適合用來表示（ C ）。amp。 A. 每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹　 B. 哈夫曼樹 C. 每個(gè)結(jié)點(diǎn)至多有兩棵子樹的有序樹 D. 每個(gè)結(jié)點(diǎn)只有一棵子樹1用順序存儲(chǔ)的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1..n]中，若結(jié)點(diǎn)R[i]有左孩子，則其左孩子是（ C ）。A. 3　 B. 4 C. 5 D. 62由權(quán)值為3，6，7，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ A ）。（ 錯(cuò) ）在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)做特殊處理。（ 對(duì) ）完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。哈夫曼樹是其樹的帶權(quán)路徑長度 最小 的二叉樹。 void InOrderTraverse(BiTree bt){ if( bt!=NULL ){ InOrderTraverse(btlchild)。 int depth(Bitree *t){ if(t==NULL) return 0。 else return hr+1。 else{ t=(Bitree *)malloc(sizeof(Bitree))。 tleft=t2。void function(Bitree *t){ if(p!=NULL){ function(plchild)?！局R(shí)點(diǎn)：二叉樹前序序列的隱含性質(zhì)：第一個(gè)一定是二叉樹的根，后面緊跟著的是其左子樹的根；二叉樹后序序列的隱含性質(zhì)：最后一個(gè)一定是二叉樹的根，它的緊前一個(gè)是其右子樹的根】答案： 假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：。答案： 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)路徑長度WPL。答案： 有一分電文共使用5個(gè)字符。 答案：先序：FDBACEGIHJ 中序：ABCDEFGHIJ 后序：ACBEDHJIGF六、編程題編寫求一棵二叉樹中結(jié)點(diǎn)總數(shù)的算法。count_preorder(tlchild)。A. 從源點(diǎn)到匯點(diǎn)的最長路徑　 B. 從源點(diǎn)到匯點(diǎn)的最短路徑 C. 最長的回路 D. 最短的回路下面（ B ）可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。A. 對(duì)稱矩陣 B. 零矩陣 C. 上三角矩陣 D. 對(duì)角矩陣當(dāng)利用大小為N的數(shù)組存儲(chǔ)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度是（ B ）。A. 頂點(diǎn)序列 B. 邊序列 C. 權(quán)值總和 D. 邊的條數(shù) 1在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ A ）鄰接點(diǎn)。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 ）。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中：（ D ）。且非0的元素個(gè)數(shù) D. 第i列非165。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 ）。A. 有向圖 B. 無向圖 C. 強(qiáng)連通圖 D. 完全圖2為便于判別有向圖中是否存在回路，可借助于（ D ）。A. k1　 B. k2 C. k1+k2 D. k1k2一個(gè)具有8個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和的差等于（ C ）。答案：極小連通子圖一個(gè)圖的 表示法是惟一的。答案：拓?fù)渑判?已知一個(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 。答案：出度三、判斷題圖的連通分量是無向圖的極小連通子圖。錯(cuò)存儲(chǔ)圖的鄰接矩陣中，鄰接矩。錯(cuò)圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。答案：n*(n1)/2 已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 。答案：深度優(yōu)先搜索在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于 。A. 通過該頂點(diǎn)的簡單路徑數(shù) B. 與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù) C. 與該頂點(diǎn)連通的頂點(diǎn)數(shù) D. 通過該頂點(diǎn)的回路數(shù)二、填空題n個(gè)頂點(diǎn)的連通圖至少有 邊。A. 只有一棵　 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在2已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（ B ）。 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ù)為（ B ）。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層次遍歷一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有（ B ）條邊。的元素之和 B. 第i列非165。 B. 有一個(gè) C. 一定有多個(gè) D. 有一個(gè)或多個(gè)1在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ B ）倍。V2,E1205。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é)果序列是（ B ）。 A. 第i行非無窮的元素之和　 B. 第i列非無窮的元素個(gè)數(shù)之和 C. 第i行非無窮且非0的元素個(gè)數(shù) D. 第i行與第i列非無窮且非0的元素之和采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類似于二叉樹的（ B ）。A. n B. n2 C. n1 D. (n1)2如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（ B ）。（以先序遍歷的方法為例）void count_preorder(Bitree *t, int *n) { if(t!=NULL){*n++。答案：1畫出與下圖所示的森林相對(duì)應(yīng)的二叉樹，并指出森林中的葉子結(jié)點(diǎn)在二叉樹中具有什么特點(diǎn)。畫出二叉樹的形態(tài)。答案： 已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。 printf(“%d”,pdata)。 } return(t)。 t1=function(btleft)。 Bitree *function(Bitree *bt){ Bitree *t,*t1,*t2。 hr= depth(trchild) 。 InOrderTraverse(btrchild) 。樹內(nèi)各結(jié)點(diǎn)度的 最大值 稱為樹的度。log2nlog2n（ 對(duì) ）中序遍歷一棵二叉排序樹的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列。A. 度為2的樹是二叉樹 B. 度為2的有序樹是二叉樹 C. 子樹有嚴(yán)格左右之分的樹是二叉樹 D. 子樹有嚴(yán)格左右之分，且度不超過2的樹是二叉樹樹的先根序列等同于與該樹對(duì)應(yīng)的二叉樹的（ A ）。A. 不發(fā)生改變　 B. 發(fā)生改變 C. 不能確定 D. 以上都不對(duì)1假定在一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ B ）個(gè)。 A. A*B+C/DE+F B. AB*C+D/EF+ C. ABC+*DEF+/ D. ABCDED*+/+1在線索二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是（ B ）。A. 98　 B. 99 C. 50 D. 48表達(dá)式a*(b+c)d的后綴表達(dá)式是（ B ）。 A. 31 B. 32 C. 33 D. 16由二叉樹的前序和后序遍歷序列（ B ）惟一確定這棵二叉樹。A. 2k B. 2k1 C. 2k1 D. 2k1用順序存儲(chǔ)的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點(diǎn)R[i]有右孩子，則其右孩子是（ B ）。二維數(shù)組，可以按照 按行序?yàn)橹骱桶戳行驗(yàn)橹?兩種不同的存儲(chǔ)方式。（ 錯(cuò) ）廣義表的長度是指廣義表中括號(hào)嵌套的層數(shù)。A. 由0個(gè)或多個(gè)原子或子表構(gòu)成的有限序列 B. 至少有一個(gè)元素是子表 C. 不能遞歸定義 D. 不能為空表1對(duì)廣義表L=((a,b),((c,d),(e,f)))執(zhí)行head(tail(head(tail(L))))操作的結(jié)果是（ D ）。A. i(i1)/2+j1 B. i(i1)/2+j C. i(i+1)/2+j1 D. i(i+1)/2+j1廣義表A=((a),a)的表頭是（ B ）。A. b,c B. (b,c) C. c D. (c)常對(duì)數(shù)組進(jìn)行兩種基本操作是（ C ）。A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子數(shù)組A[0..5,0..6]的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[5][5]的地址是（ A ）。}答案：串的模式匹配算法第五章 數(shù)組和廣義表一、選擇題設(shè)廣義表L=((a，b，c))，則L的長度和深度分別為（ C ）。 }else{ i=ij+1。 while(islenamp。i++) if(sdata[i]!=s2data[i]) return s1data[i]s2data[i]。 for(i=0。