98/59.102

ALB

Massey University

ALBANY CAMPUS

EXAMINATION FOR 59.102 COMPUTER SCIENCE FUNDAMENTALS

Semester Two - 1998

Time Allowed: THREE (3) Hours

INSTRUCTIONS

Attempt ALL FIVE (5) questions.

This final examination contributes 60% to the final assessment.

Calculators are permitted.

1. (a) Convert the following signed integers to eight bit two's complement binary.

(i) 127

(ii) -3

[2 marks]

(b) Convert the following binary numbers to hexadecimal.

(i) 01100110

(ii) 1111

[2 marks]

(c) What is the largest unsigned integer that can be stored using four bits.

[1 mark]

(d) Briefly explain the difference between a carry and an overflow; give examples of operations that cause each.

[3 marks]

(e) When a floating point number is converted from a 'double' to a 'float' what may happen to the number.

[2 marks]

(f) Give a line of C that will convert a single numeric character ('0','1','2','3','4','5','6','7','8' or '9') to an integer.

[2 marks]

2. (a) Draw the truth table for an XOR gate.

[2 marks]

(b) Briefly explain the difference between combinational and sequential logic.

[2 marks]

(c) What is the address bus? What would be the main advantage of designing a CPU with a 24 bit address bus instead of a 16 bit address bus.

[3 marks]

(d) What does the following assembly language program do? State any assumptions you make.

MOV A,[100]

MOV [100],A

[3 marks]

(e) The Pentium is a CISC processor and the Powerpc is a RISC processor. Which of these will generally have shorter programs? Why?

[2 marks]

3. (a) The following C code declares a linked list of numbers:

typedef struct _item {

int no;

struct _item *next;

} item;

(i) Write a C function to add a number to the head of the list.

[4 marks]

(ii) Write a C function to print all the numbers in the list.

[3 marks]

(b) A tree holds student ID numbers in order (smallest to the left). If the following ID's are inserted into the tree, draw a diagram showing the resulting data structure.

98043712, 98165027, 98102413, 97021643, 98321406, 98179230, 98591734

[3 marks]

(c) What is a hash table and what advantage does it have over other data structures.

[2 marks]

4. (a) What output does the following program produce:

#include <stdio.h>

void funny(int i,int j) {

if (j<20)

funny(j,i+j);

printf("%d\n",i);

}

void main() {

funny(0,1);

}

[4 marks]

(b) The following algorithm partitions an array:

int partition(int n[],int left,int right) {

```  int lo,hi,pivot,t;
pivot=n[left];
lo=left-1;
hi=right+1;
while(lo+1!=hi) {
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else {
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}
n[left]=n[lo];
n[lo]=pivot;
return lo;```

}

Show the steps involved in a quicksort of the following array using this algorithm:

[20,10,1,52,78,9]

[4 marks]

(c) The following is a BNF grammar that describes some binary numbers.

```      <bit>  := 0|1
<word> := 0<bit>|1<word>```

Give all the four bit numbers that are valid words.

[3 marks]

(d) What is the complexity (in big O notation) of the partition algorithm given in part (b).

[1 mark]

5. Briefly define the following terms:

(i) Wide Area Network

(ii) Network Protocol

(iii) Turing Test

(iv) Turing Machine

(v) Depth First Search

(vi) Functional Programming Language

(vii) Program Counter

(viii) Machine Language

(ix) Object Oriented

(xi) File System