{ You should not use calculators for doing these questions }
1. Convert the following binary numbers to decimal. Show all working.
(a) 1011 (b) 101010 (c) 110011
2. Convert the following decimal numbers to binary. Show all working.
(a) 17 (b) 22 (c) 35
3. Convert the following binary numbers to hexadecimal. Show all working.
Show that your conversion is correct by converting the hex to decimal.
(a) 1010101 (b) 111111 (c) 10011101
4. Perform the following additions in binary. In each case, convert the two numbers to binary, then
add them as binary numbers and then convert the result back to decimal. Show all working.
(a) 15 + 17 (b) 16 + 4 (c) 23 + 10
5. Perform each of the following subtractions using twos complement arithmetic and a word size
of 8 bits. Show all working and check your answers.
(a) 7 - 3 (b) 15 - 17 (c) 28 - 20
6. For each of the following 8 bit twos complement arithmetic operations, state if the operation
causes a carry or an overflow.
(a) -10+20 (b) 100+100 (c) -100-50 (d) 10+120
1. What does the following piece of code print?
int s,i;
s=0;
for(i=0;i<6;i++)
s=s+i*s;
printf("%d",s);
a) 0
b) 120
(5*4*3*2*1)
c) 15 (5+4+3+2+1)
d) 720 (6*5*4*3*2*1)
2. Why is & often placed before a variable passed to the scanf function?
a) to pass the contents of the variable
b) to pass a pointer
to the variable
c) to make a copy of the variable
d) so the
compiler knows the variable is a global variable
3. Which one of the following is true?
a) global variables must have different names to local variables.
b) local variables are automatically initialised to zero
c)
when a variable is passed to a function its value is copied to a
formal parameter of the function.
d) a global variable can not
be passed as the parameter of a function.
4. What does the following do.
int i=9;
int j=5;
int k=0;
while(j>0) {
k=k+i;
j=j-1;
}
a) adds i to j and puts the result in k.
b) divides i by j and
puts the result in k.
c) subtracts j from i and puts the result
in k.
d) multiplies i by j and puts the result in k.
5. Which of the following is NOT true?
a) C is a structured programming language.
b) in C, a "for"
loop can be rewritten as a "while" loop.
c) the
statement x==4;
does the same as the statement x=4;
d)
a function declared to take an integer will not work if it is passed
a float
6. What does the following declaration of fopen mean?
FILE *fopen (char *path, char *mode);
a) fopen is passed two strings called path and mode and returns a
structure call FILE.
b) fopen is passed two strings called path
and mode and returns a pointer to a variable of type FILE.
c)
fopen is passed two characters and returns a pointer to a FILE.
d)
fopen is passed two pointers to characters and returns pointer to a
character.
1. What is the decimal representation for the binary number 100010001?
a) 111 b) 273 c) 224 d) 223
2. The decimal number 72 is represented in binary as:
a) 1001100 b) 1011000 c) 1001000 d) 1010000
3. What is the 8 bit twos complement binary representation for the decimal number -8?
a) 11111000 b) 11111100 c) 11111001 d) 11110111
4. The binary number 11111 can be written in hexadecimal notation as:
a) 3e b) 1f c) 37 d) 3f
5. What is the largest integer that can be stored using 8 bit 2's complement?
a) 255 b) 128 c) 127 d) 256
6. Which of the following operations does NOT cause an overflow when performing 8 bit twos complement arithmetic?
a) -10+20 b) 100+100 c) -100-50 d) 10+120
7. What is the 8 bit twos complement representation of the following numbers.
(a) 126 (b) -42 (c) 200
8. Convert the following decimal numbers to fixed point binary:
(a) 6.5 (b) 13.25
9. Consider the following portion of a C program:
signed char c;
unsigned char u;
c = 0x9C;
u=c;
printf ("%d\n", c);
printf ("%u\n", u);
printf ("%c\n", c-0x50);
printf ("%x\n", u);
Write down exactly what will appear on the screen when these statements are executed.
10. What is the 32 bit hexadecimal representation of the following IEEE 754 floating point numbers?
(a) 6.5 (b) 13.25
11. What does the following piece of code do?
float f=1,g=0;
while(f != g) {
g=f;
f=f+1;
}
printf("%f \n",f);
12. What will happen if f and g are changed to ints and the %f is changed to %d?
1. Which of the following is NOT true?
a) In C, 'doubles' use more storage than 'floats'.
b) The
fraction in a 'float' can be 1.5
c) All 32 bit integers can be
stored as a 'float'
d) The exponent in IEEE 754 f.p. numbers is
stored using excess notation.
2. Which of the following can be used to convert character from upper to lower case?
a) if(c>='A' && c<='Z') c=c-('A'-'a');
b)
if(c>='a' && c<='z') c=c+('A'-'a');
c) if(c>='Z'
|| c<='a') c=c-('A'-'a');
d) if(c>='z' || c<='a')
c=c+('a'-'A');
3. The fixed point representation of 27.75 is
a) 10010.10 b) 11011.11 c) 11011.101 d) 11011.10
4. The 32 bit hexadecimal representation of -0.5 using ieee 754 floating point is:
a) bf000000 b) 3f000000 c) 8f000000 d) ff000000
5. Which of the following 32 bit ieee 754 numbers is between 0 and 1?
a) 3e000000 b) c0800000 c) 40000000 d) c0000000
6. What does this section of C program print:
char x=100,y;
int z=1;
y=x ^ 255;
while(y & z) {
y=y ^ z;
z=z*2;
}
y=y ^ z;
printf("%d\n",y);
7. The parity of a binary number is defined as:
The parity of a binary number depends on the number of 1 bits in
the number
parity is "even" if there are an even no of
1s in the number and "odd" otherwise:
e.g. parity of 0011001100110011 is even.
Draw the truth table for a logic function that takes a three bit binary number and produced an output that is 0 for even parity and 1 for odd parity.
8. Draw the logic diagram for a circuit that implements the function in question 7.
9. Draw the truth table for a logic function that will subtract three bits to produce a difference and a borrow.
10. Draw the logic diagram for a circuit that implements the function in question 9.
1. How many possible three input, one output binary logic functions are there?
a) 256 b) 64 c) 8 d) 16
2. The following truth table is for which logic gate?
_x_y_|_z_
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1
a) AND b) OR c) NOT d) XOR
3. Which of the following is NOT true?
a) An eight bit adder can be made from two four bit adders
b)
An adder is a sequential logic device
c) A full adder has three
inputs
d) A four bit adder can be made from four full adders
4. What is the truth table for the borrow output from a 3 bit subtractor
|
a) |
_x_y_z_|_b_ |
b) |
_x_y_z_|_b_ |
c) |
_x_y_z_|_b_ |
d) |
_x_y_z_|_b_ |
5. What does the following C statement print:
printf("%x",((0x654 & ~(0xf0)) ^ 0x333) | 0x124);
a) 537 b) 1335 c) 655 d) 3ef
6. What does the following piece of sequential logic do:
7. A CPU has instructions for the operations ADD, AND, OR and XOR.
These instructions take data from two memory locations, perform the
operation and store the result in the first location.
Give a
sequence of instructions that could be used to:
a) multiply a number stored in memory location 76 by 10.
b) subtract two numbers stored in memory locations 5 and 6 and put the result in location 7.
Assume the values 1 and -1 are stored in memory locations 28 and 29 respectively.
1. The address bus:
a) Carries data to and from the memory c) Carries instructions
to the memory
b) Is used to index data in the memory d) Carries
instructions to the CPU
2. Which of the following instructions is a control instruction?
a) JMP 500 b) ADD [r1+r2],r3 c) SUB r1,r2,r3 d) SUB [r1+r2],r3
3. A significant difference between a RISC CPU and CISC CPU is:
a) RISC CPUs are much slower than CISC CPU's c) CISC CPUs have
longer programs
b) RISC CPUs have a larger instruction set d)
CISC CPUs have a larger instruction set
4. A CPU has instructions using 2 addresses and an ALU operation, the operation is performed on data stored at the two addresses and the result stored at the first address. If a number 'a' is stored in location 19, what does the following do?
XOR 20,20
ADD 20,19
ADD 19,19
ADD
19,20
a) Multiply a by 2 b) Multiply a by 3 c) Multiply a by 4 d) Multiply a by 5
5. Which of the following CPU's will probably run your second assignment faster
a) A 600 Mhz RISC CPU that executes an instruction in 2 clock
cycles
b) A 300 Mhz CISC CPU that executes an instruction in 1
clock cycle
c) A 400 Mhz CISC CPU that executes an instruction
in 2 clock cycles
d) A 400 Mhz RISC CPU that executes an
instruction in 2 clock cycles
6. Think up a simple, but realistic, instruction set and write assembly language using this instruction set for the following sections of C program.
a)
int
a,b=7,c=12;
a=b+c;
b)
int
a=7;
if(a==12) a=a+1;
c)
int
i,x[100];
for(i=0;i<99;i++)
x[i]=x[i]+x[i+1];
1. If the following data is stored in memory and pointers use 32 bits.
address:data
2000:04 2004:08 2008:0c 200c:00
2001:20 2005:20 2009:20 200d:20
2002:00 2006:00 200a:00 200e:00
2003:00 2007:00 200b:00 200f:00
what does the following print?
printf("%x\n",*(*(0x2004));
a) 2000 b) 2004 c) 2008 d) 200c
2. An ordered list contains (1,3,7,9,10,20,42,89,97,145), a binary search is used to lookup 89 in the list, how many list items are examined?
a) 2 b) 3 c) 4 d) 5
3. A list contains the values (8,16,4,9,10,6). If the following is used to delete an item i from the list:
for(j=0;j<length;j++)
if(list[j]==i)
list[j]=list[--length];
what does the list contain after the following operations?
delete(16),delete(6),delete(8)
a) (9,10,4) b) (4,9,10) c) (10,4,9) d) (10,9,4)
4. After the following stack operations, what is on the stack?
push(12); pop(); push(8); push(7); push(13); pop(); pop(); push(6);
a) 8,6 b) 7,13 c) 6,12 d) 7,8,12
5. Why is the binary search algorithm
unsuitable in a situation where items are often added to or
deleted
from the list?
6. Assume that there are 400 000 names in the Auckland Telephone Directory.
a) What is the average number of names that you
would look at using linear search?
b) What is the maximum
number of names that you would look at using linear search?
c) What
is the maximum number of names that you would look at using
binary search?
7. Write a C function to insert an item into a list of integers, the list must be sorted with the smallest first and you must use binary search to find the position for the new item. Allow duplicate items.
1. The following letters are inserted into a tree and the tree is printed using preorder traversal (visit root,traverse left, traverse right) what is the result?
M,A,R,T,I,N
a) AIMNRT b) TRNMAI c) MARTIN d) MAIRNT
2. Which of the following is not true
a) A stack is a FIFO data structure
b) A queue is a type
of list
c) The item that has been in a queue the longest will
be the first to be removed.
d) A stack can be implemented using
arrays.
3. What does typedef do?
a) It makes a structure
b) it gives a new name to a
structure
c) it makes a pointer
d) nothing
4. Given the following recursive function, what does ting(100) print?
void ting(int a) {
if(a>0) ting(a/3);
printf("%d ",a);
}
a) 100 33 11 3 1 0 b) 100 33 11 3 1 c) 0 1 3 11 33 100 d) 1 3 11 33 100
5. An ordered tree has the following items inserted in it, draw the tree.
(500,600,900,200,800,1000,50,250,850)
6. Give the order that items are visited if the tree from question 5 is visited:
a) using preorder traversal
b) using inorder
traversal
c) using postorder traversal
7. Write a recursive function to print an integer with its digits in reverse order (e.g.) 578 is printed as 875.
8. Write a recursive function to find the sum of the digits in a number (e.g) sum(578)=20.
1 Sequence, Selection and Iteration are:
a) Types of programming language c) Types of construct used in a
programming language
b) Types of algorithm d) Types of program
2. What does the following function do:
int f(int c) {
if (c>0) return f(c-1)+c;
else return 0;
}
a) returns the sum of all the numbers from 1
to c inclusive c) returns the factorial of c
b) returns c-1+c
d) returns 0
3. What does the following function do:
void b(int c) {
if (c>15) b(c/16);
printf("%x",c%16);
}
a) prints the sum of all the numbers from 0 to 15 c) prints c in
hexadecimal
b) prints all the numbers from 0 to 15 in
hexadecimal d) prints "x" c times.
4. C++ is usually described as:
a) a functional programming language c) a declarative
programming language
b) an imperative programming language d) an
object oriented programming language
5. Quicksort is defined as:
void quicksort(int n[], int left,int right) {
int dp;
if (left<right) {
dp=partition(n,left,right);
quicksort(n,left,dp-1);
quicksort(n,dp+1,right);
}
}What would happen if the two recursive calls to quicksort were swapped over.
6. What is the complexity (using big O notation) of the algorithm for a binary search of an ordered list.
7. What is the complexity (using big O notation) of the algorithm to insert an item into an ordered list.
8. Derive an expression for the complexity of the following selection sort algorithm, use a comparison as a single step.
void select(int n[],int no) {
int i,j,t,s;
for(i=0;i<no-1;i++) {
s=i;
for(j=i+1;j<no;j++)
if(n[j]<n[s]) s=j; // find smallest item
t=n[s]; // swap smallest with first
n[s]=n[i];
n[i]=t;
}
}
1. Given the following BNF grammar.
<X> := A|B <Y> := A<X>|<X>B|A<Y>
Which of the following is a valid <Y>
a) BABA b) ABBA c) AABB d) BBAA
2. What is the Church-Turing thesis?
a) It is possible to make a computer from a toilet roll
b)
Complex computers are more powerful than simple ones.
c) All
computers are equally powerful
d) Some algorithms are infeasable
3. What is the complexity of a simple algorithm to find out if a number is prime by checking to see if it is divisible by all numbers less than it.
a) O(n) b) O(n2) c) O(log n) d) O(n log n)
4. What is the complexity of the partition algorithm used by quicksort?
a) O(n) b) O(n2) c) O(log n) d) O(n log n)
5. Given the following BNF grammar.
<b> := 0|1 <w> := <b>|<w>1
Which of the following is NOT a valid <w>
a) 0
b) 111
c) 011
d) 101
6. Give the BNF rules for the C switch statement, assume the following are already defined
<statement> a C statement
<intexp> a C expression evaluating to an integer
<constant> a constant value
7. The work for 59102 consists of one lecture followed by zero or more lectures interspersed by zero or more tutorials and zero or more assignments with one exam at the end.
Give BNF rules to describe this structure.
8. Give the state table for a Turing machine to subtract two 1 bit numbers.
1. Which of the following does a operating system NOT do:
a) run programs b) allocate memory c) read from hard disk d) compile programs
2. The difference between pre-emptive and non pre-emptive multitasking is:
a) pre-emptive allows more than one program to run at once
b)
pre-emptive runs each program in short, fixed length, bursts
c)
non-preemptive can not do input/output
d) pre-emptive only does
a context switch during system calls
3. What is CPU scheduling
a) using more than one CPU c) deciding which program to run next
b) deciding which CPU to use next d) running more than one
program
4. Which of the following is TRUE.
a) The operating system has access to physical addresses
b)
A user program has access to physical addresses
c) Every
physical address is mapped to one logical address
d) Logical
addresses allow programs access to operating system data
5. Which of the following is a disadvantage of indexed allocation for a file system
a) Files cannot grow in size
b) There may be gaps between
files, wasting space.
c) Reading a file may involve moving to
many places on the disk.
d) Files cannot shrink in size.
6. Given the following precondition
{ x<3 && y>x+2 }After execution of the following C code, what is the postcondition?
x=x+1; y=y-x; y=y*2;
6. How do you think most operating systems utilise a computer with more than 1 CPU?
7. What does the operating system need to do when a program asks for some memory using the malloc function?
8. Most operating systems allow programs to use more memory than is physically available. How could this be achieved?
9. A 4GB disk uses 32k blocks and has 1000 files stored on it with an average size of 64k. If the OS uses indexed allocation, roughly how much space is wasted on the disk?