114 年 國立臺北大學資訊工程研究所《資料結構與演算法》

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊

第 Part I 1 題15 分

Run Dijkstra algorithm on the following graph to find the shortest distance from the source vertex to all vertices. The source vertex is ss. Run the algorithm step by step.

🖼️【此處有附圖，請對照原卷】

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 1 頁

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

這一題的完整詳解

核心觀念

Dijkstra 演算法用來求解邊權重皆非負的有向圖中，從單一源點到各頂點的最短距離。每一步選出目前暫定距離最小、尚未確定的頂點，將其距離定案，再用該頂點的出邊更新鄰點距離：

dist⁡(v)←min⁡(dist⁡(v),dist⁡(u)+w(u,v))\operatorname{dist}(v)\leftarrow \min\bigl(\operatorname{dist}(v),\operatorname{dist}(u)+w(u,v)\bigr)

解題方法

圖中源點為 ss。依箭頭方向讀取邊，可見 s→ds\to d 權重 99、s→cs\to c 權重 88、s→es\to e 權重 22；其餘邊為 d→ed\to e 權重 44、d→cd\to c 權重 55、e→ce\to c 權重 33、c→ac\to a 權重 77、c→bc\to b 權重 1010、a→ba\to b 權重 66。

初始化 dist⁡(s)=0\operatorname{dist}(s)=0，其他頂點距離設為 ∞\infty。每次定案目前距離最小的頂點，並依其出邊更新：

步驟定案頂點更新後的暫定距離
初始化—s=0, a=b=c=d=e=∞s=0,\ a=b=c=d=e=\infty
1ss（距離 00）d=9, c=8, e=2d=9,\ c=8,\ e=2
2ee（距離 22）經 e→ce\to c 得 2+3=52+3=5，故更新 c=5c=5
🔒

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

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

免費註冊

第 Part I 2 題5 分

Give an asymptotic upper bound for the function T(n)T(n) where T(n)T(n) satisfies the recurrent equation

T(n)=T(n/5)+T(n/10)+n.T(n)=T(n/5)+T(n/10)+n.

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

這一題的完整詳解
載入中…

第 Part I 3 題15 分

The following table shows dimensions of six matrices.

MatrixDimension
A1A_130×3530\times35
A2A_235×1535\times15
A3A_315×515\times5
A4A_45×105\times10
A5A_510×2010\times20
A6A_620×2520\times25

Please fully parenthesize the product A1A2A3A4A5A6A_1A_2A_3A_4A_5A_6 in a way such that the number of scalar multiplications is minimum and compute this minimum number.

(For example, the number of scalar multiplications of (A1(A2(A3(A4(A5A6)))))(A_1(A_2(A_3(A_4(A_5A_6))))) is 4750047500.)

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 1 頁

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

這一題的完整詳解

核心觀念

這題考矩陣鏈乘法的動態規劃。矩陣相乘的先後順序不影響最終結果，但會影響純量乘法的次數。若 AiA_i 的維度為 pi−1×pip_{i-1}\times p_i，則將 Ai⋯AjA_i\cdots A_j 相乘的最少成本滿足：

m[i,i]=0,m[i,j]=min⁡i≤k<j(m[i,k]+m[k+1,j]+pi−1pkpj)m[i,i]=0,\qquad m[i,j]=\min_{i\le k<j}\left(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\right)

其中 kk 表示把矩陣鏈切成左右兩段的位置；最後一項是左右兩段相乘所需的純量乘法次數。

解題方法

依原卷表格讀得六個矩陣維度依序為 30×3530\times35、35×1535\times15、15×515\times5、5×105\times10、10×2010\times20、20×2520\times25，因此維度序列為 [30,35,15,5,10,20,25][30,35,15,5,10,20,25]。由短鏈開始計算每一種切分的成本，並記下各鏈的最小成本。

長度為 22 的矩陣鏈：

m[1,2]=30⋅35⋅15=15750m[2,3]=35⋅15⋅5=2625m[3,4]=15⋅5⋅10=750m[4,5]=5⋅10⋅20=1000m[5,6]=10⋅20⋅25=5000\begin{aligned} m[1,2]&=30\cdot35\cdot15=15750\\ m[2,3]&=35\cdot15\cdot5=2625\\ m[3,4]&=15\cdot5\cdot10=750\\ m[4,5]&=5\cdot10\cdot20=1000\\ m[5,6]&=10\cdot20\cdot25=5000 \end{aligned}

長度為 33 的矩陣鏈：

m[1,3]=min⁡(2625+30⋅35⋅5, 15750+30⋅15⋅5)=7875m[2,4]=min⁡(750+35⋅15⋅10, 2625+35⋅5⋅10)=4375m[3,5]=min⁡(1000+15⋅5⋅20, 750+15⋅10⋅20)=2500m[4,6]=min⁡(5000+5⋅10⋅25, 1000+5⋅20⋅25)=3500\begin{aligned} m[1,3]&=\min(2625+30\cdot35\cdot5,\ 15750+30\cdot15\cdot5)=7875\\ m[2,4]&=\min(750+35\cdot15\cdot10,\ 2625+35\cdot5\cdot10)=4375\\ m[3,5]&=\min(1000+15\cdot5\cdot20,\ 750+15\cdot10\cdot20)=2500\\ m[4,6]&=\min(5000+5\cdot10\cdot25,\ 1000+5\cdot20\cdot25)=3500 \end{aligned}
🔒

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

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

免費註冊

第 Part I 4 題15 分

Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:

x1−x2≤1,x1−x4≤−4,x2−x3≤2,x2−x5≤7,x2−x6≤5,x3−x6≤10,x4−x2≤2,x5−x1≤−1,x5−x4≤3,x6−x3≤8.\begin{aligned} x_1-x_2&\leq1,\\ x_1-x_4&\leq-4,\\ x_2-x_3&\leq2,\\ x_2-x_5&\leq7,\\ x_2-x_6&\leq5,\\ x_3-x_6&\leq10,\\ x_4-x_2&\leq2,\\ x_5-x_1&\leq-1,\\ x_5-x_4&\leq3,\\ x_6-x_3&\leq8. \end{aligned}

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

這一題的完整詳解
載入中…

第 Part II 1 題18 分

請針對 Figure 1 所示的 AOE（Activity On Edge）網路，其中有向邊（directed edge）代表工作或活動，且邊上的數值代表工作或活動所需時間。

🖼️【此處有附圖，請對照原卷】

(a) 請算出每個邊的最早（earliest）開始時間 e()e() 和最晚（latest）開始時間 l()l() 與鬆散數（slack）時間，並寫出其臨界路徑（critical path）。

(b) 哪些活動，單獨的加速會導致專案長度的縮短？

活動所需時間如下：

a1=5,a2=6,a3=3,a4=4,a5=6,a6=6,a7=5,a8=3,a9=2,a10=4,a11=4,a12=5,a13=2,a14=2.\begin{aligned} a_1&=5,\quad a_2=6,\quad a_3=3,\quad a_4=4,\\ a_5&=6,\quad a_6=6,\quad a_7=5,\quad a_8=3,\\ a_9&=2,\quad a_{10}=4,\quad a_{11}=4,\quad a_{12}=5,\\ a_{13}&=2,\quad a_{14}=2. \end{aligned}
🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 2 頁

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

這一題的完整詳解

核心觀念

AOE 網路以頂點表示事件、以有向邊表示活動，邊上的數值是活動工期。頂點最早發生時間 ve(v)ve(v) 由起點向前計算，取所有前置活動完成時間的最大值；頂點最晚發生時間 vl(v)vl(v) 由終點向後計算，取所有後續活動所允許時間的最小值。

對活動 ai=(u,v)a_i=(u,v)，其最早開始時間、最晚開始時間及鬆弛時間為

e(ai)=ve(u),l(ai)=vl(v)−ti,slack(ai)=l(ai)−e(ai).e(a_i)=ve(u),\qquad l(a_i)=vl(v)-t_i,\qquad slack(a_i)=l(a_i)-e(a_i).

鬆弛時間為 00 的活動位於臨界路徑上。單獨加速某活動會縮短專案工期，該活動必須出現在每一條臨界路徑上。

解題方法

依圖讀得網路結構如下：起點分別經 a1,a2a_1,a_2 到上、下兩個節點；a3,a4a_3,a_4 匯入同一節點，接著 a5,a8a_5,a_8 匯入下一節點；其後分別經 a6,a7,a9,a10a_6,a_7,a_9,a_{10} 通往右側節點。圖中 a11a_{11} 是右上節點到終點的活動；a12,a13a_{12},a_{13} 匯入終點前的節點，再由 a14a_{14} 通往終點。

先由左向右計算各事件的最早發生時間。令起點為 SS，按圖中位置將其餘事件稱為上方節點、左下節點、中央上節點、中央下節點、右上節點、右中節點、右下節點、終點前節點及終點：

ve(S)=0,ve(上方節點)=0+5=5,ve(左下節點)=0+6=6,ve(中央上節點)=max⁡(5+3, 6+4)=10,ve(中央下節點)=max⁡(6+6, 10+3)=13,ve(右上節點)=10+6=16,ve(右中節點)=max⁡(10+5, 13+2)=15,ve(右下節點)=13+4=17,ve(終點前節點)=max⁡(15+5, 17+2)=20,ve(終點)=max⁡(16+4, 20+2)=22.\begin{aligned} ve(S)&=0,\\ ve(\text{上方節點})&=0+5=5,\\ ve(\text{左下節點})&=0+6=6,\\ ve(\text{中央上節點})&=\max(5+3,\,6+4)=10,\\ ve(\text{中央下節點})&=\max(6+6,\,10+3)=13,\\ ve(\text{右上節點})&=10+6=16,\\ ve(\text{右中節點})&=\max(10+5,\,13+2)=15,\\ ve(\text{右下節點})&=13+4=17,\\ ve(\text{終點前節點})&=\max(15+5,\,17+2)=20,\\ ve(\text{終點})&=\max(16+4,\,20+2)=22. \end{aligned}

因此專案最短完成時間為 2222。再由終點向左回推最晚發生時間：

🔒

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

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

免費註冊

第 Part II 2 題12 分

請依序利用下列數值 1000,1010,1110,0110,0111,0010,01001000,1010,1110,0110,0111,0010,0100 建一 Patricia（Practical Algorithm To Retrieve Information Coded In Alphanumeric）trie。

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

這一題的完整詳解
載入中…

第 Part II 3 題10 分

請將下列數字 49,5,9,1049,5,9,10 and 1515 依序插入 Figure 2 AVL tree 並平衡之。

🖼️【此處有附圖，請對照原卷】

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 2 頁

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

這一題的完整詳解

核心觀念

AVL 樹要求每個節點的平衡因子都介於 −1-1 與 +1+1。本題採用

BF(v)=h(左子樹)−h(右子樹)\mathrm{BF}(v)=h(\text{左子樹})-h(\text{右子樹})

其中空子樹高度為 −1-1、葉節點高度為 00。插入節點後，從插入位置往根節點檢查；若某節點的平衡因子變成 +2+2 或 −2-2，就依失衡方向進行單旋轉或雙旋轉。

解題方法

圖中的初始 AVL 樹根節點為 1414；左子樹為 77，其子節點是 44 與 1111，而 1111 的右子節點是 1313。右子樹為 1717，其右子節點是 5353。依序插入 49,5,9,10,1549,5,9,10,15，每次插入後都立即檢查並平衡。

  1. 插入 4949：對節點 1717 做 RL 雙旋轉

    4949 插入為 5353 的左子節點，使 1717 的平衡因子成為 −2-2，而其右子節點 5353 的平衡因子為 +1+1。因此對 1717 做 RL 雙旋轉，該子樹調整為：

        49
   /  \
  17  53

    此時全樹為：

        14
   /  \
  7    49
 / \   / \
4  11 17 53
    \
    13

  2. 插入 55：不需旋轉

    55 插入為 44 的右子節點。調整後，44、77、1414 的平衡因子都仍在 −1-1 至 +1+1 之間，因此不旋轉。

  3. 插入 99：不需旋轉

    99 插入為 1111 的左子節點。此時 1111 的左右子樹高度相同，77 與 1414 也仍符合 AVL 平衡條件，因此不旋轉。

  4. 插入 1010：對根節點 1414 做 LR 雙旋轉

    1010 插入為 99 的右子節點。此時節點 1414 的平衡因子為 +2+2，其左子節點 77 的平衡因子為 −1-1，屬於 LR 失衡。

🔒

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

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

免費註冊

第 Part II 4 題10 分

請利用 Bellman-Ford 演算法一步一步算出 Figure 3 從 node 11 到各點之最短距離。

e12=6,e13=5,e14=5,e25=−1,e32=−2,e35=1,e43=−2,e46=−1,e56=2.\begin{aligned} e_{12}&=6,\quad e_{13}=5,\quad e_{14}=5,\\ e_{25}&=-1,\quad e_{32}=-2,\quad e_{35}=1,\\ e_{43}&=-2,\quad e_{46}=-1,\quad e_{56}=2. \end{aligned}

🖼️【此處有附圖，請對照原卷】

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 2 頁

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

這一題的完整詳解

核心觀念

Bellman–Ford 演算法可處理含負權重邊的有向圖。令 Dk(v)D_k(v) 表示從起點 11 到節點 vv、且最多使用 kk 條邊的最短距離，則：

Dk(v)=min⁡(Dk−1(v), min⁡(u,v)∈E{Dk−1(u)+w(u,v)})D_k(v)=\min\left(D_{k-1}(v),\ \min_{(u,v)\in E}\{D_{k-1}(u)+w(u,v)\}\right)

圖中共有 66 個節點，因此最多考慮 ∣V∣−1=5|V|-1=5 條邊；若第 66 輪仍有距離改善，才表示存在從起點可到達的負權重環。

解題方法

圖中有向邊為 1→21\to2（權重 66）、1→31\to3（55）、1→41\to4（55）、2→52\to5（−1-1）、3→23\to2（−2-2）、3→53\to5（11）、4→34\to3（−2-2）、4→64\to6（−1-1）、5→65\to6（22）。以節點 11 為起點，初始距離為 D0(1)=0D_0(1)=0，其餘節點距離皆為 ∞\infty。以下每一輪都用上一輪的距離計算，表示最多使用指定條數的邊。

最多使用邊數 kkDk(1)D_k(1)Dk(2)D_k(2)Dk(3)D_k(3)Dk(4)D_k(4)Dk(5)D_k(5)Dk(6)D_k(6)
0000∞\infty∞\infty∞\infty∞\infty∞\infty
1100665555∞\infty∞\infty
22003333555544
33001133552244
44001133550044
🔒

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

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

免費註冊

其他考古題

114 年臺北大學的其他科目

線性代數與離散數學

臺北大學《資料結構與演算法》其他年度

115 年113 年112 年111 年109 年108 年

其他學校的資工系考古題

臺灣大學36清華大學3陽明交通大學24成功大學24中央大學51中正大學34中山大學50高雄大學7暨南國際大學6嘉義大學4臺南大學2