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

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

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

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

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

5、1)2 C. n-1 D. n 18、判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?還可以利用（）。選擇一項(xiàng)：A. 求關(guān)鍵路徑的方法 B. 求最短路徑的Dijkstm方法 C. 深度優(yōu)先遍歷算法D. 寬度優(yōu)先遍歷算法 19、下列序列不是圖5的拓?fù)溆行蛐蛄械氖牵哼x擇一項(xiàng)：A. 1 5 6 2 3 4 B. 1 5 2 3 6 4 C. 5 6 1 2 3 4 D. 1 2 5 6 3 4 20、對(duì)含有（ ）個(gè)結(jié)點(diǎn)的非空二叉樹，采用任何一種遍歷方式，其結(jié)點(diǎn)的訪問序列均相同選擇一項(xiàng)：A. 不存在這樣的二叉樹 B. 0 C. 2 D. 1 21、具有6個(gè)頂點(diǎn)的無向圖至少有（）條邊才可能是一個(gè)連

6、通圖。選擇一項(xiàng)：A. 5 B. 8 C. 7 D. 6 22、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。選擇一項(xiàng)：A. 后序遍歷 B. 先序遍歷 C. 按層遍歷 D. 中序遍歷 23、一棵深度為5的滿二叉樹，應(yīng)該有多少個(gè)結(jié)點(diǎn)（ ）選擇一項(xiàng)：A. 32 B. 31 C. 17 D. 16 24、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。選擇一項(xiàng)：A. 按層遍歷 B. 先序遍歷 C. 中序遍歷 D. 后序遍歷 25、沒有度為1的結(jié)點(diǎn)的二叉樹，被稱之為嚴(yán)格二叉樹。下列不是嚴(yán)格二叉樹的是：選擇一項(xiàng)：A. 滿二叉樹 B. 哈夫曼樹 C. 所有非終端結(jié)點(diǎn)都有非空的左右子樹的二叉

7、樹 D. 完全二叉樹 26、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結(jié)點(diǎn)總數(shù)是（ ）選擇一項(xiàng)：A. e/2 B. n+e C. e D. 2e 27、一個(gè)所有非終端結(jié)點(diǎn)都有非空的左右子樹的二叉樹，葉子結(jié)點(diǎn)的個(gè)數(shù)為n，那么二叉樹上的結(jié)點(diǎn)總數(shù)為（ ）選擇一項(xiàng)：A. 2n-1 B. 2n+1 C. 2n D. 2n-2 28、用Prim算法求下列連通的帶權(quán)圖（圖4）的最小代價(jià)生成樹，在算法執(zhí)行的某刻，已選取的頂點(diǎn)集合U1，2，3，邊的集合TE（1，2），（2，3），要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從（）組中選取。選擇一項(xiàng)：A. （1，4），（3，4），（3，5），（2，4） B. （3，4），（3，5），（4，5），（1，4） C. （4，5），（1，3），（3，5） D. （1，2），（2，3），（3，5