關務人員升官等薦任資料結構：91
高考三級資料結構：91
檢察事務官三等資料結構：91
資訊技師高等資料結構(去除資料庫)：91
專門職業及技術人員檢覈資料結構：91
地方特考三等資料結構：91
九十一年關務人員升官等考試試題 關：20560 全一頁
等 別：薦任升等
類 科：資訊處理
科 目：資料結構
考試時間：二小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、請回答下列問題：
(一)兩個變數 X 與 Y 欲做內容之交換，往往需要藉由第三個變數 temp，例如：
temp←X; X←Y；Y←temp
今假設變數 X = 63，Y = 28 規定不能使用第三個變數 temp 來做交換，問有什麼其他方法使得 X = 28，Y = 63？（10分）
(二)一個數字的 inversion 是在其左邊大於它的數字的數目，一組數字的inversion 的集合稱為 inversion table。請寫出一組數字 = (4, 1, 5, 3, 2) 的 inversion table。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、給予下列美國五個城市的交通圖：
(一)提出一種方式表示這個圖。（5分）
(二)提出一種方法計算城市間的最短距離。（10分）
(三)找出這個圖的遞移性閉包 (Transitive closure)。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、(一)把一筆鍵值 (key value) 加入一棵 order 為 m 的 B-樹 (B-tree)，在什麼情況下，這棵樹的高度會增加1 層。請說明新資料所加入的節點 (node)在加入之前，節點內所含鍵值的個數，以及高度如何變化？（10分）
(二)把一筆特定的鍵值 (key value) 由一棵 order 為 m 的 B-樹 (B-tree) 中去除，請說明那個節點的資料被去除，以及在什麼情況下，這棵樹的高度會減少1層。答案必須包括在資料被除去之前，節點內的鍵值個數，和高度如何變化。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、多相式合併排序法 (Polyphase meging) 是一種磁帶的外部排序方法。其做法是將已排序好的資料組 (sorted blocks 或 runs) 依某一種方式分配到不同的磁帶機上，再加以合併。問：
(一)今若有四個磁帶機可用，而最初有57個資料組，請說明使用多相式合併排序法的過程。（你必須先寫出最初分配的過程，再寫出實際合併排序的過程）（15分）
(二)使用多相式合併排序法有什麼限制？應如何處理？例如：當中只有53 個已排序好的資料段落時。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、若一個「雜湊表格」(hash table) 有 m 個儲存格，且已存放了 n 個「關鍵值」(keys)，我們會說此雜湊表格的「載重因子」(load factor) 為 α= n/m。當 α>1 時，到此雜湊表格所進行的每一次查詢運算，是否一定要使用 O(1+α) 的時間？請詳細說明為什麼？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
2002年高上高普特考！
資訊
《資料結構》
一、給予如下三個碰撞處理機制(collision handling mechanisms)，請先別描述其原理，再比較其異同。（二十分）
(一)線性探測法(linear probing)
(二)二次式探測法(quadratic probing)
(三)串連法(chaining)
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、選擇排序法 (Selection sort) 的基本觀念是從那一堆尚未排序好的資料中，挑選出一個最小的資料，而將它依序置於排序好的位置上。它的演算法如下：
1 Procedure selection
2 for i ← 1 to n-1
3 min ← i
4 for j ←i+1 to n
5 if (A[j]<A[min] ) then min ← j
6 end for
7 temp←A[i]; A[i] ← A[j]; A[j] ← temp
8 end for
9 end
問題：
(一)演算法的第七行是做兩個位置，A[i] 與 A[j] 內容的交換，明顯的若兩者的內容相同則可不用交換，那麼第七行應改為：
if (A[i]≠A[j]) then temp ← A[i]; A[i] ← A[j]; A[j] ← temp
但是一般的選擇排序演算法都沒有這樣的修改，請問為什麼？請寫出理由。（十分）
(二)演算法的第五行是做資料的比較。對於n個資料而言，最多的比較次數是多少？（五分）
(三)同(二)，最少的比較次數是多少？（五分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、給予14個元素，編號1~14，如果這些元素間具有如下的等價關係 (equivalence relation)：
R = {(1,11), (7,11), (2,12), (12,8), (11,12), (3,13), (4,13), (13,14), (14,9), (5,14), (6,10)}
(一)試找出所有等價類別 (equivalence classes)。（4分）
(二)試提出集合 (set) 表現方式，並定義相關運算，以找出所有等價類別。（16分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、(一)將一般算術陳式 (expression) 轉換成後序式 (postfix) 有什麼優點？（五分）
(二)試將 A + B×C / (E-2)×F轉換成後序式。（五分）
(三)再說明我們如何去計算 (二) 中的後序式，請寫出計算過程。（十分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、某程式的輸入為一串 n 個介於1到 n 的正整數 a(1), a(2),..., a(n);且 a(i)<>a(j) if i<>j。故共有 n! 種不同輸入，假設每種輸入的發生機率都是一樣。
給定 a(1), a(2),..., a(n)，
假設該程式的執行時間經分析後為 | a(1) - a(n) |。
令 T(n) 為該程式的平均執行時間。
試列出 T(n) 和 T(n+1) 的關係，並說明計算過程。（二十分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
九十一年公務人員特種考試司法人員考試試題 三：3053 全一張
等 別：三等考試
類 科：檢察事務官電子資訊組
科 目：資料結構
考試時間：二小時 座號：______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、一個n 乘n 的二維矩陣若其非零的元素 (element) 都位於由右上到左下的主對角線之中或其右下方，則稱之為「右下三角矩陣」。本題另外假設上述這些非零元素可能存在的地方，都存放不為零的數值。A 為一個右下三角矩陣，A[i,j]，1<=i<=n；1<=j<=n；代表A 在第 i 列與第 j 行交叉處的元素。今用一維陣列 D 儲存 A 的非零元素，D 的指標由1 開始計算，A 的非零元素以列為主 (rowwise)，由左到右再由上而下的次序儲存於 D。試問：（20分）
(一) D 總共有幾個元素？
(二)假設 i<=j，則 A[i,j] 儲存於 D 的指標位置為何？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、於下列圖一的單一鏈結串列 (singly linked list) 中，只知道指標 P 指向某一個節點其儲存的資料為48，而不知道串列首的所在位置。今欲加入一個新資料39於指標 P 之前，產生下列圖二的結果，請說明你的做法或者寫出其演算法。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、給予一棵樹的前序追蹤 (preorder traversal)，和中序追蹤 (inorder traversal) 如下：
前序追蹤：A B D G C E H I F
中序追蹤：D G B A H E I C F
(一)繪出這棵樹。
(二)以遞迴方式 (recursion) 寫出後序追蹤 (postorder traversal) 演算法。
(三)列出這棵樹的後序追蹤結果。
(四)以重複方式 (iteration)，寫出層次追蹤 (level-order traversal) 演算法。
（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、所謂〝穩定〞(stable) 的排序方法是指相同鍵值的資料，經過排序後仍然保持原來的相對次序。請回答下列的問題：（20分）
(一)說明在什麼情況下會需要穩定的排序方法？
(二)〝不穩定〞(unstable) 的排序方法通常會比〝穩定〞的排序方法執行速度快。這個陳述是否屬實？請說明之。
(三)選擇排序法 (Selection sort) 與快速排序法 (Quick sort) 都是屬於〝不穩定〞的排序方法。試以此兩者為例，說明是什麼原因造成兩者的不穩定？
(四)插入排序法 (Insertion sort)、合併排序法 (Merge sort) 與堆積排序法(Heap sort) 三者都是屬於〝穩定〞的排序方法。這個陳述是否屬實？請說明之。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、用來製作「雜湊表格」(hash table) 的「雜湊函數」(hash function) 必須具有一定的性質，方可保證其所製作出的雜湊表格有較佳的執行效率。假設「可能出現的關鍵值」(universe of keys) 的集合為 U = { n | 0 <= n <= 99 }；「實際出現的關鍵值」(actual keys) 的集合為 K = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 97 }。現在要把集合 K 中的所有值放入一恰有20個儲存格的雜湊表格 (儲存格位址為0, 1, 2,…, 19)，且採取「聯結」(chaining) 方式處理「碰撞」 (collision) 情形，請問以下那一個雜湊函數所作出的雜湊表格在作「查詢」(search) 運算時，其「最糟狀況」(worst case) 下的查詢效率最低？請詳細說明為什麼？（我們同時假設以下各雜湊函數的函數值計算時間皆相同，集合K 之各個值被查詢的機率皆為1/10。以下之 mod 為整數值餘數運算、/是整數商數值計算。）（20分）
(一) h (n) = n mod 20
(二) h (n) = (n + 1) mod 20
(三) h (n) = (n * n) mod 20
(四) h (n) = (n / 10) + (n mod 10)
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
[九一年資訊技師高等資料結構(去除資料庫)]
高等考試建築師、技師、不動產估價師、
九十一年專門職業及技術人員 考試試題 代號：01410 全一張
呼吸治療師、心理師暨普通考試不動產經紀人
等 別：高等考試
類 科：資訊技師
科 目：資料結構（包括資料庫）
考試時間：二小時 座號：__________________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、在二元樹 (Binary Tree) 中，滿節點 (Full Node) 是有兩個孩子 (children) 的節點 (Node)。請證明：在非空的二元樹 (non-empty binary tree) 中，滿節點的數目加1等於樹葉 (leaves) 的數目。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、簡述關聯式資料庫中的關聯式完整性 (relational completeness)。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、下圖中，邊 (arc) 之數字代表成本 (cost)。（20分）
(一)請用相鄰矩陣 (adjacency matrix) 表示此圖之成本。
(二)請用相鄰串列 (adjacency list) 表示此圖之成本。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、某校資訊系課程可視為N 個資料元素 (data elements) 構成的一個集合，裏面每個資料元素即一門課，含(1)課號 (四位數字)(4 digits)，(2)名稱 (四個中文字) 等資料欄位 (data fields)，以”課號”為鍵 (key)，假設依序加入 (insert) 下面四門課於該集合：
1234 資料結構
2345 軟體工程
3456 網際網路
2333 離散結構
分別用下面三種資料結構來表示該集合，請分別畫圖表示之：（20分）
(一)陣列 (array)
(二)雙鏈結環狀串列 (double linked circular list)（要有頭節點 (head node)）
(三)二元搜尋樹 (binary search tree)。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、假設我們用五個桶 (buckets) 的雜湊表 (hashing table)，每個桶可放一筆資料，而雜湊函數 (hash function) h 為：
h(i) = i mod 5
使用線性探測 (linear probing) 來解決碰撞 (collision)。假設一開始雜湊表是空的，依序加入 (insert) 23, 48, 35, 4, 10 五筆資料。請繪圖顯示最後雜湊表之內容。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、對於下列元素：
2, 7, 1, 8, 4, 5, 9, 0, 3, 6
依序加入 (insert) 到原來為空 (empty) 的 2-3 樹 (即度數為 3 的 B 樹) (2-3 tree, a B tree of order 3)。請畫出結果的 2-3 樹。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
律師、會 計 師
九十一年第一次專門職業及技術人員 建 築 師、技 師 檢覈筆試試題 代號：1210 全一頁
社 會 工 作師
土地登記專業代理人
類 科：資訊技師
科 目：程式語言
考試時間：二小時 座號：______________
※注意：(1)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(2)本試題禁止使用電子計算器。
一、依序讀入下列字串資料：
Jul, Feb, May, Aug, Jan, Mar, Oct, Apr, Dec, Jun, Nov, Sep
擬以符號表 (symbol table) 存放這些資料，請回答以下問題。
（每小題4分，共20分）
(一)定義此符號表 (symbol table)。
(二)提出一種雜湊函數 (hash function)。
(三)提出一種碰撞 (collision) 處理方式。
(四)繪出資料存入後的結果。
(五)最後查詢所有資料，計算平均比較的次數。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、「堆疊」(stack) 內的元素只能從同一個出入口進出。「佇列」(queue) 裡的元素必須從同一個入口加入，但必須從另一個出口依序取出。「雙向佇列」(deque, double-ended queue) 裡的元素的加入和取出，在兩個出入口皆可進行。請詳細說明，如何以「雙連結串列」(doubly linked list) 來「製作」 (implement) 無限容量的雙向佇列，讓在兩個出入口的元素加入和取出運算，各只要花費常數時間即可達成。請注意你必須檢查雙向佇列為空或滿的情形。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、某函數的遞迴定義如下：
f(0) = 2；f(1) = 3；f(2) = 4；f(n) = 7f((n-1)/2)+2f((n-3)/2) 若 n 是奇數且大於1；f(n) = 2f(n/2) + 3f(n/2 -1) 若 n 是偶數且大於2。
試以big-oh 表示法寫出該函數遞迴版程式的空間複雜度(space complexity)，並說明計算過程。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、一個深度 (depth) 為 k 的 d 元樹 (d-ary tree) 中：
(一)最多有幾個節點 (node)？（10分）
(二)最少有幾個節點？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、試回答下列問題：
(一)四個節點能建立出多少種不同的二元樹？（5分）
(二)什麼是延伸二元樹 (Extended binary tree)？（5分）
(三)於延伸二元樹中定義二元樹的外部路徑長度為樹根到所有外部節點的路徑長度的加總。請問於(一)中的所有二元樹，什麼情況會有最大的外部路徑長度？是多少？什麼情況會有最小的外部路徑長度？是多少？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
九十一年特種考試臺灣省及福建省基層公務人員考試試題 代號：2310 全一頁
等 別：三等考試
科 別：資 訊
科 目：資料結構
考試時間：二小時 座號：____________
※注意：(1)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(2)本試題禁止使用電子計算器。
一、本題考慮的對角線均位於一個 n 乘 n 的二維矩陣由右上方到左下方的45 度斜線中。兩條對角線的距離為其位於同列元素中相差的行數。一個 n 乘n 的矩陣若其非零的元素 (element) 都位於由右上到左下的主對角線之中或離該主對角線距離為 s 且在其右下方的對角線之中，則稱之『右下 s 帶狀矩陣』。本題另外假設上述這些非零元素可能存在的地方，都存放不為零的數值。A 為一個右下 s 帶狀矩陣，A[i, j], 1<=i<=n; 1<=j<=n; 代表 A 在第 i 列與第 j 行交叉處的元素。今用一維陣列 D 儲存A 的非零元素，D 的指標由1開始計算，A 的非零元素以列為主 (row-wise)，由左到右再從上而下的次序儲存於 D。試問：
(一) D 總共有幾個元素？
(二)假設 A[i, j] 為非零，則 A[i, j] 儲存於 D 的指標位置為何？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、「佇列」(queue) 裡的元素在存放和使用上，遵循「先進先出」(first-in first-out)的原則。我們可以使用一個「單向串列」(singly linked list) 來製作一個佇列嗎？還是一定要使用「雙向串列」(doubly linked list)？如果可以，請寫出插入 (insert) 與刪除 (delete) 之演算法。如果不行，請寫出使用雙向串列之演算法。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、本題是有關於 AVL-樹，請回答下列的問題。（20分）
(一)高度為4的AVL-樹，最少的節點數目是多少？（規定樹根在 level 1）
(二)高度為4的 AVL-樹，最多的節點數目是多少？（規定樹根在 level 1）
(三)n 個任意資料所建立出來的 AVL-樹，其高度大約是多少？請以 Big-Oh表示。
(四)加入一個新資料於有 n 個節點的 AVL-樹中，所需要的時間複雜度是多少？請以 Big-Oh 表示。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、考慮三種排序方法：選擇排序法 (Selection sort)、插入排序法 (Insertion sort)、與泡沫排序法 (Bubble sort)。對於下列的問題請說明其原因：（20分）
(一)當欲排序的資料都是很長的資料錄，且它們的鍵值長度都很短時，最適合用選擇排序法，為什麼？
(二)當欲排序的資料已經幾乎達到排序結果時，最適合用插入排序法，為什麼？
(三)當欲排序的資料是完全相反次序時，最適合用選擇排序法，為什麼？
(四)當欲排序的資料是完全相同時，最適合用泡沫排序法，為什麼？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、假設一「雜湊表格」(hash table) 恰有10個儲存格(儲存格位址為 0, 1, 2,…, 9)，且採用 h(n) = n mod 10 為其「雜湊函數」(hash function, mod 為整數值餘數運算)。假設我們採取「聯結」(chaining) 方式處理「碰撞」(collision) 情形，且將新加入元素放入碰撞串列的最前頭。現要依序加入 2, 31, 15, 72, 91, 11, 13, 7, 92, 18 等十個數字，請畫出最後的雜湊表格內容。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
留言列表
國考資訊處理解答 (7)
