COMP104 Questions

Which of the following is NOT a form of intermediate representation
used by compilers?

Why can’t we allocate data frames statically, i.e. have one fixed area
for each subprogram? Which of the following are true
I. Data Structures may be dynamically allocated
II. Object Orientation demands the creation of Instances
III. Recursion causes data frames to grow arbitrarily

In calculating the formula ut + ½at2 using maximal concurrency,
which of the operations might be computed in parallel?

Consider the following grammar, where S, A and B are nonterminals,
and a and b are terminals:
S ::= AB
A ::= a
A ::= BaB
B ::= bbA
• Which of the following is FALSE?

Which of the following statements about threads is FALSE?

If a process executes a fork() system call, which of the following are
true?

What optimisation technique could be applied in the following
examples?
a = b^2
a = a / 2

Which of the following is usually NOT represented in a subroutine’s
activation record frame for a stack-based programming language?

If the UNIX command ‘head file’ outputs the first 10 lines of file, the
command ‘tail –n file’ outputs the last n lines of file, and the
command ‘wc –w file’ counts the number of words in file, what will
the following output?

head file | tail -1 | wc –w

If the symbol table for a compiler is size 4096, how many
comparisons on average need to be made when performing a
lookup using the binary chop method?

Consider the following sequence of page references in a paged
memory management system:
page | p | q | r | q | q | q | p | r | r | q |
time 0 1 2 3 4 5 6 7 8 9 10
• Page s arrives at time 10. Which of the following policies suggests
we should throw out page p to make room for s?
I. LRU
II. LFU
III. FIFO

In a paged memory system, why are page sizes invariably a power
of 2?

A computer uses 16-bit addressing. Its page size is 512 bytes. What
is the maximum number of entries that the page table must be
capable of holding?

Consider the following situation regarding two processes (A and B),
and two resources (X and Y):
– Process A is granted resource X and then requests resource Y.
– Process B is granted resource Y and then requests resource X.
• Which of the following is (are) true about the potential for deadlock?

I. Deadlock can be avoided by sharing resource Y between the two processes
II. Deadlock can be avoided by taking resource X away from process A
III. Deadlock can be avoided by process B voluntarily giving up its control of
resource Y

A paricular BNF definition for a “word” is given by the following rules:
word ::= letter|letter pairlet | letter pairdig
pairlet ::= letter letter| pairlet letter letter
pairdig ::= digit digit | pairdig digit digit
letter ::= a|b|c|…|y|z
digit ::= 0|1|2|…|9
Which of the following lexical entities can be derived from ⟨word⟩ ?
I. note
II. notes
III. c22

A Java object called ‘helper’ contains
the two methods opposite, where num
is an integer variable that is private to
helper. Its value is initially 100.

• One thread makes the call
– helper.addone();
• At the same time, another thread
makes the call
– helper.subone();
___________________

public void addone() {
num = num + 1;
}
public void subone() {
num = num - 1;
}
___________________

A new program requires 100K of memory to run. The memory
management approach adopted is a simple partitioning one, and the
operating system has the following list of empty partitions:
60K, 240K, 150K, 600K, 108K, 310K
• Assuming that the 150K partition is chosen, say which of the
following selection strategies is being used:

The page table shown below is for a job in a paged virtual storage
system with a page size of 1K:
segment datum
0 4
1 2
2 0
3 1
• A virtual address of [1, 352] would map on to what actual address?

To assist in locating a bug that is causing a program to crash, a
programmer inserts print statements as follows:
begin
...
print(“Got to point A without crashing”);
...
print(“Got to B without crashing”);
...
end

A BNF grammar includes the following statement:
"statement ::= iden := ( expr );"
• What kind of message would be produced by the following line of
code?
a := (2 + b;

The value of a semaphore s is initially 1. What could happen in the
following situation?
T1 T2
V(s); P(s);
critical region critical region
P(s); V(s);

Which code optimisation technique could be applied in the following
piece of code?
a = (20+10*2)/4;

Suppose two users simultaneously type the following command at
the unix shell command prompt ($):
$ ls –l
• Which of the following are true?

In a computer memory, a 100K partition becomes available. In the
ready list is a program image of size 300K, plus three others of sizes
100K, 85K and 15K.
• Assuming that our current priority is to avoid starvation of the 300K
program, which of those in the list should be swapped into the
available partition?

Lex is a software tool that can be used to aid compiler construction.
It is an example of which of the following?

A filestore allocation system uses a bit string to record the use of its
blocks, with 0 denoting free and 1 denoting allocated. A 16-bit
segment of this string has the hexadecimal value A9B3. How many
blocks are free?

Which of the following programming constructs tend to contribute to
the phenomenon expressed in the Principle of Locality?
I. Iteration (e.g. FOR and WHILE loops)
II. Selection (e.g. IF-statements)
III. Recursion

Which of the following is true about linked filestore allocation versus
contiguous allocation?

The following two statements describe the performance of two
programs:
– A performs a total of 20 seconds of computation and 15 seconds of input/output.
– B performs a total of 30 seconds of computation and 10 seconds of I/O
• Which of the following are true?
I. It will take up to 50 seconds to run A and B sequentially
II. It will take up to 75 seconds to run A and B sequentially
III. Using multiprogramming, the shorted time to execute both is 30 seconds
IV. Using multiprogramming, the shorted time to execute both is 50 seconds

A running process makes a system call to read data from a file.
Which process state should it enter next?

A starvation-free job-scheduling policy guarantees that no job waits
indefinitely for service. Which of the following job-scheduling policies
is starvation-free?

A program is split into 3 segments. The segment table contains the
following information:
segment datum limit
0 1700 5500
1 5600 8100
2 8300 9985
• where ‘limit’ is the physical address following the end of the
segment, and instructions take the form opcode segment, offset
• If the program executes
– LOAD 1, 135
• what physical address is accessed?

Consider the following sequence of page references in a paged
memory management system:
page | p | q | r | q | q | q | p | r | r | q |
time 0 1 2 3 4 5 6 7 8 9 10
• What would be the predicted working set expressed as W(10,3)?

Concerning compilation, which of the following is NOT a method for
symbol table access?

If the array x contains 20 ints, as defined by the following
declaration:
int x[] = new int[20];
• What kind of message would be generated by the following line of
code?
a := 22;
val := x[a];

Process A and process B both share the same code segment S.
Which of the following statements is (are) true?
I. An entry for S appears in both segment tables
II. The segment code must be re-entrant
III. The segment code must be recursive

When should a deleted file not be garbage collected?

In generating code for the following assignment
X := X / 4
• an optimising compiler might use strength reduction and generate
code equivalent to which of the following?

Which of the following postfix expressions is equivalent to the
following expression?
a*b – c/d

If you type ‘cat prog.c’ at a UNIX command prompt, which of the
following sequences of system calls would be invoked?

The lookup page table shown below is for a job in a paged virtual
storage system with a page size of 1024 locations. Each virtual
address is of the form [p,d] where p and d are the page number and
the displacement in that page, respectively
Virtual Page Actual Page
0 3
1 -
2 4
3 0
• A virtual address of [0, 200] maps
on to an actual address of?

Consider the following sequence of page references in a paged
memory management system:
page | p | q | r | q | q | q | p | r | r | q |
time 0 1 2 3 4 5 6 7 8 9 10
• What is the working set expressed as W(3,4)?

Consider the following Gantt chart showing the CPU burst times (in
milliseconds) of three processes using the round robin scheduling algorithm:


P1 P2 P1 P3 P1 P1
0 5 9 14 19 24 28

• Suppose the three processes, P1, P2 and P3, all arrive at time 0 and we are
using a time quantum of 5 milliseconds. Assuming we are not including time
for performing context switching, what is the average waiting time in the
above example?