數(shù)據(jù)結(jié)構(gòu)練習2-10答案[1].pdf

1 數(shù)據(jù)結(jié)構(gòu)練習數(shù)據(jù)結(jié)構(gòu)練習 二二 參考參考答案答案 一 填空題 1 若一棵樹的括號表示為 A B E F C G H I J K L D M N 則該樹的度為 1 4 樹的深度為 2 4 樹中葉子結(jié)點的個數(shù)為 3 8 2 一棵滿二叉樹中有 m 個葉子 n 個結(jié)點 深度為 h 請寫出 m n h 之間 關系的表達式 4 n 2h 1 m 2h 1 n n0 n2 2m 1 3 一棵二叉樹中如果有 n 個葉子結(jié)點 則這棵樹上最少有 5 2n 1 個結(jié)點 一棵深度為 k 的完全二叉樹中最少有 2k 1 6 個結(jié)點 最多有 7 2k 1 個 結(jié)點 4 具有 n 個結(jié)點的二叉樹 當它是一棵 8 完全 二叉樹時具有最小高度 9 log2n 1 當它為一棵單支樹時具有高度 10 n 5 對具有n個結(jié)點的完全二叉樹按照層次從上到下 每一層從左到右的次序?qū)?所有結(jié)點進行編號 編號為i的結(jié)點的雙親結(jié)點的編號為 11 i 2 左孩子的編號為 2i 右孩子的編號為 2i 1 6 若具有n個結(jié)點的二叉樹采用二叉鏈表存儲結(jié)構(gòu) 則該鏈表中有 2n 個指 針域 其中有 n 1 個指針域用于鏈接孩子結(jié)點 n 1 個指針域空閑存 放著NULL 7 二叉樹的遍歷方式通常有 先序 中序 后序 和 層序 四種 8 已知二叉樹的前序遍歷序列為ABDCEFG 中序遍歷序列為DBCAFEG 其 后序遍歷序列為 DCBFGEA 9 已知某完全二叉樹采用順序存儲結(jié)構(gòu) 結(jié)點的存放次序為 A B C D E F G H I J 該完全二叉樹的后序序列為 HIDJEBFGCA 10 若具有n個結(jié)點的非空二叉樹有n0個葉結(jié)點 則該二叉樹有 n0 1 個度為 2的結(jié)點 n 2n0 1 個度為1的結(jié)點 11 任何非空樹中有且僅有一個結(jié)點沒有前驅(qū)結(jié)點 該結(jié)點就是樹的 根 度為k的樹中第i層最多有 ki 1 個結(jié)點 i 1 深度為h的k叉樹最 多有 k0 k1 kh 1 個結(jié)點 12 非空二叉樹一共有 4 種基本形態(tài) 第i層最多有 2i 1 個結(jié)點 13 在一棵完全二叉樹中 編號 i 和編號 j 的兩個結(jié)點處于同一層的條件是 log2i log2j 14 有 n 個頂點的強連通圖至少有 7 n 弧 有 n 個頂點的連通圖至少有 8 n 1 邊 15 設無向圖 G 的頂點數(shù)為 n 圖 G 最少有 12 0 邊 最多有 13 n n 1 2 條邊 若邊數(shù)為 e 用鄰接矩陣表示圖 求每一頂點度的時間復雜性為 14 2 O n2 若用鄰接表表示圖 訪問一個頂點的所有鄰接頂點的時間復雜性 為 15 O e 一個有 n 個頂點的有向圖中 最少有 16 0 弧 最多有 17 n n 1 弧 二 選擇題 1 樹型結(jié)構(gòu)最適合用來描述 A 有序的數(shù)據(jù)元素 B 無序的數(shù)據(jù)元素 C 數(shù)據(jù)元素之間具有層次關系的數(shù)據(jù) D 數(shù)據(jù)元素之間沒有關系的數(shù)據(jù) 2 對于一棵具有n個結(jié)點 度為4的樹而言 A 樹的深度最多是n 4 B 樹的深度最多是n 3 C 第i層上最多有4 i 1 個結(jié)點 3 二叉樹為空 意味著二叉樹 A 由一些未賦值的空結(jié)點組成 B 根結(jié)點無子樹 C 不存在 D 沒有結(jié)點 4 按照二叉樹的定義 具有3個結(jié)點的二叉樹有 種形態(tài) 不考慮數(shù)據(jù)信息的 組合情況 A 2 B 3 C 4 D 5 5 若一棵二叉樹具有 10 個度為 2 的結(jié)點 5 個度為 1 的結(jié)點 則度為 0 的結(jié) 點個數(shù)為 A 9 B 11 C 15 D 不確定 6 一個具有 1025 個結(jié)點的二叉樹的高 h 為 A 11 B 10 C 11 1025 D 12 1024 7 若二叉樹的前序序列與后序序列的次序正好相反 則該二叉樹一定是 樹 A 空或僅有一個結(jié)點 B 其分支結(jié)點無左子樹 C 其分支結(jié)點無右子樹 D 其分支結(jié)點的度都為1 8 任何一棵非空二叉樹中的葉結(jié)點在前序遍歷 中序遍歷與后序遍歷中的相 對位置 A 都會發(fā)生改變 B 不會發(fā)生改變 C 有可能會發(fā)生改變 D 部分會發(fā)生改變 9 如圖所示的二叉樹 T2 是由森林 T1 轉(zhuǎn)換而來 的二叉樹 那么森林 T1 有 個葉子結(jié)點 A 4 B 5 C 6 D 7 10 設 n m 為一棵二叉樹上的兩個結(jié)點 在中 序遍歷時 n 在 m 前的條件是 A n 在 m 右方 B n 是 m 祖先 C n 在 m 左方 D n 是 m 子孫 11 一棵二叉樹的先序遍歷序列為 ABCDEFG A BE C D FH GJI 3 它的中序遍歷序列可能是 A CABDEFG B ABCDEFG C DACEFBG D ADCFEGB 12 引入線索二叉樹的目的是 A 加快查找結(jié)點的前驅(qū)或后繼結(jié)點的速度 C 為了能方便找到雙親 B 為了能在二叉樹中方便插入和刪除 D 使二叉樹的遍歷結(jié)果唯一 13 線索二叉樹是一種 結(jié)構(gòu) A 邏輯 B 邏輯和存儲 C 物理 D 線性 14 判斷線索二叉樹中 p 結(jié)點有右孩子結(jié)點的條件是 A p NULL B P rchild NULL C p rtag 0 D p rtag 1 15 n 個結(jié)點的線索二叉樹上含有的線索數(shù)為 A 2n B n 1 C n 1 D n 16 根據(jù)使用頻率為 5 個字符設計的哈夫曼編碼不可能是 A 000 001 010 011 1 B 0000 0001 001 01 1 C 000 001 01 10 11 D 00 100 101 110 111 18 設有 13 個值 用它們組成一棵哈夫曼樹 則該哈夫曼樹共有 個結(jié)點 A 13 B 12 C 26 D 25 19 在一個圖中 所有頂點的度數(shù)之和等于所有邊數(shù)的 倍 A 1 2 B 1 C 2 D 4 20 一個具有n個頂點的無向圖最多有 條邊 A n n 1 2 B n n 1 C n n 1 2 D n2 21 一個具有n個頂點的有向圖最多有 條邊 A n n 1 2 B n n 1 C n n 1 2 D n2 22 在一個具有n個頂點的無向圖中 要連通全部頂點至少需要 條邊 A n B n 1 C n 1 D 2n 23 具有n個頂點的連通圖的生成樹一定有 條邊 A n B n 1 C n 1 D 2n 24 若一個非連通的無向圖最多有28條邊 則該無向圖至少有 個項點 A 6 B 7 C 8 D 9 25 在帶權(quán)圖中 兩個頂點之間的路徑長度是 A 路徑上的頂點數(shù)目 B 路徑上的邊的數(shù)目 C 路徑上頂點和邊的數(shù)目 D 路徑上所有邊上的權(quán)值之和 26 若具有n個頂點的元向圖采用鄰接矩陣存儲方法 該鄰接矩陣一定為一個 A 一般矩陣 B 對稱矩陣 C 對角矩陣 D 稀疏矩陣 27 若圖的鄰接矩陣中主對角線上的元素均為0 其余元素全為1 則可以斷定 4 該圖一定 A 是無向圖 B 是有向圖 C 是完全圖 D 不是帶權(quán)圖 28 有向圖的鄰接表的第i個鏈表中的邊結(jié)點數(shù)目是第i個頂點的 A 度數(shù) B 出度 C 人數(shù) D 邊數(shù) 29 若某圖的鄰接表中的邊結(jié)點數(shù)目為奇數(shù) 則該圖 A 一定有奇數(shù)個頂點 B 一定有偶數(shù)個頂點 C 一定是有向圖 D 可能是無向圖 30 若某圖的鄰接表中的邊結(jié)點數(shù)目為偶數(shù) 則該圖 A 一定是無向圖 B 可能是有向圖 C 可能是無向圖 也可能是有向圖 D 一定有偶數(shù)個頂點 31 若無向圖有k條邊 則相應的鄰接表中就有 個邊結(jié)點 A k 1 B k C 2k D k2 32 若有向圖有k條邊 則相應的鄰接表中就有 個邊結(jié)點 A k 1 B k C 2k D k2 33 對于一個不帶權(quán)的無向圖的鄰接矩陣而言 A 矩陣中非零元素的數(shù)目等于圖中邊的數(shù)目 B 矩陣中非全零的行的數(shù)目等于圖中頂點的數(shù)目 C 第i行的非零元素的數(shù)目與第i列的非零元素的數(shù)目相等 D 第i行與第i列的非零元素的總數(shù)等于第i個頂點的度數(shù) 34 導致圖的遍歷序列不惟一的因素有 A 出發(fā)點不同 遍歷方法不同 B 出發(fā)點不同 存儲結(jié)構(gòu)不同 C 遍歷方法不同 存儲結(jié)構(gòu)不同 D 出發(fā)點不同 存儲結(jié)構(gòu)不同 遍歷方法不同 35 若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索便可以訪問該圖的 所有頂點 則該圖一定是一個 圖 A 非連通 B 連通 C 強連通 D 完全 36 可以進行拓撲排序的圖一定是 A 連通圖 B 帶權(quán)連通圖 C 無回路的圖 D 無回路的有向圖 37 已知某有向圖G V E 其中V v1 v2 v3 v4 v5 v6 E G的拓撲序列 是 A v3 v1 v4 v5 v2 v6 B v3 v4 v1 v5 v2 v6 C v1 v3 v4 v5 v2 v6 D v1 v4 v3 v5 v2 v6 38 下面關于AOE網(wǎng)的敘述中 不正確的是 A 若所有關鍵活動都提前完成 則整個工程一定能夠提前完成 B 即使所有非關鍵活動都未按時完成 整個工程仍有可能按時完成 5 C 任何一個關鍵活動的延期完成 都會導致整個工程的延期完成 D 任何一個關鍵活動的提前完成 都會導致整個工程的提前完成 39 無向圖的鄰接矩陣是一個 A 對稱矩陣 B 零矩陣 C 上三角矩陣 D 對角矩陣 40 如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點 則該圖一定是 A 完全圖 B 連通圖 C 有回路 D 一棵樹 41 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的 算法 A 先序遍歷 B 中序遍歷 C 后序遍歷 D 按層遍歷 42 一個無向連通圖的生成樹是含有該連通圖的全部頂點的 A 極小連通子圖 B 極小子圖 C 極大連通子圖 D 極大子圖 43 任何一個無向連通圖 最小生成樹 A 只有一棵 B 有一棵或多棵 C 一定有多棵 D 可能不存在 44 求最短路徑的 Dijkstra 算法的時間復雜度為 A O n B O n e C O n2 D O n3 45 求最短路徑的 Floyd 算法的時間復雜度為 A O n B O ne C O n2 D O n3 45 2 有向網(wǎng) G 用鄰接矩陣 A 存儲 則頂點 i 的入度等于 A 中 A 第 i 行非 的元素之和 C 第 i 列非 的元素之和 B 第 i 行非 且非 0 的元素個數(shù) D 第 i 列非 且非 0 的元素個數(shù) 46 關鍵路徑是事件結(jié)點網(wǎng)中 A 從起點到終點的最長路徑 B 從起點到終點的最短路徑 C 最長的回路 D 最短的回路 47 已知一個有向圖如右圖所示 則從頂點 a 出發(fā)進行深 度優(yōu)先遍歷不可能得到的 DFS 序列為 A adbefc B adcefb C adcbfe D adefcb 三 判斷題 1 在樹型結(jié)構(gòu)中 每一個結(jié)點最多只有一個前驅(qū)結(jié)點 但可以有多個后繼結(jié) 點 2 在樹型結(jié)構(gòu)中 每一個結(jié)點不能沒有前驅(qū)結(jié)點 3 在度為k的樹中 至少有一個度為k的結(jié)點 4 在度為k的樹中 每個結(jié)點最多有k 1個兄弟結(jié)點 5 度為2的樹是二叉樹 6 二叉樹的度一定為2 7 在非空完全二叉樹中 只有最下面一層的結(jié)點為葉結(jié)點 8 在完全二叉樹中 沒有左孩子的結(jié)點一定是葉結(jié)點 6 9 在完全二叉樹中 沒有右孩子的結(jié)點一定是葉結(jié)點 10 在結(jié)點數(shù)目一定的前提下 各種形態(tài)的二叉樹中 完全二叉樹具有最小深 度 11 滿二叉樹一定是完全二叉樹 12 滿二叉樹中的每個結(jié)點的度不是0就是2 13 在所有深度相同的二叉樹中 滿二叉樹具有最大結(jié)點數(shù)目 14 具有n個結(jié)點的非空二叉樹一定有n 1個分支 15 n個結(jié)點的二叉樹采用二叉鏈表結(jié)構(gòu) 鏈表中有n 1個存放NULL指針域 16 由二叉樹的前序序列和中序序列可以惟一地確定一棵二叉樹 17 由二叉樹的中序序列和后序序列可以惟一地確定一棵二叉樹 18 由二叉樹的前序序列和后序序列可以惟一地確定一棵二叉樹 19 實現(xiàn)二叉樹的按層次遍歷算法時需要用到隊列結(jié)構(gòu) 20 實現(xiàn)二叉樹的遍歷算法時不需要用到堆棧結(jié)構(gòu) 21 線索二叉樹對應的二叉鏈表中不存在空的指針域 22 給定一組權(quán)值 構(gòu)造出來的哈夫曼樹是唯一的 23 哈夫曼樹中不存在度為1的結(jié)點 24 在哈夫曼樹中 權(quán)值相同的葉結(jié)點都在同一層上 25 沒有頂點的圖稱為空圖 26 圖的度是圖中所有頂點的度的最大值 27 邊上帶權(quán)值的圖稱為網(wǎng) 絡 28 圖中一個頂點的度應該是它的出度與人度之和 29 n個頂點的無向圖最多有n n 1 條邊 30 在有向圖中 所有頂點的人度之和等于所有頂點的出度之和 31 在無向圖中 若頂點i到頂點j有路徑 則這兩個頂點之間是連通的 32 在有向圖中 若頂點i到頂點j有路徑 則這兩個頂點之間是連通的 33 連通圖的最小生成樹是惟一的 34 鄰接矩陣主要用來表示頂點之間的關系 35 若表示某圖的鄰接矩陣不是對稱矩陣 則該圖一定是有向圖 36 若表示某圖的鄰接矩陣中出現(xiàn)了全零行或者全零列 則該圖一定是非連 通圖或者非強連通圖 37 對于同一個有向圖 鄰接表中的邊結(jié)點數(shù)目與逆鄰接表中邊結(jié)點數(shù)目相 等 38 無向圖的鄰接表中邊結(jié)點數(shù)目一定為偶數(shù) 39 鄰接表中邊結(jié)點數(shù)目為奇數(shù)的圖一定是有向圖 40 鄰接表中邊結(jié)點數(shù)目為偶數(shù)的圖一定是無向圖 41 對圖進行廣度優(yōu)先搜索的過程中要用到隊列 7 42 對圖進行深度優(yōu)先搜索的過程中要用到堆找 43 帶權(quán)連通圖的最小生成樹是惟一的 44 最短路徑一定是簡單路徑 45 求源點到各點的最短路徑的迪杰斯特拉算法不適用于存在回路的有向 網(wǎng)絡 46 若AOV網(wǎng)中存在拓撲序列 則一般情況下 拓撲序列不是惟一的 47 關鍵路徑是由權(quán)值最大的邊構(gòu)成的 48 給定的AOE網(wǎng)的關鍵路徑一定是惟一的 四 簡答題 1 已知森林的先序遍歷序列為 ABDJCEFHK 中序序列為 DJBAECHKF 請 畫出該森林 2 若一棵度為 4 的樹中度為 1 2 3 4 的結(jié)點個數(shù)分別為 4 3 2 2 則 該樹葉子結(jié)點的個數(shù)是多少 總結(jié)點個數(shù)是多少 14 25 3 一棵度為2的樹與一棵二叉樹有什么區(qū)別 將樹轉(zhuǎn)化為二叉樹的基本目的是 什么 可以采用二叉樹的結(jié)構(gòu)并利用已有的算法解決樹的有關問題 4 已知一棵完全二叉樹共有 892 個結(jié)點 試求 1 樹的高度 10 2 葉子結(jié)點數(shù) 446 3 單支結(jié)點數(shù) 1 4 最后一個非終端結(jié)點的序號 446 5 畫出二叉樹的后序前驅(qū)線索 6 一文件中只出現(xiàn) 9 種字符 a b c d e f g h 它們出現(xiàn)的頻率分 別為 8 9 3 5 6 4 2 1 請根據(jù)書上算法畫出相應的哈夫曼樹 葉子 結(jié)點用相應字母表示 左子樹的權(quán)小于右子樹的權(quán) 給出哈夫曼編碼 并計 算其帶權(quán)的路徑長度 WPL 7 已知某二叉樹的中序遍歷序列為CBGEAFHD 后序遍歷序列為 CGEBHFDA 請畫出該二叉樹的前序線索二叉樹的二叉鏈表結(jié)構(gòu)的表示 8 已知按前序遍歷二叉樹的結(jié)果為ABC 試問 有幾種不同的二叉樹可以得到 這一遍歷結(jié)果 5 8 9 將圖所示的樹林轉(zhuǎn)換為一棵二叉樹 10 分別寫出如圖所示的樹的前序遍歷序列與后序遍歷序列 題9 題10 11 已知某樹林轉(zhuǎn)化為二叉樹后所對應的順序存儲結(jié)構(gòu)為 A B H C E I J D F G 請畫出該樹林 5 請寫出用普里姆算法對下圖求最小生成