96/59.102

ALB

Massey University

Albany Campus

EXAMINATION FOR 59.102 COMPUTER SCIENCE FUNDAMENTALS (B)

Second Semester - 1996

Time allowed: THREE (3) hours

The use of calculators is NOT allowed.

1. (a) Convert the following C constants to binary.
(i) 23
(ii) 0x022
(iii) 65
[3 marks]
(b) Convert the following binary numbers to hexadecimal.
(i) 1011
(ii) 10100111
(iii) 111111111111
[3 marks]
(c) When a number is stored using two's complement notation, what does the most significant bit represent.
[1 mark]
(d) What is the relationship between the representation of a signed integer stored using excess notation, and using two's complement notation.
[2 marks]
(e) Give the 8 bit binary, two's complement representations of the following numbers.
(i) Zero
(ii) -4
(iii) -128
[3 marks]
(f) Briefly explain the difference between an overflow and a carry.
[2 marks]
(g) Name the three components of a floating point number.
[3 marks]
(h) Give an example of an arithmetic operation on floating point numbers that may cause an underflow. State any assumptions you make.
[3 marks]
2. (a) Given two binary numbers, A and B, draw a logic diagram and truth table for the following logic function:
C= (NOT(A) AND B) OR (NOT(B) AND A)

Comment on this logic function.
[4 marks]
(b) Briefly explain the purpose of the Arithmetic/Logic Unit (ALU) in a modern CPU.
[2 marks]
(c) Why is it necessary for most CPUs to have a flags register
[2 marks]
(d) Every CPU has control instructions called jump or branch instructions, what is the purpose of these instructions.
[2 marks]
(e) Give brief definitions of the following terms:
i) Instruction Register
ii) Assembly Language
iii) Memory Mapped Input/Output
iv) Pipelining
v) Multiprocessing
[10 marks]

3. (a) A program is to be written to hold information about a record collection, each record is an ordered collection of tracks and each track has a title and a duration. A suitable typedef for a record is:
typedef struct {
char *title;
char *artist;
track_list tracks;
} record;
Give a suitable typedefs for a type track (a single track) and for the type track_list.
[5 marks]
(b) Describe the differences between the queue and the stack data structures.
[5 marks]
(c) What is the output of the following program.

#include <stdio.h>

void strange(int what, int how, int why) {
int when;
if (why > 0) {
when=what+how;
strange(how,when,why-1);
printf("%d\n",when);
}
}

int main() {
strange(0,1,6);
}
[5 marks]

(d) Rewrite the function called `strange` so that the output from the program is in reverse order.
[5 marks]

4. (a) A program written in an imperative programming language uses three algorithmic forms. What are these forms? For each one give a short example in C.
[3 marks]
(b) The quicksort algorithm calls a function to partition an array. Describe what this function does.
[3 marks]

(c) Give BNF production rules that completely describe the C 'if' statement. Assume the following symbols are already defined.
<expr>       An expression
<statement>  A statement (with terminating ';')
[4 marks]
(d) Give brief definitions of the following:
(i) The Church-Turing thesis
(ii) Big-O notation
(iii) Turing Machine
(iv) Game Tree
(v) Depth First Search
[10 marks]
5. (a) What is the difference between a program that is totally correct and a program that is partially correct.
[2 marks]
(b) What are the main functions of an operating system?
[4 marks]
(c) Draw an E-R diagram to describe an exam paper. Use the following entities:

exam      The complete exam paper.
question  One question on the paper.
part      Part of a question.

Show the attributes for each entity on your diagram. What is the primary key for each entity?
[6 marks]
(d) What is the difference between a depth first and a breadth first search?
[3 marks]
(e) The following diagram shows six towns called A,B,C,D,E and F
Diagram missing, think of one yourself!
Draw a search tree that could be used to find a route from A to F. Ignore circular routes.
[5 marks]

+ + + + + + + + + +