Indicate the correct answer for each of the following:

1. We draw high-level structure charts to
1. hierarchically model the design of a problem’s solution
2. specify the data/control flow to/from modules
3. specify a complete representation of the internal structure of individual modules
4. a and b
5. a, b, and c
2. After introducing multiple modules, the use of #ifndef is required because
1. the same constants cannot be included multiple times
2. separation of functions from data is desirable
3. conditional defines allow us to separate debug versions from release versions
4. a and c
5. a, b, and c
3. We can have multiple constructors for a class under the following circumstances
1. each has different types and/or numbers of parameters and return types
2. each has a different name
3. each has different default values
4. a and c
5. a, b, and c
4. The following expression/s have the same net effect as "int i = *(p+0)"
1. int i = p[0]
2. int i = *p+0
3. int i = **(&p)
4. a and b
5. a, b, and c
5. A non-circular doubly linked list can best and most generally be defined as
1. a linear sequence of elements chained together with pointers
2. a linear sequence of elements in sequential memory locations
3. a set of elements chained together with pointers
4. a set of elements in sequential memory locations
5. a set of elements, each with two pointers
6. Object-oriented programming is used in conjunction with linked lists to
1. enhance the level of encapsulation and therefore modularity
2. altogether eliminate the need for a head pointer
3. allow for multiple instantiation of the same data structure
4. a and c
5. a, b, and c
7. Deep copying of objects is needed when
1. objects with dynamic variables are used in assignment statements
2. objects with dynamic variables are passed as value parameters
3. objects with dynamic variables are passed as reference parameters
4. a and b
5. a, b, and c
8. A recursive function can cause an infinite sequence of function calls if
1. the problem size is halved at each step
2. the termination condition is missing
3. no useful incremental computation is done in each step
4. a and c
5. a, b, and c
9. In a circular queue we can disambiguate empty from full queues by
1. using a gap in the array
2. incrementing queue positions by 2 instead of 1
3. keeping a count of the number of elements
4. a and c
5. a, b, and c
10. Searching in an unsorted list can be made faster by using
1. binary search
2. a sentinel at the end of the list
3. interpolation search
4. a and c
5. a, b, and c

Indicate whether each of the following statements is TRUE or FALSE

1. a DeQue is a combination of a stack and queue __FALSE__
2. when an element is not found, Binary Search is O(N) __FALSE__
3. Bubble Sort always has the same order as Selection Sort __FALSE__
4. ADTs define how data is stored and manipulated __FALSE__
5. f(n)£ Cg(n) for n>N implies that f(n) has order g(n) __TRUE___
6. circular linked lists are more efficient for some operations __TRUE___
7. every linked list has to have at least one external pointer __TRUE___
8. recursive solutions may be easier to understand __TRUE___
9. if d is a dynamic array we can delete it with "delete d" __FALSE__
10. an explicit constructor is always required in a class __FALSE__

1. Give a precise and complete definition for the abstract data type known as a stack. [3]

A stack is a linear sequence of elements such that insertion and deletion can only be done at one end.

2. Discuss one application where the direct or indirect use of a stack is necessary to solve a problem. [2]

Consider bracket-matching for expressions - we need a stack to enforce that a bracket/brace/parenthesis is matched with the most recently encountered partner, and a stack, by its very nature, enforces this condition.

3. What are the time complexities of the following stack operations, given efficient and clean (i.e. leaving no dangling objects) class-based implementations incorporating a linear singly linked list or static array? Indicate only the order of each operation.[8]

	Array	Linked List
Initialization	O(1)	O(1)
Push	O(1)	O(1)
Pop	O(1)	O(1)
Destruction	O(1)	O(N)

4. Write an efficient definition for a destructor for a typical stack implemented as a static array within the stack class. Assume the following are part of the class declaration: [3]

class Stack
{
public:
   int Data[100];
   int TopOfStack;
   . . .
};

Stack::~Stack ()
{ 
  // nothing is necessary since the data is all static
}

5. In the context of stacks, write out definitions for the PUSH and POP functions, where the stack is implemented as a singly linked list. Use the following node and stack class declarations. A POP operation on an empty stack should return -1. [10]

class Node
{
public:
   int Data;
   Node *Next;
};

class Stack
{
   Node *Head;
public:
   void PUSH ( int Data );
   int POP ();
   . . .
};

void Stack::PUSH ( int Data )
{
   Node *n = new Node;
   n->Data = Data;
   n->Next = Head;
   Head = n;
}

int Stack::POP ()
{
   if (Head == NULL) return -1;
   int val = Head->Data;
   Node *n = Head;
   Head = Head->Next;
   delete n;
   return val;
}

6. If you need to construct a keyboard buffer to store keystrokes temporarily while the computer is busy processing, what data structure would you use and why? [4]

Queue. So that keys pressed in a certain order are eventually processed in the same order.

For the following questions, the named algorithms refer to the implementations discussed during the course:

1. Partition the following array of integers using the QuickSort algorithm (i.e. perform only one iteration - do not fully sort the list). Indicate the complete list as well as Left and Right pointers before each swap operation. Clearly indicate what the final partitions are. Assume that the first element is chosen to be the pivot. [6]

     7 4 8 2 6 4 1 9
     L             R

9 4 8 2 6 4 1 7
L             R
9 4 8 2 6 4 1 7
L           R
1 4 8 2 6 4 9 7
    L     R
1 4 4 2 6 8 9 7
        R L

The partitions are : (1 4 4 6 2) (8 9 7)

2. What is the average-case time complexity (order) of the QuickSort algorithm? [2]

O(N Log N)

3. For any arbitrary list of integers, is it at all possible to find a comparison-based sorting algorithm with a better average-case order than QuickSort? [2]

No

4. For a given list of integers, is it at all possible to find a comparison-based sorting algorithm with a faster absolute time than QuickSort? [2]

Yes

5. When is Selection Sort a better choice than QuickSort? [2]

Small lists

6. If we consider only comparisons of array elements, what is the worst-case time complexity (order) of the Duplex Selection Sort algorithm? [2]

O(N-squared)

7. For any arbitrary list of integers, is Radix Sort always a better choice than QuickSort? Why or why not? [4]

No. When there are a small number of integers with many digits, Quicksort is faster.