**NO QUESTIONS WILL BE ANSWERED DURING THIS TEST **

About his test:

  • has 14 questions. Check you have them all.
  • out of 43 marks
  • closed-book with no aids
  • code to be written in ANSI C
  • only questions answered in pen can be re-evaluated
  • given formulas:

First Name: ______SOLUTION______

Last Name: ______

Student ID: ______

Labsection/day/time (check one):

□Section 1 Thursday 10am ENG202

□Section2 Monday10am ENG202

□Section 3 Wednesday11am ENG201

□Section 4 Thursday 2pm ENG201

□Section 5 Wednesday 2pm ENG203

□Section 6Thursday 11am ENG202

  1. (2 marks) Define the term ADT (Abstract Data Type).

Anything similar to either of these:

-Data structure plus operations (I-2 of notes)

-A way of packaging data structures and operations into a useful collection whose properties have been carefully studied. (P10-11 of text)

  1. (3 marks) Your textbook statesthat data structures such as files, lists, arrays and strings are “fictional entities that we create in our imaginations,” and that “they provide no essential capacity that cannot be implemented in terms of machine primitives.” Then why do computer scientists use data structures? Briefly, give 3 very different reasons:

See Page 9-10 of text and I-3 of notes. Any 3 from these, i.e., any 3 from:

more efficient (cheaper) to use components vs. building from scratch (text and notes)

helps us deal with complexity (text and notes)

useful for helping us solve programming problems, providing a stock of ideas (text)

provide building-blocks (notes)

provide information-hiding (notes)

  1. (3 marks) Consider the following function X and list L. Suppose a main program calls: X(&L);

Draw L at location /*HERE*/ in the function (just before the call returns.)

  1. (2 marks) A programmer usesinformation hiding when writing an ADT.

(a)Who is the programmer hiding information from?

the user (of the ADT)

(b)What information is the programmer hiding?

any of these: the implementation, the function code, etc.

  1. (5 marks) Consider these 7 recursive terms:

(1) going down(2) going up(3) edges-and-center (4) division-in-half

(5) last and all-but-last (6) first and all-but-first (7) tail recursion

For each of the following 4 algorithms, list ALL the recursive terms above that apply to it (write

only numbers in the boxes).

SumSquares (m, n)

if (m < n) return m*m + SumSquares(m+1,n)

return m*m

SumSquares (m, n)

if (m = n) return m*m

temp = (m+n)/2 /*integer division*/

return SumSquares(m, temp) + SumSquares (temp+1, n)

SumSquares (m, n)

if (m < n) return m*m + SumSquares(m+1, n-1) + n*n

return m*m

SumSquares (m, n)

if (m >= n) return n*n

return n*n + SumSquares (m, n-1)

  1. (3 marks) There are several reasons why infinite regress may occur. Give 3 very different reasons.

R-13 of notes gives several. Any 3 from:

forget base case

incomplete base case

never gets to base case (but need to say WHY): Why?

programmer error

incorrect usage given API

not enough resources

Text page 83 also gives many. These are accepted.

  1. (3 marks) Draw an fully annotated call tree(including operations) for Fib(4), where Fib is as follows:

Fib(x) {

if (x <= 1) return x;

return Fib(x-1) + Fib(x-2);

}

NOTE: annotated call trees from notes R-8, and text p. 69-70

  1. (4 marks) The following algorithm inserts an item into a linked list. Assume:
  2. list is circular with a header node, and list items are in ascending order.
  3. “” is like the C short-circuit operator. i.e., in code (A B), B is not evaluated when A is false.
  4. overflow is impossible

Derive theexact average number of times the “point” moves along the listin order toinsert the item;i.e., count ONLY “point=point->link”. Show your work. Do not give big-O notation.

insert (item, list)
new=GetNode()
new->info = item
point = list
while (point->link != list & point->link->info < item )
point = point->link
new->link = point->link
point->link = new

From Notes LL2

into position 1: 0 times

into position 2: 1 times

…

into position n: n-1 times

into position n+1:n times

Average n+1 things: average is:

(0+1 + 2 + … + n )/ (n+1) = n/2.

  1. (4 marks) Consider the following algorithm.

(a) Give a recurrence relation to express its space complexity. DO NOT SOLVE IT.

S(1) = K S(n) = K + S(n-1)

(b) Give a recurrence relation to express its time complexity. DO NOT SOLVE IT.

T(1) = K1 T(n) = K2 + T(n-1) Note the constants differ here

  1. (3 marks) Consider function makeList, which puts n integers into a linked list. Derive the space complexity of makeList, in bytes. Assume all variables (integers, pointers, etc.) each take 4 bytes of storage, and a stack frame takes 128 bytes. Show your work. Do not give big-O notation.

  1. (2 marks) A linked list is implemented using the parallel array approach, as shown below. What are the items of the list, in order from first to last?

List

C U U S T T R (Note: Parallel arrays done in notes LL1)

  1. (2 marks) Suppose you implement a list (of integers)in C, using an array size 100.Suppose the list grows and shrinks over time, but always maintains X items, where 65≤X≤85. This array implementation uses less space (memory) than if the list were implemented in C as a linked list with pointers, assuming integers and pointers each take 4 bytes of storage. Explain why.

The array always uses 100*4 bytes = 400 bytes.

The linked-list always uses AT LEAST 65*(4+4) bytes

(65 nodes, where each node uses 1 int and 1 pointer)

= 65*8 = 520 bytes.

Since the array uses 400 bytes and the linked-list at least 520 bytes, the array always uses less memory.

(Might also include pointer for list/array itself, but does not change result).

  1. (3 marks)We studied an algorithm that used a stack to evaluate postfix expressions. Show how the stack changes over time when that algorithm is used to evaluate the following expression. Start a new stack drawing each time the algorithm completes action “pop 2 things from stack”.Draw more stacks if you need to.

3 1 +2 2 + + 1+Algorithm was done in notes RLL2

Time →

  1. (4 marks)Suppose a Queue is implemented with linked allocation, using the following definitions

and functions:

Complete the function below to remove an item from the queue and place it into F.

int Remove ( Queue *Q, ItemType *F ){

QueueNode *Temp;

if ( Empty(Q) ) {

Underflow();

return 0;

}

*F = Q->Front->Item;

Temp = Q->Front;

Q->Front = Q->Front->Link;

free(Temp);

if (Q->Front == NULL) Q->Rear = NULL;

return 1;

}

1 mark for resetting front; 1 mark for freeing the node; 1 mark for resetting rear if deleted from a 1-item Q; 1 mark for returning an integer.