計概15-08排序與搜尋－統測試題

【四技試題】

【B】01.一組10個已排序的數值資料，若用二元搜尋法找其中某一個特定值，至多需要比對幾次即可找到？ (A)3 (B)4 (C)5 (D)9。[101管理]

Log₂10≒4次，2³ < 10 < 2⁴

 

【A】02.下列Visual Basic程式片段執行後，若將陣列A之值由A(0)至A(3)列出，並以逗點分隔各元素，其結果為何？ (A)1, 3, 5, 8 (B)3, 1, 5, 8 (C)8, 5, 3, 1 (D)8, 1, 5, 3。[102商業]

Dim A() As Integer = {8, 1, 5, 3}

Dim tmp As Integer

For i = 1 To 3

　For j = 0 To (3 - i)

　　If A(j) > A(j + 1) Then → 氣泡排序法，由小到大的遞增排序

　　　tmp = A(j): A(j) = A(j + 1): A(j + 1) = tmp

　　End If

　Next j

Next i

 

【D】03.使用一維陣列以隨機順序儲存N筆相異紀錄，若利用循序搜尋法(Sequential Search)，在這N筆資料紀錄中找到一個特定的鍵值(Key Value)，關於此搜尋法的平均比對次數，下列何者正確？ (A)logN (B)N² (C)N (D)(N+1)/2。[111管理]

 

【B】04.下列關於搜尋演算法的敘述何者正確？ (A)資料的排列順序不影響搜尋的效率 (B)二元搜尋法只能對排序過的資料進行搜尋 (C)利用雜湊碼產生鍵值，建立雜湊表(Hash Table)，可以提升搜尋的時間效率，且需要的記憶體空間更少 (D)搜尋演算法只能應用在鏈結串列所儲存的資料上。[111管理]

 

【B】05.假設有n筆可排序的資料，下列關於循序搜尋(Sequential Search)與二元搜尋(Binary Search)的敘述何者正確？ (A)循序搜尋資料須先排序 (B)二元搜尋資料須先排序 (C)兩者均須得知資料動態範圍 (D)二元搜尋須比對全部n筆資料方能確認所尋資料不存在。[112管理]

(A)循序搜尋資料不須排序。(C)二元搜尋須得知資料動態範圍。(D)二元搜尋藉由與中間資料比較，不斷刪去資料前(後)半段，縮減搜尋範圍直到找到目標資料或無資料為止。

 

【D】06.使用二分搜尋法(Binary Search)對有序陣列{2, 4, 6, 8, 10, 11, 12, 14, 16, 18, 20}搜尋目標元素14，在第二次數值比較後，搜尋範圍變成下列何者？ (A){16, 18} (B){18, 20} (C){14, 16} (D){12, 14}。[113管理]

第1次搜尋：(1 + 11) ÷ 2 = 6 → 11 → 第2次搜尋範圍{12, 14, 16, 18, 20}

第2次搜尋：(7 + 11) ÷ 2 = 9 → 16 → 第3次搜尋範圍{12, 14}

 

【B】07.某一陣列內容為[4, 3, 1, 2, 5]，擬以氣泡排序法(Bubble Sort)由小到大進行排序，總共會有四個回合從左至右的操作過程，每個操作涉及數次資料大小比較與交換的動作，下列何者為第一回合後的結果？ (A)[3, 4, 1, 2, 5] (B)[3, 1, 2, 4, 5] (C)[4, 3, 1, 5, 2] (D)[1, 2, 3, 4, 5]。[112管理]

執行前	比較	執行後
4, 3, 1, 2, 5	4, 3	3, 4, 1, 2, 5
3, 4, 1, 2, 5	4, 1	3, 1, 4, 2, 5
3, 1, 4, 2, 5	4, 2	3, 1, 2, 4, 5
3, 1, 4, 2, 5	4, 5	3, 1, 2, 4, 5

 

【C】08.下列何者是分析排序演算法時間複雜度的主要目的？ (A)評估演算法輸入資料所需的硬碟容量 (B)計算演算法執行時電腦所需的記憶體容量 (C)推導演算法運算量與資料筆數的趨勢關係 (D)比較演算法輸入與輸出間的資料傳輸速度。[113管理]

【二技試題】

01.假設R是一個陣列，儲存了R1, R2, …, Rn，共有n項資料，有一演算法如下

Procedure SELSORT(R, n)

m = 0

For i = 1 to n - 1

  For j = i + 1 to n

    If Ri < Rj Then

      Temp = Ri

      Ri = Rj

      Rj = Temp

    End If

  m = m + 1

  Next j

Next i

End SELSORT

【C】01-1.在執行上段演算法後，陣列R1, R2, …, Rn的資料會如何？ (A)全部變成最大值 (B)全部變成最小值 (C)由大到小排序 (D)由小到大排序。

【B】01-2.續上題的演算法，假設n=5，執行完程式之後，m的值應該成為 (A)5 (B)10 (C)20 (D)25。[90護理]

 

【A】02.下列有關資料結構的描述，何者不正確？ (A)B tree的資料結構不能儲存在硬碟中 (B)B tree的搜尋時間通常要比二元樹短 (C)遞迴是一種常常用來實作樹狀資料結構的程式設計方式 (D)AVL樹是一種在建構過程中左右子樹(subtree)能保時適當平衡的二元樹。[91管理]

 

【C】03.中序式(Infix form)表示的運算式B-C+D*E/(F-G)，如果轉換成為後序式(Postfix form)應為 (A)+-BC/*DE-FG (B)BCDEFG+-*/- (C)BC-DE*FG-/+ (D)GF-E/D*C+B-。[91護理]

 

【D】04.在一顆二元樹(binary tree)中，若分支度(degree)為0的節點有40個，則分支度為2的節點有幾個？ (A)10 (B)20 (C)29 (D)39。[92電機]

 

【D】05.有關電腦系統中資料結構的應用，下列敘述何者不正確？ (A)多項式(polynomial)適合以串列(linked list)來表示 (B)多工的作業系統常利用佇列(queue)來記錄各個程序(process)的資訊 (C)遞迴(recursive)呼叫適合用堆疊(stack)來處理 (D)環狀佇列(circular queue)可以改善資料存取的時。[92電機]

 

【C】06.有一棵二元樹，總節點數為100個，分枝度(branch factor)為1的節點數有41個，則分枝度為2的節點數有幾個？ (A)27 (B)28 (C)29 (D)30。[92管理]

 

【D】07.某個二元樹(binary tree)的前序式(preorder)為ABDFGEC，中序式(inorder)為FDGBAEC，則其後序式(postorder)為何？ (A)FDGBECA (B)FGDBECA (C)FDGBCEA (D)FGDBCEA。[92管理]

      A

     /  \

    B   E

   /      \

  D       C

 /  \

F   G

 

【A】08.假設a = 5, b = 4, c = 3, d = 2，則依後序(postfix)運算式ab * cd + /之計算值為何？ (A)4 (B)11.5 (C)0.25 (D)10.5。[92護理]

 

【C】09.資料總筆數為n的串列資料，若以快速排序法(quick sort)進行資料排序，平均共需要多少次的資料相互比較，才可完成資料排序？ (A)log₂ n (B)log₂ n² (C)n log₂ n (D)n log₂ n²。[92護理]

 

【D】10.二分搜尋法(binary search)最適合應用於下列何種情況？ (A)資料未排序且為循序存取 (B)資料未排序且為隨機存取 (C)資料已排序且為循序存取 (D)資料已排序且為隨機存取。[92護理]

 

【A】11.下列關於二元搜尋法(binary search)和循序搜尋法(sequential search)的敘述，何者不正確？(n為資料總筆數) (A)二元搜尋法適合用在大量未排序之資料 (B)循序搜尋法適合用在小量未排序之資料 (C)二元搜尋法之時間複雜度(time complexity)在平均情況(average case)下為O(log n) (D)循序搜尋法之時間複雜度在最差情況(worst case)下為O(n)。[93電機]

 

【B】12.下列關於二元樹(binary tree)的敘述，何者正確？ (A)前序追蹤(preorder traversal)與後序追蹤(posrorder traversal)可以決定唯一的二元樹 (B)前序追蹤(preorder traversal)與中序追蹤(inorder traversal)可以決定唯一的二元樹 (C)二元樹的每個節點的分支度degree)必須為2 (D)若一棵完全二元樹(full binary tree)含有128個樹葉節點(leaf node)，則其總節點數為256個。[93電機]

 

【B】13.三個節點最多可以排成幾棵不同的二元樹？ (A)4棵 (B)5棵 (C)6棵 (D)7棵。[93電機]

 

【A】14.將中序(infix)運算式A+ B×C+D×E×F轉成前序(prefix)或後序(postfix)的表示式，下列何者正確？(註：+與×的優先順序為×大於+，左右關係皆為由左而右) (A)前序：++A×BC××DEF (B)前序：++A×BC×D×EF (C)後序：AB+C×DE×F×+ (D)後序：ABC×+DEF××+。[93管理]

 

【C】15.將運算子置於運算元之前稱為前序(pre-order)表示法，例如：a+b*c可表示成+a*bc。若所有運算元均為一位數，則下列前序表示法的算術結果何者不正確？ (A)-+*3424的結果為10 (B)++23*34的結果為17 (C)+1-*234的結果為11 (D)+3*2-41的結果為9。[94電機]

 

【A】16.對於單向鏈結串列(singly linked list)而言，下列何種操作最沒有效率？ (A)在鏈結指標所指節點與上一節點間插入一新的節點 (B)在鏈結指標所指節點與下一節點間插入一新的節點 (C)存取目前指標所指向之節點 (D)將鏈結指標移動到下一個節點。[94管理]

 

【C】17.有300個節點的三元樹(ternary tree)，其最小高度(height)為何？(註：僅有一個節點的三元樹，其高度為1) (A)4 (B)5 (C)6 (D)7。[94管理]

 

【B】18.在已排序的1000個相異元素之陣列中，欲執行二元搜尋法(binary search)以找尋某資料。若要找尋的資料並不在陣列中，則大約要比對多少個元素才能確定不在陣列中？ (A)4 (B)10 (C)500 (D)1000。[94管理]

二元搜尋法：若有N筆資料，最少比較1次，最多比較次數為INT((Log₂N) + 1)次，故INT((Log₂1000) + 1) = 10。

 

【A】19.中序(infix)運算式K-L+M*N的前序(prefix)表示式應為 (A)+-KL*MN (B)KL-MN*+ (C)+-MN*KL (D)MN-KL*+。[94護理]

 

【A】20.有一個前序表示式(prefix expression)為：-2+＊/6226，則該式之計算結果為多少？ (A)-10 (B)-2 (C)2 (D)10。[95電機]

 

【B】21.下列有關二元樹(binary tree)之敘述，何者錯誤？ (A)二元樹中的節點(node)數可為零 (B)完整二元樹(full binary tree)，若樹的高度為3，則此二元樹節點數為8 (C)二元樹的根節點(root)下可分成兩個子樹，稱為左子樹與右子樹 (D)二元樹中的節點至多只能有兩個子節點。[95管理]

 

【C】22.後序(postfix)運算式6,3,/,3,-,5,2,*,+之計算結果為何？ (A)3 (B)6 (C)9 (D)11。[95護理]

 

【D】23.令a = 7，b = 5，c = 3，d = 1，則下列四個前序(prefix)表示式中，何者的值為最大？ (A)---abcd (B)-a-b-cd (C)--a-bcd (D)-a--bcd。[96電機]

 

【A】24.有一個中序(infix)表示式為(a/(b-c+d))×e-a×c，則此式之後序(postfix)表示式為何？ (A)abc-d+/e×ac×- (B)ab/c-de×+ac×- (C)abcdeac-+/-×× (D)abcd-+/ea-c××。[96電機]

 

【D】25.若樹(tree)高度的定義為根節點(root)的高度；節點(node)高度的定義為該節點至葉節點(leaf)的最長路徑(path)的長度；路徑長度的定義為路徑上節點的數目減1。對於鍵值(key)不得重複的二元搜尋樹(binary search tree)，若已知某個二元搜尋樹有40個節點，則下列敘述何者正確？ (A)該二元搜尋樹之高度至少為6 (B)該二元搜尋樹之高度至多為15 (C)若在該二元搜尋樹中尋找某個值，則至少需比對5個節點才有可能找到 (D)若在該二元搜尋樹中尋找某個值，且該值不一定存在於該二元搜尋樹中，則至多需比對40個節點才能確定結果。[96管理]

 

【A】26.下列有關磁碟檔案組織(file organization)的敘述，何者錯誤？ (A)對循序檔(sequential file)以非鍵值屬性(non-key attribute)進行搜尋時，可以採用二元搜尋法(binary search)找出結果 (B)對循序檔進行新增時，若不採用溢位資料區(overflow area)且未預留空閒位置，則通常須先找到適當的插入位置(insertion point)，然後再循序讀取並覆寫插入位置後的記錄 (C)在索引循序檔(indexed-sequential file)中，通常會對索引(index)再建立索引，直到最上層的索引小到能被完全載入記憶體時為止 (D)索引循序檔的主索引(primary index)可以不對每筆記錄進行索引，而僅對每個區段(block)的第一筆記錄進行索引。[96管理]

 

【B】27.利用二元搜尋(binary search)法，在已排序的1000筆資料中，搜尋某一特定資料，最多比對幾次？ (A)5 (B)10 (C)500 (D)1000。[96護理]

2^X > 1000，X = 10

 

【D】28.假設W = 4, X = 2, Y = 5, Z = 3，後序(posrfix)運算式為WX/YZ-+X*的值為何？ (A)6 (B)7 (C)12 (D)8。[97管理]

 

【D】29.若有一個中序(infix)式為((a+b)+c×(p-q))/(r-s/t)，其後序式應為下列何者？ (A)abc+-p+/q×rst/- (B)ab/c-p+q+rst×-/ (C)ab+cpqrst-+/-×/ (D)ab+cpq-×+rst/-/。[98電機]

 

【C】30.某運算式的前序(Prefix)式為×,+,÷,4,×,1,2,6,5，若以運算二元樹表示此運算式，其樹高(Height)為何？ (A)3 (B)4 (C)5 (D)6。[98管理]

 

【A】31.要使用深度優先搜尋(Depth First Search)的方式，來拜訪一棵樹中所有的節點，採用下列何種資料結構最合適？ (A)堆疊 (B)佇列 (C)雙向佇列 (D)多階層佇列。[98管理]

 

【C】32.一個網路圖如圖所示，其中的數字表示各邊(Edge)的權重(Weight)，則在此網路圖的「最小成本擴展樹」(Minimum Cost Spanning Tree)中，邊的權重總和為多少？ (A)9 (B)14 (C)15 (D)21。[98管理]

 A-C-B-D-F = 1 + 3 + 4 + 7 = 15

【D】33.下列關於AVL Tree與B-Tree的敘述，何者正確？ (A)均是二元樹(Binary Tree) (B)均不是二元樹 (C)只有B-Tree是二元樹 (D)只有AVL Tree是二元樹。[98管理]

 

【D】34.有一棵二元樹，其分枝度(Branch Factor)為1的節點個數為12，分枝度為2的節點個數為26，則此二元樹的總節點個數為何？ (A)38 (B)63 (C)64 (D)65。[98管理]

 

【D】35.後序(Postfix)式為ABC+*之運算式，其前序(Prefix)式為何？ (A)+*ABC (B)*+ABC (C)+A*BC (D)*A+BC。[99電機]

 

【C】36.以後序(Post Order)法走訪圖之二元樹，在走訪次序中，哪一個節點(Node)是緊接著節點B之後出現？ (A)C (B)D (C)E (D)F。[99電機]

 

【D】37.有一前序表示式(prefix expression)為+-AB*CD，其中A = 1, B = 3, C = 2, D = 4，請問此前序表示式的運算結果為何？ (A)-6 (B)0 (C)2 (D)6。[99管理]

 

【B】38.有一後序表示式(postfix expression)為AB+CD*+，下列何者為其中序表示式(infix expression)？ (A)(A + B) * (C + D) (B)A + B + C * D (C)A * B + C + D (D)A * B + C * D。[99管理]

 

【B】39.有一高度為5的二元樹，此二元樹最多可包含多少個節點？(假設僅有一個節點的二元樹，其高度為1) (A)15 (B)31 (C)32 (D)63。[99管理]

 

【B】40.aa-(b/c-d×e)/f的後序表示法為何？ (A)ab/cd×e-f/- (B)abc/de×-f/- (C)a-bc/-de×f/ (D)a-bc/de×-f/。[100管理]

 

【A】41.二元樹之後序追蹤結果為：A、H、E、B、I、F、G、C、D，則其樹根為何？ (A)D (B)C (C)H (D)A。[100管理]

 

【B】42.一陣列資料包含元素依序如下：10, 91, 23, 56, 71, 18, 若用氣泡排序法由小至大排序，則在第二回合(pass)排序後的順序為何？ (A)10, 23, 56, 71, 18, 91 (B)10, 23, 56, 18, 71, 91 (C)10, 18, 23, 56, 71, 91 (D)10, 18, 23, 71, 56, 91。[91電機]

 

【D】43.在3000筆已經排序的資料中，以二分搜尋法(binary search)尋找某筆資料時，最多只要搜尋幾次即可找到？ (A)9 (B)10 (C)11 (D)12。[91電機]

2¹¹ < 3000 < 2¹² → 2048 < 3000 < 4096

 

【B】44.當預備進行排序之資料量太大，而必須使用如硬碟、磁帶等輔助記憶體進行數個階段的排序，此技術稱為 (A)內部排序 (B)外部排序 (C)分層排序 (D)分頁排序。[92護理]

 

【A】45.以下是對有n個元素的陣列a(註標範圍：1 ~ n)，執行氣泡式排序(bubble sort)的Visual Basic程式片段。第二行空格處應填入何式才正確？

For pass = 1 To n - 1

  For j = 1 To ＿＿＿＿

    If a(j) > a(j + 1) Then

      Temp = a(j): a(j) = a(j + 1): a(j + 1) = temp

    End If

  Next j

Next pass (A)n - pass (B)n - pass + 1 (C)n - pass - 1 (D)n - pass - 2。[94管理]

 

【B】46.關於選擇排序法(selection sort)，若其原始資料排列順序為：24, 57, 48, 37, 12, 92, 86, 34。則其pass 2(第二回合)之排序結果為下列何者？ (A)92, 86, 57, 37, 12, 24, 48, 34 (B)92, 86, 24, 37, 12, 48, 57, 34 (C)92, 86, 57, 48, 37, 34, 24, 12 (D)92, 86, 57, 48, 12, 24, 37, 34。[95電機]

 

【B】47.有一陣列資料包含8個元素：55，15，85，25，65，75，45，35。若採用插入排序法(insertion sort)將它們由小到大排序，在過程中，假如第一回合(pass 1)之結果為15，55，85，25，65，75，45，35，試問第三回合(pass 3)之結果為何？ (A)15，25，35，55，65，75，45，85 (B)15，25，55，85，65，75，45，35 (C)15，25，55，65，85，75，45，35 (D)15，25，35，45，55，65，75，85。[96電機]

 

【B】48.利用相鄰資料兩兩相比而完成的資料排序，稱為 (A)插入排序法(insertion sort) (B)氣泡排序法(bubble sort) (C)謝耳排序法(shell sort) (D)快速排序法(quick sort)。[96管理]

 

【A】49.下列哪一種排序法是將數列分成「已排序數列」與「未排序數列」二部分，每次將「未排序數列」中的第一個數，移到「已排序數列」中，並且使「已排序數列」仍然維持由小排到大的性質？ (A)插入排序法(insertion sort) (B)選擇排序法(selection sort) (C)泡沫排序法(bubble sort) (D)快速排序法(quick sort)。[96管理]

 

【B】50.利用氣泡排序法將(25、18、22、13、4)等五筆資料自左至右，由小到大排列，若第一次循環(Pass1)後結果為(4、25、18、22、13)，則第二次循環(Pass2)後之結果應為 (A)(4、13、18、22、25) (B)(4、13、25、18、22) (C)(4、18、22、13、25) (D)(13、4、25、18、22)。[97電機]

 

【B】51.請利用氣泡排法(bubble sort)將陣列中的七筆資料：88, 44, 55, 22, 11, 99, 33由左而右且由小到大排列，第二次排序後的順序為何？ (A)44, 11, 22, 55, 33, 88, 99 (B)44, 22, 11, 55, 33, 88, 99 (C)22, 44, 11, 55, 33, 88, 99 (D)11, 22, 44, 33, 55, 88, 99。[97管理]

 

【B】52.某診所有2000筆病患資料，且已依身分證字號排序，若用二元搜尋法尋找某一位病患資料，則最多需比對幾次？ (A)10 (B)11 (C)20 (D)21。[97護理]

 

【A】53.下列哪種排序法不是穩定性(Stable)排序法？ (A)快速排序法 (B)合併排序法 (C)氣泡排序法 (D)插入排序法。[99電機]

 

【A】54.快速排序(Quick Sort)法是屬於下列哪種程式設計方法？ (A)個別擊破法(Divide and Conquer) (B)動態程式法(Dynamic Programming) (C)貪婪法(Greedy Method) (D)模組法(Modular Method)。[99電機]

 

【C】55.若以快速排序法(Quick Sort)將數列11, 13, 10, 14, 15, 12由小到大排序，則排列完成須執行幾次排序過程？ (A)5 (B)4 (C)3 (D)2。[100電機]

 

【C】56.下列何者是採用個別擊破法(divide and conquer)的排序法？ (A)選擇排序法 (B)氣泡排序法 (C)快速排序法 (D)插入排序法。[100管理]

 

【B】57.一陣列包含下列六個元素：25, 34, 17, 45, 66, 8。利用氣泡排序法排序(由左向右掃描)，第三回合(pass)排序後的結果為何？ (A)8, 17, 34, 25, 45, 66 (B)17, 25, 8, 34, 45, 66 (C)17, 8, 25, 34, 45, 66 (D)8, 25, 17, 34, 45, 66。[100管理]