A Previous CS 310 Final ExamJuly 20, 2004Print Your Name:Read the following now.• To ensure partial credit, show all your work!• Write your name on all pages of the exam.• Write down your answers clearly. I reserve the right to take off points due to poorwriting or English structures.• One blank page is provided at the end for your convenience.STOP! Do not turn to the next page until instructed to do so.Name: 21. (10pt) Show the outcome of the cout statement at the end of the following C++ codesegment.int n=10;int *p, *q;int **r;q = &n;r = &p;p = new int[5];for (int i=0; i<5; i++)p[i] = *q - i;p = p + 1;*r = *r + 1;cout << *p;Name: 32. (35pt in total) Graphs.Consider the weighted, directed graph shown below. Answer the following questions.012345638153267111214631014(a) (5pt) Argue in one sentence that the graph is not a DAG.(b) (10pt) Show the adjacency list representation of the graph. (hint: don’t forgetweights)Name: 4(c) (5pt) Argue in one sentence that the graph is not connected.(d) (15pt) Using vertex 4 as the starting point, show the contents of the pred anddist arrays of the Dijkstra’s algorithm after the completion of 4 iterations.Name: 53. (20pt) Sorting algorithms.Consider the array shown below. Answer the following questions.54, 33, 21, 25, 60, 40, 75, 83, 62, 34, 79, 90(a) (10pt) Show the contents of the array after applying the partition() routine,the first phase in the quicksort algorithm, to the array.(b) (10pt) Using the heapsort algorithm, show the contents of the array after inserting6 data items into the heap.Name: 64. (25pt in total) B-trees.Consider the B-tree shown below. Answer the following questions.5015,30 60,807 18,22 35,40 67 79 84(a) (10pt) Circle the correct statement(s).• The removal of 50 will reduce the height of the tree by 1.• It is “possible” to add 3 data items to the tree without causing any node-splitting operation.• It is “possible” to add 1 data item to the tree and cause the root to be split.• It is “possible” to remove 3 data items from the tree without reducing theheight of the tree.• There is one data item in the tree whose removal will reduce the height ofthe tree.(b) (15pt) Insert 45 to the tree and show the result.Name: 75. (20pt in total) Consider the graph declaration shown below (similar to the one we usedin Project 4).template <class T>class Digraph {public:Digraph ();void add_vertex (T new_vertex_label);void add_edge (int u, int v);void remove_edge (int u, int v);void dijkstra (int start, int* pred, int* dist);T operator[] (int i); // returns the label/name of vertex i... other digraph methods ...private:ListNode** neighbors_list;T* labels;int vertex_count;int max_size;... you can add new private members here ...};Your task is to implement a second array reference operatorint operator[] (T& label);so that the user of the Digraph class, when given the label or name of a vertex, caneasily obtain the number of the vertex. To illustrate the use of the routine, considera “Digraph<string> g,” which contains 4 vertices. Presuming that vertices 0, 1, 2, 3have names “British,” “France,” “Peru,” and “Italy,” respectively, then the expressiong[‘‘France’’] should give value 1, g[‘‘Italy’’] should result in 3, and so on. Itis mandatory that each invocation to the routine can be done in O(log N) time orless, where N is the number of vertices in the graph. Furthermore, run times of theadd vertex() routine should also be bounded by O(log N). Answer the questions onthe next page.Name: 8(a) (10pt) Discuss in four or less sentences how you are going to implement theroutine. Note that for this question C++ coding is unnecessary, not welcomeactually. Just clearly present your “idea.”(b) (10pt) List the additional, private data members you need to add to class Digraphin order to implement the routine. For each item you add, explain its use/purposein one sentence.Name: 9This page is intentionally left