Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

Multiple choice question for engineering

Set 1

1. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) All of the mentioned

View Answer

Answer: d [Reason:] Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the most efficient one being the heap.

2. Which of the following is not an application of priority queue?
a) Huffman codes
b) Interrupt handling in operating system
c) Undo operation in text editors
d) Bayesian spam filter

View Answer

Answer: c [Reason:] Undo operation is achieved using a stack.

3. Select the appropriate code that inserts elements into the list based on the given key value.
(head and trail are dummy nodes to mark the end and beginning of the list, they do not contain any priority or element)
a)

public void insert_key(int key,Object item) 
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = head;
while((key>dup.getKey()) && (dup!=trail))
{
dup = dup.getNext();
cur = cur.getNext();
}
cur.setNext(temp);
temp.setNext(dup);
}
count++;
}
}

b)

public void insert_key(int key,Object item) 
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = dup;
while((key>dup.getKey()) && (dup!=trail))
{
dup = dup.getNext();
cur = cur.getNext();
}
cur.setNext(temp);
temp.setNext(dup);
}
count++;
}
}

c)

public void insert_key(int key,Object item) 
{
if(key<0)
{
Systerm.our.println("invalid");
System.exit(0);
}
else
{
Node temp = new Node(key,item,null);
if(count == 0)
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node dup = head.getNext();
Node cur = head;
while((key>dup.getKey()) && (dup!=trail))
{
dup = dup.getNext();
cur = cur.getNext();
}
cur.setNext(dup);
temp.setNext(cur);
}
count++;
}
}

d) None of the mentioned

View Answer

Answer: a [Reason:] Have two temporary pointers ‘dup’ and ‘cur’ with ‘cur’ trailing behind ‘dup’. Traverse through the list until the given key is greater than some element with a lesser key, insert the new node ‘temp’ in that position.

4. What is the time complexity to insert a node based on key in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

View Answer

Answer: c [Reason:] In the worst case, you might have to traverse the entire list.

5. What is the functionality of the following piece of code?

public Object delete_key() 
{
if(count == 0)
{
System.out.println("Q is empty");
System.exit(0);
}
else
{
Node cur = head.getNext();
Node dup = cur.getNext();
Object e = cur.getEle();
head.setNext(dup);
count--;
return e;
}
}

a) Delete the second element in the list
b) Return but not delete the second element in the list
c) Delete the first element in the list
d) Return but not delete the first element in the list

View Answer

Answer: c [Reason:] A pointer is made to point at the first element in the list and one more to point to the second element, pointer manipulations are done such that the first element is no longer being pointed by any other pointer, its value is returned.

6. What is not a disadvantage of priority scheduling in operating systems?
a) A low priority process might have to wait indefinitely for the CPU
b) If the system crashes, the low priority systems may be lost permanently
c) Interrupt handling
d) None of the mentioned

View Answer

Answer: c [Reason:] It is in fact an advantage, interrupts should be given more priority than the task at hand so that the interrupt can be serviced.

7. What are the advantages of priority queues?
a) Easy to implement
b) Processes with different priority can be efficiently handled
c) Applications with differing requirements
d) All of the mentioned

View Answer

Answer: d [Reason:] All of these properties of priority queue help in achieving its applications like Huffman coding, priority scheduling and the like.

8. What is the time complexity to insert a node based on position in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

View Answer

Answer: c [Reason:] In the worst case, you might have to traverse the entire list.

Set 2

1. Which of the following properties is associated with a queue?
a) First In Last Out
b) First In First Out
c) Last In First Out
d) None of the mentioned

View Answer

Answer: b [Reason:] Queue follows First In First Out structure.

2. In a circular queue, how do you increment the rear end of the queue?
a) rear++
b) (rear+1) % CAPACITY
c) (rear % CAPACITY)+1
d) rear–

View Answer

Answer: b [Reason:] Ensures rear takes the values from 0 to (CAPACITY-1).

3. What is the term for inserting into a full queue known as?
a) overflow
b) underflow
c) null pointer exception
d) all of the mentioned

View Answer

Answer: a [Reason:] Just as stack, inserting into a full queue is termed overflow.

4. What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)

View Answer

Answer: d [Reason:] Enqueue operation is at the rear end, it takes O(1) time to insert a new item into the queue.

5. What does the following piece of code do?

public Object function()
{
if(isEmpty())
return -999;
else
{
Object high;
high = q[front];
return high;
}
}

a) Dequeue
b) Enqueue
c) Return the front element
d) None of the mentioned

View Answer

Answer: c [Reason:] q[front] gives the element at the front of the queue, since we are not moving the ‘front’ to the next element, it is not a dequeue operation.

6. What is the need for a circular queue?
a) effective usage of memory
b) easier computations
c) all of the mentioned
d) none of the mentioned

View Answer

Answer: a [Reason:] In a linear queue, dequeue operation causes the starting elements of the array to be empty, and there is no way you can use that space, while in a circular queue, you can effectively use that space.

7. Which of the following represents a dequeue operation? (count is the number of elements in the queue)
a)

public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
count--;
return ele;
}
}

b)

public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
front = (front+1)%CAPACITY;
q[front] = null;
count--;
return ele;
}
}

c)

public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
front = (front+1)%CAPACITY;
Object ele = q[front];
q[front] = null;
count--;
return ele;
}
}

d)

public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
return ele;
count--;
}
}

View Answer

Answer: a [Reason:] Dequeue removes the first element from the queue, and ‘front’ points to the front end of the queue. Note that even though option d is performing the dequeue operation, it is returning from the function before decrementing the count value.

8. Which of the following best describes the growth of a linear queue at runtime? (Q is the original queue, size() returns the number of elements in the queue)
a)

private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
front = 0;
rear = size()-1;
}

b)

private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
}

c)

private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i];
}
Q = newQ;
front = 0;
rear = size()-1;
}

d)

private void expand()
{
int length = size();
int[] newQ = new int[length*2];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
}

View Answer

Answer: a [Reason:] A common technique to expand the size of array at run time is simply to double the size. Create a new array of double the previous size and copy all the elements, after copying do not forget to assign front = 0 and rear = size()-1, as these are necessary to maintain the decorum of the queue operations.

9. What is the space complexity of a linear queue having n elements?
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)

View Answer

Answer: a [Reason:] Because there are n elements.

10. What is the output of the following piece of code?

public class CircularQueue
{
protected static final int CAPACITY = 100;
protected int size,front,rear;
protected Object q[];
int count = 0;
 
public CircularQueue()
{
this(CAPACITY);
}
public CircularQueue (int n)
{
size = n;
front = 0;
rear = 0;
q = new Object[size];
}
 
 
public void enqueue(Object item)
{
if(count == size)
{
System.out.println("Queue overflow");
return;
}
else
{
q[rear] = item;
rear = (rear+1)%size;
count++;
}
}
public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%size;
count--;
return ele;
}
}
public Object frontElement()
{
if(count == 0)
return -999;
else
{
Object high;
high = q[front];
return high;
}
}
public Object rearElement()
{
if(count == 0)
return -999;
else
{
Object low;
rear = (rear-1)%size;
low = q[rear];
rear = (rear+1)%size;
return low;
}
}
}
public class CircularQueueDemo
{
public static void main(String args[])
{
Object var;
CircularQueue myQ = new CircularQueue();
myQ.enqueue(10);
myQ.enqueue(3);
var = myQ.rearElement();
myQ.dequeue();
myQ.enqueue(6);
var = mQ.frontElement();
System.out.println(var+" "+var);
}
}

a) 3 3
b) 3 6
c) 6 6
d) 10 6

View Answer

Answer: a [Reason:] First enqueue 10 and 3 into the queue, followed by a dequeue(removes 10), followed by an enqueue(6), At this point, 3 is at the front end of the queue and 6 at the rear end, hence a call to frontElement() will return 3 which is displayed twice.

Set 3

1. In linked list implementation of queue, if only front pointer is maintained, which of the following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both a and c

View Answer

Answer: d [Reason:] Since front pointer is used for deletion, so worst time for the other two cases.

2. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) None of the mentioned

View Answer

Answer: c [Reason:] Since queue follows FIFO so new element inserted at last.

3. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the mentioned

View Answer

Answer: b [Reason:] Since queue follows FIFO so new element inserted at last.

4. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the mentioned

View Answer

Answer: c [Reason:] Since its the starting of queue, so both values are changed.

5. In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the queue.
a) AVAIL
b) FRONT
c) REAR
d) None of the mentioned

View Answer

Answer: a [Reason:] All the nodes are collected in AVAIL list.

6. In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) None of the mentioned

View Answer

Answer: a [Reason:] Since queue follows FIFO so new element deleted from first.

7. In linked list implementation of a queue, the important condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) None of the mentioned

View Answer

Answer: a [Reason:] Because front represents the deleted nodes.

8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value

View Answer

Answer: b [Reason:] To check whether there is space in the queue or not.

9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value

View Answer

Answer: a [Reason:] To check whether there is element in the list or not.

10. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
b) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning
c) Both a and b
d) None of the mentioned

View Answer

Answer: c [Reason:] It can be done by both the methods.

Set 4

1. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a ?
a) Queue
b) Stack
c) Tree
d) Linked list

View Answer

Answer: a [Reason:] Self Explanatory.

2. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree

View Answer

Answer: c [Reason:] Self Explanatory.

3. A queue is a ?
a) FIFO (First In First Out) list
b) LIFO (Last In First Out) list
c) Ordered array
d) Linear tree

View Answer

Answer: a [Reason:] Self Explanatory.

4. In Breadth First Search of Graph, which of the following data structure is used?
a) Stack
b) Queue
c) Linked list
d) None of the mentioned

View Answer

Answer: b [Reason:] Self Explanatory.

5. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABCD

View Answer

Answer: a [Reason:] Queue follows FIFO approach.

6. A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue

View Answer

Answer: c [Reason:] Self Explanatory.

7. A normal queue, if implemented using an array of size MAX_SIZE, gets full when
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front

View Answer

Answer: a [Reason:] Condition for size of queue.

8. Queues serve major role in
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) All of the mentioned

View Answer

Answer: c [Reason:] Rest all are implemented using other data structures.

9. Which of the following is not the type of queue?
a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue

View Answer

Answer: b [Reason:] Queue always has two ends.

Set 5

1. Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
a) Brute force
b) Dynamic programming
c) All of the mentioned
d) Recursion

View Answer

Answer: c [Reason:] All the methods mentioned above can be used to solve the rod cutting problem.

2. You are given a rod of length 5 and the prices of each length are as follows:

length     	price
1		  2
2		  5
3		  6
4		  9
5		  9

What is the maximum value that you can get after cutting the rod and selling the pieces?
a) 10
b) 11
c) 12
d) 13

View Answer

Answer: 12 [Reason:] The pieces {1,2 2} give the maximum value of 12.

3. Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?
a) O(n2)
b) O(n3)
c) O(nlogn)
d) O(2n)

View Answer

Answer: d [Reason:] The brute force implementation finds all the possible cuts. This takes O(2n) time.

4. You are given a rod of length 10 and the following prices.

length     	price
1		  2
2		  5
3		  6
4		  9
5		  9
6		  17
7 		  17	
8		  18
9		  20
10		  22

Which of these pieces give the maximum price?
a) {1,2,7}
b) {10}
c) {2,2,6}
d) {1,4,5}

View Answer

Answer: c [Reason:] The pieces {2,2,6} give the maximum value of 27.

5. Consider the following recursive implementation of the rod cutting problem:

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
max_price = max_of_two(_____________); // subtract 1 because index starts from 0
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}

Complete the above code.
a) max_price, prices[i] + rod_cut(prices,len – i – 1)
b) max_price, prices[i – 1].
c) max_price, rod_cut(prices, len – i – 1)
d) max_price, prices[i – 1] + rod_cut(prices,len – i – 1)

View Answer

Answer: a [Reason:] max_price, prices[i] + rod_cut(prices,len – i – 1) completes the above code.

6. What is the time complexity of the ABOVE recursive implementation?
a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)

View Answer

Answer: d [Reason:] The time complexity of the above recursive implementation is O(2n).

7. What is the space complexity of the ABOVE recursive implementation?
a) O(1)
b) O(logn)
c) O(nlogn)
d) O(n!)

View Answer

Answer: a [Reason:] The space complexity of the above recursive implementation is O(1) because it uses a constant space.

8. What will be the value stored in max_value when the following code is executed?

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
max_price = max_of_two(prices[i] + rod_cut(prices,len - i - 1), max_price); // subtract 1 because index starts from 0
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 3;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}

a) 5
b) 6
c) 7
d) 8

View Answer

Answer: c [Reason:] The value stored in max_value after the code is executed is equal to 7.

9. For every rod cutting problem there will be a unique set of pieces that give the maximum price.
a) True
b) False

View Answer

Answer: b [Reason:] Consider a rod of length 3. The prices are {2,3,6} for lengths {1,2,3} respectively. The pieces {1,1,1} and {3} both give the maximum value of 6.

10.Consider the following dynamic programming implementation of the rod cutting problem:

#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
tmp_price = _____________; //subtract 1 because index of prices starts from 0
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}

Which line will complete the ABOVE code?
a) prices[j-1] + max_val[tmp_idx].
b) prices[j] + max_val[tmp_idx].
c) prices[j-1] + max_val[tmp_idx – 1].
d) prices[j] + max_val[tmp_idx – 1].

View Answer

Answer: a [Reason:] prices[j-1] + max_val[tmp_idx] completes the code.

11. What is the time complexity of the ABOVE dynamic programming implementation of the rod cutting problem?
a) O(1)
b) O(n)
c) O(n2)
d) O(2n)

View Answer

Answer: c [Reason:] The time complexity of the above dynamic programming implementation of the rod cutting problem is O(n2).

12. What is the space complexity of the ABOVE dynamic programming implementation of the rod cutting problem?
a) O(1)
b) O(n)
c) O(n2)
d) O(2n)

View Answer

Answer: b [Reason:] The space complexity of the above dynamic programming implementation of the rod cutting problem is O(n) because it uses a space equal to the length of the rod.

13. What is the output of the following program?

#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
tmp_price = prices[j-1] + max_val[tmp_idx];//subtract 1 because index of prices starts from 0
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}

a) 26
b) 27
c) 28
d) 29

View Answer

Answer: b [Reason:] The program prints the maximum price that can be achieved by cutting the rod into pieces, which is equal to 27.

14. What is the value stored in max_val[5] after the following program is executed?

#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx; 
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
tmp_price = prices[j-1] + max_val[tmp_idx];//subtract 1 because index of prices starts from 0
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}

a) 12
b) 27
c) 10
d) 17

View Answer

Answer: a [Reason:] The value stored in max_val[5] after the program is executed is 12.