第三次作業樹和圖
1、下列說法中正確的是
a. 二叉樹的線索化就是對二叉鍊錶中的n個空鏈域進行線索化;
b. 二叉樹一定是度為2的樹;
c. 乙個度為2的樹一定為二叉樹;
d. 任何一棵樹都可以按照孩子兄弟法轉化為一棵二叉樹,而且這個二叉樹的根結點的右孩子一定不存在。
2、四組編碼中,哪一組是字首碼
a.b.
c.d.
3、對於圖1示的二叉樹,先根序列和後根序列分別為:
a. acb和cba
b. abc和cba
c. abc和bca
d. acb和 bca
4、n個結點的線索二叉樹中的線索數目為:
a. (n-1)個
b. (n+1)個
c. (n+2)個
d. n個
5、哈夫曼樹的帶權路徑長度是指:
選擇一項:
a. 所有結點的權值之和
b. 除根結點之外所有結點權值之和
c. 所有葉子結點帶權路徑長度之和
d. 帶權結點的值
6、圖2示的二叉樹的帶權路徑長度為:
a. 36
b. 46
c. 48
d. 47
7、具有4個頂點的無向完全圖有()條邊。
a. 16
b. 6
c. 12
d. 20
8、在乙個有向圖中,所有頂點的入度之和等於所有頂點的出度之和的()倍。
選擇一項:
a. 1/2
b. 1
c. 4
d. 2
9、乙個深度為4的完全二叉樹,至少有多少個結點:
a. 15
b. 7
c. 8
d. 14
10、在乙個具有n個頂點的無向圖中,要連通全部頂點至少需要()條邊。
a. n-1
b. n+1
c. n/2
d. n
11、有n個結點的二叉樹的二叉鍊錶儲存結構中有( )個空鏈域。
a. 2n
b. n-1
c. n
d. n+1
12、已知圖6所示的圖,若從頂點a出發按深度優先搜尋法進行遍歷,則可能得到的遍歷序列為:
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. 11011100
d. 110100
14、乙個有n個頂點的無向圖最多有()條邊。
選擇一項:
a. n(n-1)
b. n(n-1)/2
c. n
d. 2n
15、對於乙個具有n個頂點和e條邊的無向圖,若採用鄰接表表示,則表頭向量的大小為()
選擇一項:
a. n-1
b. n
c. n+1
d. n+e
16、將含有41個結點的完全二叉樹從根結點開始編號,根為1號,後面按從上到下、從左到右的順序對結點編號,那麼編號為21的雙親結點編號為:
選擇一項:
a. 10
b. 20
c. 41
d. 11
17、對於乙個具有n個頂點的無向圖,若採用鄰接矩陣表示,則該矩陣的大小()
選擇一項:
a. n2
b. (n-1)2
c. n-1
d. n
18、判定乙個有向圖是否存在迴路除了可以利用拓撲排序方法外,還可以利用()。
選擇一項:
a. 求關鍵路徑的方法
b. 求最短路徑的dijkstm方法
c. 深度優先遍歷演算法
d. 寬度優先遍歷演算法
19、下列序列不是圖5的拓撲有序序列的是:
選擇一項:
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、對含有( )個結點的非空二叉樹,採用任何一種遍歷方式,其結點的訪問序列均相同
選擇一項:
a. 不存在這樣的二叉樹
b. 0
c. 2
d. 1
21、具有6個頂點的無向圖至少有()條邊才可能是乙個連通圖。
選擇一項:
a. 5
b. 8
c. 7
d. 6
22、採用鄰接表儲存的圖的深度優先遍歷演算法類似於二叉樹的()。
選擇一項:
a. 後序遍歷
b. 先序遍歷
c. 按層遍歷
d. 中序遍歷
23、一棵深度為5的滿二叉樹,應該有多少個結點( )
選擇一項:
a. 32
b. 31
c. 17
d. 16
24、採用鄰接表儲存的圖的廣度優先遍歷演算法類似於二叉樹的()。
選擇一項:
a. 按層遍歷
b. 先序遍歷
c. 中序遍歷
d. 後序遍歷
25、沒有度為1的結點的二叉樹,被稱之為嚴格二叉樹。下列不是嚴格二叉樹的是:
選擇一項:
a. 滿二叉樹
b. 哈夫曼樹
c. 所有非終端結點都有非空的左右子樹的二叉樹
d. 完全二叉樹
26、對於乙個具有n個頂點和e條邊的無向圖,若採用鄰接表表示,則所有鄰接表中的結點總數是( )
選擇一項:
a. e/2
b. n+e
c. e
d. 2e
27、乙個所有非終端結點都有非空的左右子樹的二叉樹,葉子結點的個數為n,那麼二叉樹上的結點總數為( )
選擇一項:
a. 2n-1
b. 2n+1
c. 2n
d. 2n-2
28、用prim演算法求下列連通的帶權圖(圖4)的最小代價生成樹,在演算法執行的某刻,已選取的頂點集合u=,邊的集合te=,要選取下一條權值最小的邊,應當從( )組中選取。
選擇一項:
a.b.
c.d.
29、在乙個有向圖中,所有頂點的度數之和等於所有邊數的()倍。
選擇一項:
a. 1
b. 2
c. 1/2
d. 4
30、在二叉樹的第i層上至多有( )個結點
選擇一項:
a. 2i-1
b. i+2
c. 2i
d. 2i-2
份考試資料結構第三次作業
一 填空題 共15題 總分30分 1.由 個結點所構成的二叉樹有 5 種形態。本題分數 2 分。2.對不同的關鍵字可能得到同一雜湊位址,即key1 key2,而f key1 f key2 這種現象稱為碰撞 具有相同函式值的關鍵字對該雜湊函式來說稱作 同義詞本題分數 2 分。3.在aoe網中,路徑長度...
資料結構及其演算法第三次作業
1 已知一關鍵碼序列為 3,87,12,61,70,97,26,45。試根據堆排序原理,填寫完整下示各步驟結果。建立堆結構 交換與調整 1 87 70 26 61 45 12 3 97 2 3 61 45 26 3 12 70 87 97 4 5 26 12 3 45 61 70 87 97 6 7...
廣告文案第三次網上作業及答案
03任務 1.1 好的廣告標題一定是 濃眉大眼 的和 強力 推出的。2.2 美國廣告文案大師威廉 伯恩巴克 william bembach 在談到廣告標題寫作時,曾引用一句老話 當你 言之有物時 時,你就會寫得更好。3 廣告的 主要內容 要依靠正文來表達,所以,正文大都占有相當的篇幅,以突出其主體和...