【HBU】數據結構月考2019-11選擇題
- 2019 年 12 月 3 日
- 筆記
版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY 版權協議，轉載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/shiliang97/article/details/103315072
若一棵二叉樹的後序遍歷序列是{ 1, 3, 2, 6, 5, 7, 4 }，中序遍歷序列是{ 1, 2, 3, 4, 5, 6, 7 }，則下列哪句是錯的？(2分)
- 這是一棵完全二叉樹
- 2是1和3的父結點
- 這是一棵二叉搜索樹
- 7是5的父結點
還原，這棵樹不是完全二叉樹
樹最適合於用來表示 (2分)
- 有序數據元素
- 無序數據元素
- 元素之間無聯繫的數據
- 元素之間具有分支層次關係的數據
看圖不覺得有層次嗎？
在AOE網中，什麼是關鍵路徑？ (2分)
- 最短迴路
- 最長迴路
- 從第一個事件到最後一個事件的最短路徑
- 從第一個事件到最後一個事件的最長路徑
關鍵看他有多長，所以就是最長路徑。
任何一個帶權無向連通圖的最小生成樹—— (2分)
- 是唯一的
- 是不唯一的
- 有可能不唯一
- 有可能不存在
選的點不一樣，根都不一樣，肯定是不唯一啊
給定有向圖的鄰接矩陣如下：
頂點2（編號從0開始）的出度和入度分別是：(2分)
- 3, 1
- 1, 3
- 0, 2
- 2, 0
橫著看是出度，都是 0 ，豎著看是入度，有倆，從0開始數，第二行，就是定點2作為起點的邊。
設一段文本中包含4個對象{a,b,c,d}，其出現次數相應為{4,2,5,1}，則該段文本的哈夫曼編碼比採用等長方式的編碼節省了多少位數？ (2分)
- 0
- 2
- 4
- 5
節省了倆，畫圖看看。
5*1+4*2+2*3+1*3=22
4*2+2*2+5*2+1*2=24,差2
設樹T的度為4，其中度為1、2、3、4的結點個數分別為4、2、1、1。則T中有多少個葉子結點？ (2分)
- 4
- 6
- 8
- 10
先序遍歷圖示二叉樹的結果為 (2分)
- A，B，C，D，H，E，I，F，G
- A，B，D，H，I，E，C，F，G
- H，D，I，B，E，A，F，C，G
- H，I，D，B，E，F，G，A，C
先序，A，然後左B，然後左D。選B
下圖為一個AOV網，其可能的拓撲有序序列為： (2分)
- ACBDEF
- ABCEFD
- ABCDFE
- ABCEDF
作者: DS課程組
拓撲排序只輸出沒有入度的點，輸出後刪除點，從刪除A開始
A選項，A B C 這時，D有入度，為ED，不對
B選項，A B C E 這時，F有入度 DF，不對
C選項，ABCD這時，F有入度，EF，不對
D選項，沒問題。
我們用一個有向圖來表示航空公司所有航班的航線。下列哪種演算法最適合解決找給定兩城市間最經濟的飛行路線問題？ (2分)
- Dijkstra演算法 （最短路徑）
- Kruskal演算法 （Prim演算法和Kruskal演算法最小生成樹的演算法）
- 深度優先搜索（深度優先遍歷演算法和廣度優先遍歷演算法 是圖的遍歷演算法）
- 拓撲排序演算法（回溯法是求解遞歸過程的一種重要方法）
