A Previous CS310 Mid-Term Exam.June 23, 2004Print Your Name:Read the following now.• You can use one page of double-sided, letter-size cheating sheet.• Print your name clearly on this page.• Print your initials on the top of every page.• 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.Initial: 21. (10pt) Write a (small) segment of C++ code to re-organize a binary tree as depictedbelow.1020 30abc102030rootrootEach tree node is defined as:struct Binary_node {int data;Binary_node *left, *right;};Variables root, a, b, and c in the figure are Binary node pointers. In your answer,you can update these variables and the left and right pointers of tree nodes but arenot allowed to touch the data part of tree nodes. Notice that you are NOT creatinga general-purpose function. Just write down a sequence of C++ statements to carryout the above reorganization by manipulation pointers.Initial: 32. (total 20pt) Consider the following C++ code:class X {public:int a;X () {a=1;};void f () {a += 1;};virtual void g () {a += 10;}virtual void h () = 0;};class Y : public X {public:int b;Y () {a = 10; b=20;}void h () {b += 10;}};class Z : public Y { class W : public Y {public: public:Z () {a = -1; b = -2;} W () {a=100; b=200;}void f () {a -= 10;} void g () {a += 150;}void g () {b += 100;} };};Answer the following questions.(a) (5pt) Circle abstract class(es): X, Y, Z, W(b) (5pt) Circle base class(es): X, Y, Z, W(c) (10pt) Show the outcome of the following code segment.Z z, *z_ptr=&z;z.f(); z.g(); z.h();X *x_ptr=&z;x_ptr->f(); x_ptr->g(); x_ptr->h();cout << z.a << ’ ’ << z.b << ‘‘\n’’;Initial: 43. (5pt) Consider the circular linked list shown below.1020 5 3qpnextprevdataCircle the expression(s) that is/are true.(a) p->next->data > q->prev->prev->data(b) p->next == q->next->next->next(c) p->prev->prev->data > q->next->data(d) p->next->next == q->prev->prev->prev(e) p == p->next->next->next4. (10pt) Draw the binary tree whose inorder and postorder traversals are given below.Inorder: P A R T S C Q B VPostorder: P R A C S Q V B TInitial: 55. (15pt) Starting with the AVL tree shown below, show the tree after inserting 51.507060 90551003010 403535266671357Initial: 66. (10pt) Consider the binary search tree shown below. Show the tree after removing 70.507060 90551003010 403535266671357Initial: 77. (total 30pt) Consider a heap whose array representation is shown below. Answer thefollowing questions.84 20 80 5 15 60 40 1 2 3 4 50(a) (10pt) Draw the heap as a complete binary tree.(b) (10pt) Show the heap, as a tree, after removing the largest element, 84.Initial: 8(c) (10pt) Starting from the original heap, show the heap after inserting 90.Initial: 9This page is intentionally left