CSS 343 Exam Name
CSS 343 Exam Be as clear as possible. You don't have to comment code, but use meaningful names and proper indentation. Show all work. Name
1. Assume a BinTree class has a member function called mystery and a tree has been built as shown.
What's the output of main? Show the execution tree. (10 pts)
int BinTree::mystery() const { main: BinTree T; ...
return mysteryHelper(root); cout right); SOME TREE HERE
return 1 + mysteryHelper(current->left)
+ mysteryHelper(current->right);
}
2. Give the worst-case complexity of the following operations. You do not need to show work. (10 pts)
(a) Retrieve in an AVL tree of n items.
(b) FindMin in a general tree (not a binary search tree) of n items.
(c) FindMin (not DeleteMin) in a heap of n items.
(d) Huffman encoding of n characters.
(e) Deleting an edge in a graph of N nodes and E edges stored in an adjacency list.
3. Demonstrate the heap sort (done efficiently) on the values: 10 5 7 11 6 3 2 13 15 1 4.
Show only the first three passes of the algorithm (three values are sorted). There is no code writing.
Redraw your heaps when needed for clarity. (15 pts)
4. Given the following AVL tree structure (letters represent appropriate values). Suppose a value was added as
shown (in the P position). Show the balanced tree after the insertion. Show each step. (10 pts)
A
/ \ Which node is unbalanced?
B C
/ \ / \
D E F G
\ / \ / \
H I J K L
/ / \
M N O
/
P
5. Consider the following graph. Assume the nodes are stored in their numerical order. (25 pts)
(a). What is the breadth-first ordering? (No need to show work.)
SOME GRAPH HERE
(b). What is the depth-first ordering? (No need to show work.)
Let N be the number of graph nodes, E the number of edges. Suppose a graph is stored in an adjacency matrix.
(c). What is the complexity of Dijkstra’s shortest path algorithm for one source node?
(d). What is the complexity of depth-first ordering?
(e). Use Dijkstra’s algorithm to find the shortest path from node 1 to all other nodes in the graph.
Show v, T[source][i].dist and T[source][i].path at each state in the algorithm.
6. Implement function(s) for a BSTree class that determine whether or not the tree is complete (all levels
filled completely). Assume our usual Node, with member data: NodeData* data, Node* left, right.
Any function you use, you must write. For example: (20 pts)
T1: A Sample main:
/ \ BSTree T1;
B C BSTree T2;
/ \ / \ bool complete;
D E F G ...
/ \ / \ / \ / \ complete = T1.isComplete(); // returns true
H I J K L M N P complete = T2.isComplete(); // returns false
T2: A
/ \
B C
/ \ / \
D E F G
/ \ /
H I J
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- science enhanced s s biology
- programming on the ti 92 plus calculator as a teaching
- programming microsoft windows with visual basic
- t1 onc office of the national coordinator for health
- niagara div 23 09 guide specification honeywell
- c intermediate and advanced features
- computer science pacific university
- rfid children s game
- css 343 exam name
- august 1 2002