297
技術社區[雲棲]
mooc 第五章 習題
-
Q1
您已經提交0次，共有2次提交機會。某二叉樹有n個節點，高度為h。在其中插入一個新的節點，高度發生改變的節點個數最多為：
O(1)O(n)O(h)O(hlog2(n)) -
Q2
您已經提交0次，共有2次提交機會。高度為h的完全二叉樹可能有多少個節點?
2h+12h2h−1−12h−1 -
Q3
您已經提交0次，共有2次提交機會。下列關於樹的命題中錯誤的是：
頂點數為n的樹的邊數為n-1。樹中任意兩頂點之間存在唯一路徑。在樹中添加任一條邊都會破壞樹的結構。在樹中刪除任一條邊得到的還是樹。 -
Q4
您已經提交0次，共有2次提交機會。並查集是一種用於表示不相交集合的數據結構，支持以下操作：
- Union(x, y): 將元素x和y所在的集合合並
- Find(x): 返回元素x所在集合（實際上是返回該集合的一個代表元）
一種基本的實現是將每一個集合中的元素組織成一棵有根樹，集合中的元素即樹中的節點，選取樹根為該集合的代表元，而整個並查集就是由若幹棵樹組成的森林。接口實現的方法是：
- Union(x, y): 將x所在樹的根節點的父親設為y所在樹的根節點，從而將它們合並成一棵樹
- Find(x): 返回節點x所在樹的根節點。
例子：下圖中的並查集原先有兩棵表示集合的樹{c,h,b,e}和{f,d,g}，調用Union(h, f)後得到了右邊的樹，如果此時再調用Find(e)會返回f。
並查集中的樹最適合用什麼方法表示：
父節點法孩子節點法長子-兄弟法鄰接表法 -
Q5
您已經提交0次，共有2次提交機會。從n個節點的二叉樹的葉節點u逐個節點地上溯到根節點的過程中，以下說法中錯誤的是：
經過的節點都是u的祖先。最壞時間複雜度為O(n)經過的路徑是唯一確定的每上溯一層，當前節點的深度減小1，而高度增加1。-
Q6
您已經提交0次，共有2次提交機會。對二叉樹進行中序遍曆，節點v在中序遍曆下的後繼為（假設v的後繼存在）：
其右子樹中第一個被訪問的節點其左子樹中第一個被訪問的節點其右子樹中第一個被訪問的節點或v的某個祖先其右子樹中第一個被訪問的節點或其左子樹中的某個節點 -
Q7
您已經提交0次，共有2次提交機會。與先序、中序遍曆類似，以左子->右子->根節點的順序來訪問二叉樹稱為後序遍曆。後序遍曆中第一個被訪問的節點是：
左側鏈中最深的節點根節點右側鏈中最深的節點以上皆不是 -
Q8
您已經提交0次，共有2次提交機會。對二叉樹進行先序遍曆，u和v是左側鏈上兩個節點，且u是v的祖先，x、y分別是u和v的右子，試問這四個節點被訪問的順序是：
y,v,x,ux,y,v,uu,v,y,x無法確定 -
Q9
您已經提交0次，共有2次提交機會。關於二叉樹遍曆序列之間關係的說法錯誤的是：
已知先序遍曆序列和中序遍曆序列可以確定後序遍曆序列已知中序遍曆序列和後序遍曆序列可以確定先序遍曆序列已知中序遍曆序列和後序遍曆序列可以確定層次遍曆序列已知先序遍曆序列和後序遍曆序列可以確定中序遍曆序列 -
Q10
您已經提交0次，共有2次提交機會。借助隊列對二叉樹進行層次遍曆時,任意時刻隊列中的節點滿足：
均位於從根節點到當前節點的路徑上均是當前節點的後代高度相差不超過1深度相差不超過1
-
最後更新：2017-04-03 14:54:35