THE UNIVERSITY OF AUCKLAND
(Time Allowed: TWO hours) r>Note:
Your Teleform sheet is stapled at the end of this question/answer book. Remove the Teleform sheet
from the question/answer book.
The version code for this question/answer book is 00003978 . You MUST carefully check that this
version code corresponds to the one on the Teleform. If the version codes do not match, please inform
the exam supervisor IMMEDIATELY.
Enter your name and student ID on the Teleform sheet. You must also enter your name and student ID
on this question/answer book in the space provided below.
Enter your answers on the Teleform. Answers entered in the question/answer book will not be marked.
At the end of the exam, submit the Teleform only. You MUST retain this question/answer book until
the marking is complete and you have received the mark or grade for this assessment.
Each of the 45 questions is expected to have exactly 1 (one) correct answer. If you believe that a
question has either NO or MULTIPLE correct answers, select the ONE you believe is most likely to be
the intended answer.
All questions carry equal marks. You must answer 40 out of the 45 questions correctly in order to obtain
full marks in this exam. Any excess marks may be used to offset marks lost in the mid-semester test.
This exam counts for 50% of your final grade.
Name: ......................................
ID: ......................................
COMPSCI 110
Page 1 of 22
1. Which of the following strings, when compressed with the RLE algorithm discussed in class, will result in a compression ratio
of 1.5 or more?
X. WHHAAAAAAMMM
Y. bookkeeper
Z. zzzzZZZZzzzz!!
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
2. Which of the following additions are CORRECT? Note the subscripts denote the bases (8=octal, 16=hexadecimal).
X. 21358 + 3548 = 25118
Y. 11528 + 2628 = 14348
Z. 21158 + 3668 = 25038
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
3. Which of the following subtractions are CORRECT? Note the subscripts denote the bases (8=octal, 16=hexadecimal).
X. 34168 - 3708 = 30268
Y. CEB16 - A116 = C4B16
Z. 56528 - 238 = 56278
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
COMPSCI 110
Page 2 of 22
4. Which of the following answers correctly give the 8-bit two's complement of the specified decimal number?
X. -65 is 1011 1110
Y. 111 is ?0110 1111?
Z. 9 is ?1111 0111?
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
5. Which of the following are correct representations of the specified decimal values in the 16-bit floating point format presented
in lectures and the textbook? Note that the floating point representation has been expressed in hexadecimal.
X. 0.1875(decimal) is 6022 (hexadecimal).
Y. -55.375 (decimal) is EEC6 (hexadecimal).
Z. -0.375 (decimal) is E001 (hexadecimal).
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
COMPSCI 110
Page 3 of 22
6. Given that the hexadecimal value of the ASCII code for "A" is 41, the ASCII code for "a" is 61 and the ASCII code for "1"(one)
is 31, which of the following statements are TRUE? All numbers are in hexadecimal.
X. The ASCII code for "m" is 6D.
Y. All uppercase letters have ASCII codes numerically smaller than the ASCII codes of all lowercase letters.
Z. The decimal value of numeric characters can be obtained by looking at the 4 most significant bits of their hexadecimal
ASCII codes.
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
7. Consider the truth table below:
Which of the following boolean expressions match the output column in the truth table above?
X. (NOT A AND B AND C) OR (A AND NOT B AND NOT C)
Y. (NOT A AND NOT B AND C) OR (NOT A AND B AND NOT C)
Z. (NOT A OR A) AND (NOT B OR B) AND NOT C
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
COMPSCI 110
Page 4 of 22
8. Consider the Huffman tree below:
Which of the following statments about this Huffman tree are TRUE?
X. The Huffman code for 'f' is 1101.
Y. The Huffman code for 'e' is 000.
Z. The Huffman code for space (' ') is 111.
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
9. Which of the following statements are TRUE?
X. The MAR determines whether data is to be fetched from memory or stored to memory.
Y. A multiplexor circuit can be used to select the proper ALU result.
Z. Data stored at larger memory addresses in RAM, take longer to be accessed than data stored at smaller memory
addresses.
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
COMPSCI 110
Page 5 of 22
10. Here is a program using the pseudocode presented in lectures:
Using this program, which of the following give the correct output with the given input?
X. Input: 7, Output: 39
Y. Input: 6, Output: 21
Z. Input: 1, Output: 0
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
COMPSCI 110
Page 6 of 22
11. Here is an assembly language program using the textbook language (the appendix contains the textbook instruction set):
.BEGIN
IN X
L: LOAD X
COMPARE Z
JUMPEQ E
LOAD W
ADD Y
STORE W
INCREMENT Y
DECREMENT X
JUMP L
E: OUT W
HALT
W: .DATA 0
X: .DATA 0
Y: .DATA 1
Z: .DATA 0
.END
Using this program which of the following give the correct output with the given input?
X. Input: 0, Output: 1
Y. Input: 4, Output: 4
Z. Input: 2, Output: 2
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
COMPSCI 110
Page 7 of 22
12. Here is an assembly language program using the textbook language. The comments at the right end of each line are for
numbering the lines. The program starts at address zero. The appendix contains the textbook instruction set.
.BEGIN -- line 1
IN X -- line 2
L: LOAD X -- line 3
ADD X -- line 4
STORE X -- line 5
LOAD Z -- line 6
COMPARE Y -- line 7
JUMPEQ E -- line 8
DECREMENT Z -- line 9
JUMP L -- line 10
E: OUT X -- line 11
HALT -- line 12
X: .DATA 0 -- line 13
Y: .DATA 0 -- line 14
Z: .DATA 3 -- line 15
.END -- line 16
Using this program, which of the following have the correct machine code and data (both in hexadecimal) for the specified
line?
X. Line 3 - 000D
Y. Line 6 - 000D
Z. Line 12 - F000
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
COMPSCI 110
Page 8 of 22
13. Consider the following C or Java source code:
while (l==5) { l = - b + c / _x2;}
If analysed with the lexicographical analyser from the lectures, how many tokens and token classes do we find here?
A. 17 tokens and 11 token classes
B. 17 tokens and 13 token classes
C. 17 tokens and 12 token classes
D. 16 tokens and 13 token classes
E. 18 tokens and 13 token classes
14. Which of the following BNF specifications are recursive?
X. ::= | $ | _ | @ | ! | % | ^ | * | ( | ) | . |
Y. ::= |
Z. ::= |
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
15. Consider the following BNF grammar:
::= 1|2|3|4|5|6|7|8|9
::= 0|
::= +|
Which of the following patterns does this grammar match?
X. +64
Y. 03
Z. 570
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
COMPSCI 110
Page 9 of 22
16. Consider the parsing tree below:
Which of the following BNF grammar definitions could have been involved in the production of this tree?
X. ::= =|<|>
Y. ::= |+
Z. ::= |
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
17. Which of the following statements are true about semantic analysis during compilation?
X. A syntactically correct statement might be semantically wrong.
Y. The semantic analysis phase generates a parse tree for the input tokens.
Z. A non-terminal symbol may be linked to an existing semantic record.
A. X and Y only
B. X and Z only
C. Y and Z only
D. All of X, Y, and Z
E. None, or only one of X, Y, and Z
18. Assume that in a multiprocess OS, each process spends about 50% of it's time waiting for I/O operations to be completed.
Which of the following statements are true?
X. If there are 3 processes loaded into memory, the processor utilization will be 75%.
Y. If there are 4 processes loaded into memory, the processor utilization will be 100%.
Z. If there are 2 processes loaded into memory, the processor utilization will be 50%.
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
COMPSCI 110
Page 10 of 22
19. A file on a Linux machine has permissions rw-------. This file is:
X. executable by its owner.
Y. not writable by its owner.
Z. readable by members of its group.
A. X only
B. Y only
C. Z only
D. None of X, Y, and Z
E. All, or two of X, Y, and Z
20. A file on a Linux machine should have permissions rwxr-x--x. Which command do you use to set these permissions?
A. chperm 771
B. chgrp 711
C. chmod 751
D. chmod 771
E. chperm 751
21. Which of the following statements about file permissions in Unix are correct?
X. The owner user of a file can change file ownership to any other user.
Y. A file with permissions drw-rw-rw- is a directory.
Z. A file can be associated with multiple groups at a time.