Q1 Suppose, a circular queue of capacity
(n–1) elements is implemented with
an array of n elements. Assume
that the insertion and deletion
operations are carried out using
REAR and FRONT as array index
variables respectively. Initially,
REAR = FRONT = 0. The conditions
to detect queue full and queue
empty are
[A] full:(REAR+1) mod n ==FRONT
empty:REAR ==FRONT
[B] full:(REAR+1) mod n==FRONT
empty:(FRONT+1) mod n==REAR
[C] full:REAR==FRONT
empty:(REAR+1) mod n==FRONT
[D] full:(FRONT+1) mod n==REAR
empty:REAR==FRONT
Solution
A circular queue is a queue whose last position is connected back to the first position.
ENQUEUE – It is the operation to insert elements into the queue.
DEQUEUE – It is the operation to delete elements from the queue.
After inserting an element in the last position, the next element again gets inserted into the first position.
Given, Rear = Front = 0
Here, the Rear is used to insert elements & the front is used to delete elements.
To check full condition in queue:
(Rear + 1) % n == Front
Example: Consider queue is full that means Rear = 6, front = 0, n = 7
(6+1) % 7 = 7 % 7 = 0
To check empty condition in queue:
Rear == Front
Example: Consider queue is empty that means Rear = 0, front = 0, n = 7
Rear = Front = 0
Q2 N items are stored in a sorted
doubly linked list. For a delete
operation, a pointer is provided to
the record to be deleted. For a
decrease-key operation, a pointer
is provided to the record on
which the operation is to be
performed. An algorithm performs
the following operations on
the list in this order: (N)delete,
O(logN)insert, O(logN)find and
O(N)decrease-key. What is the
time complexity of all these
operations put together?
[A] O(log2N)
[B] O(N)
[C] O(N2)
[D] O(N2logN)
Solution
In doubly linked list complexity of
Delete O(1)
Insert. O(n)
find. O(n)
Decrease. O(n)
Now number of each operation performed is given so finally total complexity
Delete=O(1)*O(n)=O(n)
Insert=O(n)*O(logn)=O(nlogn)
Find=O(n)*O(logn)=O(nlogn)
Decrease key
=O(n)*O(n)=O(n^2)
So overall time complexity is
O(n^2)
Q3 What is the maximum number of
edges in a bipartite graph having
10 vertices?
[A] 24
[B] 21
[C] 25
[D] 16
Solution
Both the set will contain 5 vertices and every vertex of first set will have an edge to every other vertex of the second set.
Total edges=5*5=25
Q4 If the array A contains the items
10, 4, 7, 23, 67, 12 and 5 in that
order, what will be the resultant
array A after third pass of
insertion sort?
[A] 67, 12, 10, 5, 4, 7, 23
[B] 4, 7, 10, 23, 67, 12, 5
[C] 4, 5, 7, 67, 10, 12, 23
[D] 10, 7, 4, 67, 23, 12, 5
Solution
Phase1. 4,10,7 ,23 ,67 ,12 ,5
Phase2. 4,7,10,23,67,12,5
Phase3. 4,7,10,23,67,12,5
In insertion sort give list is
10, 4, 7, 23, 67, 12 and 5
10 is single element already sorted when 4 in inserted compare with 10 which is greater than 4 so sorted list is
Phase1. 4,10,7 ,23 ,67 ,12 ,5
When 7 is inserted compare with 10 and then 4 .7 is less than 7 but greater than 4
Phase2. 4,7,10,23,67,12,5
When 23 is inserted which is greater than all 4,7,10
Phase3. 4,7,10,23,67,12,5
0 Comments