Erik's answers to the 331 Review questions
9.
| Algorithm |
Best Case | Average | Worst Case | Extra
space |
| Insertion Sort | O( n lg n ) |
(best+worst)/2 | O( n2 ) | None |
| Bubble Sort | O( n ) | (best+worst)/2 | O(
n2 ) | None |
| Selection Sort | O( n2 ) | O( n2
) | O( n2 ) | none |
| Merge Sort | O( n lg n ) | O( n lg n ) | O( n lg
n ) | O( n ) |
| Quick Sort | O( n lg n ) | (best+worst)/2 |
O(n2 ) | None |
| Heap Sort |
10.
How does merge sort work?
See sorting notes for notes and an
example.
11.
How does quick sort work?
See sorting notes for notes and an
example.
12.
How does heap sort work?
See sorting notes for notes and an
example.
13.
How many words of memory are needed to store an array
A[1..n][1..5][0..n2], where each cell is 2 words?
The [1..5] requires 5 elements (to index 1 2 3 4 5). Same goes for
[1..n]. The [0..n2] requires 1 + n2. So in total we
have 2 words * 5 * n * (1+n2).
14.
How much time does it take to find the second smallest item in a sorted
array?
Since the array is sorted, we can just access it as A[1] in O( 1 ) time.
15.
What is a sparce matrix?
Matrices that have many zero-elements, and very few acutal numbers, are
inefficient to store. The solution is a sparce matrix, where we store each
number (other than the zero's) along with their position in the matrix,
and put them into a list where each element knows where its 'neighbors'
(ie elements above and below) are:
Each node has the following form: the lower-left and -right elements
point the the next element in that column and row, respectively
Optionally, we can have the last element in each row/column point to the
first element in the next column (blue lines).
16.
What data structure exhibits FIFO behaviour?
FIFO = first in first out, which is how a queue works.
17.
What data structure exhibits LIFO behaviour?
LIFO = last in first out, which is how a stack works.
18.
Given the infix expression (A+B/C) - (E*F+G), what is the corresponding
postfix expression?
First thing to do is put the expression into a tree. Then we can just do
a travesal and read off the answer:
Recall that postfix is where the operator comes after the variables,
infix is where its between them, and prefix is where the operator comes
first
| Type | expression | converted |
traversal order |
| postfix | A + B | AB+ | L R node |
| infix | C / D | C / D | L node R |
| prefix | E * F | *EF | node L R |
For this question we want postfix, so we traverse the tree in the order L
R node:
ABC/+EF*G+-
19.
Given the infix expression (A+B/C) - (E*F+G), what is the corresponding
prefix expression?
For this question we want prefix, so we go in the order node L R:
-+A/BC+*EFG
20.
Put elements 1,2,3,4,5 onto a stack and take them off one by one. What
order are they printed out in?
5 4 3 2 1
21.
Inserting a node into a list:
Insert( Node n ) {
if( head == NULL ) head = n;
else {
Node tmp = head;
while( tmp.next != NULL) tmp = tmp.next;
tmp.next = n;
}
22.
Inserting a node into a doubly linked list:
Insert( DNode n ) {
if( head == NULL ) head = n;
else {
Node tmp = head;
while( tmp.next != NULL) tmp = tmp.next;
tmp.next = n;
n.prev = tmp;
}
23.
Delete a node from a linked list
Delete( Node n ) {
if( head == n ) head = head.next;
else {
Node tmp = head;
while( tmp.next != n ) tmp = tmp.next;
tmp.next = n.next;
}
}
24.
Delete a node from a doubly linked list
Delete( DNode n ) {
// we assume n is in this list
Node pr = n.prev;
Node nx = n.next;
if( head == n ) head = n.next;
if( pr != null ) pr.next = nx;
if( nx != null ) nx.prev = pr;
}
25.
Search for an element in a linked list
Search( int key ) {
Node tmp = head;
while( tmp ) {
if( tmp.value == key ) return 1;
tmp = tmp.next;
}
return 0;
}
26.
Given the graph below, perform a depth-first spanning tree starting at
vertex 1.
What does the depth-first spanning tree look like?
Your answers may varry, but should be like either of these:
- 1, 0, 2, 5, 3, 4
- 1, 3, 5, 2, 0, 4
The depth first spanning tree follows the nodes on the outside first: 1,
0, 2, 4, 3 with only one connection from 4 to one of its neighbors.
page 1 | page 3