104 公 職 地 方 特 考 分 詳 解 程 式 語 言 一 請 試 述 下 列 名 詞 之 意 涵 :( 每 小 題 3 分, 共 15 分 ) ( 一 )Context-Free Grammar ( 二 )LR parser ( 三 )Binding time ( 四 )Turing Machine ( 五 )Dynamic Programming 考 命 中 本 題 為 名 詞 解 釋, 相 較 於 以 往 三 等 程 式 語 言 考 試 中, 屬 於 較 少 見 的 題 目 但 名 詞 部 分 除 LR parser 外, 其 餘 充 分 準 備 的 考 生 應 都 不 陌 生, 歷 年 也 曾 出 現 過 許 多 相 似 題, 如 103 檢 事 官 100 檢 事 官 99 考 94 地 特 等 由 於 每 題 僅 佔 3 分, 因 此 僅 需 簡 單 說 明 每 個 概 念 的 內 容 即 可, 不 需 要 太 深 入 探 討 以 免 錯 失 其 餘 題 目 得 分 機 會 1. 程 式 語 言 講 義 第 六 回, 金 乃 傑 編 撰, 頁 1-2 2. 程 式 語 言 講 義 第 三 回, 金 乃 傑 編 撰, 頁 56-57 3. 程 式 語 言 講 義 第 一 回, 金 乃 傑 編 撰, 頁 115 4. 程 式 語 言 講 義 第 二 回, 金 乃 傑 編 撰, 頁 29-30 ( 一 ) 下 文 無 關 文 法 (Context-Free Grammar): 若 一 個 形 式 文 法 G = (N, Σ, P, S) 的 產 生 規 則 都 如 :V w, 則 稱 之, 其 中 V N,w (N Σ)* 因 為 V 符 號 總 可 以 被 w 字 串 自 由 替 換, 而 無 需 考 慮 V 符 號 出 現 的 下 文 故 為 下 文 無 關 由 於 下 文 無 關 語 法 表 達 能 力 好, 幾 乎 所 有 程 式 語 言 的 語 法 都 是 用 此 語 法 定 義 ( 二 )LR 剖 析 器 (LR parser): 為 編 譯 器 中 語 法 剖 析 的 程 式, 功 能 為 建 構 語 法 樹 LR 意 指 由 左 至 右 (left to right) 處 理 輸 入 字 串, 並 以 最 右 邊 優 先 衍 生 (Right derivation) 的 推 導 順 序 由 於 LR 剖 析 器 嘗 試 由 剖 析 樹 的 葉 節 開 始, 向 一 層 層 透 過 文 法 規 則 的 化 簡, 最 後 規 約 回 到 樹 的 根 部 ( 起 始 符 號 ), 所 以 它 是 一 種 由 下 而 的 剖 析 方 法 ( 三 ) 繫 結 時 間 (Binding time): 為 程 式 實 體 (program entity) 與 其 屬 性 (attributes) 發 生 關 聯 (association) 的 動 作 依 照 時 間 的 不 同 可 分 為 定 義 (Definition, 設 計 程 式 語 言 ) 實 作 (Implementation, 在 機 器 的 運 行 規 範 ) 編 譯 (Compilation / Translation) 及 執 行 (Execute) 等 四 個 時 期 ( 四 ) 圖 靈 機 (Turing Machine): 為 英 國 數 學 家 圖 靈 於 1936 年 提 出 的 一 種 抽 象 計 算 模 型 圖 靈 的 基 本 思 想 是 用 機 器 來 模 擬 人 用 紙 筆 進 行 數 學 運 算 的 過 程, 可 分 為 兩 種 動 作 : 在 紙 寫 或 擦 除 某 個 符 號 ; 把 注 意 力 從 紙 的 一 個 位 置 移 動 到 另 一 個 位 置 基 於 此 動 作, 圖 靈 機 的 元 件 包 括 一 條 無 限 長 的 紙 帶 讀 寫 頭 狀 態 暫 存 器 及 一 套 控 制 規 則 ( 五 ) 動 態 規 劃 (Dynamic Programming): 是 一 種 在 數 學 電 腦 科 學 中 使 用 的 計 算 方 法, 透 過 將 原 問 題 分 解 為 相 對 簡 單 的 子 問 題 的 方 式 求 解 複 雜 的 問 題 動 態 規 劃 的 效 益 來 自 於 將 子 問 題 的 答 案 暫 存, 避 免 子 問 題 被 重 新 計 算, 以 空 間 換 取 時 間 例 如 : 在 計 算 費 式 級 數 時, 將 f(2) f(3) 的 結 果 暫 存, 因 此 在 計 算 f(4) 時 就 不 需 要 重 複 計 算 f(1)~f(3) 了 二 1O TBytes 換 算 為 多 少 bits?(5 分 ) 本 題 屬 於 計 算 機 概 論 題 目, 只 要 細 心 應 可 輕 鬆 得 分 1 TB = 8 * 2^40 bits = 8,796,093,022,208bits 因 為 : 1TB = 1,024GB = 2^10GB 1GB = 1,024MB = 2^10MB 1MB = 1,024KB = 2^10KB - 1 -
104 公 職 地 方 特 考 分 詳 解 1KB = 1,024B = 2^10B 1B = 8bits 三 關 於 副 程 式 中 參 數 的 binding 可 分 為 shallow binding deep binding 和 ad hoc binding 等 方 法 : ( 一 ) 請 解 釋 述 三 種 binding 的 差 別 與 優 缺 (9 分 ) ( 二 ) 下 列 為 Java Script 的 syntax codes, 請 問 執 行 subl 之 後, 最 後 x 的 輸 出 ( 在 sub2) 為 多 少? 請 根 據 述 三 種 binding 分 別 作 答 (6 分 ) function subl() { var x; function sub2() {altert(x);} // 輸 出 x function sub3() { var x; x=3; suh4(sub2);} function sub4(subx) { var x; x=4; subx();} x=l; sub3();}; 本 題 為 繫 結 的 進 階 考 題, 考 非 區 域 變 數 取 值 的 三 種 方 法 雖 以 往 繫 結 都 以 名 詞 解 釋 出 現 ( 如 101 年 關 務 四 等 考 試 ), 沒 有 較 深 入 題 目, 但 由 於 此 題 為 講 義 中 經 典 補 充, 若 充 分 準 備 的 考 生 應 能 得 心 應 手, 獲 得 不 錯 的 分 數 考 命 中 1. 程 式 語 言 講 義, 第 三 回, 金 乃 傑 編 撰, 頁 76-77 2. 地 方 特 考 題 神 考 前 猜 題 程 式 語 言 重 整 理, 金 乃 傑 編 撰, 考 6 再 次 命 中! ( 一 ) 三 種 繫 結 的 差 別 與 優 缺 比 較 如 下 : 內 容 淺 繫 結 (Shallow Binding) 深 繫 結 (Deep Binding) 特 設 繫 結 (Ad-hoc Binding) 為 副 程 式 變 數 取 值 的 實 作 方 為 副 程 式 變 數 取 值 的 實 作 方 為 副 程 式 變 數 取 值 的 實 作 方 式, 指 副 程 式 中 若 無 定 義 變 式, 指 副 程 式 中 若 無 定 義 變 式, 指 副 程 式 中 若 無 定 義 變 數, 則 會 參 考 執 行 副 程 式 的 敘 數, 則 會 參 考 副 程 式 定 義 時 結 數, 則 會 參 考 呼 叫 副 程 式 時 的 述 當 時 環 境 的 變 數 值 來 取 值 構 的 層 來 取 變 數 值 環 境 來 取 變 數 值 優 執 行 效 率 : 可 直 接 參 考 活 動 可 讀 性 : 依 照 結 構 取 值, 容 彈 性 : 可 在 執 行 時 動 態 決 定 紀 錄 堆 疊 層 決 定 變 數 值 易 理 解 推 算 變 數 值 副 程 式 中 的 變 數 值 缺 可 讀 性 低 : 難 以 直 觀 判 斷 函 數 彈 性 低 : 程 式 設 計 師 無 法 根 據 執 行 效 能 差 : 尋 找 變 數 定 義 必 中 的 變 數 值, 程 式 維 護 難 需 求 自 動 替 換 函 數 中 的 變 數 須 沿 動 態 鏈 往 找 到 呼 叫 處 才 值 能 決 定 ( 二 )X 的 輸 出 結 果 如 下 : 1. 淺 繫 結 (Shallow Binding): 印 出 4 sub1() 中 敘 述 呼 叫 sub3(), 而 sub3() 將 sub2() 視 為 參 數 傳 入 sub4(), 在 sub4() 中 的 subx() 即 為 sub2(), 且 sub4() 中 區 域 變 數 x 值 為 4, 故 sub2() 將 4 印 出 2. 深 繫 結 (Deep Binding): 印 出 1 sub1() 中 經 過 一 連 串 的 呼 叫 到 版 sub2() 權 時 所, 要 有 取 x 的, 值 即 重 往 sub2() 製 必 的 究 層 (sub1()! 中 ) 取 出 區 域 變 數 x 值 為 1, 故 將 1 印 出 3. 特 設 繫 結 (Ad-hoc Binding): 印 出 3 sub1() 中 敘 述 呼 叫 sub3(), 而 sub3() 將 sub2() 視 為 參 數 傳 入 sub4(), 在 此 同 時, 也 是 程 式 調 用 sub2() 之 處, 故 sub2() 要 取 出 x 值 的 時 候, 就 會 參 考 到 此 時 sub3() 中 的 x 的 值, 故 印 出 3-2 -
104 公 職 地 方 特 考 分 詳 解 四 函 數 f(n) 定 義 如 下 :f(l)=1,f(0)=0,f(n)=f(n-2)+2f(n-l), 請 問 f(5) 等 於 多 少?(5 分 ) 本 題 為 費 式 數 列 計 算, 必 須 寫 出 計 算 過 程, 若 僅 寫 答 案 分 數 恐 不 理 想 由 於 題 目 較 簡 單, 應 細 心 作 答, 以 免 懊 悔 萬 分 考 命 中 程 式 語 言 講 義, 第 二 回, 金 乃 傑 編 撰, 頁 28-30 f(5) = 5 計 算 過 程 如 下 : f(5) = f(3) + f(4) = 2 + 3 = 5 f(4) = f(2) + f(3) = 1 + 2 = 3 f(3) = f(1) + f(2) = 1 + 1 = 2 f(2) = f(0) + f(1) = 0 + 1 = 1 五 對 於 字 串 的 長 度, 不 同 的 語 言 有 不 同 的 設 計 方 式, 包 括 static length string limited dynamic length string dynamic length string:( 每 小 題 6 分, 共 12 分 ) ( 一 ) 請 解 釋 述 三 種 不 同 設 計 方 式 ( 二 ) 對 於 Java C 和 C++ 這 三 種 語 言, 它 們 對 字 串 長 度 設 計 的 方 式 各 採 取 那 種 方 式 或 混 和? 本 題 為 字 串 長 度 之 題 目 以 往 雖 有 不 同 語 言 中 字 串 的 細 部 考 題, 如 101 年 警 察 100 年 普 考 96 關 務 四 等, 但 今 年 的 題 型 不 僅 較 有 結 構, 而 且 還 須 說 明 三 種 語 言 的 實 作, 必 須 對 每 種 語 言 的 字 串 都 有 一 定 了 解 才 能 拿 到 分 在 答 案 撰 寫 面, 亦 必 須 注 意 題 意, 第 一 小 題 先 條 列 寫 出 三 種 方 法, 並 配 合 舉 例 說 明 三 種 方 法 之 用 法 背 後 可 能 的 技 術 ; 第 二 小 題 也 應 切 合 問 題 指 出 各 採 取 哪 種 方 式, 始 能 拿 到 分 考 命 中 1. 程 式 語 言 講 義 第 三 回, 金 乃 傑 編 撰, 頁 34-37 2. 程 式 語 言 講 義 第 四 回, 金 乃 傑 編 撰, 頁 2 ( 一 ) 三 種 不 同 的 設 計 方 式 說 明 如 下 : 1. 靜 態 長 度 字 串 (static length string): 字 串 在 宣 告 時 長 度 已 決 定, 且 不 能 再 修 改 例 如 : 在 C 語 言 中 以 char *s = hello world 宣 告, 則 此 時 s 之 長 度 就 已 經 固 定 為 12 個 char 了 ( 包 含 最 後 一 個 結 束 符 號 \0) 2. 有 限 可 變 長 度 字 串 (limited dynamic length string): 字 串 在 宣 告 時 長 度 已 決 定, 但 可 能 會 預 留 一 些 空 間 以 在 未 來 存 入 更 多 字 串 例 如 : 在 C 語 言 中 以 char s[50] 宣 告, 則 s 最 大 長 度 是 50, 但 程 式 設 計 師 可 透 過 strcpy(s, hello world ) 將 較 短 的 字 串 存 入 3. 動 態 長 度 字 串 (dynamic length string): 字 串 在 使 用 時, 可 以 依 照 需 求 動 態 改 變 長 度, 通 常 在 實 作 時 必 須 將 字 串 型 態 定 義 為 類 別, 並 透 過 宣 告 字 串 物 件 來 建 立 因 為 字 串 為 一 個 物 件, 故 內 容 可 透 過 鏈 結 串 列 或 參 考 到 另 一 實 際 儲 存 字 串 的 空 間 來 儲 存 字 元, 達 到 長 度 可 動 態 變 化 ( 二 ) 對 於 Java C 與 C++ 三 種 語 言 所 採 取 的 方 式 說 明 如 下 : 1.Java: 提 供 動 態 長 度 字 串 靜 態 長 度 字 串 在 Java 中 字 串 為 一 類 別, 宣 告 方 法 如 String s1 = new String( hello world ); 但 另 外 也 可 以 透 過 String s2 = hello world 將 字 串 定 義 為 一 常 數 若 字 串 為 常 數 時, 則 字 串 為 靜 態 長 度 ( 儲 存 在 code segment) 但 因 s2 為 一 個 參 考, 仍 然 可 以 透 過 s2 = new String( Jack ) 等 語 法 參 考 到 其 他 字 串 物 件, 引 此 長 度 的 限 制 不 會 對 程 式 造 成 影 響 2.C 語 言 : 提 供 靜 態 長 度 字 串 有 線 靜 態 長 度 字 串 在 C 語 言 中 字 串 是 使 用 字 元 陣 列 模 擬 而 來, 因 此 若 預 先 沒 有 宣 告 長 度, 如 char *s1 = hello world 就 為 固 定 長 度 ; 若 預 先 宣 告 長 度 char s2[50] 則 為 有 限 可 變 長 度 3.C++: 提 供 靜 態 長 度 字 串 有 線 可 變 長 度 字 串 動 態 長 度 字 串 三 種 在 C++ 標 準 函 式 庫 提 供 了 string 類 別, 使 用 前 要 先 include <string> C++ 中 建 立 String 物 件 可 透 過 string - 3 -
104 公 職 地 方 特 考 分 詳 解 s1( hello world ) 來 建 立 六 給 定 下 列 的 文 法 (Grammar): <assign> <id> = <expr> <id>=a B C <cxpr> <expr>+<id> <expr>*<id> (<expr>) <id> 請 畫 出 右 列 字 串 :A = ((A*B)+C*A), 所 對 應 right-most derivation sequence 與 對 應 的 分 析 樹 (parse tree) (5 分 ) 本 題 為 104 身 心 障 礙 104 關 務 4 等 102 升 官 101 地 特 101 鐵 路 等 的 相 似 題, 若 充 分 練 習, 細 心 作 答, 得 到 滿 分 絕 非 難 事 考 命 中 1. 程 式 語 言 講 義 第 六 回, 金 乃 傑 編 撰, 頁 56-57 2. 地 方 特 考 題 神 考 前 猜 題 程 式 語 言 重 整 理, 金 乃 傑 編 撰, 考 15 再 次 命 中! ( 一 ) 最 右 推 倒 過 程 如 下 : 1. <assign> 2. <id> = <expr> 3. <id> = (<expr>) 4. <id> = (<expr>*<id>) 5. <id> = (<expr>*a) 6. <id> = (<expr>+<id>*a) 7. <id> = (<expr>+c*a) 8. <id> = ((<expr>)+c*a) 9. <id> = ((<expr>*<id>)+c*a) 10. <id> = ((<expr>*b)+c*a) 11. <id> = ((<id>*b)+c*a) 12. <id> = ((A*B)+C*A) 13. A = ((A*B)+C*A) ( 二 ) 分 析 樹 如 下 : - 4 -
104 公 職 地 方 特 考 分 詳 解 七 請 計 算 下 列 式 子 最 後 的 y 值 :( 每 小 題 3 分, 共 15 分 ) ( 一 ) int x=3, y=2; y*= ++x + 3; ( 二 ) int x=3, y=2; y /= x++; ( 三 ) int x=10, y=l; y= x++ + --y; ( 四 ) int x=10, y=l; y /= ++x + y--; ( 五 ) int y=0; for(int k=0; k < 10; y+=k) { if(++k ==6) continue; k++;} 本 題 一 到 四 小 題 為 前 置 加 ( 減 ) 與 後 繼 加 ( 減 ) 的 題 目, 作 答 時 需 掌 握 後 繼 會 再 敘 述 完 成 後 再 改 變 變 數 之 值 另 外 也 需 注 意 *= 等 指 定 運 算 子 也 優 先 順 序 比 加 減 乘 除 還 低, 因 此 必 須 等 右 手 邊 算 式 做 完 後 才 會 展 開 帶 入 若 能 掌 握 這 些 原 則 搭 配 細 心 作 答, 應 能 得 分 第 五 小 題 為 迴 圈 求 值 的 題 目, 其 考 還 是 在 其 中 的 if() 每 次 進 迴 圈 都 會 判 斷, 故 if() 中 的 ++k 也 會 每 次 進 迴 圈 都 做, 故 k 的 值 都 會 被 先 加 1 考 命 中 1. 程 式 語 言 講 義 第 一 回, 金 乃 傑 編 撰, 頁 37-40 2. 地 方 特 考 題 神 考 前 猜 題 程 式 語 言 重 整 理, 金 乃 傑 編 撰, 考 3 再 次 命 中! ( 一 )14 y *= ++x + 3; y *= 4 + 3 y *= 7 y = y * 7 y = 2 * 7 y = 14 ( 二 )0 y /= x++ y /= 3 y = y/3 y = 2/3 = 0.6666 但 取 整 數 部 分 ( 無 條 件 捨 去 ), 故 為 0 ( 三 )10 y = x++ + --y y = 10 + 0 y = 10 ( 四 )-1 y /= ++x + y-- y /= 11 + 1 y /= 12 y = y/12 y = 1/12 y = 0 在 此 敘 述 執 行 後, 因 前 有 y--, 會 再 將 答 案 減 1, 故 為 -1 ( 五 )30 原 式 可 改 寫 為 : for(k = 0~9){ ++k; if(k == 6) continue; k++; y += k; - 5 -
104 公 職 地 方 特 考 分 詳 解 } 每 一 圈 k 與 y 的 值 為 : 圈 數 0( 初 始 狀 態 ) 1 2 3 4 5 k 0 2 4 6 8 10( 下 次 會 跳 出 迴 圈 ) y 0 2 6 12 20 30 八 若 採 取 二 種 不 同 參 數 傳 遞 的 方 法 :pass by reference pass by value result, 執 行 下 列 程 式, 則 x 與 y 的 值 各 為 多 少?(8 分 ) int x=1, y=3; void fun(int a, int b); void main() { int x=2; fun(x, y); printf("x=%d, y=%d", x, y); } void fun(int a, int b) {a=b+x; b=a+y;} 本 題 為 參 數 傳 遞 考 題, 與 103 考 102 考 99 關 務 94 地 特 相 似, 但 因 有 全 域 變 數, 因 此 在 作 答 時 建 議 使 用 老 師 課 所 教 之 解 題 線, 較 不 會 因 為 粗 心 而 丟 失 分 數 另 外 值 得 注 意 的 是 今 年 考 出 多 年 未 考 的 pass by value result, 需 掌 握 此 法 為 使 用 call by value 模 擬 call by reference, 先 做 call by value, 等 副 程 式 執 行 完 後 再 將 結 果 寫 回, 故 若 副 程 式 中 沒 有 副 作 用, 則 答 案 與 call by reference 相 同 考 命 中 1. 程 式 語 言 講 義 第 二 回, 金 乃 傑 編 撰, 頁 6-14 2. 地 方 特 考 題 神 考 前 猜 題 程 式 語 言 重 整 理, 金 乃 傑 編 撰, 考 7 再 次 命 中! ( 一 )pass by reference 結 果 為 :x = 4, y = 7 global main fun x y x a b 1 3 7 2 4 參 考 到 main 的 x 運 算 式 :a = b + x global: y + global: x 3 + 1 = 4( 與 main 的 x 同 步 ) ( 二 )pass by value result 結 果 為 :x = 4, y = 7 global main fun x y x a b 1 3 7 2 4 數 值 2 運 算 式 :a = b + x 3 + global: x 3 + 1 = 4 ( 寫 回 main) 參 考 到 global 的 y 運 算 式 :b = a + y 4 + global: y 4 + 3 = 7( 與 global 的 y 同 步 ) 數 值 3 運 算 式 :b = a + y 4 + global: y 4 + 3 = 7 ( 寫 回 global) 九 ( 一 ) 如 果 有 兩 個 整 數 x,y, 請 寫 出 相 對 應 的 副 程 式 碼, 使 得 這 兩 數 可 以 做 交 換 (5 分 ) ( 二 )T c[l0];int m=3, n=2;(t 為 某 種 type, 可 能 為 int float double 等 ), 請 寫 出 相 對 應 的 副 程 式 碼 swap, 當 呼 叫 形 式 為 swap(c, m, n), 可 讓 c[m] 跟 c[n] 的 值 做 交 換, 即 使 T 的 型 態 不 同, 此 程 式 一 樣 可 以 正 確 處 理 (5 分 ) - 6 -
104 公 職 地 方 特 考 分 詳 解 本 題 為 久 未 出 現 的 C 語 言 函 數 樣 板 題 目, 與 97 年 考 類 似 若 能 掌 握 C 語 言 函 數 樣 板 的 語 法, 並 能 熟 悉 C 語 言 中 陣 列 傳 入 函 數 的 寫 法, 此 題 應 能 迎 刃 而 解 考 命 中 程 式 語 言 講 義 第 四 回, 金 乃 傑 編 撰, 頁 115-117 ( 一 ) 以 C++ 撰 寫 如 下 : 註 : 此 處 使 用 C++ 的 傳 參 考 呼 叫, 寫 起 來 最 簡 潔 乾 淨 ( 二 ) 以 C++ 撰 寫 如 下 : 執 行 結 果 : n 十 利 用 template 的 概 念, 寫 出 一 個 函 數 power(x, n) 可 以 計 算 x, 不 管 x 為 實 數 整 數 或 自 然 數, - 7 -
104 公 職 地 方 特 考 分 詳 解 但 假 設 n 為 整 數 (10 分 ) 本 題 配 10 分, 考 除 了 template 外, 還 需 實 作 次 方 雖 C++ 中 有 Math 函 式 庫 中 的 pow() 可 用, 但 若 使 用 了 會 使 答 案 程 式 碼 沒 有 內 容 (pow() 已 經 很 完 整, 有 7 種 多 載, 也 可 以 接 受 整 數 浮 數 雙 倍 精 度 浮 數 長 整 數 等 ) 因 此 若 要 得 到 滿 分, 除 了 必 須 自 己 用 迴 圈 處 理 次 方, 還 必 須 要 注 意 題 目 中 提 到 的 n 為 整 數, 故 n 可 能 為 負 因 此 要 考 慮 到 n 次 方 n 為 負 數 0 或 1 的 情 形 考 命 中 程 式 語 言 講 義 第 四 回, 金 乃 傑 編 撰, 頁 115-117 以 C++ 撰 寫 如 下 : - 8 -