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

上交大---網(wǎng)絡(luò)教育學(xué)院---數(shù)據(jù)結(jié)構(gòu)--第三次作業(yè)上海交通大學(xué)網(wǎng)絡(luò)教育學(xué)院----數(shù)據(jù)結(jié)構(gòu)------第三次作業(yè)------------------樹和圖1、下列說法中正確的是A.二叉樹的線索化就是對二叉鏈表中的n個空鏈域進行線索化；B.二叉樹一定是度為2的樹；C.一個度為2的樹一定為二叉樹；D.任何一棵樹都可以按照孩子兄弟法轉(zhuǎn)化為一棵二叉樹，而且這個二叉樹的根結(jié)點的右孩子一定不存在。2、四組編碼中，哪一組是前綴碼A.{0,1,00,11}B.{0,10,110,111}C.{00,01,001,0001}D.{0,01,10,11}A.所有結(jié)點的權(quán)值之和B.除根結(jié)點之外所有結(jié)點權(quán)值之和C.所有葉子結(jié)點帶權(quán)路徑長度之和D.帶權(quán)結(jié)點的值6、圖2示的二叉樹的帶權(quán)路徑長度為：

A.36B.46C.48D.477、具有4個頂點的無向完全圖有（）條邊。A.16B.6C.12D.208、在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的（）倍。選擇一項：A.1/2B.1C.4D.29、一個深度為4的完全二叉樹，至少有多少個結(jié)點：A.15B.7C.8D.1410、在一個具有n個頂點的無向圖中,要連通全部頂點至少需要（）條邊。A.n-1B.n+1C.n/2D.n11、有n個結(jié)點的二叉樹的二叉鏈表存儲結(jié)構(gòu)中有()個空鏈域。A.2nB.n-1C.nD.n+112、已知圖6所示的圖，若從頂點A出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的遍歷序列為：

A.A,E,D,F,C,BB.A,C,F,E,B,DC.A,B,E,C,D,FD.A,E,B,C,F,D13、已知如圖3示的哈夫曼樹，那么電文CDAA的編碼是：

A.11111100B.010110111C.11011100D.11010014、一個有n個頂點的無向圖最多有（）條邊。選擇一項：A.n(n-1)B.n(n-1)/2C.nD.2n15、對于一個具有n個頂點和e條邊的無向圖,若采用鄰接表表示,則表頭向量的大小為（）選擇一項：A.n-1B.nC.n+1D.n+e16、將含有41個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點編號，那么編號為21的雙親結(jié)點編號為：選擇一項：A.10B.20C.41D.1117、對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大?。ǎ┻x擇一項：A.n2B.(n-1)2C.n-1D.n18、判定一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用（）。選擇一項：A.求關(guān)鍵路徑的方法B.求最短路徑的Dijkstm方法C.深度優(yōu)先遍歷算法D.寬度優(yōu)先遍歷算法19、下列序列不是圖5的拓撲有序序列的是：

選擇一項：A.156234B.152364C.561234D.12563420、對含有（）個結(jié)點的非空二叉樹，采用任何一種遍歷方式，其結(jié)點的訪問序列均相同選擇一項：A.不存在這樣的二叉樹B.0C.2D.121、具有6個頂點的無向圖至少有（）條邊才可能是一個連通圖。選擇一項：A.5B.8C.7D.622、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。選擇一項：A.后序遍歷B.先序遍歷C.按層遍歷D.中序遍歷23、一棵深度為5的滿二叉樹，應(yīng)該有多少個結(jié)點（）選擇一項：A.32B.31C.17D.1624、采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。選擇一項：A.按層遍歷B.先序遍歷C.中序遍歷D.后序遍歷25、沒有度為1的結(jié)點的二叉樹，被稱之為嚴(yán)格二叉樹。下列不是嚴(yán)格二叉樹的是：選擇一項：A.滿二叉樹B.哈夫曼樹C.所有非終端結(jié)點都有非空的左右子樹的二叉樹D.完全二叉樹26、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結(jié)點總數(shù)是（）選擇一項：A.e/2B.n+eC.eD.2e27、一個所有非終端結(jié)點都有非空的左右子樹的二叉樹，葉子結(jié)點的個數(shù)為n，那么二叉樹上的結(jié)點總數(shù)為（）選擇一項：A.2n-1B.2n+1C.2nD.2n-228、用Prim算法求下列連通的帶權(quán)圖（圖4）的最小代價生成樹，在算法執(zhí)行的某刻，已選取的頂點集合U＝{1，2，3}，邊的集合TE＝{（1，2），（2，3）}，要選取下一條權(quán)值最小的邊，應(yīng)當(dā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）}29