Question 1 - partition.c
Question 2 - treeEq.c
Question 3 - inDegree.c
To get the all the relevant files change into an appropriate directory and type the following command
cp ~cs2521/public_html/18x1/exams/prac2/* .
Which of the following statements are true for a complete graph with 3 or more vertices?
.[A] The least hops path between 2 different vertices always has exactly one edge .[B] The shortest weighted path between 2 different vertices always has exactly one edge .[C] There can not be a hamilton tour .[D] All of the above .[E] None of the above
After running tests and determining that an unknown sorting algorithm has a time complexity of O(n) for descending ordered data, we would assume the algorithm could be
.[A] Quicksort with Median of Three Partitioning .[B] A non-comparison based sorting method .[C] unstable .[D] In-place .[E] None of the above
15 / \ 3 16 / \ \ 1 8 17 \ 9A pre-order traversal would give the output in which order:
.[A] 1 3 8 9 15 16 17 .[B] 1 9 8 3 17 16 15 .[C] 15 3 16 1 8 17 9 .[D] 15 3 1 8 9 16 17 .[E] None of the above
The following alternatives list expressions for the worst-case time complexity T(n) of various algorithms. Which alternative has an asymptotic worst-case complexity of O(n^2^)?
.[A] n^2^ .[B] 0.3n^2^ + n + 1000 .[C] 1.3n(n+1) + 10logn .[D] 2n^2^ - 10 .[E] All of the above
We can change a depth first search to a breadth first search by using
.[A] A queue instead of a stack .[B] A stack instead of a queue .[C] Using recursion instead of iteration .[D] None of the above
Assume we have the following minHeap 5 / \ / \ 10 29 / \ / \ 11 12 30 31
.(a) Give an example of a key that would result in a worst case scenario for heap insertion. Show the resulting heap and state how many comparisons were made.
You may show the resulting heaps in either a tree or array format.
.(b)
Give an example of a key that would result in a best case scenario for heap insertion. Show the resulting heap and state how many comparisons were made.
You may show the resulting heaps in either a tree or array format.
After running a djikstra's algorithm from the starting vertex with id 3, we get the following st and dist arrays.
0 1 2 3 4 5 6 st: 3 6 3 3 3 -1 4 dist: 5 7 1 0 2 inf 5
.(a)
What is the shortest path from 3 to 1? What is the cost of this path?
.(b)
Is the graph fully connected? Explain why.