115年 - 90004 電腦軟體設計共同科目乙級工作項目 07：資料結構 51-100（2026/01/14 更新）#136865

科目：技檢◆電腦軟體設計共同科目 | 年份：115年 | 選擇題數：50 | 申論題數：0

試卷資訊

所屬科目：技檢◆電腦軟體設計共同科目

選擇題 (50)

51. 假設樹根的高度定義為 1，各節點的高度為各節點至樹根的距離加1 。高度為 6 的 AVL-Tree，最少有幾個節點？ (A)18 (B)19 (C)20 (D)21 。

52. 4 個節點(node)可構成多少種不同的二元樹？ (A)14 (B)10 (C)16 (D)12 。

53. 若一個只包含根節點的二元樹其高度(Height)為 1，則高度為 7 的二元樹最多有幾個節點？ (A)63 (B)64 (C)127 (D)128 。

54. 下列有關擴張樹(Spanning Tree)的敘述何者錯誤？ (A)一個圖形可能有許多個的擴張樹 (B)一個圖形的最小成本擴張樹只會有一個 (C)圖形有 n個節點與 e 個邊，若以相鄰矩陣(Adjacency Matrix)表示，則利用深度優先搜尋(Depth-First Search)得出擴張樹的時間複雜度(TimeComplexity)為 O(n2 ) (D)圖形有 n 個節點與 e 個邊，若以相鄰串列(Adjacency Link)表示，則利用深度優先搜尋(Depth-First Search)得出擴張樹的時間複雜度(Time Complexity)為 O(e) 。

55. 下列排序法何者具有穩定(Stable)特性？ (A)選擇排序(Selection Sort) (B)堆積排序(Heap Sort) (C)插入排序(Insertion Sort) (D)快速排序(QuickSort) 。

56. 下圖為一延伸二元樹(Extended Binary Tree)，其中圓形節點表內節點（Internal Node），方形節點代表外節點（External Node），其外路徑長(External Path Length) 是多少？

(A)7 (B)12 (C)16 (D)17 。

57. 建立一個含有五個內節點(Internal Node)的延伸二元樹(Extended BinaryTree)，使此延伸二元樹的外路徑長(External Path Length)為最小，則此最小外路徑為何？ (A)16 (B)17 (C)18 (D)20 。

58. 欲將數值資料 1、2、3、4 建立二元搜尋樹，則最多可構成多少種高度平衡二元樹(AVL 樹)？ (A)14 (B)10 (C)6 (D)4 。

59. 設一個只包含根節點的二元樹之高度(Height)為 1，則高度為 6 的高度平衡二元樹(AVL 樹)至多有幾個節點？ (A)20 (B)31 (C)32 (D)63 。

60. 下列二元樹(Binary Tree)，何者是一棵 AVL-Tree？(A)

61. 下列四棵二元樹(Binary Tree)，滿足最大堆積(Max-heap)特性之二元樹共有幾棵？

(A)0 (B)1 (C)2 (D)3 。

62. 某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為EFGBHCDATRS，而後序走訪(Postorder Traversal)為GFEHDCBTSRA，對於該二元樹之性質，下列敘述何者是正確的？ (A)根節點(Root Node)為 A (B)葉節點(Leaf Node)共 6 個 (C)G 節點之父節點(Parent Node)為 E (D)前序走訪(Preorder Traversal)為ABEFGCDHRTS 。

63. 關於圖(Graph)的漢米頓迴路(Hamiltonian Cycle)，請問下列何者是錯誤的？ (A)除了起點以外，必須經過每一個節點正好一次 (B)必須經過每一個邊正好一次 (C)判斷一個圖是否具有漢米頓迴路是 NP-Complete (D)若不是連結圖(Connected Graph)，則不具有漢米頓迴路。

64. 一棵二元樹含有 50 個節點，分支度為 1 的節點數為 21 個，則其分支度為 2 的節點數有多少？ (A)10 (B)12 (C)14 (D)29 。

65. 某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為 BCAEDGF，而前序走訪(Preorder Traversal)為 ABCDEFG，對於該二元樹之性質，下列敘述何者是正確的？ (A)根節點(Root Node)為 G (B)葉節點(Leaf Node)共 4 個 (C)分支度為 1 之節點共有 2 個 (D)分支度為 2 之節點共有 3 個。

66. 某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為GDBAEHCIFJ，而前序走訪(Preorder Traversal)為 ABDGCEHFIJ，對於該二元樹之性質，下列敘述何者是正確的？ (A)分支度為 1 之節點共有 3個 (B)分支度為 2 之節點共有 4 個 (C)葉節點(Leaf Node)共 5 個 (D)二元樹共有 5 層。

67. 有一整數序列 26, 59, 77, 31, 51, 11, 19, 42 以 Merge Sort 由小而大排序，第一階段(Pass)的合併結果，下列何者是正確的？ (A)31, 51, 11,42, 26, 77, 59, 19 (B)26, 59, 31, 77, 11, 51, 19, 42 (C)11, 19, 26, 31, 42,59, 51, 77 (D)26, 11, 19, 31, 51, 59, 77,42 。

68. 一整數序列 26, 59, 77, 31, 51, 11, 19, 42 以 Radix Sort 由小而大排序，第一階段(Pass)的結果，下列何者是正確的？ (A)31, 51, 11, 42, 26, 77,59, 19 (B)26, 59, 31, 77, 11, 51, 19, 42 (C)11, 19, 26, 31, 42, 59, 77, 51(D)26, 11, 19, 31, 51, 59, 77,42 。

69. 有一文字檔共有 4 個符號，這些符號所對應的 Huffman Code，其長度何者是可能出現？ (A)2 2 2 2 (B)3 2 2 2 (C)4 3 2 1 (D)3 3 2 2 。

70. 下列有關拓樸排序法(Topological Sort)的敘述，何者為錯誤？ (A)適用此法的有向圖形(Directed Graph)必須沒有循環(Acyclic)才有意義 (B)用深度先搜尋法(Depth-First Search)可產生具拓樸順序的序列 (C)對一個有V 個頂點，E 個邊的有向圖形作拓樸排序，需時 O(V+E) (D)一個有向圖形經拓樸排序後的結果可能超過一個。

71. Infix 轉換成 Postfix 需要的資料結構，下列何者正確？ (A)Stack (B)Queue (C)AVL-Tree (D)Red-Black Tree 。

72. 一個只包含根節點的 B-tree 其高度為 1 。一個分支度(order)為 3 的B-tree ，若其高度為 4，最多可儲多少筆資料？ (A)80 (B)26 (C)120 (D)39 。

73. 下列有關資料結構的描述，那一項有誤？ (A)B-tree 的資料結構適合儲存於硬碟中 (B)B-tree 的搜尋時間較二元樹長 (C)遞迴(Recursive)可用來實作樹狀資料結構的程式設計方式 (D)高度平衡二元樹(AVL 樹)是一種建構過程中左右子樹(Sub Tree)能保持適當平衡的二元樹。

74. 有關分支度(Order)為 m 的 B-tree，下列敘述何者錯誤？ (A)根節點(RootNode)不是葉節點時，其最少的子節點數量為 2 (B)所有葉節點均在同一階層(Level)上 (C)除根節點外的所有節點至少有 m/2 個子節點 (D)m=3 的B-tree 亦稱為 2-3 樹。

75. 若要對一組訊息 AAABCDDDDEEE 做二進位數的編碼，且每個字元代碼為等長度，則此訊息編碼後所需的最少位元是多少？ (A)20 (B)48 (C)15(D)36 。

76. 若要對一組訊息 AAABCDDDDEEE 做二進位數的編碼，其中每個字元代碼為可變長度，當使用霍夫曼碼(Huffman Codes)來進行編碼時，此訊息編碼後最少需要多少位元？ (A)26 (B)36 (C)15 (D)30 。

77. 關於要符合雜湊函數(Hashing Function)設計原則的敘述，何者有誤？(A)運算要簡單 (B)碰撞機會愈小愈好 (C)儘量將數字轉換成文字 (D)儘量充分利用所有的雜湊桶(Bucket)位置。

78. 關於使用雜湊函數(Hashing Function)的敘述，下列何者為錯誤？ (A)使用雜湊法搜尋時，檔案須事先排序 (B)在無碰撞及溢位情況下，只需一次即可讀取，與資料量大小無關 (C)保密性高，若不知雜湊函數，無法擷取到資料 (D)可作資料壓縮，節省空間。

79. 下列何者不是影響雜湊法(Hashing)執行效率的因素？ (A)雜湊桶大小(Bucket Size) (B)雜湊函數(Hashing Function) (C)負載係數(LoadingFactor) (D)資料量大小(Data Volume) 。

80. 一雜湊函數(Hashing Function)為 H(X)=X mod 11，則 H(35)與下列那一項會碰撞(Collision)？ (A)H(13) (B)H(25) (C)H(38) (D)H(100) 。

81. 利用雜湊法(Hashing)將下列六個數字：22、29、40、45、54、59 依序放入 0~5 共六個位置，雜湊函數(Hashing Function)為 X mod 6，碰撞以循序偵測(Linear Probing)，則 0、1、2、3、4、5 六個位置的內容依序為何？ (A)40、54、59、45、22、29 (B)40、59、54、45、22、29 (C)59、45、54、40、22、29 (D)40、54、45、59、22、29 。

82. 下列關於循序搜尋法(Sequential Searching)的敘述，那一項為錯誤？ (A)被搜尋的資料記錄不需要依鍵值大小排列 (B)又稱為線性搜尋法(LinearSearching) (C)對於有 N 個資料記錄檔案最壞情況需比較 N 次 (D)若該檔案有 N 筆資料，找到一筆正確資料，平均需比較 N 次。

83. 資料共有 4096 筆，若採用二元搜尋法(Binary Search)，最差情況下需搜尋幾次才能找到一筆已知的資料？ (A)11 (B)12 (C)13 (D)14 。

84. 設有 n 個資料錄(Data Record)，而且每些資料錄被搜尋的機率均相同，我們要在這些資料錄中找到一個特定鍵(Key Value)值的資料錄，則下列那一項為錯誤？ (A)若用循序搜尋(Sequential Search)，則平均搜尋長度(Search Length)為

次 (B)若用二分搜尋(Binary Search)，則平均搜尋長度為

次 (C)在已排序過的直接檔下才能使用二分搜尋法去找出一特定資料錄 (D)若找不到所要的資料錄，則在二分搜尋法中會做 n 次比較。

85. 若 n 大於 10¹⁰⁰⁰，演算法的時間複雜度(Time Complexity)由小到大的排序，下列何者是正確的？ (A)

86. 當 n>=2 時，T(n)=2T(n-1)+1；當 n=1 時，T(n)=1 。請問 T(n)之值是多少？ (A)log n (B)n (C)n² -1 (D) 2ⁿ-1。

87. 若 n 大於 10¹⁰⁰⁰，演算法的時間複雜度(Time Complexity)由小到大的排序，下列何者是正確的？ (A)

88. 下列敘述何者是正確的？ (A)

(D)對於一個時間複雜度為 O(1)的演算法而言，不管其輸入資料量(Input Size)為何，其所需記憶體大小是固定的。

89. 下列敘述何者是正確的？ (A)

90. 有一遞迴(Recursive)程式如下，下列何者是這個程式的時間複雜度(Time Complexity)？

(D)θ(n log n) 。

91. 有一遞迴(Recursive)程式如下，下列何者是這個程式的時間複雜度(Time Complexity)？

(A)θ(log n) (B)

(C)θ(n) (D)θ(n log n) 。

92. 有一遞迴(Recursive)程式如下，以下何者是這個程式的時間複雜度(Time Complexity)？

(A)θ(log n) (B)

(D)θ(n log n) 。

93. 下列程式片段之計算時間，何者是正確?

(A)θ(log n) (B)θ(n) (C)

(D)θ(n log n) 。

94. 下列程式片段之計算時間，何者是正確?

(A)θ(log n) (B)θ(n) (C)

(D)θ(n log n) 。

95. 若 DoIt 之計算時間為

，下列程式片段之計算時間，何者是正確?

96. 利用環狀鏈結串列(Circular Linked List)來實作一個佇列(Queue)，且該串列有一個後端指標(rearPtr)指向佇列之最後一個元素，若佇列之每一個節點結構如下，下列敘述中何者可以正確地取得佇列中的第一個元素資料 (假設在一個成員函式(Member Function)中，Private Member 的存取是合法的)？

(A)element＝rearPtr-＞item (B)element＝rearPtr-＞next-＞frontPtr-＞next (C)element＝rearPtr-＞next (D)element＝rearPtr-＞next-＞item 。

97. 下列有關樹的敘述，何者錯誤？ (A)三向搜尋樹(3-way Search Tree)就是2-3 樹 (B)2-3 樹(2-3 Tree)是 B 樹(B Tree)的一種 (C)從紅黑樹(Red-BlackTree)刪除一個節點所需時間複雜度為 O(log n) (D)從 AVL 樹, 2-3 樹, 2-3-4 樹,紅黑樹刪除一個節點所需時間複雜度均為 O(log n) 。

98. 下列有關 n 個鍵值所形成之 2-3 樹(2-3 Tree)的敘述，何者錯誤？ (A)是一個分支度(Order)為 3 的 B-tree (B)搜尋一個節點所需時間複雜度為O(log n) (C)刪除一個節點所需時間複雜度為 O(log n) (D)根節點(Root)至少有三個子節點。

99. 有關 Tree 的敘述，下列何者正確？ (A)B-tree 的建立方式是採由上往下(Top-down)做法 (B)二元搜尋樹(Binary Search Tree)的建立方式是採由下往上(Bottom-up)做法 (C)將 100000 筆資料存入分支度(Order)為 256之 B-tree，其高度最高為 4 (D)將 100000 筆資料存入分支度(Order)為256 之 B-tree，其高度至少為 3 。

100. 將 20, 40, 10, 30, 15, 35, 7, 26, 18, 2 依序加入一個分支度(Order)為 3之空的 B-tree，下列敘述何者正確？ (A)根節點包括 20 (B)18 與 26 存放在同一節點 (C)20 與 26 存放在同一節點 (D)35 與 40 存放在同一節點。

申論題 (0)