考試

2020 年 7 月 2 日

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

已複製到剪貼板

｜台師大資工暑轉：詳解文章前言

此篇文章為：台師大資工轉學考 103 學年度「計算機概論」的解答、詳解。需要其他學年度的歷屆題、計算機概論和微積分的解答詳解，可點擊至主要文章！

－尊重智慧財產權

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

－互相交流討論

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

｜國立臺灣師範大學 103 學年度學士班二年級轉學生招生考試：資工歷屆題「計算機概論」詳解

－題組一

  1. Number systems, data storage, and data operations：

（1）Convert the decimal number 1001 to the hexadecimal, octal, and binary form, respectively.

解答：

  • hexadecimal form：3E9
  • octal form：1751
  • binary form：1111101001

詳解：

先將 1001 轉換成二進位數，八與十六進位數便好求了。

0 ← 1 ← 3 ← 7 ← 15 ← 31 ← 62 ← 125 ← 250 ← 500 ← 1001
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 1 1 1 1 0 1 0 0 1

將二進位轉成八進位時，只要將每 3 位轉成十進位的 1 位數字就好了。

1 111 101 001
↓ ↓ ↓ ↓
1 7 5 1

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

11 1110 1001
↓ ↓ ↓
3 E 9

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

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

（2）Assume that in a programming language K, the sizes of three integral signed data types, short, int, and long are 16, 32, and 64 bits, respectively. If we want to store an integral value 10⁹ and keep the variable size minimal, which data type should we use？What about 2·10⁹？

解答：

  • 10⁹：int
  • 2·10⁹：int

詳解：

  • short 能表示的最大值：2¹⁶ ÷ 2 − 1＝32767
  • int 能表示的最大值：2³² ÷ 2 − 1＝2147483647
  • long 能表示的最大值：2⁶⁴ ÷ 2 − 1＝9,223,372,036,854,775,807

能表示的數字總數：負數＆零＋整數各佔一半，所以除以 2 後的減 1 是減掉零這個數字。
而，2147483647＜1000000000＝10⁹＜32767，所以表示 10⁹ 可使用 int。
2147483647＜2000000000＝2·10⁹＜32767，所以表示 2·10⁹ 依然可使用 int。

（3）Find the minimal x（1 ≤ x ≤ 15）to maximize the value of x OR 134.（OR means the bit-wise OR operation.）

解答：x＝9。
詳解：（雖然有點看不懂題目，但答案應該是這樣，有錯的話可以在下方留言區留言更正！）

先將 134 轉換成二進位，因為我們要做 bit-wise OR operation：

0 ← 1 ← 2 ← 4 ← 8 ← 16 ← 33 ← 67 ← 134
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 0 0 0 0 1 1 0

所以，134＝10000110
而 x 介於 1 和 15 之間，因為 15＝1111，所以 x 最多 4 bits。
現在我們要讓 x OR 134 最大，所以結果會是 10001111，那 x 就會是 1001＝9。

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

（4）Which of the following floating-point values cannot be represented accurately by the IEEE single-precision floating-point representation：123.0, 99.5, 25.1, 68.4, 30.625, and 77.75？

解答：25.1、68.4。
詳解：

無法轉換成有限位數的二進位的話，就無法正確的用 IEEE single-precision floating-point representation 表示。

而整數部分是用 2 一直除到 0，所以沒有無限位數的問題。但小數部分是用乘的，所以只要沒被法乘 2 乘到 0 的小數，就沒辦法以有限小數來用二進位表示。所以答案會有：25.1、68.4

（5）Find the truth assignment of boolean variables x, y, and z to satisfy
        （x＋y）•（x'＋y）•（x'＋z）•（y'＋z'）
, i.e., to make the value of the boolean expression true.（Symbols ', •, and＋mean NOT, AND, and OR, respectively.）

解答：（x, y, z）＝（0, 1, 0）。
詳解：因為結果要 true，而四項又用 AND 串接，所以只有 1 種可能：1・1・1・1（1 代表 true）。

  • x＋y＝1
  • x'＋ y＝1
  • x'＋ z＝1
  • y'＋ z'＝1

把四項一個一個可能列出來，把不合可能一個一個刪去，答案就出來了。

x 1 0 1
x' 0 1 0
y 0 1 1
y' 1 0 0
z 0 1
z' 1 0

所以，答案是：（x, y, z）＝（0, 1, 0）。


－題組二

  1. Computer organization：

（1）Assume that the format of an instruction STORE is [Opcode][Memory address][Register address]. If we have eleven types of instructions, 256 memory address, and 32 registers, please calculate the minimal number of bits required to represent instructions.

解答：17 bits。
詳解：Opcode 即指令，因為：

  • instruction：11＝2⁴ − 5
  • memory address：256＝2⁸
  • register：32＝2⁵

所以表示 STORE 指令所需的最小 bit 數為 4＋8＋5＝17。

（2）In the following figure, how many instructions are completed in the second computer（b）when the second instruction is just completed in the first computer（a）？

台師大 103 學年度資工暑轉｜題組二：第 2 題
台師大 103 學年度資工暑轉｜題組二：第 2 題

（Behrouz Forouzan and Firouz Mosharraf, Foundations of Computer Science, Fig. 5.24, 2nd edition, Thomson, 2008.）

解答：4 instructions。
詳解：

台師大 103 學年度資工暑轉｜題組二：第 2 題詳解
台師大 103 學年度資工暑轉｜題組二：第 2 題詳解

完整執行完 Fetch、Decode、Execute 的程式有：1、2、3、4。


（3）Match the I/O methods（A/B/C）and descriptions（a/b/c）：

（A）programmed I/O （B）interrupt-driven I/O （C）direct memory access

（a）It transfers a large block of data between I/O devices and memory directly without passing it through the CPU.
（b）The CPU informs the I/O device but does not test the status of the I/O device continuously.
（c）The CPU does nothing during data transfer.

Write down the answers in the form like (A)-(a).

解答＆詳解：(A)-(c)、(B)-(b)、(C)-(a)。

（4）Comparing the isolated I/O and memory-mapped I/O methods：Which one needs different instructions to access memory and I/O devices？Which one does not need to allocate memory address space to I/O devices？

解答＆詳解：(A)-(c)、(B)-(b)、(C)-(a)。

  • isolated I/O needs different instructions to access memory and I/O devices.
  • isolated I/O does not need to allocate memory address space to I/O devices.

（5）The capacity of David's, Judy's, and Lucy's hard disks are 1TB, 5000GB, and 900000MB, respectively. Whose hard disk has the largest capacity？

解答：Judy＞David＞Lucy。
詳解：因為 1 TB＝1024 GB、1 GB＝1024 MB，所以：

  • David：1 TB＝1024 GB
  • Judy：5000 GB
  • Lucy：900000 MB＝900000 ÷ 1024 GB＝878.90625 GB

⇒ Judy＞David＞Lucy


（6）A computer has 256 MiB of memory, and each word in it is 4 bytes. How many bits are required to address any single word in memory？

解答：16 bits。
詳解：memory 大小有 256 × 1024 bytes，每個 word 佔 4 bytes，所以 address 有 256 × 1024 ÷ 4 個，轉成二的次方的話，address 有 2¹⁶ 個，所以每個 word 的地址需要 16 bits 來表示。

－題組三

  1. Computer networks：

（1）Match the TCP/IP layers（A/B/C/D）and protocols（a/b/c/d）：

（A）application （B）transport （C）network （D）data link
（a）IP （b）TCP （c）Ethernet （d）SMTP

Write down the answers in the form like (A)-(a).

解答：(A)-(d)、(B)-(b)、(C)-(a)、(D)-(c)。
詳解：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

（2）How many bits does IPv4 address use？What about IPv6？

解答＆詳解：IPv4：32 bits、IPv6：128 bits。

（3）Which of the following IPv4 address is a private address？
（a）140.122.65.150（b）74.125.31.94（c）119.160.242.96（d）192.168.122.35

解答：（d）192.168.122.35。
詳解：IPv4 私有 IP 定義

IP 位址區段 IP 數量 網路類別
10.0.0.0～10.255.255.255 16777216 1 個 A 類網路
172.16.0.0～172.31.255.255 1048576 16 個連續 B 類網路
192.168.0.0～192.168.255.255 65536 256 個連續 C 類網路

（4）Assume that the subnet mask is 255.255.255.128, does the two address 140.122.65.150 and 140.122.65.149 belong to the same subnet？

解答：Yes！
詳解：memory 大小有 256 × 1024 bytes，每個 word 佔 4 bytes，所以 address 有 256 × 1024 ÷ 4 個，轉成二的次方的話，address 有 2¹⁶ 個，所以每個 word 的地址需要 16 bits 來表示。

subnet mask 會與 address 進行 AND 運算，而 255 換成二進位為 11111111，所以進行 AND 將不會改變原式。看最後一個數字 128 轉成二進位為 10000000，進行 AND 運算後只會留下最左邊的數字，其他都會變成 0。

  • 140.122.65.150：第四個數字 150＝10010110
  • 140.122.65.149：第四個數字 149＝10010101

與 10000000 進行 AND：

  • 10010110＋10000000＝10000000
  • 10010101＋10000000＝10000000

相等！所以屬於同的子網路！

（5）Give the full name of DNS and explain the function of a DNS server.

解答＆詳解：Domain Name System（DNS）is a client-server application that identifies each host on the Internet with a unique name.

（6）Choose the statements that describe the TCP protocol：

（a）a connection-oriented protocol
（b）uses sequence numbers
（c）uses acknowledgment numbers
（d）uses checksums

解答：(a)(b)(c)(d)。
詳解：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

－題組四

  1. Operating systems：

（1）One of the responsibilities of the operating system is memory managment. In multiprogramming methods, more than one program is in memory at the same time. Multiprogramming methods can be divided into two categories. What are they？

解答：Swapping & Nonswapping。
詳解：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 的大小不一。

（2）Match the memory management methods（A/B/C）and the descriptions（a/b/c）：

（A）partitioning （B）paging （C）demand paging

（a）It loads the entire program into the memory but does not require the program to be contiguous in the memory.
（b）It allows loading only part of the program into the memory.
（c）It requires the program to be contiguous in the memory.

Write down the answers in the form like (A)-(a).

解答：(A)-(c)、(B)-(a)、(C)-(b)。
詳解：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 的大小不一。

（3）A program becomes a job when it is selected by the operating system and enters the ＿(a)＿ state. When it is loaded into memory, the job moves to the ＿(b)＿ state and becomes a process. When the CPU execute it, it moves to the ＿(c)＿ state. If an I/O operation is encountered, it changes to the ＿(d)＿ state and goes back to the ＿(b)＿ state when I/O is completed. When the process ends, it enters the terminated state. Write down the states in the blanks (a)-(d) in order.

解答：

  • （a）：Hold
  • （b）：Ready
  • （c）：Running
  • （d）：Waiting

詳解：

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

（4）A computer has 64MB of memory and its multiprogramming operating system divides the memory into four partitions of 4MB, 10MB, 20MB, and 30MB. After loading four programs of 1MB, 8MB, 15MB, and 20MB into the memory at the same time, how much memory is wasted？

解答：20 MB。
詳解：

 （4 − 1）＋（10 − 8）＋（20 − 15）＋（30 − 20）
＝3＋2＋5＋10
＝20

（5）Following the above question, the computer installs a new operating system that uses paging and divides the memory into 16 frames, each of 4MB. How many frames are used after loading all four programs？How much memory is wasted？

解答：16 frames；2 MB。
詳解：先算出每個程式所需的 frame 數

4 ÷ 4＝1
10 ÷ 4＝2 ... 2
20 ÷ 4＝5
30 ÷ 4＝7 ... 2

① 餘數不足 4 的部分直接用一個 frame

1＋（2＋1）＋5＋（7＋1）＝17
但 memory 中最多只有 16 個 frame，所以答案是 16。

② 只有一個餘數的 2 MB 有辦法進入 memory，所以只浪費 4 − 2＝2 MB。


－題組五

  1. Data structures, algorithms, and programming：

（1）Given a sequence of numbers［8, 2, 1, 3, 5, 6, 4］, how many swaps are required by using the bubble sort to sort the numbers from the smallest to the largest？

解答：9 次。
詳解：徒手嘗試就有答案了～如果有更有效率的方法，可以留言告訴我！

幾個箭頭「⇒」就代表 swap 幾次：

［8, 2, 1, 3, 5, 6, 4］⇒［2, 8, 1, 3, 5, 6, 4］⇒［2, 1, 8, 3, 5, 6, 4］⇒［2, 1, 3, 8, 5, 6, 4］⇒［2, 1, 3, 5, 8, 6, 4］⇒［2, 1, 3, 5, 6, 8, 4］⇒［2, 1, 3, 5, 6, 4, 8］⇒［1, 2, 3, 5, 6, 4, 8］⇒［1, 2, 3, 5, 4, 6, 8］⇒［1, 2, 3, 4, 5, 6, 8］

所以，共 9 次。

（2）After sorting the above number sequence, how many numbers does the binary search check to find out that 7 is not in the sequence？

解答：3 次。
詳解：binary search 從中間開始尋找，和目標比大小，決定往左還是往右繼續尋找。

幾個「綠色數字」就代表 check 幾次：
［1, 2, 3, 4, 5, 6, 8］⇒［1, 2, 3, 4, 5, 6, 8］⇒［1, 2, 3, 4, 5, 6, 8］

（3）If we store the above sorted number sequence in the binary search tree with the minimal height, what value is stored in the root node？

解答：4。
詳解：就 binary search tree 的定義為一邊子節點大於母節點，另一邊子節點小於母節點，而題目又要求高度要最小，所以 root node 母節點勢必就需要是中間數字 4。

（4）Given an empty stack and a set of operations as follows：

PUSH(w), PUSH(x), POP(), PUSH(y), POP(), POP(), PUSH(z), POP()

If the popped values are 1, 2, 3, and 4 in order, what are the values of variables w, x, y, and z？

解答：x＝1；y＝2；w＝3；z＝4。
詳解：因為第一個為 POP（1），所以前一個 PUSH(x) 就是 x＝1，再來 POP（2），PUSH(y) 就是 y＝2，再 POP（3），PUSH(w) 就是 w＝3，最後一個 POP（4），PUSH(z) 就是 z＝4。


（5）The time complexity of the function f1 is O(n²). What is the time complexity of f2 and f3？

int f1(int n)
{
    int sum=0;
    for(int i=0; i＜n; i+=1)
    {
        for(int j=0; j＜n; j+=1)
        {
            sum=sum+j;
        }
    }
    return sum;
}
int f2(int n)
{
    int sum=0;
    for(int i=0; i＜n; i+=2)
    {
        for(int j=i; j＜n; j+=3)
        {
            sum=sum+j;
        }
    }
    return sum;
}
int f3(int n)
{
    int sum=0;
    for(int i=0; i＜n; i*=2)
    {
        for(int j=0; j＜n; j+=1)
        {
            sum=sum+j;
        }
    }
    return sum;
}

解答：

  • f2：n²/6
  • f3：n√n

詳解：時間複雜度指的是輸入 n，則程式需要跑多少次。

  • f2：n/2 × n/3＝n²/6
  • f3：n√n

｜台師大資工暑轉詳解相關文章：

分享文章

已複製到剪貼板

主題文章

查看 考試

關於看我所見

「看我所見」主題多元，分享作者的生活經歷、特殊經驗，舉凡：教育、生活、科技、3C、音樂、娛樂 ⋯⋯，我們也將持續優化，提供讀者最好的體驗！

Contacts

Ricky Chuang

看我所見

linktr.ee/5j54d93

最新文章