Deck 12: Theory of Computation

Question 1

What value is represented by the bit pattern 01011100 when interpreted using floating-point format in which the most significant bit is the sign bit, the next three bits represent the exponent field in excess notation, and the last four bits represent the mantissa?

A) -1 1/2
B) 1 1/2
C) -3/8
D) 3/8

Answer 1

B

Question 2

Which of the following storage systems is best suited for storing and retrieving long strings of data that are processed in their sequential order?

A) Main memory
B) Magnetic disk
C) CDs/DVDs

Answer 2

C

Question 3

Which of the following mass storage system does not require physical motion?

A) Magnetic tape
B) Magnetic disk
C) DVDs
D) Flash drives

Answer 3

D

Question 4

Which of the following bit patterns (represented in hexadecimal notation) represents a positive number in two's complement notation?

A) 7F
B) F7
C) A8
D) 8A

Question 5

Which of the following bit patterns (represented in hexadecimal notation) represents a negative number in two's complement notation?

A) 7F
B) 55
C) A6
D) 08

Question 6

Which of the following data storage systems provides the most efficient random access to individual data items?

A) Main memory
B) Magnetic disk
C) CDs/DVDs
D) Flash drives

Question 7

What is the result of the following subtraction problem (using two's compliment notation)? 00001111
- 10101010

A) 011000101
B) 10111001
C) 01010101
D) 10110101

Question 8

Which of the following is the binary representation of 4 5/8?

A) 100.11
B) 10.011
C) 110.101
D) 100.101

Question 9

In which of the following addition problems (using two's complement notation) does an overflow error occur?

Question 10

Which of the following Boolean operations produces the output 1 for the fewest number of input patterns?

A) AND
B) OR
C) XOR

Question 11

What is the result of the following addition problem (using two's compliment notation)?

A) 011000101
B) 10111001
C) 01010101
D) 10110101

Question 12

Which of the following bit patterns represents the value 5 in two's complement notation?

A) 00011010
B) 11111011
C) 00000101
D) 11111011

Question 13

Which of the following bit-patterns represents the smallest value using the floating-point format in which the most significant bit is the sign bit, the next three bits represent the exponent field in excess notation, and the last four bits represent the mantissa?

A) 01001000
B) 01011000
C) 00101000
D) 01111000

Question 14

Which of the following bit patterns represents the value -5 in two's complement notation?

A) 00011010
B) 11111011
C) 00000101
D) 11111011

Question 15

Which of the following bit patterns cannot be expressed in hexadecimal notation?

A) 11111111
B) 1001
C) 110011
D) 100000000001

Question 16

Which of the following best describes the NOR operation?

A) An XOR followed by a NOT
B) An OR followed by a NOT
C) A NOT followed by a NOT
C) An AND followed by a NOT

Question 17

Which of the following representations in two's complement notation represents the largest value?

A) 00000010
B) 11111111
C) 00000001
D) 11111110

Question 18

Which of the following values cannot be stored accurately using a floating-point format in which the most significant bit is the sign bit, the next three bits represent the exponent field in excess notation, and the last four bits represent the mantissa?

A) 2 1/2
B) 3/16
C) 7
D) 6 1/4

Question 19

Assuming that each of the following bit patterns originally had even parity, which one contains an error?

A) 100110100
B) 110000011
C) 000011000
D) 100001001

Question 20

Which of the following representations in two's complement notation represents the smallest value?

A) 00000010
B) 11111111
C) 00000001
D) 11111100

Question 21

Explain why adding only a few characters to a text file may increase the file's size by several hundred bytes and at other times may not increase the file's size at all.

Question 22

If the input and output bit patterns in the circuit below are interpreted as binary representations of numeric values, what operation does the circuit perform?

Question 23

Which of the following is a possible LZW compression of the message "xyz xyz xyz"?

A) 1234
B) 1234545
C) 232
D) 12

Question 24

Explain why such terms as kilo, mega, and giga have acquired double meanings.

Question 25

To what does the term "normalized form" refer in the context of floating-point notation?

Question 26

How many different symbols can be encoded using Unicode?

A) 256
B) 4,096
C) 65,536
D) 1,046,476

Question 27

Data compression techniques apply various principles to reduce the size of data. One, called _______________________, avoids repeating long strings of the same data item. Another, called _______________________, encodes the difference between consecutive blocks of data rather than encoding each block in its entirety. Still another, called _________________________, uses short bit patterns to encode frequently occurring items and longer patterns to encode less frequent items.

Question 28

In a two's complement system, what value can be added to any other value without causing an overflow? How many values in the system have this property? Explain your answer.

Question 29

Explain why the final version of the dictionary need not be transmitted with a message encoded using LZW compression.

Question 30

Which of the following systems is least efficient when encoding numeric values?

A) Two's complement notation
B) Excess notation
C) ASCII
D) Floating-point notation

Question 31

Which of the following is a means of encoding music?

A) ASCII
B) MIDI
C) JPEG
D) GIF

Question 32

Construct the entire two's complement scale in which each value is represented by three bits.

Question 33

Among the Boolean operations AND, OR, EXCLUSIVE OR, and NOT, which is least like the others? Explain your answer.

Question 34

Convert the following addition problem into two's complement notation (using four bits per value), perform the addition, convert the answer back into base ten notation, and explain the results.

Question 35

The following is a message that was originally encoded so that each pattern had odd parity. Circle the patterns in which an error has definitely occurred.

Question 36

Describe how the concept of Hamming distance is used to produce an error-correcting code.

Question 37

How many errors per pattern could be corrected when using an error-correcting code in which any two code patterns differ by a Hamming distance of 8?

A) 3
B) 4
C) 5
D) 6

Question 38

Why is the rightmost bit in a string of bits considered to be the least significant bit?

Question 39

What is frequency-dependent encoding?

Question 40

Describe how a computer can produce an incorrect answer when performing numerical computations even though it has not malfunctioned.