台師大資工暑轉 102 轉學考：計概詳解！

解答：

• decimal：85.625
• hexadecimal：55.A

詳解：

以下列出 (1010101.101)₂ 每一位置的權重。

1	0	1	0	1	0	1	.	1	0	1
64	32	16	8	4	2	1	.	0.5	0.25	0.125

將 (1010101.101)₂ 換成十進位（decimal）：64＋16＋4＋1＋0.5＋0.125＝85.625

將二進位轉成十六進位時，只要將每 4 位轉成十進位的 1 位數字就好了

101	0101	.	101
↓	↓	↓	↓
5	5	.	A

註：十六進位中大於十的部分會用大寫英文字母代替：

A	B	C	D	E	F
10	11	12	13	14	15

解答：

• unsigned：［ 0 , 63 ］
• two's complement：［ -32 , 31 ］

詳解：

• unsigned format：［ 0 , 63 ］
• two's complement format：［ -32 , 31 ］

unsigned：無正負號。代表全 bit 都只用來表示正數。6-bits 最大值：111111；最小值：000000。換成十進位數就是，Max：63；min：0。

二的補數表示法（two's complement format）能表示的數字總數：負數＆零＋整數，各佔一半，2⁶ ÷ 2＝32，所以負數能表示到 -32，但正數只能表示到 32 − 1＝31，減 1 是減掉零這個數字。Max：31、min：-32。

解答：-43。
詳解：

在 two's complement number 二的補數表示法中，只要第一個數字是「1」，就代表這是一個負數，而求值的話，就必須轉成二的補數才能計算：

註：轉換二的補數的快速方法或技巧：從右邊往左，遇到第一個「1」前都照抄，包含第一個「1」，而後的數字 0 換成 1，1 換成 0。

原數	1	0	1	0	1	0	1
補數	0	1	0	1	0	1	1

計算二的補數得值：1＋2＋8＋32＝43，所以 (1010101)₂ 轉成十進位為 -43。

解答：14 bits。
詳解：（註：因為題目沒特別說是用哪種數字表示法，所以以下我將每一種表示法所需的 bit 數都列了出來。）

• Unsigned Representation：unsigned：無正負號。代表全 bit 都只用來表示正數。13 bits 最大可表示 2¹³ − 1＝8191；14 bits 最大可表示 2¹⁴ − 1＝16383。所以此表示法最少需要 14 bits。
• Sign-and-Magnitude Representation：最左邊第一個 bit 用來表示正負號，右邊剩餘的 bit 才用來表示數值。14 bits 最大可表示 2¹³ − 1＝8191；15 bits 最大可表示 2¹⁴ − 1＝16383。所以此表示法最少需要 15 bits。
• Two's Complement Representation：二的補數表示法能表示的數字總數：負數＆零＋整數，各佔一半。14 bits 最大可表示 2¹⁴ ÷ 2 − 1＝8191；15 bits 最大可表示 2¹⁵ ÷ 2 − 1＝16383。所以此表示法最少需要 15 bits。

註：而這種數字表示法中「Unsigned Representation」所需的 bit 數最少，所以答案認為是 14 bits。

解答：（a）OR（b）AND（c）NOR
詳解：

• OR：與 0 做運算時，會保持原狀態。
• AND：與 1 做運算時，會保持原狀態。
• NOR：與 1 做運算時，會改變原狀態。

解答：x'＋y。
詳解：

    （x'・y'）＋（x'・y）＋（x・y）（後兩項可由公式簡化：ab＋ab'＝a）
＝（x'・y'）＋y（可由公式簡化：a＋ab'＝a＋b）
＝   x'＋y

解答：fetch、decode。
詳解：CPU 執行程序：

• Fetch：將 Instruction 存在 Instruction Register（IR）中，將地址存在 Program Counter（PC）中
• Decode：將 Instruction Register（IR）中的 Instruction 解碼
• Execute：執行 decode 後的 Instruction，將所需的 data 存到 Register 中，並靠 ALU 做計算。

解答：Program Counter。
詳解：一開始 instruction 與 data 都儲存在 Memory 中。

CPU 包含三個部分：

• ALU
• Register
• Control unit：Program Counter（PC）、Instruction Register（IR）

CPU 執行程序：

• Fetch：將 Instruction 存在 Instruction Register（IR）中，將地址存在 Program Counter（PC）中
• Decode：將 Instruction Register（IR）中的 Instruction 解碼
• Execute：執行 decode 後的 Instruction，將所需的 data 存到 Register 中，並靠 ALU 做計算。

解答＆詳解：

• Programmed I/O：CPU 在執行程式碼時，遇到需要從 I/O 輸入資料時，會通知 I/O，並等到 I/O 完成輸入時，才會再繼續執行下面的程式碼。
• Interrupt-driven I/O：CPU 在執行程式碼時，遇到需要從 I/O 輸入資料時，會通知 I/O，並繼續執行其他程式碼，等到 I/O 完成輸入時，會再通知 CPU。
• Interrupt-driven I/O：CPU 在執行程式碼時，遇到需要從 I/O 輸入資料時，會通知 I/O，並繼續執行其他程式碼，等到 I/O 完成輸入時，會再通知 CPU。

解答＆詳解：Data bus／Address bus／Control bus。

解答：19 bits。
詳解：

Opcode 指的是指令 instruction，所以需要至少 4 bits，因為 2³＝8 ≤ 10 ≤ 16＝2⁴。
Register address 則需要 5 bits，因為 2⁵＝32。
所以題目的 instruction 總共需要 4＋5 × 3＝19 bits。

解答：

• Application
• Transport
• Network
• Data Link
• Physical

詳解：TCP/IP 分為五層

• Application：client-server、peer-to-peer（P2P）、WWW、HTTP、URL、FTP、Email、TELNET、Secure Shell（SSH）、Domain Name System（DNS）、STMP
• Transport：port number、User Datagram Protocol（UDP）、Transmission Control Protocol（TCP）
• Network：Packetizing、Routing、IP、IPv4、IPv6
• Data link：Local area networks（LANs）、Ethernet、WiFi、WANs、MAC
• Physical：Analog＆Digital

解答＆詳解：port number。

解答＆詳解：CDBA。

解答＆詳解：

User Datagram Protocol（UDP）	Transmission Control Protocol（TCP）
connectionless	connection-oriented
不可靠的傳輸層協定	可靠的傳輸層協定
8 bytes Header	20 to 60 bytes Header
use checksums
	use sequence numbers
	use acknowledgment numbers

解答＆詳解：

• Bus Topology：各節點連接到一個公用的網絡上
• Star Topology：各節點連接到一個網絡集中設備
• Ring Topology：每個節點連接左右兩個節點，將各節點串成一個環狀
• Mesh Topology：網狀網絡拓墣

解答：

• Partitioning：Memory 切割成大小不一的分段，每個分段儲存一個完整的程式。
• Paging：Memory 和 Program 切割成相同大小的分段，相同程式的分段可不連續的存於 Memory 中。

詳解：Multiprogramming 同時有大於一個程式在 Memory 中，可分成以下四種：

• Nonswapping：Partitioning、Paging
• Swapping：Demand paging、Demand segmentation
• Partitioning：Memory 切割成大小不一的分段，每個分段儲存一個完整的程式。
• Paging：改善 Partitioning 方法。Memory 和 Program 切割成相同大小的分段，相同程式的分段可不連續的存於 Memory 中，但還是必須整個程式都在 Memory 中。
• Demand paging：改善 Paging 方法。Memory 和 Program 切割成相同大小的分段，但不須整個程式都在 memory 中。
• Demand segmentation：將 Demand paging 中「切割成相同大小分段」的方法，改成符合程式設計的分段，所以每個 Segmentation 的大小不一。

解答：

• Paging：必須整個程式都在 Memory 中。
• Demand paging：改善 Paging 方法。不須整個程式都在 memory 中。

詳解：Multiprogramming 同時有大於一個程式在 Memory 中，可分成以下四種：

• Nonswapping：Partitioning、Paging
• Swapping：Demand paging、Demand segmentation
• Partitioning：Memory 切割成大小不一的分段，每個分段儲存一個完整的程式。
• Paging：改善 Partitioning 方法。Memory 和 Program 切割成相同大小的分段，相同程式的分段可不連續的存於 Memory 中，但還是必須整個程式都在 Memory 中。
• Demand paging：改善 Paging 方法。Memory 和 Program 切割成相同大小的分段，但不須整個程式都在 memory 中。
• Demand segmentation：將 Demand paging 中「切割成相同大小分段」的方法，改成符合程式設計的分段，所以每個 Segmentation 的大小不一。

解答：

• program：在 Disk 中沒被 CPU 所呼叫。
• job：仍在 Disk 中，但被 CPU 呼叫了。
• process：已經進入 Memory 中，正在被 CPU 所執行。

詳解：

• Program：存在硬碟中沒被呼叫。
• Job：當 Program 被呼叫，但還沒載入到 memory 時，稱為 Job。（可能是 memory 還沒空位）有兩種狀態：Hold、Terminated。
• Process：Job 載入 memory 後就稱為 process。有三種狀態：Ready、Running、Waiting。

解答＆詳解：四個讓 deadlock 發生的必要條件：

• Mutual exclusion：只有一個 process 可以抓住資源。
• Resource holding：一個 process 能抓住所需的某些資源，即便其他所需的資源有別的 process 在使用。
• No preemption：作業系統不能暫時重新分配資源。
• Circular waiting：每個 process 抓住的資源同時是其他 process 所需的資源，造成迴圈的現象。

解答＆詳解：

｛ 5, 7, 1, 3, 2, 6, 4 ｝⟹｛ 1, 5, 7, 3, 2, 6, 4 ｝⟹｛ 1, 2, 5, 7, 3, 6, 4 ｝⟹｛ 1, 2, 3, 5, 7, 6, 4 ｝⟹｛ 1, 2, 3, 4, 5, 7, 6 ｝⟹｛ 1, 2, 3, 4, 5, 7, 6 ｝⟹｛ 1, 2, 3, 4, 5, 6, 7 ｝

解答＆詳解：（註：綠色數字為正在檢查的數字）

｛ 1, 2, 3, 4, 5, 6, 7 ｝⟹｛ 1, 2, 3, 4, 5, 6, 7 ｝⟹｛ 1, 2, 3, 4, 5, 6, 7 ｝⟹ 8 不在裡面！

解答＆詳解：array 中的地址為連續地址，而 link lists 則不需要地址連續，但每筆資料都需要儲存下一筆資料的地址。如果一資料需要經常的刪除和插入，那用 link lists 會比較適合！

• Mutual exclusion：只有一個 process 可以抓住資源。
• Resource holding：一個 process 能抓住所需的某些資源，即便其他所需的資源有別的 process 在使用。
• No preemption：作業系統不能暫時重新分配資源。
• Circular waiting：每個 process 抓住的資源同時是其他 process 所需的資源，造成迴圈的現象。

void f(int a[5]){ }

int main（void）
{
    int arr[5]；
    f(arr)；
    return 0；
}

解答＆詳解：arr 並無指定說資料儲存的是 int 或是 char 或別的...。但 a 指定了說資料必須只能儲存 int。