第1頁共6頁

計算機概論

課堂作業六

系級： 座號： 姓名：

一、是非題(每題2分)

( )1. A database management system (DBMS) defines, creates, and maintains a database and allows controlled access to users.

( )2. The internal level of a DBMS interacts directly with the user.

( )3. Each column in a relation is called an attribute, and each row in a relation is called a tuple.

( )4. In lossless data compression, the integrity of the data is preserved.

( )5. Run-length encoding method is one of the lossless methods in data compression.

( )6. In Huffman coding, we assign longer codes to symbols that occur more frequently.

( )7. The Lempel Ziv (LZ) algorithm uses the idea of adaptive dictionary-based encoding.

( )8. Joint photographic experts group (JPEG) compression technique is used to compress video.

( )9. In discrete cosine transform (DTC) the AC value gives the average value of the pixels.

( )10. The quantization step in data compression will lose some information that can not be recoverable.

( )11. In motion picture experts group (MPEG) compression technique, a B-frame is never related to I-frame.

( )12. The RSA algorithm is the basis of a private key encryption method.

( )13. In public key encryption, the same key is used in encryption and decryption.

( )14. In the world, if N people want to use secret key encryption then there need to be N(N-1)/2secret keys.

( )15. In secret key encryption method, the encryption and decryption algorithms are not the inverse of each other.

二、選擇題 (每題2分)

( )1.After a sequence file is updated, the file contains the most current data.

(A)new master(B) old master

(C) transaction(D) error report

( )2. The level of a three-level DBMS architecture defines the logical view of the data.

(A) external(B) conceptual(C) internal(D) physical

( )3. In DBMS, the operation that takes two relations and combines them based on common attributes is the operation.

(A) join (B) project(C) union(D) intersection

( )4. In DBMS, you want to create a relation called New that contains tuples that belong to both relation A and relation B. For this, you can use the

operation.

(A) join (B) project(C) update(D) intersection

( )5. In DBMS, which operator is unary?

(A) difference (B) union(C) join(D) insert

( )6. To create a digest of a document, you can use .

(A) a digital signature(B) a prime number

(C) data encryption standard (DES)(D) a hash function

( )7. In the digital signature method, the receiver uses the key to decrypt the message.

(A) public(B) private(C) secret(D) skeleton

( )8. One of the advantages of public key encryption is .

(A) the short amount of time required for encryption/decryption

(B) a smaller number of keys is needed

(C) integrity is preserved

(D) everyone knows all the keys

( )9. Of the various database models, the model is the most prevalent today.

(A) hierarchical (B)network(C) relational(D) link list

系級： 座號： 姓名：

三、填充、問答、計算題

  1. (5%)Given the old master file and the transaction file as follows, fine the new master file. (where A : add; R: revise; D : delete)
Old Master File / Transaction File
14 / John / 17.00 / D / 16
16 / George / 18.00 / A / 18 / Martha / 17.00
17 / Due / 11.00 / A / 21 / Jully / 22.00
20 / Li / 12.00 / D / 26
26 / Ted / 23.00 / R / 31 / 28.00
31 / Joanne / 27.00 / D / 45
45 / Bruce / 12.00 / A / 89 / Orva / 20.00
  1. (5%)Find the address of the following keys using the modulo division method and a file of size 411. If there is a collision, use open addressing to resolve it. Draw a figure to show the position of the records.

(1) 10278

(2) 20553

(3) 17526

系級： 座號： 姓名：

  1. (4%) Given a COURSES relation table as follows:

COURSES

No / Course-Name / Unit
CIS15 / Intro to C++ / 5
CIS17 / Intro to Java / 7
CIS19 / Unix / 6
CIS51 / Networking / 5

Please show the results after the following operations.

(a) Inserts a new course CIS52 after the CIS51.

CIS52 / TCP/IP Protocols / 6

(b) Delete the course CIS51.

(c) Update the number of units for CIS19 to 7.

(d) Inserts a new course CIS60 after the CIS52.

CIS60 / Data Structure / 7

(e) Select the seven-unit courses.

ANS:

系級： 座號： 姓名：

  1. Given tworelation tables as follows:

1

第1頁共6頁

CIS51-Roster

ID / F-Name / L-Name
6754 / John / Brown
5690 / George / Yellow
6580 / Anne / Green
6789 / Ted / Purple

CIS52-Roster

ID / F-Name / L-Name
9999 / Rich / White
6754 / John / Brown
5690 / George / Yellow
4477 / Andy / Brown

1

第1頁共6頁

(1) (4%) Show the union results of CIS51-Roster and CIS52-Roster relation tables.

(2) (4%) Show the intersection results of CIS51-Roster and CIS52-Roster relation tables.

(3) (4%) Show the results of CIS52-Roster difference CIS51-Roster.

  1. (8%) (1) Please compress the following sequence by LZ encoding.

BAABABBBAABBBBAA

(2) Please uncompress the following sequence by LZ decoding.

A, C, 1C, 1B, 2A, 4C

ANS:

  1. (12%) Given the frequency table as follows

Character / A / B / C / D / E / F
Frequency / 19 / 6 / 5 / 1 / 45 / 24

(1) if the Huffman code of character “C” is 11110, please show the Huffman codes of other characters.

(2) encoding the character list “EEBACFD”

(3) decoding the Huffman code “110111011111010”

ANS:

  1. (6%) Please finish the RSA (Rivest-Shamir-Adleman encryption) method, and answer the following question.

The private key is a pair of numbers (N, d) = (119, 5)

The public key is a pair of numbers (N, e) = (119, 77)

Encryption: C = Pe mod N

Decryption: P =

where C:ciphertext P: plaintext

Question: If C = 20, then P = .

1