Prac Exam 2

Programming Questions

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/* .

Multiple Choice (10 Marks)

Question 4

(2 marks)

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

Question 5

(2 marks)

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

Question 6

(2 marks) Consider the following Binary Search Tree:
       15
      /  \
     3    16
    / \    \
   1   8   17
        \
         9
A 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

Question 7

(2 marks)

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

Question 8

(2 marks)

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

Short Answer

Question 9

(5 marks)
 
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.

Question 10

(5 marks)

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.