Midterm 1

1. Why do we study advanced data structures ? [5]

   Efficiency and generalization

2. What does it mean when we say that "f(n) is in O(g(n))" ? [5]

   There exists a c and n0 such that f(n) <= c g(n) for all n > n0

3. Why do we use a dummy head node in a linked list ? [5]

   To avoid having to write special coding cases to handle trivial (eg. empty) lists

4. In a singly linked list, why is it more efficient to use a "current" pointer that points to the node before the current node ? [5]

   So that operations that need relinking to be performed on the previous node can find it without an O(n) search from the head.

Match the following terms with the most appropriate descriptions :
queue, parent, doubly linked list, stack, average case, worst case, data structure, right child, singly linked list, freelist

data structure	implementation
single linked list	one pointer per node
stack	elements are added/removed at one end of the data structure
queue	FIFO (first-in-first-out)
right child	2r+2
doubly linked list	ability to always find previous node in O(1) time
parent	(r-1)/2
worst case	crucial for real-time applications
freelist	avoid unnecessary allocation/deallocation of storage
average case	consider all input combinations

Question Three [40]

1. What is a stack ? [4]

An abstract data type where the first element added is the last removed (FILO).

2. What are the specific names of the 3 primitive abstract operations associated with a stack ? [6]

(a) Push, (b) Pop, (c) Top

3. What is the asymptotic time complexity (in the average case) for each of these operations, when the stack is implemented efficiently using a linked dynamic data structure, as compared to when the stack is implemented efficiently using an array ? [6]

Operation	T(n) for array	T(n) for linked list
(a) Push	O(1)	O(1)
(b) Pop	O(1)	O(1)
(c) Top	O(1)	O(1)

4. Fill in the code to REMOVE an element from the top of the stack, and return it to the calling routine, in a linked list implementation. [14]

Node *Stack::Remove ()
{
   if (TopOfStack == NULL) return NULL;
   Node *Temp = TopOfStack;
   TopOfStack = TopOfStack->Next;
   return Temp;
}

with the following definitions :

class Node {
   char aValue;
   Node *Next;
};

class Stack {
   Node *TopOfStack;
   Stack () { TopOfStack = NULL; }
   Node *Remove ();
   .
   .
};

Assume that TopOfStack points to the topmost element and that there is no dummy head node.

5. Explain how you would use a stack to check if the parentheses in a string or expression are properly balanced. In a balanced string, when scanning from left to right, you will never have encountered more right parentheses than left parentheses. For example, "(())()" is balanced while "()))" is not. Two errors are possible – either there are too many left parentheses (e.g. "(()" ) or too many right parentheses (e.g. "())" ) – indicate how each of these can be checked for. [10]

Scan string L->R

• on ( push onto stack
• on ) pop from stack
  • if stack is empty then "too many )s"

After scanning, if stack is not empty then "too many (s"

Consider the following tree:

1. Write out the order in which elements are visited if a PostOrder traversal is performed on the tree. [5] 4, 6, 2, 3, 7, 1, 8, 5
2. Write out the order in which elements are visited if an InOrder traversal is performed on the tree. [5] 4, 7, 6, 3, 2, 5, 1, 8
3. Approximately how many nodes in a full tree (where the tree has n nodes) are leaf nodes ? [2] n/2
4. Answer the following questions [8] :

what are the parents of "6" : 3
what are the children of "4" : none
what are the ancestors of "3" : 5, 7
what are the descendents of "7" : 4, 3, 6, 2