台師大 106 資工暑轉：計概詳解！

此篇詳解為本人所撰寫，禁止：轉貼、修改、和商業使用！歡迎分享網址連結！

因為此篇詳解為本人獨自撰寫，如有錯誤的地方，或是對於解答有其他意見，都歡迎在下方的留言區一起討論！一起撰寫出正確完整的詳解！

一、The following figure shows a conversion example from a floating-point number to a binary number.

（A）What does "floating-point" stand for？

解答：用來區分整數部分和小數部分的標點符號（小黑點）。

（B）The above figure only converts a fraction part 0.125 to a binary number (0.001)₂. If the float-point number is 123.875, please draw a picture to show the conversion process from 123.875, please draw a picture to show the conversion process from 123.875 to its corresponding binary number.

解答：整數部分：123，十進位轉二進位

0	←	1	←	3	←	7	←	15	←	30	←	61	←	123
		↓		↓		↓		↓		↓		↓		↓
		1		1		1		1		0		1		1

小數部分：0.875，十進位轉二進位

0.875	→	1.75	→	1.5	→	1	→	0
		↓		↓		↓
0	.	1		1		1

所以，123.875（十進位）＝1111011.111（二進位）

（C）What will happen if we convert 72.4 to its corresponding binary number？

解答：

整數部分：72，十進位轉二進位

0	←	1	←	2	←	4	←	9	←	18	←	36	←	72
		↓		↓		↓		↓		↓		↓		↓
		1		0		0		1		0		0		0

小數部分：0.4，十進位轉二進位

0.4	→	0.8	→	1.6	→	1.2	→	0.4	→	0.8
		↓		↓		↓		↓		↓
0	.	0		1		1		0		重複

所以將 72.4 轉二進位時會遇到無止境的小數部分：0110 循環。

（D）How does IEEE 754 standard for representing single-precision floating-point numbers resolve the above problem when we convert 72.4 to its corresponding binary number？

解答：IEEE 754 使用 1 bit 來儲存正負號；8 bits 來儲存指數部分；23 bits 來儲存尾數部分。IEEE 754 以較多的 bits 儲存小數部分來降低誤差，但無法完全解決這個問題。

（E）The above process shows a conversion algorithm. But it has serious problem when dealing with some input. Please redesign the above algorithm to fix the serious problem.

解答：我們只能將儲存小數部分的 bits 數增加，來減少誤差，但無法真正解決這個問題。

二、The following figure shows an example of a simple computer.

（A）In the above figure, what is the purpose of PC？

解答：儲存 IR 中的指令或程式碼在 Memory 中的 Address 地址。

（B）In the above figure, what is the purpose of IR？

解答：儲存即將被 CPU 執行的指令或程式碼。

（C）How many bits are there in the Memory of above simple computer？

解答：

十六進位中表示：

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

FF＝15×16＋15＝255，255＋1＝256（＋1 為 Memory 位址 00）
所以，這個 Memory 有 256 個 16 bits，相當於 256×16＝4096 個 bits。

（D）There are two methods for addressing I/O：（1）Isolated I/O Addressing（2）Memory-Mapped I/O Addressing. What method does the above simple computer use？Why？

解答：（2）Memory-Mapped I/O Addressing，因為 CPU 將 I/O 視為 Memory 中的一個 word。

（E）In the above figure, what does "ALU" stand for？

解答：ALU 用來執行算術和邏輯的運算。

三、The following figure shows an SQL（Structured Query Language）statement on database.

（A）What is the purpose of this Select statement？

解答：在 COURSE 中選出 Unit ≥ 5 的 Course-Name 和 Unit。

（B）How many attributes are there in the COURSE table？

解答：3 個。

（C）This database is regarded as a "relational" database. Why？

解答：因為資料都由二維表格儲存，而這些表格都相互關聯（relational）。

（D）What is the result of using the following SQL statement in the above figure？

解答：

No	Unit
CIS19	4

（E）What is the purpose of Entity-Relationship Diagram for database？

解答：找出需要儲存的資料，這些資料之間的關係。

四、Consider the steps required to find a solution through the maze in the following figure with point A and T as starting and finishing points respectively.

The tree diagram for the maze is shown in the following figure.

（A）Show the order of the visited nodes if we use the breadth-first search in the above figure. Assume that the children nodes of a parent node are arranged from left to right.

解答：ABCEDFHIGPLJKMRNQOST

（B）Show the order of the visited nodes if we use the depth-first search in the above figure. Assume that the children nodes of a parent node are arranged from left to right.

解答：ABEHILRJKMNQSTODGCFP

（C）The breadth-first search and depth-first search are both regarded as brute-force method. What does brute-force method mean？

解答：Brute-force method 暴力法，指將所有的可能跑過一次。

（D）Another method to solve the maze problem is the heuristic search. We assign a heuristic value（heuristic function）to each node. Please give a reasonable heuristic function for the maze problem.

解答：

節點旁的紅色數字為前往終點「T」所需的步數。

（E）What is the advantage of the heuristic search over the brute-force method?

解答：heuristic search 在選擇下一步時，會選擇離終點較近的方法，所以會省去計算 brute-force method 中遠離終點的方法。

五、The following figure shows the general idea of asymmetric-key cryptosystem.

（A）Why can we know this is an "asymmetric-key" cryptosystem？

解答：因為加密和解密時，使用的鑰匙不同。

（B）In the above figure, what is the main difference between the Plaintext and the Ciphertext？

解答：Plaintext 經過函數（key）轉換後，即變成了 Ciphertext。

（C）In the above figure, what is the main difference between the Public-key distribution channel and the Insecure channel？

解答：Public-key distribution channel 用於公開傳輸；Insecure channel 用於私人傳輸。

（D）What is the main difference between the asymmetric-key cryptosystem and the symmetric-key cryptosystem？

解答：在加密和解密時，the asymmetric-key cryptosystem 使用不同的鑰匙，the symmetric-key cryptosystem 使用相同的鑰匙。

（E）RSA is one of the practical cryptosystems and is widely used for secure data transmission. Does RSA belong to the asysmmetric-key cryptosystem or the sysmmetric-key cryptosystem or both？

解答：RSA 屬於 the asymmetric-key cryptosystem。