# 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

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

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

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(n^{2})

### View Answer

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

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

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

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(n^{2})

### View Answer

## 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

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

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

4. What is the time complexity of enqueue operation?

a) O(logn)

b) O(nlogn)

c) O(n)

d) O(1)

### View Answer

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

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

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

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

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

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

## 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

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

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

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

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

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

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

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

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

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

## 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

2. The data structure required for Breadth First Traversal on a graph is?

a) Stack

b) Array

c) Queue

d) Tree

### View Answer

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

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

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

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

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

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

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

## 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

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

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(n^{2})

b) O(n^{3})

c) O(nlogn)

d) O(2^{n})

### View Answer

^{n}) 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

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

6. What is the time complexity of the ABOVE recursive implementation?

a) O(n)

b) O(n^{2})

c) O(n^{3})

d) O(2^{n})

### View Answer

^{n}).

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

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

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

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

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(n^{2})

d) O(2^{n})

### View Answer

^{2}).

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(n^{2})

d) O(2^{n})

### View Answer

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

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