加載中. ..
PDF
111年公務人員特種考試關務人員、身心障礙人員考試及
111年國 軍 上 校 以 上軍 官 轉 任 公 務人 員 考 試 試 題
考 試 別
：
關務人員考試
等 別
：
三等考試
類 科
：
資訊處理
科 目
：
資料結構
考試時間：2小時 座號：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號
：
105
6
0
頁次
：
1
－
1
請分別以 bigOnotation 表示下列各個小題的時間複雜度（timecomplexity）：
（每小題 10 分，共 30 分）
2022 n ln n+111 n1.001
2022 n32n+111 n23n
2022 n!+2n
遞迴函數（recursive function）起始數值與遞迴關係定義為：
P(0) = P(1) = P(2) = 1,P(n) = P(n−1)-2P(n−2)+P(n−3), n>=3
請問 P(n)的前 5個值依序為：1,1,1,及那兩個數字？（10 分）
請問 P(6)+P(8)的值為何？（10 分）
7個工作的利潤及處理的最後期限如下表所示，並假設每個工作的處理時間均
為一個時間單位，請求出最適排程及最大利潤（maximalprofit）為何？（20 分）
工作編號 1 2 3 4 5 6 7
利潤 40 15 60 20 45 10 55
最後期限 2 4 3 2 1 3 1
以文本（text）X=“AGTCATTCGATTC”，樣式（pattern）Y=“ATTC”兩字
串為例，請問使用暴力比較/窮舉法（exhaustive search）中的樣式前向法
（forward）及後向法（backward）各需比較幾次？（10 分）
m,n N ,已知三維陣列（three-dimensional array）A[1：8, 1：9, 1：4]每一
個元素占用 2個儲存單元，並且 A[1,2,1]的儲存地址為 234，A[2,3,1]的儲
存地址是 m，A[2,3,4]的儲存地址為 n。
採用列序為主序（row major）方式儲存，則 m、n分別為何？（10 分）
採用行序為主序（column major）方式儲存，則 m、n分別為何？（10 分）