課程名稱︰計算機概論
課程性質︰資工選修
課程教師︰周承復
開課學院：電機資訊學院
開課系所︰資工系
考試日期（年月日）︰2016/11/07
考試時限（分鐘）：100 mins
試題 :
1. (10%)Show how to build a 2-input OR gate using NOT gates and 2-input AND
gates. That is, produce a circuit made of ANDs and NOTs, whose behavior is
exactly the same as a 2-input OR gate.
2. (20%)Data Compression
a) (10%) Encode the message "xxy yyx xxy yyx xxy" using the LZW method,
then decode the encoded message to get the original message.
b) (10%) Encode the following characters using Huffman coding with the
given frequencies: A(8), B(12), C(25), D(20), E(15), F(16), G(4)
3. (25%)Number system
a) (10%) Using an 8-bit allocation, first convert each of the following
integers to two's complement, do the operation, and then convert the
result to decimal.(1) 46+57 (2) 23-71
b) (5%) To what does the term "normalized form" refer in the context of
floating-point notation?
c) (10%) What bit pattern(and its value) represents the sum of 10101011
and 01101011 if the patterns represent values stored in two's complement
notation? What if the patterns represent values stored in floating-point
format discussed in Chapter 1?
4. (30%) Operating Systems
a) (10%)Suppose an operating system allocates time slices in 10 millisecond
units and the time required for a context switch is negligible.
(i) How many processes can obtain a time slice in one second?
(ii) How many processes can obtain a time slice in one second if half of
them use only half of their slice?
b)(5%)If it takes one microsecond to perform a context switch and processes
use only half of their allotted 10 millisecond time slices, what percent
of a CPUs time is spent performing context switches rather than
executing processes?
c) (10%) Please choose the part on the operating system(file manager,
memory manager, device drivers, window manager, scheduler, dispatcher)
that performs the activity described.
(i) Performs the switching from one process to another.
(ii) Performs the actual communication with I/O units.
(iii) Maintains a record of memory allocations.
(iv) Protects files from unauthorized access.
(v) Places new entires in the process table.
d) (5%) Describe the bootstrap process.
5. (10%) Using the machine language described in the language description
table, write a sequence of instructions that will shift the contents of
the memory cell at address A0 three bit positions to the right while
filling the holes at the left end with 0s.
6. (10%) What bit patterns are represented by the following hexadecimal
notations?
(i) 1107
(ii) C105
(iii) B02902
(iv) AFDE
(v) 34C8
7. (15%) Suppose the memory cells at address 20 through 28 in the machine
described in Appendix contain the following bit patterns:
Address Contents
20 10
21 21
22 30
23 30
24 B0
25 21
26 55
27 C0
28 00
(i) What bit patterns will be in register 0 and 1 when machine halts?
(ii) What bit pattern will be in the memory cell at address 30 when the
machine halts?
(iii) What bit pattern will be in the memory cell at address B0 when the
machine halts?