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

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

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

1. A register in a CPU can hold ＿＿＿.
（A）data
（B）instruction
（C）program counter values
（D）all of the above

解答：（D）all of the above。
詳解：一開始 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 做計算。

所以：

（A）data：存在 Register 中
（B）instruction：存在 Instruction Register（IR）中
（C）program counter values：存在 Program Counter（PC）中
（D）all of the above

而 Register 暫存器，IR 和 PC 也都屬暫存器，所以答案是以上皆是。

2. In a method for synchronizing the operation of the CPU with an I/O device, the I/O device informs the CPU when it is ready for data transfer. What is this method？
（A）direct memory access（DMA）
（B）interrupt-driven I/O
（C）isolated I/O
（D）programmed I/O

解答：（B）interrupt-driven I/O。
詳解：

• direct memory access（DMA）：CPU 需要 data 時會通知 DMA，並由 DMA 來向 Memory 或 I/O 索取，再由 DMA 將 data 傳給 CPU。
• interrupt-driven I/O：CPU 在執行程式時，遇到需要從 I/O 索取資料時，CPU 會通知 I/O，並繼續執行其他程式，I/O 完成輸入時會主動通知 CPU。
• isolated I/O：CPU 向 Memory 和 I/O 索取資料時使用不同的 instruction，所以 Memory 和 I/O 會出現重複的地址。
• 註：Memory-mapped I/O：CPU 將 I/O 看成 Memory，I/O 會佔用 Memory 的地址，所以不會有 isolated I/O 重複地址的問題，CPU 也不會使用不同的 instruction 來向 Memory 和 I/O 索取資料。
• programmed I/O：CPU 在執行程式時，遇到需要從 I/O 索取資料時，CPU 會停下來不斷檢查 I/O 的輸入狀態而不執行其他程式碼，直到 I/O 完成輸入，所以這也算是較原始的方法。

3. An imaginary computer has 32 data registers（R）, 2048 words in memory（M）, and 32 different instructions（I）. What is the minimum size of an instruction in bits if the instruction format is［ I M R ］？
（A）2112
（B）4096
（C）12
（D）21

解答：（D）21。
詳解：

• I：32＝2
• M：2048＝2¹¹
• R：32＝2⁵

所以，5＋11＋5＝21

4. Mimmy and Ninny are using a computer for Internet surfing. Mimmy noticed that Ninny accessed an image file through typing http://www.getsomeimage.com:1988/cake.jpg in the browser. Which statement is wrong？
（A）http refers to a protocol used to access data on the World Wide Web.
（B）1998 refers to a password required to access data.
（C）cake.jpg refers to the name of the image file on the server.
（D）A domain name server is required to get the actual IP address of www.getsomeimage.com.

解答：（B）1998 refers to a password required to access data.。
詳解：http://www.getsomeimage.com:1988/cake.jpg 稱為 Uniform resource locator (URL)，格式如下：

絕大部分時候的格式：protocol://host/path
需要 port number 時：protocol://host:port/path

• Protocol：用來擷取網頁的 client-server program
• Host identifer：司服器的 IP 位址 or 司服器的特殊名稱
• Port number：16-bit 的整數，一般用於事先定義 client-server application
• Path：定義檔案的位置和名稱。形式通常取決於作業系統。

所以：

（A）http 為 Protocol，用來在全球資訊網上擷取資料
（B）1998 為 Port number，而非擷取資料的密碼
（C）cake.jpg 為 Path，這裡定義檔案名稱
（D）www.getsomeimage.com 為 Host identifer，是司服器的特殊名稱

5. Comparing the UDP and TCP protocols, which statement is wrong？
（A）Both UDP and TCP are protocols at the transport layer.
（B）Both UDP and TCP add a checksum to the packet.
（C）Both UDP and TCP add a sequence number to the packet.
（D）UDP is suitable for applications whose timing is more important than accuracy.

解答：（C）Both UDP and TCP add a sequence number to the packet.。
詳解：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

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

6. About the TCP/IP protocol suite, which statement is wrong？
（A）The TCP/IP protocol has five layers：application, transport, network, data link, and physical layers.
（B）The transport layer does multiplexing and demultiplexing.
（C）The network layer is responsible for routing.
（D）The IP and Ethernet protocols belong to the network layer.

解答：（D）The IP and Ethernet protocols belong to the network layer.。
詳解：同第 5 題

• 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
• Physical：Analog＆Digital

所以：（D）當中，IP 屬於 Network 網路層；Ethernet 屬於 Data link 資料鏈接層。

7. About multiprogramming method, which statement is wrong？
（A）The partitioning method divides the memory into variable-length sections.
（B）The paging method is different from the partitioning method in that the paging method does not require the entire program to be in memory during execution.
（C）The demand paging method allows the programs to occupy noncontiguous frames in memory.
（D）Virtual memory is a common technique in current operating systems.

解答：（B）The paging method is different from the partitioning method in that the paging method does not require the entire program to be in memory during execution.。
詳解：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 的大小不一。

8. Operating systems use three terms to describe a set of instructions in different states：program, job, and process. Which statement is wrong？
（A）When a program is selected for execution, it becomes a job.
（B）When a job is loaded in memory, it becomes a process.
（C）When a process goes into the waiting state and waits for I/O operations, it is a job but not a process.
（D）Every job is a program, and every process is a job.

解答：（C）When a process goes into the waiting state and waits for I/O operations, it is a job but not a process.。
詳解：

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

9. One solution to prevent deadlock is not to allow a process to start running until the required resources are free. In this solution, which of the following necessary conditions of deadlock is not met？
（A）mutual exclusion
（B）resource holding
（C）no preemption
（D）circular waiting

解答：（B）resource holding。
詳解：四個讓 deadlock 發生的必要條件：

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

10. For the history of tech acquisitions, which statement is wrong？
（A）Microsoft acquired LinkedIn in 2006.
（B）Compaq acquired HP in 2002.
（C）Google acquired Youtube in 2006.
（D）Oracle acquired Sun Microsystems in 2010.

解答：（B）Compaq acquired HP in 2002.。
詳解：應為 HP acquired Compaq in 2002.，寫相反了。

1. N is a base-2 positive integer with 24 binary digits, and the leftmost digit is 1. How many hexadecimal digits are required to represent N？

解答：6 hexadecimal digits
詳解：每 4 個 binary digits 可以轉換成 1 個 hexadecimal digits。所以：24 ÷ 4＝6。

2. With unsigned representation, let m and M be the minimal and maximal values represented by 8 bits, respectively. What is the value of m OR M, where OR refers to the bit-wise OR operator？

解答：11111111
詳解：

m 為 00000000
M 為 11111111
所以，m OR M 為：

	0	0	0	0	0	0	0	0
OR	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1

3. How many negative values can be represented by the 2's complement representation with 9 bits？

解答：255 個
詳解：

假設只有 2 bits：00、01、10、11，共 2^2＝4 個，總數 4 個 ÷ 2＝2＝正＋零 or 負。

• 正：01
• 零：00
• 負：10、11

假設有 3 bits：000、001、010、100、110、101、011、111，共 2³＝8 個，總數 8 個 ÷ 2＝4＝正＋零 or 負。

• 正：001、010、011
• 零：000
• 負：100、110、101、111

現有 9 bits 共可表示 2⁹＝512 個數，512 ÷ 2＝256＝正＋零 or 負，可表示 256 − 1＝255 個正數。

4. Given three boolean variables x, y, and z, how many combinations of truth-value assignment can make the boolean expression（x．y'＋y．z'）true？Operator ．,', and＋refer to AND, NOT, and OR, respectively.

解答：4個
詳解：3 個變數可有 2³＝8 個輸入組合，true 和 false 各佔一半，所以：true 的組合有 8 ÷ 2＝4個。
驗證：

x	y	y'	z	z'	題目
0	0	1	0	1	0
0	0	1	1	0	0
0	1	0	0	1	1
1	0	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
0	1	0	1	0	0
1	1	0	1	0	0

5. A pipeline consists of three stages. Stage 1, 2, and 3 needs 4, 5, and 3 minutes to complete an operation, respectively. Each job is completed after being processed by stages 1, 2, and 3 sequentially. Assume that the pipeline is empty at the beginning. How many jobs will be completed after 50 minutes？

解答：4 jobs
詳解：

• Stage 1：4 minutes
• Stage 2：5 minutes
• Stage 3：3 minutes

Stage			1	2	3	1
Stage		1	2	3	1	2
Stage	1	2	3	1	2	3
分鐘	4	13	25	37	49	61

6. A CPU usually consists of an arithmetic logic unit（ALU）, a control unit, and a set of registers. How many operations can a control unit with six wires define？

解答：64 個
詳解：共 2⁶＝64 個。

7. Abby and Bibby are asked to write a program that reads in N positive integers and sort them in the non-decreasing order. In Abby's program, she reads the integers one by one, stores them in an array, and inserts each integer at the ordered position right after the integer is read. In Bibby's program, he runs a procedure of merge sort every time when an integer is read. Please write the time complexity of their programs, respectively.（Abby's first）

解答、詳解：

• Abby：O（N²）
• Bibby：O（N × log N）

8. A is a two-dimensional array of integers in row-major order. Assume that each integer occupies four bytes of memory. If we know that the address of element A[1][2] is 1052 and the address of A[3][3] is 1096, how many elements does a row have？

解答：5 elements in a row
詳解：將二維陣列畫出來答案就知道了！

Array A：

[0][0]
1028
[1][0]	[1][1]	[1][2]	[1][3]
		1052	1056
[2][0]	[2][1]	[2][2]	[2][3]
1060
[3][0]	[3][1]	[3][2]	[3][3]
			1096

將 [3][3] 的地址減掉 [1][3] 的地址就是兩行的 bit 數：1096 − 1056＝40。
一行的 bit 數：40 ÷ 2＝20。
所以：一行有 20 ÷ 4＝5 個元素。

9. If we put three integral values 1, 2, and 3 sequentially into a stack, we take them out of the stack in the reverse order 3, 2, and 1. If we put these three values into a queue, we take them out in the order 1, 2, and 3. If we put them into a min-heap, we also take them out in the order 1, 2, and 3. In other words, the insertion sequence ［1, 2, 3］can distinguish the stack from the min-heap but connot distinguish the queue from the min-heap. Given three values 1, 2, and 3, there are 3！＝ 6 input sequences. How many of them can distinguish the three data structures, that is, the orders of taking these values out of the three data structures are all different？

解答：4
詳解：

輸入［1, 2, 3］不可分辨

stack	queue	min-hea
［3, 2, 1］	［1, 2, 3］	［1, 2, 3］

輸入［1, 3, 2］可分辨

stack	queue	min-hea
［2, 3, 1］	［1, 3, 2］	［1, 2, 3］

輸入［2, 1, 3］可分辨

stack	queue	min-hea
［3, 1, 2］	［2, 1, 3］	［1, 2, 3］

輸入［2, 3, 1］可分辨

stack	queue	min-hea
［1, 3, 2］	［2, 3, 1］	［1, 2, 3］

輸入［3, 1, 2］可分辨

stack	queue	min-hea
［2, 1, 3］	［3, 1, 2］	［1, 2, 3］

輸入［3, 2, 1］ 不可分辨

stack	queue	min-hea
［1, 2, 3］	［3, 2, 1］	［1, 2, 3］

10. Among all binary trees containing four nodes with four distinct values, how many trees can be regarded as both a min-heap and a binary search tree？

解答：0
詳解：從定義來看，min-heap tree 是母節點比子節點都小；binary search tree 是其中一邊的子節點小於母節點，另一邊的子節點大於母節點。所以找不到 binary tree 既是 min-heap tree 又是 binary search tree。

11. The following is a simple C program. What is the output on the screen？

#include＜stdio.h＞ void f(int data[], int i) {     printf("%d", data[i]);     if(i==0) return;     else f(data, i-1); } int main(void) {     int data[5] = {3, 8, 2, 4, 7};     f(data, 4);     return 0; }

解答：74283
詳解：程式題不好打出詳解，建議自己徒手順著程式將輸入跑過幾次，仔細、細心一點就會有答案了！解答為將程式碼輸入 Compiler 輸出的結果。

12. The following is a simple C program. Operator % gets the integer remainder, and operator / is integer division. What is the output on the screen？

#include＜stdio.h＞ int main(void) {     int N=20160711, s=0;     while(N!=0)     {         s = s + N%10;         N = N/10;     }     printf("%d", s);     return 0; }

解答：18
詳解：程式題不好打出詳解，建議自己徒手順著程式將輸入跑過幾次，仔細、細心一點就會有答案了！解答為將程式碼輸入 Compiler 輸出的結果。

13. The following is a simple C program. What is the output on the screen？

#include＜stdio.h＞ int main(void) {     int c = 0;     for(int i=11; i＜30; i+=1)     {         int d=2;         while(d*d＜=i)         {             if(i%d==0) break;             d = d+1；         }         if(d*d＞i) c=c+1;     }     printf("%d", c);     return 0; }

解答：6
詳解：程式題不好打出詳解，建議自己徒手順著程式將輸入跑過幾次，仔細、細心一點就會有答案了！解答為將程式碼輸入 Compiler 輸出的結果。

14. The following is a simple C program. After the loop, M stores the maximal value in the array. What about m？What is the output on the screen？

#include＜stdio.h＞ int main(void) {     int m=101, M=-1;     int scores[5] = {10, 80, 40, 90, 20};     for(int i=0; i＜5; i+=1)     {         if(M＜scores[i]) M=scores[i];         else if(m＞scores[i]) m=scores[i];     }     printf("%d", m);     return 0; }

解答：m 儲存最大值以後的最小值。螢幕顯示：20。
詳解：程式題不好打出詳解，建議自己徒手順著程式將輸入跑過幾次，仔細、細心一點就會有答案了！解答為將程式碼輸入 Compiler 輸出的結果。

15. The following is a simple C program. What is the output on the screen？

#include＜stdio.h＞ void f(int data[], int i) {     if(i==0)     {         data[0] = data[0] + 1;         return;     }     for(int j=i; j＜=4; j+=1)     {         if(data[j]==0)         {             data[j] = 1;             f(data, i-1);             data[j] = 0;         }     } } int main(void) {     int data[5] = {0, 0, 0, 0, 0};     f(data, 4);     printf("%d", data[0]);     return 0; }

解答：1
詳解：程式題不好打出詳解，建議自己徒手順著程式將輸入跑過幾次，仔細、細心一點就會有答案了！解答為將程式碼輸入 Compiler 輸出的結果。