Question

1. Given the array a and the binary search function below, list all ACTIVATIONS IN FINDING t=19. (15 Points)

-9

-5

-2

0

1

3

7

11

17

19

21

25

27

31

37

41

a

  

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int search(int a[], int t, int l, int r){

if(l<=r){

int m=(l+r)/2;

if(t==a[m]) return m;

else if (t<a[m]) return search(a, t, l,m-1);

else return search(a, t, m+1, r)

}

return -1;

}

8. Use array as storage body to implement a circular template queue class. (20 Points)

Answer 1

1) Binary Search Question

1) l=0, r=14, t=19

m = (l+r)/2 = (0+14)/2 = 14/2 = 7

a[m] = a[7] = 17

t > a[m] (19 > 17)

call : search(a, t, m+1, r) i.e. search(a, t, 8, 14)

2) l=8, r=14, t=19

m = (l+r)/2 = (8+14)/2 = 22/2 = 11

a[m] = a[11] = 27

t < a[m] (19 < 27)

call : search(a, t, l, m-1) i.e. search(a, t, 8, 10)

3) l=8, r=10, t=19

m = (l+r)/2 = (8+10)/2 = 18/2 = 9

a[m] = a[9] = 21

t < a[m] (19 < 21)

call : search(a, t, l, m-1) i.e. search(a, t, 8, 8)

4) l=8, r=8, t=19

m = (l+r)/2 = (8+18)/2 = 16/2 = 8

a[m] = a[8] = 19

t == a[m] (19 == 19)

stop

return m i.e return 8

Thus total number of activation steps are 4.

2) Circular Queue Question

#include<bits/stdc++.h>

using namespace std;

#define MAX 10

// Creating a generic Queue class

template <class Type>

class Queue

{

Type Q[MAX];

int front,rear;

public:

void init()

{

front=-1;

rear=0;

}

void push(Type ch);

Type pop();

void display();

};

/*

----------------------------------------------------

push function

----------------------------------------------------

*/

template <class Type>

void Queue<Type>::push(Type item)

{

if ((front == 0 && rear == MAX-1) || (rear == (front-1)%(MAX-1)))

{

cout<<"\nQueue is Full";

return;

}

  

else if (front == -1) /* Insert First Element */

{

front = rear = 0;

Q[rear] = item;

}

  

else if (rear == MAX-1 && front != 0)

{

rear = 0;

Q[rear] = item;

}

  

else

{

rear++;

Q[rear] = item;

}

}

/*

----------------------------------------------------

delet function

----------------------------------------------------

*/

template <class Type>

Type Queue<Type>::pop()

{

if (front == -1)

{

printf("\nQueue is Empty");

return INT_MIN;

}

  

Type data = Q[front];

Q[front] = -1;

if (front == rear)

{

front = -1;

rear = -1;

}

else if (front == MAX-1)

front = 0;

else

front++;

  

return data;

}

template <class Type>

void Queue<Type>::display()

{

if(front==-1)

cout<<"\n Circular Queue is Empty";

if (rear >= front)

{

for (int i = front; i <= rear; i++)

cout<<Q[i]<<" ";

}

else

{

for (int i = 0; i <= rear; i++)

cout<<Q[i]<<" ";

for (int i = front; i < MAX; i++)

cout<<Q[i]<<" ";

  

}

cout<<"\n";

}

/*

----------------------------------------------------

The main function

----------------------------------------------------

*/

int main()

{

Queue <int> Q;

Q.init();

cout<<"Enter the number of elements to add in the Circular Queue :\n";

int n;

cin>>n;

cout<<"Add "<<n<<" elements to the Circular Queue :\n";

for(int i = 0; i <n;i++)

{

int x;

cin>>x;

Q.push(x);

}

cout<<"\nThe Circular Queue is : "<<endl;

Q.display();

cout<<"Enter the number of elements to pop from the Circular Queue :\n";

int m;

cin>>m;

cout << "Pop "<<m<<" elements from Circular Queue : "<<endl;

for (int i=0; i<m; i++)

cout<<" "<<Q.pop() << "\n";

cout<<"\nThe Circular Queue is : "<<endl;

Q.display();

cout<<"Enter the number of elements to add in the Circular Queue :\n";

int n1;

cin>>n1;

cout<<"Add "<<n1<<" elements to the Circular Queue :\n";

for(int i = 0; i <n1;i++)

{

int x;

cin>>x;

Q.push(x);

}

cout<<"\n The Circular Queue is : "<<endl;

Q.display();

return 0;
  

}

code secreenshot

output

( PLEASE VOTE FOR THIS ANSWER)

I THINK IT WILL BE USEFULL TO YOU

PLZZZZ COMMENT IF YOU HAVE ANY PROBLEM I WILL TRY TO SOLVE IT

TANK YOU