2022年東大18秋學(xué)期《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線作業(yè)3

1、 單項題 1: 下面的說法中正確選項 1 任何一棵二叉樹的葉子節(jié)點在三種遍歷中的相對次序不變； 2 按二叉樹定義,具有三個節(jié)點的二叉樹共有 6 種；A: 1, 2 B: 1 C: 2 , 2 都錯 D: 1 正確答案： 單項題 2: n 個頂點的有向完全圖中含有向邊的數(shù)目最多為 A: n-1 B: n C: nn-1/2 D: nn-1 正確答案： 單項題 3: 深度為 h 的滿 m叉樹的第 k 層的結(jié)點 1=k=h 數(shù)有 A: mk-1 B: mk-1 C: mh-1 D: mh-1 正確答案： 單項題 4: 下面關(guān)于線性表的表達中,錯誤選項 A: 線性表采納次序儲備,必需占用一片連續(xù)的儲備

2、單元；B: 線性表采納次序儲備,便于進行插入和刪除操作；C: 線性表采納儲備,不必占用一片連續(xù)的儲備單元；D: 線性表采納儲備,便于插入和刪除操作；正確答案： 單項題 5: 在運算機內(nèi)實現(xiàn)遞歸算法時所需的幫助數(shù)據(jù)結(jié)構(gòu)是 A: 棧 B: 隊列 C: 樹 D: 圖 正確答案： 單項題 6: 在目標(biāo)串 T 0.n-1 = xwxxyxy 中,對模式串 結(jié)果是 A: 1 B: 2 C: 3 D: 5 P0.m-1 = xy 進行子串定位操作的正確答案： 單項題 7: 設(shè)有一個次序棧,6 個元素 1、2 、3、4、5、6 依次入棧,假如6 個元素出棧的次序是2、3、4、6、5、1,就棧的容量至少應(yīng)當(dāng)是

3、A: 2 B: 3 C: 5 D: 6 正確答案： 單項題 8: 如長度為 n 的線性表采納次序儲備結(jié)構(gòu),在其第 度為 A: O0 B: O1 C: On D: On2 正確答案： 單項題 9: i 個位置插入一個新元素的算法的時間復(fù)雜如采納孩子兄弟鏈表作為樹的儲備結(jié)構(gòu),就樹的后序遍歷應(yīng)采納二叉樹的 A: 層次遍歷算法 B: 前序遍歷算法 C: 中序遍歷算法 D: 后序遍歷算法正確答案： 單項題 10: 一棵樹高為 K 的完全二叉樹至少的結(jié)點是 A: 2k 1 B: 2k-1 1 C: 2k-1 D: 2k 正確答案： 單項題 11: 一個含 n 個頂點和 e 條弧的有向圖以鄰接矩陣表示法為儲

4、備結(jié)構(gòu),就運算該有向圖中某個頂點出度的時間復(fù)雜度為 A: On B: Oe C: On+e D: On2 正確答案： 單項題 12: for（i=0 ；im；i+ ） for（ j=0 ；jt ；j+ ）ci j =0；for （i=0 ；im； i+ ）for （j=0 ；jt ； j+ ）for （k=0；kn； k+）ci j =c i j +a i k*bk j ；上列程序的時間復(fù)雜度為 A: O（m+n t ）B: O（m+n+t）C: O （m n t ）D: O （m t+n ）正確答案： 單項題 13: 如在 9 階 B- 樹中插入關(guān)鍵字引起結(jié)點分裂,就該結(jié)點在插入前含有的關(guān)鍵

5、字個數(shù)為 A: 4 B: 5 C: 8 D: 9 正確答案： 單項題 14: 對于哈希函數(shù) Hkey=key%13, 被稱為同義詞的關(guān)鍵字是 A: 35 和 41 B: 23 和 39 C: 15 和 44 D: 25 和 51 正確答案： 單項題 15: 已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35,其中每相鄰兩個為有序子序列；對這些子序列進行一趟兩兩歸并的結(jié)果是A: .25,36,48,72,23,40,79,82,16,35 B: .25,36,48,72,16,23,40,79,82,35 C: .25,36,48,72,16,23,35,40,79,82

6、 D: .16,23,25,35,36,40,48,72,79,82 正確答案： 單項題 16: 含 n 個關(guān)鍵字的二叉排序樹的平均查找長度主要取決于 A: 關(guān)鍵字的個數(shù) B: 樹的形狀 C: 關(guān)鍵字的取值 X圍 D: 關(guān)鍵字的數(shù)據(jù)類型 正確答案： 單項題 17: 用 DFS遍歷一個無環(huán)有向圖,并在 列是 A: 逆拓?fù)溆行?B: 拓?fù)溆行?C: 無序的DFS算法退棧返回時打印相應(yīng)的頂點,就輸出的頂點序D: A 和 B 正確答案： 單項題 18: 設(shè)樹 T的度為 4,其中度為1, 2,3 和 4 的結(jié)點個數(shù)分別為4,2,1,1 就 T 中的葉子數(shù)為A: 5 B: 6 C: 7 D: 8 正確答案

7、： 單項題 19: 某二叉樹的先序序列和后序序列正好相反,就該二叉樹的特點肯定是 A: 空或只有一個結(jié)點 B: 高度等于其結(jié)點數(shù) C: 任一結(jié)點無左孩子 D: 任一結(jié)點無右孩子 正確答案： 單項題 20: 無向圖中一個頂點的度是指圖中 A: 通過該頂點的簡潔路徑數(shù) B: 與該頂點相鄰接的頂點數(shù) C: 通過該頂點的回路數(shù) D: 與該頂點連通的頂點數(shù) 正確答案： 單項題 1: 下面的說法中正確選項 1 任何一棵二叉樹的葉子節(jié)點在三種遍歷中的相對次序不變； 2 按二叉樹定義,具有三個節(jié)點的二叉樹共有 6 種；A: 1, 2 B: 1 C: 2 D: 1, 2 都錯 正確答案： 單項題 2: n 個頂

8、點的有向完全圖中含有向邊的數(shù)目最多為 A: n-1 B: n C: nn-1/2 D: nn-1 正確答案： 單項題 3: 深度為 h 的滿 m叉樹的第 k 層的結(jié)點 1=k=h 數(shù)有 A: mk-1 B: mk-1 C: mh-1 D: mh-1 正確答案： 單項題 4: 下面關(guān)于線性表的表達中,錯誤選項 A: 線性表采納次序儲備,必需占用一片連續(xù)的儲備單元；B: 線性表采納次序儲備,便于進行插入和刪除操作；C: 線性表采納儲備,不必占用一片連續(xù)的儲備單元；D: 線性表采納儲備,便于插入和刪除操作；正確答案： 單項題 5: 在運算機內(nèi)實現(xiàn)遞歸算法時所需的幫助數(shù)據(jù)結(jié)構(gòu)是 A: 棧 B: 隊列

9、C: 樹 D: 圖 正確答案： 單項題 6: 在目標(biāo)串 T 0.n-1 = xwxxyxy 中,對模式串 結(jié)果是 A: 1 B: 2 C: 3 D: 5 正確答案： 單項題 7: P0.m-1 = xy 進行子串定位操作的設(shè)有一個次序棧,6 個元素 1、2 、3、4、5、6 依次入棧,假如6 個元素出棧的次序是2、3、4、6、5、1,就棧的容量至少應(yīng)當(dāng)是 A: 2 B: 3 C: 5 D: 6 正確答案： 單項題 8: 如長度為 n 的線性表采納次序儲備結(jié)構(gòu),在其第 度為 A: O0 B: O1 C: On D: On2 正確答案： 單項題 9: i 個位置插入一個新元素的算法的時間復(fù)雜如采納

10、孩子兄弟鏈表作為樹的儲備結(jié)構(gòu),就樹的后序遍歷應(yīng)采納二叉樹的 A: 層次遍歷算法 B: 前序遍歷算法C: 中序遍歷算法 D: 后序遍歷算法 正確答案： 單項題 10: 一棵樹高為 K 的完全二叉樹至少的結(jié)點是 A: 2k 1 B: 2k-1 1 C: 2k-1 D: 2k 正確答案： 單項題 11: 一個含 n 個頂點和 e 條弧的有向圖以鄰接矩陣表示法為儲備結(jié)構(gòu),就運算該有向圖中某個頂 點出度的時間復(fù)雜度為A: On B: Oe C: On+e D: On2 正確答案： 單項題 12: for（i=0 ；im；i+ ） for（ j=0 ；jt ；j+ ）ci j =0；for （i=0 ；i

11、m； i+ ）for （j=0 ；jt ； j+ ）for （k=0；kn； k+）ci j =c i j +a i k*bk j ；上列程序的時間復(fù)雜度為 A: O（m+n t ）B: O（m+n+t）C: O （ m n t ）D: O （ m t+n ）正確答案： 單項題 13: 如在 9 階 B- 樹中插入關(guān)鍵字引起結(jié)點分裂,就該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為 A: 4 B: 5 C: 8 D: 9 正確答案： 單項題 14: 對于哈希函數(shù) Hkey=key%13, 被稱為同義詞的關(guān)鍵字是 A: 35 和 41 B: 23 和 39 C: 15 和 44 D: 25 和 51 正確答案

12、： 單項題 15: 已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35,其中每相鄰兩個為有序子序列；對這些子序列進行一趟兩兩歸并的結(jié)果是 A: .25,36,48,72,23,40,79,82,16,35 B: .25,36,48,72,16,23,40,79,82,35 C: .25,36,48,72,16,23,35,40,79,82 D: .16,23,25,35,36,40,48,72,79,82 正確答案： 單項題 16: 含 n 個關(guān)鍵字的二叉排序樹的平均查找長度主要取決于 A: 關(guān)鍵字的個數(shù) B: 樹的形狀 C: 關(guān)鍵字的取值 X圍 D: 關(guān)鍵字的數(shù)據(jù)類型 正確答案： 單項題 17: 用 DFS遍歷一個無環(huán)有向圖,并在 列是 A: 逆拓?fù)溆行?B: 拓?fù)溆行?C: 無序的 D: A 和 B 正確答案： 單項題 18: DFS算法退棧返回時打印相應(yīng)的頂點,就輸出的頂點序設(shè)樹 T的度為 4,其中度為1, 2,3 和 4 的結(jié)點個數(shù)分別為4,2,1,1 就 T 中的葉子數(shù)為A: