Queue

A. Given the shown Circular Queue of size 8. Execute the following code on the
shown queue, then do the following:
1. Re-draw the queue after code execution to show changes.
2. Show the new positions of Front and Rear as shown.

dequeue( );
dequeue( );
dequeue( );
enqueue( 100);
enqueue( 50);

Answer:

B. Given the Array-based queue Implementation, Trace the following C++ code,
given that Queue SIZE is 5. Write down the results of each displayQueue() and
showfront() functions exist in this code:

cout<<"Inserting elements in queue\n";

enqueue(10);
displayQueue();
enqueue(30);
displayQueue();
enqueue(50);
displayQueue();
enqueue(70);
displayQueue();
enqueue(90);
displayQueue();
enqueue(100);
showfront();
cout<<"Removing elements from queue\n";
dequeue();
displayQueue();
dequeue();
displayQueue();
dequeue();
displayQueue();
dequeue();
displayQueue();
dequeue();
displayQueue();
Answer:
Inserting elements in queue
10
10 30
10 30 50
10 30 50 70
10 30 50 70 90
Queue is full
10
Removing elements from queue
30 50 70 90
50 70 90
70 90
 90
Queue is empty

Programs:
1. Suppose you have a Queue q, containing various items, another stack s,
containing various items and an empty auxiliary queue r. Write a function
that adds stack s elements to the top of the queue q with the same order.
Answer:
Stack s
7
6
5

Queue q
1 2 3

7 6 5 1 2 3

Queue<int> AddElementsFromStacktoQueue (Queue<int> q,

Stack<int> s)
{
Queue<int> r;
While ( !s.isEmpty ( ))
{
r.enqueue (s.top( ));
s.pop();
}
While ( !q.isEmpty ( ))
{
r. enqueue (q.showfront( ));
q.dequeue();
}
return r;
}

2. Write a recursive function ReverseQueue(Queue &q) to reverse queue items.

Answer:
Queue q
1 2 3
x=1
2 3
x=2
3
x=3

3
3 2
3 2 1

Void ReverseQueue (Queue &q)

{
int x;
if (!q.isEmpty ())
{
x = q. showfront();
q. dequeue();
ReverseQueue (q);
q. enqueue(x);
}

3. Write a boolean function EqualQueues ( Q1 , Q2 ) which receives two queues

Q1 and Q2 and returns True if they are identical and False otherwise.
bool EqualQueues (Queue<int> Q1 , Queue<int> Q2 )
{
While ( ! Q1. isEmpty ())
{
if (Q1. showfront() != Q2. showfront())
return false;
else
{
Q1.dequeue;
Q2.dequeue;
}
}
return true;
}

Linked List
A. In the following single linked list, write code to add a new node at the
start node.

Answer:
void LinkedList<DataType>::insert( DataType & element )
{
 Node<DataType> *newNode =new Node<DataType>;
newNode->info = element ;
newNode->next = start ;
start = newNode;
}

B. Complete the missing parts in the following Simple Link List according
to its working strategy.

Answer:

C. In the following diagram a reference is indicated by an arrow, the list

nodes have an info variable containing an integer and a next variable
 containing a reference, and list, ref1, and ref2 are references to list
nodes.

According to the previous information, give the values of the following: -

Expression Answer
ref1->info 30
ref2->next-> info 90
List->next->next-> info 45
ref2->next-> next Null
ref2->next-> next-> info Run time error

Write one statement to do the following: -

1. Make list points to the node containing 45.
List=list->next->next
2. Make ref2 point to the last node in the list.
ref2=ref2->next;
3. Make list point to an empty list
List=Null;
4. Set the info variable of the node containing 60 to 80.
ref1->next-> next->info=80;

D. In the following single linked list, write code to make the single list
empty
Answer:
LinkedList<DataType>::makeEmpty( )
 {
while ( start != NULL )
{
current = start; // starts from the beginning
start = start->next;
delete current;
}
current = NULL;
}

E. Complete the missing parts in the following Doubly Circular Link List
according to its working strategy.

Answer:

Choose the correct answer:

i. Suppose you have implemented the queue with a circular array, keeping track of front,
rear, and itemsNo (the number of items in the array). Suppose front is zero, and rear is
one less than the current capacity. What can you tell me about itemsNo?
A. itemsNo must be zero.
B. itemsNo must be equal to the current capacity.
C. could be zero or the capacity, but no other values could occur.
D. None of the above.
Answer:
B.
------------------
ii. Suppose cursor refers to a node in a linked list (using the IntNode class with instance
variables called data and link). What statement changes cursor so that it refers to the
next node?
A. cursor++;
B. cursor = link;
C. cursor += link;
D. cursor = cursor.link;
Answer:
D
------------------
iii. Suppose cursor refers to a node in a linked list (using the Node structure with the
elements data and link). What boolean expression will be true when cursor refers to the
tail node of the list?
A. (cursor == null)
B. (cursor.link == null)
C. (cursor.data == null)
D. (cursor.data == 0.0)
E. None of the above.
Answer:
B
------------------
iv. Which boolean expression indicates whether the numbers in two nodes (p and q) are
the same. Assume that neither p nor q is null.
A. p == q
B. p.data == q.data
C. p.link == q.link
 D. None of the above.
Answer:
B

Tree
A. Draw the expression tree for the following expressions, then calculate
their results using the created trees in detailed steps:
1. 17 * 3 + 2 - (10 * 9 / 3) + 3 * 4
2. ( ( ( 6 + 4 ) * 9) / ( 8 – 1) ) ^( (2 + 5 ) – 4 )
B. What is the degree and the depth for those created trees?

Answer:
1. 17 * 3 + 2 - (10 * 9 / 3) + 3 * 4
Degree: 2
Depth: 4

2. ( ( ( 6 + 4 ) * 9) / ( 8 –
1) ) ^ ( (2 + 5 ) – 4)

Degree: 2
Depth: 4

C. Using the BinaryTree implementation, Write C++ program that

draw this tree:
 typedef BinaryTree < int > intTree;
typedef intTree * intTreePtr;

// Create left subtree

intTreePtr bt1(new intTree);
bt1->insert(9);
// ** done creating left subtree

// Create right subtree (rooted at 20)

// Create 20's right subtree
intTreePtr bt2(new intTree);
bt2->insert(7);
// Create 20's left subtree
intTreePtr bt3(new intTree);
bt3->insert(15);

// Create node containing 20, and link up its right and left subtrees
intTreePtr bt4(new intTree);
bt4->insert(20);
bt4->makeLeft(bt3); //15
bt4->makeRight(bt2); //7
// ** done creating right subtree

// Create the root of the tree containing 3, and link together

intTreePtr bt5(new intTree);
bt5->insert(3);
bt5->makeLeft(bt1); //9
bt5->makeRight(bt4); //20
 D. Construct a binary search tree (BST) using the following
sequence:

25,36,30,20,40,10,22,48,28,5,38,12
1- Remove node 10 from the original tree then re-draw the tree.
2- Remove node 36 from the original tree then re-draw the tree.
Note: Show details in creation and removal

Answer:

1- Remove node 10

2- Remove node 36
 Search and sort

A. Given the following array of 7 integers { 10, 4, 6, 0, 8, 2, 1 }. Perform the

following operations of sorting.
1. Draw the detailed steps to sort this array using Selection Sort Algorithm
Answer:
Step 1:
0, 4, 6, 10, 8, 2, 1
Step 2:
0, 1, 6, 10, 8, 2, 4
Step 3:
0, 1, 2, 10, 8, 6, 4
Step 4:
0, 1, 2, 4, 8, 6, 10
Step 5:
0, 1, 2, 4, 6. 8, 10
Step 6
0, 1, 2, 4, 6. 8, 10
Step 7:
0, 1, 2, 4, 6. 8, 10
2. Write C++ code for the selection sort of an Array.
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array … initially assume it is the
//first element
        min_idx = i;
        for (j = i+1; j < n; j++)
{
         if (arr[j] < arr[min_idx]) // finds the minimum element
             min_idx = j;
  }
         // Swap the found minimum element with the first element
        if(min_idx!=i)
            swap(&arr[min_idx], &arr[i]);
    }
}
//Swap function
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

B. Given the following array of 4 integers { 5 , 3 , 4 , 2 }. Perform the following

operations of sorting.
1. Draw the detailed steps to sort this array using Bubble Sort Algorithm
Answer:

2. Write C++ code for the Bubble sort of an Array

void bubbleSort(int arr[], int n)
{
    int i, j;
    for (i = 0; i < n - 1; i++)
     {  // (n-i-1) is for ignoring comparisons of elements which have already
//been compared in earlier iterations
// Last i elements are already in place
        for (j = 0; j < n - i - 1; j++)
          {  if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}
}
}
C. Write a C++ code for Binary search program.
int BinarySearch(int arr[], int n, int key)
{
int low, high, half, found;
low = 0;
high = n;
half = int(n/2); //half of the array size
found = 0;
while ((found == 0) && (low <= high))
{ if (key == array[half] ) //item is in the middle of the array
found = 1;
if ((key > array[half])) //search in the bigger half
{ low = half + 1; //new low will start from half+1
half = int((high+low)/2); //new half will be (new low +old high)/2
}
 if ( key < array[half]) //search in the smaller half
{ high = half – 1; //new high will end at half-1
half = int((high+low)/2); //new half will be (old low +new high)/2
}
}
return found;
}