Answer Happy

Q12 (6%): Topological sort For the graph shown following, give a topological sort. When you have a choice for next node, choose the smallest alphabetically. Show your work for possible partial credit. Answer: Work: T M B R K E
Q13 (6%) True or False (T/F): a) b) c) d) e) f) Q14 (3%) Consider the structure represented to the right. a) (T/F) This could be a min binary heap b) (T/F) This could be a splay tree c) (T/F) This could be a (balanced) AVL tree No undirected graph can have only one node with odd degree No polynomial time algorithm can exist to find Hamiltonian paths in a graph In a balanced AVL tree, the shortest path and the longest path may differ by more than 1 There is no known linear time algorithm for finding Euler paths in a graph The SHA-256 hash function guarantees that any 2 unique strings of text will produce 2 different values when hashed If a undirected graph with weighted edges has exactly one minimum spanning tree then two edges might have the same weight 16 10 29 12 24 33 19