111 身心障礙特考三等 資訊處理 資料結構 考古題詳解

111 年・身心障礙特考・三等・資訊處理
試題代碼 資料結構

第 一 題25 分

請回答下列 Big O 的相關問題：

(一) Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在數量上的漸進趨勢。

某個問題可採用 5 個演算法 AA～EE 求解，各演算法執行時間的 Big O 分別如下：

  • AA 為 O(N2)O(N^2)
  • BB 為 O(Nlog⁡(log⁡N))O(N\log(\log N))
  • CC 為 O(N1.5)O(N^{1.5})
  • DD 為 O(N2log⁡N)O(N^2\log N)
  • EE 為 O(N)O(\sqrt{N})

當 NN 很大時，請根據演算法的執行時間，由慢至快排序這 5 個演算法。（10 分）

(二) 給定 100 萬個介於 0 到 100（含 0 及 100）的整數，請利用任一種高階程式語言寫出一個 O(N)O(N) 的由大至小排序演算法，並說明此演算法為何是 O(N)O(N) 的方法。（15 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

Big O 描述輸入規模 NN 增大時，演算法執行時間的漸進成長率。比較時忽略常數因子與低階項，重點是比較各成長函式的快慢。

本題考的是不同成長率的排序，以及利用資料值域有限的特性，以計數排序達成線性時間。

解題方法

（一）依執行時間由慢至快排序

常用成長率由慢至快的關係為：

N<Nlog⁡log⁡N<N1.5<N2<N2log⁡N\sqrt{N} < N\log\log N < N^{1.5} < N^2 < N^2\log N

逐項比較：

  • E=O(N)E=O(\sqrt{N})：次線性成長，最慢。
  • B=O(Nlog⁡log⁡N)B=O(N\log\log N)：比 N\sqrt N 快，但比 N1.5N^{1.5} 慢。
  • C=O(N1.5)C=O(N^{1.5})：介於一次與二次成長之間。
  • A=O(N2)A=O(N^2)：平方成長。
  • D=O(N2log⁡N)D=O(N^2\log N)：在平方成長上再乘以 log⁡N\log N，成長最快。

題目要求由慢至快，因此順序為：

E≺B≺C≺A≺DE \prec B \prec C \prec A \prec D

（二）值域有限的 O(N)O(N) 由大至小排序

資料共有 N=1,000,000N=1{,}000{,}000 個整數，且每個值都介於 00 到 100100。值域只有 101101 種，因此可以使用計數排序：先統計每個數值出現的次數，再依數值由大至小輸出相應次數。

以下以 Python 表示，假設輸入資料存放於串列 data：

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 二 題30 分

以下 7 個數字 [21,1,16,11,25,9,35][21, 1, 16, 11, 25, 9, 35] 要儲存到 Hash Table 中。Hash Table 的儲存空間是一個索引從 0 開始的一維陣列（Array）。

假設 Hash 函數為：

H(Key)=(Key×3) mod 7H(\mathrm{Key})=(\mathrm{Key}\times 3)\bmod 7

裝填因子（Load Factor）為 0.7。

(一) 若處理 Hash Table 衝突的方法為開放定址法（Open Addressing Hashing）中的線性探測法（Linear Probing），增量函數為：

F(i)=iF(i)=i

其中 ii 為衝突的次數。

請依序列出每存入一個數字後的 Hash Table 內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length，ASL）。（15 分）

(二) 若處理 Hash Table 衝突的方法為開放定址法（Open Addressing Hashing）中的平方探測法（Quadratic Probing），增量函數為：

F(i)=i2F(i)=i^2

其中 ii 為衝突的次數。

請依序列出每存入一個數字後的 Hash Table 內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length，ASL）。（15 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

裝填因子定義為

α=nm\alpha=\frac{n}{m}

其中 nn 是資料筆數，mm 是雜湊表大小。本題有 n=7n=7 筆資料、α=0.7\alpha=0.7，因此

m=70.7=10m=\frac{7}{0.7}=10

雜湊表索引為 00 至 99。初始位置依題目公式計算：

H(Key)=(Key×3) mod 7H(\mathrm{Key})=(\mathrm{Key}\times 3)\bmod 7

發生碰撞時，探測位置採用 (H(Key)+F(i)) mod 10(H(\mathrm{Key})+F(i))\bmod 10，其中第一次檢查的增量為 F(0)=0F(0)=0。查找成功的 ASL 是各已存資料所需探測次數的平均；查找失敗的 ASL 是各可能初始位置所需探測次數的平均。本題的雜湊值只會落在 00 至 66，故失敗查找按這 7 個初始位置等機率計算。

（一）線性探測法

線性探測的增量函數為 F(i)=iF(i)=i，因此碰撞後依序往下一格探測，並以表格大小 1010 為模數。

存入資料雜湊位置探測過程存入後的 Hash Table（索引 00 至 99）
21000[21,_,_,_,_,_,_,_,_,_][21,\_,\_,\_,\_,\_,\_,\_,\_,\_]
1333[21,_,_,1,_,_,_,_,_,_][21,\_,\_,1,\_,\_,\_,\_,\_,\_]
16666[21,_,_,1,_,_,16,_,_,_][21,\_,\_,1,\_,\_,16,\_,\_,\_]
11555[21,_,_,1,_,11,16,_,_,_][21,\_,\_,1,\_,11,16,\_,\_,\_]
2555,6,75,6,7[21,_,_,1,_,11,16,25,_,_][21,\_,\_,1,\_,11,16,25,\_,\_]
966,7,86,7,8[21,_,_,1,_,11,16,25,9,_][21,\_,\_,1,\_,11,16,25,9,\_]
3500,1,20,1,2[21,35,_,1,_,11,16,25,9,_][21,35,\_,1,\_,11,16,25,9,\_]

查找成功的 ASL

依序對應 [21,1,16,11,25,9,35][21,1,16,11,25,9,35]，探測次數為 1,1,1,1,3,3,21,1,1,1,3,3,2。因此

ASL成功=1+1+1+1+3+3+27=127≈1.714\mathrm{ASL}_{\mathrm{成功}} =\frac{1+1+1+1+3+3+2}{7} =\frac{12}{7} \approx 1.714

查找失敗的 ASL

從初始位置 00 至 66 開始查找，遇到空格即判定查找失敗。各初始位置的探測次數如下：

初始位置探測位置探測次數
00,1,20,1,23
11,21,22
2221
33,43,42
4441
55,6,7,8,95,6,7,8,95
66,7,8,96,7,8,94

故

ASL失敗=3+2+1+2+1+5+47=187≈2.571\mathrm{ASL}_{\mathrm{失敗}} =\frac{3+2+1+2+1+5+4}{7} =\frac{18}{7} \approx 2.571

（二）平方探測法

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 三 題25 分

請寫出對以下 8 個數字 [44,62,31,5,82,49,16,7][44, 62, 31, 5, 82, 49, 16, 7]，依序建構最小堆積樹（Min Heap Tree）的過程。

為方便最小堆積樹的建構，通常會使用一個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆積樹的建構。

最小堆積樹建構完成後，請寫出如何用此樹依序將數字由小到大的排序過程。請說明此種排序法的計算複雜度 Big O 為何？（25 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

最小堆積樹（Min Heap）是一棵完全二元樹，且每個節點的鍵值都小於或等於其子節點。因此，根節點是目前堆中最小的數。

若用一維陣列由上而下、由左而右儲存堆積樹，採用 1 起始索引時，索引為 ii 的節點：

  • 父節點索引：⌊i/2⌋\lfloor i/2\rfloor
  • 左子節點索引：2i2i
  • 右子節點索引：2i+12i+1

依序插入新數字時，先將數字放在陣列末端，再與父節點比較；若新數字較小，就交換並繼續向上調整，直到符合最小堆積性質。

解題方法：依序建構最小堆積

將數字依題目順序逐一插入，每次插入後進行向上調整：

插入數字插入及調整後的陣列
44[44][44]
62[44,62][44, 62]
31[44,62,31]→[31,62,44][44, 62, 31]\rightarrow[31, 62, 44]
5[31,62,44,5]→[31,5,44,62]→[5,31,44,62][31, 62, 44, 5]\rightarrow[31, 5, 44, 62]\rightarrow[5, 31, 44, 62]
82[5,31,44,62,82][5, 31, 44, 62, 82]
49[5,31,44,62,82,49]→[5,31,49,62,82,44][5, 31, 44, 62, 82, 49]\rightarrow[5, 31, 49, 62, 82, 44]
16[5,31,49,62,82,44,16]→[5,31,16,62,82,44,49]→[5,16,31,62,82,44,49][5, 31, 49, 62, 82, 44, 16]\rightarrow[5, 31, 16, 62, 82, 44, 49]\rightarrow[5, 16, 31, 62, 82, 44, 49]
7[5,16,31,62,82,44,49,7]→[5,16,31,7,82,44,49,62]→[5,7,31,16,82,44,49,62][5, 16, 31, 62, 82, 44, 49, 7]\rightarrow[5, 16, 31, 7, 82, 44, 49, 62]\rightarrow[5, 7, 31, 16, 82, 44, 49, 62]

因此，建構完成的最小堆積陣列為：

[5,7,31,16,82,44,49,62][5, 7, 31, 16, 82, 44, 49, 62]

對應的樹形如下：

 5
 / \
 7 31
 / \ / \
 16 82 44 49
 /
 62
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 四 題20 分

下圖中有 4 個城市、8 條公路，公路上的數字表示這條公路的長短。請注意，這些公路是單向的。

【題目圖表】 （原卷圖表未包含於文字層擷取結果，請參考原卷。）

若使用 Floyd Warshall 的動態規劃法求解從任意兩個城市之間的最短路徑，請回答下列問題：

(一) 首先將圖的資訊建成一個 N×NN\times N 的初始距離矩陣，其中 NN 是節點的個數。矩陣的各列（Rows）代表 From Nodes，各行（Columns）代表 To Nodes，矩陣中的值則分別代表上圖中從 From Node 到 To Node 的距離。（5 分）

(二) 其次列舉從 DD 到 CC 的最短路徑求解過程（需輸出最短路徑的值及路徑），並說明此方法的計算複雜度 Big O 為何。（15 分）

🖼️ 本題原卷含圖表。基於試題來源之版權考量，本站不轉載原卷影像； 題目文字已完整轉錄，圖表請自行參閱考選部公告之試題原檔。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查有向加權圖的 Floyd–Warshall 全點對最短路徑演算法。

令 D(k)[i][j]D^{(k)}[i][j] 表示：允許前 kk 個節點作為中繼點時，從節點 ii 到節點 jj 的最短距離。其遞迴公式為

D(k)[i][j]=min⁡(D(k−1)[i][j],D(k−1)[i][k]+D(k−1)[k][j])D^{(k)}[i][j] = \min\left( D^{(k-1)}[i][j], D^{(k-1)}[i][k]+D^{(k-1)}[k][j] \right)

也就是比較：

  • 不經過節點 kk；
  • 經過節點 kk。

本圖為單向道路，因此 i→ji\to j 與 j→ij\to i 必須分別判斷，不能將道路視為雙向。

解題方法

依圖可讀出 8 條有向道路：

A→B=2,B→C=3A\to B=2,\quad B\to C=3 A→C=6,C→A=7A\to C=6,\quad C\to A=7 A→D=4,D→A=5A\to D=4,\quad D\to A=5 C→D=1,D→C=12C\to D=1,\quad D\to C=12

節點排列順序採用 A,B,C,DA,B,C,D。

（一）初始距離矩陣

主對角線為 00；沒有直接道路的位置設為 ∞\infty。

D(0)=ABCDA0264B∞03∞C7∞01D5∞120D^{(0)} = \begin{array}{c|cccc} & A & B & C & D\\ \hline A & 0 & 2 & 6 & 4\\ B & \infty & 0 & 3 & \infty\\ C & 7 & \infty & 0 & 1\\ D & 5 & \infty & 12 & 0 \end{array}

其中列代表 From Node，欄代表 To Node。例如：

  • D[A][B]=2D[A][B]=2 表示 A→BA\to B 的距離為 22；
  • D[D][C]=12D[D][C]=12 表示 D→CD\to C 的距離為 1212；
  • D[B][A]=∞D[B][A]=\infty 表示沒有直接的 B→AB\to A 道路。

（二）求 DD 到 CC 的最短路徑

以 AA 為中繼點

D→CD\to C 可經過 AA：

D→A→C=5+6=11D\to A\to C=5+6=11

因此將原本的 1212 更新為 1111。

同時：

C→B=7+2=9C\to B=7+2=9 D→B=5+2=7D\to B=5+2=7

得到

D(A)=ABCDA0264B∞03∞C7901D57110D^{(A)} = \begin{array}{c|cccc} & A & B & C & D\\ \hline A & 0 & 2 & 6 & 4\\ B & \infty & 0 & 3 & \infty\\ C & 7 & 9 & 0 & 1\\ D & 5 & 7 & 11 & 0 \end{array}

以 BB 為中繼點

A→CA\to C 可經過 BB：

A→B→C=2+3=5<6A\to B\to C=2+3=5<6

D→CD\to C 也可經過 BB：

D→B→C=7+3=10<11D\to B\to C=7+3=10<11

因此

D(A,B)=ABCDA0254B∞03∞C7901D57100D^{(A,B)} = \begin{array}{c|cccc} & A & B & C & D\\ \hline A & 0 & 2 & 5 & 4\\ B & \infty & 0 & 3 & \infty\\ C & 7 & 9 & 0 & 1\\ D & 5 & 7 & 10 & 0 \end{array}
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

其他考古題

資訊處理《資料結構》其他年度

115110109