上交大---網(wǎng)絡(luò)教育學(xué)院---數(shù)據(jù)結(jié)構(gòu)--第三次作業(yè)

1、-第三次作業(yè)下列說法中正確的是二叉樹的線索化就是對二叉鏈表中的 n個空鏈域進(jìn)行線索化; 二叉樹一定是度為 2的樹； 一個度為2的樹一定為二叉樹；樹和圖1、A.海交通大學(xué)網(wǎng)絡(luò)教育學(xué)院-數(shù)據(jù)結(jié)構(gòu)B.C.D. 任何一棵樹都可以按照孩子兄弟法轉(zhuǎn)化為一棵二叉樹，而且這個二叉樹的根結(jié)點(diǎn)的右孩 子一定不存在。# 2、四組編碼中，哪一組是前綴碼A. 0,1,00,11B. 0,10,110,111 閉C. 00,01,001,0001D. 0,01,10,113、對于圖1示的二叉樹，先根序列和后根序列分別為:B. ABCC. ABCD. ACBCBA第BCABCA 4、n個結(jié)點(diǎn)的線索二叉樹中的線索數(shù)目為:A.

2、 (n-1)個B. ( n+1)個 #C. (n+2 )個D. n個 5、哈夫曼樹的帶權(quán)路徑長度是指: 選擇一項：A. 所有結(jié)點(diǎn)的權(quán)值之和B. 除根結(jié)點(diǎn)之外所有結(jié)點(diǎn)權(quán)值之和C. 所有葉子結(jié)點(diǎn)帶權(quán)路徑長度之和#D. 帶權(quán)結(jié)點(diǎn)的值6、圖2示的二叉樹的帶權(quán)路徑長度為:25B. 46C. 48圖2A. 36D. 47 7、具有4個頂點(diǎn)的無向完全圖有（）條邊。A. 16B. 6 #C. 12D. 20 8、在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。 選擇一項：A. 1/2B. 1 #C. 4D. 2 9、一個深度為4的完全二叉樹，至少有多少個結(jié)點(diǎn):A. 15B. 7C. 8 #D

3、. 1410、在一個具有n個頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）條邊。A. n-1 #B. n+1C. n/2D. n11、有n個結(jié)點(diǎn)的二叉樹的二叉鏈表存儲結(jié)構(gòu)中有（）個空鏈域。A. 2nB. n-1C. nD. n+1 #12、已知圖6所示的圖，若從頂點(diǎn) A出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的遍歷 序列為：圖6A. A,E,D,F,C,B #B. A,C,F,E,B,DC. A,B,E,C,D,FD. A,E,B,C,F,D13、已知如圖3示的哈夫曼樹，那么電文 CDAA的編碼是:A. 11111100B. 010110111C. 11011100#D. 11010014、一個有

4、n個頂點(diǎn)的無向圖最多有（）條邊。 選擇一項：A. n(n-1)B. n(n-1)/2#C. nD. 2n 15、對于一個具有n個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（） 選擇一項：A. n-1B. n #C. n+1D. n+e16、將含有41個結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號，那么編號為21的雙親結(jié)點(diǎn)編號為：選擇一項：A. 10 就B. 20C. 41D. 1117、對于一個具有n個頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大?。ǎ?選擇一項：A. n2 #B. （n-1）2C. n-1D. n,還可以利用（）。18

5、、判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?選擇一項：A. 求關(guān)鍵路徑的方法#B. 求最短路徑的 Dijkstm方法C. 深度優(yōu)先遍歷算法D. 寬度優(yōu)先遍歷算法選擇一項:A. 1 5 6 2 3 4B. 1 5 2 3 6 4C. 5 6 1 2 3 4D. 1 2 5 6 3 4）個結(jié)點(diǎn)的非空二叉樹，采用任何一種遍歷方式，其結(jié)點(diǎn)的訪問序列均相同20、對含有（ 選擇一項：A. 不存在這樣的二叉樹B. 0C. 2D. 1譜21、具有6個頂點(diǎn)的無向圖至少有（）條邊才可能是一個連通圖。 選擇一項：A. 5我B. 8C. 7D. 622、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（

6、）。選擇一項：A.后序遍歷B.C.D.先序遍歷#按層遍歷 中序遍歷23、一棵深度為5的滿二叉樹，應(yīng)該有多少個結(jié)點(diǎn)（）選擇一項：A. 32B. 31 耆C. 17D. 1624、采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。 選擇一項：按層遍歷#先序遍歷中序遍歷后序遍歷A.B.C.D.25、沒有度為1的結(jié)點(diǎn)的二叉樹，被稱之為嚴(yán)格二叉樹。下列不是嚴(yán)格二叉樹的是: 選擇一項：滿二叉樹哈夫曼樹所有非終端結(jié)點(diǎn)都有非空的左右子樹的二叉樹完全二叉樹#A.B.C.D.26、對于一個具有 n個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結(jié) 點(diǎn)總數(shù)是（）選擇一項：A. e/2B. n+eC.

7、 eD. 2e *n，那么二叉樹27、一個所有非終端結(jié)點(diǎn)都有非空的左右子樹的二叉樹，葉子結(jié)點(diǎn)的個數(shù)為 上的結(jié)點(diǎn)總數(shù)為（）選擇一項：A. 2n-1B. 2n+1C. 2nD. 2n-2）組中選取。應(yīng)當(dāng)從（A. B. C. D. (1，(3，(4，(1，4），4），5），2），(3，(3，(1，(2，4），（ 3，5），（ 4，3），（ 3，3），（ 3，5),( 2, 4) /5),( 1 , 4) 5) 5) 在一個有向圖中 選擇一項：29、，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。28、用Prim算法求下列連通的帶權(quán)圖（圖 4）的最小代價生成樹，在算法執(zhí)行的某刻，已 選取的頂點(diǎn)集合 U= 1 , 2, 3，邊的集合