# Multiple choice question for engineering

## Set 1

1. What is the advantage of recursive approach than an iterative approach?

a) Consumes less memory

b) Less code and easy to implement

c) Consumes more memory

d) All of the mentioned

### View Answer

2. Choose the appropriate code that does binary search using recursion.

a)

public static int recursive(int arr[], int low, int high, int key) { int mid = low + (high - low)/2; if(arr[mid] == key) { return mid; } else if(arr[mid] < key) { return recursive(arr,mid+1,high,key); } else { return recursive(arr,low,mid-1,key); } }

b)

public static int recursive(int arr[], int low, int high, int key) { int mid = low + (high + low)/2; if(arr[mid] == key) { return mid; } else if(arr[mid] < key) { return recursive(arr,mid-1,high,key); } else { return recursive(arr,low,mid+1,key); } }

c)

public static int recursive(int arr[], int low, int high, int key) { int mid = low + (high - low)/2; if(arr[mid] == key) { return mid; } else if(arr[mid] < key) { return recursive(arr,mid,high,key); } else { return recursive(arr,low,mid-1,key); } }

d) None of the mentioned

### View Answer

3. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?

a) 5

b) 2

c) 3

d) 4

### View Answer

4. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?

a) 90 and 99

b) 90 and 94

c) 89 and 99

d) 89 and 94

### View Answer

5. What is the worst case complexity of binary search using recursion?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

6. What is the average case time complexity of binary search using recursion?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

7. What are the applications of binary search?

a) To find the lower/upper bound in an ordered sequence

b) Union of intervals

c) Debugging

d) All of the mentioned

### View Answer

8. Choose among the following code for an iterative binary search.

a)

public static int iterative(int arr[], int key) { int low = 0; int mid = 0; int high = arr.length-1; while(low <= high) { mid = low + (high + low)/2; if(arr[mid] == key) { return mid; } else if(arr[mid] < key) { low = mid - 1; } else { high = mid + 1; } } return -1; }

b)

public static int iterative(int arr[], int key) { int low = 0; int mid = 0; int high = arr.length-1; while(low <= high) { mid = low + (high - low)/2; if(arr[mid] == key) { return mid; } else if(arr[mid] < key) { low = mid + 1; } else { high = mid - 1; } } return -1; }

c)

public static int iterative(int arr[], int key) { int low = 0; int mid = 0; int high = arr.length-1; while(low <= high) { mid = low + (high + low)/2; if(arr[mid] == key) { return mid; } else if(arr[mid] < key) { low = mid + 1; } else { high = mid - 1; } } return -1; }

d) None of the mentioned

### View Answer

9. Binary Search can be categorized into which of the following?

a) Brute Force technique

b) Divide and conquer

c) Greedy algorithm

d) Dynamic programming

### View Answer

10. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?

a) 1

b) 3

c) 4

d) 2

### View Answer

11. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations?

a) 90 and 99

b) 90 and 100

c) 89 and 94

d) 94 and 99

### View Answer

12. What is the time complexity of binary search with iteration?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

## Set 2

1. The number of edges from the root to the node is called __________ of the tree.

a) Height

b) Depth

c) Length

d) None of the mentioned

### View Answer

2. The number of edges from the node to the deepest leaf is called _________ of the tree.

a) Height

b) Depth

c) Length

d) None of the mentioned

### View Answer

3. What is a full binary tree?

a) Each node has exactly zero or two children

b) Each node has exactly two children

c) All the leaves are at the same level

d) Each node has exactly one or two children

### View Answer

4. What is a complete binary tree?

a) Each node has exactly zero or two children

b) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left

c) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right

d) None of the mentioned

### View Answer

5. What is the time complexity for finding the height of the binary tree?

a) h = O(loglogn)

b) h = O(nlogn)

c) h = O(n)

d) h = O(log n)

### View Answer

6. Which of the following is not an advantage of trees?

a) Hierarchical structure

b) Faster search

c) Router algorithms

d) Undo/Redo operations in a notepad

### View Answer

7. In a full binary tree if number of internal nodes is I, then number of leaves L are?

a) L = 2I

b) L = I + 1

c) L = I – 1

d) L = 2I – 1

### View Answer

8. In a full binary tree if number of internal nodes is I, then number of nodes N are?

a) N = 2I

b) N = I + 1

c) N = I – 1

d) N = 2I + 1

### View Answer

9. In a full binary tree if there are L leaves, then total number of nodes N are?

a) N = 2L

b) N = L + 1

c) N = L – 1

d) N = 2L – 1

### View Answer

10. Which of the following is correct with respect to binary trees?

a) Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k

b) Let T be a binary tree with λ levels. Then T has no more than 2^{λ – 1} nodes

c) Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))

d) All of the mentioned

### View Answer

## Set 3

1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?

a) Pre-order Traversal

b) Post-order Traversal

c) Level-order Traversal

d) In-order Traversal

### View Answer

2. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)

a) O(V + E)

b) O(V)

c) O(E)

d) None of the mentioned

### View Answer

3. The Data structure used in standard implementation of Breadth First Search is?

a) Stack

b) Queue

c) Linked List

d) None of the mentioned

### View Answer

4. The Breadth First Search traversal of a graph will result into?

a) Linked List

b) Tree

c) Graph with back edges

d) All of the mentioned

### View Answer

5. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?

a) Depth First Search

b) Breadth First Search

c) Trim’s algorithm

d) None of the mentioned

### View Answer

6. What can be the applications of Breadth First Search?

a) Finding shortest path between two nodes

b) Finding bipartiteness of a graph

c) GPS navigation system

d) All of the mentioned

### View Answer

7. When the Breadth First Search of a graph is unique?

a) When the graph is a Binary Tree

b) When the graph is a Linked List

c) When the graph is a n-ary Tree

d) None of the mentioned

### View Answer

8. Regarding implementation of Breadth First Search using queues, what is the maximum distance between two nodes present in the queue? (considering each edge length 1)

a) Can be anything

b) 0

c) At most 1

d) Insufficient Information

### View Answer

9. In BFS, how many times a node is visited?

a) Once

b) Twice

c) equivalent to number of indegree of the node

d) None of the mentioned

### View Answer

## Set 4

1. What is an external sorting algorithm?

a) Algorithm that uses tape or disk during the sort

b) Algorithm that uses main memory during the sort

c) Algorithm that involves swapping

d) Algorithm that are considered ‘in place’

### View Answer

2. What is an internal sorting algorithm?

a) Algorithm that uses tape or disk during the sort

b) Algorithm that uses main memory during the sort

c) Algorithm that involves swapping

d) Algorithm that are considered ‘in place’

### View Answer

3. What is the worst case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

4. Select the appropriate code that performs bubble sort.

a)

for(int j=arr.length-1; j>=0; j--) { for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

b)

for(int j=arr.length-1; j>=0; j--) { for(int k=0; k<j; k++) { if(arr[k] < arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

c)

for(int j=arr.length; j>=0; j--) { for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

d) None of the mentioned

### View Answer

5. What is the average case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

6. What is the advantage of bubble sort over other sorting techniques?

a) It is faster

b) Consumes less memory

c) Detects whether the input is already sorted

d) All of the mentioned

### View Answer

7. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?

a) 4

b) 2

c) 1

d) 0

### View Answer

8. How can you improve the best case efficiency in bubble sort? (The input is already sorted)

a)

boolean swapped = false; for(int j=arr.length-1; j>=0 && swapped; j--) { swapped = true; for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; swapped = false; } } }

b)

boolean swapped = true; for(int j=arr.length-1; j>=0 && swapped; j--) { swapped = false; for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

c)

boolean swapped = true; for(int j=arr.length-1; j>=0 && swapped; j--) { swapped = false; for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; swapped = true; } } }

d)

boolean swapped = true; for(int j=arr.length-1; j>=0 && swapped; j--) { for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; swapped = true; } } }

### View Answer

9. What is the best case efficiency of bubble sort in the improvised version?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

10. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?

a) 4

b) 2

c) 1

d) 0

### View Answer

## Set 5

1. What differentiates a circular linked list from a normal linked list?

a) You cannot have the ‘next’ pointer point to null in a circular linked list

b) It is faster to traverse the circular linked list

c) You may or may not have the ‘next’ pointer point to null in a circular linked list

d) All of the mentioned

### View Answer

2. How do you count the number of elements in the circular linked list?

a)

public int length(Node head) { int length = 0; if( head == null) return 0; Node temp = head.getNext(); while(temp != head) { temp = temp.getNext(); length++; } return length; }

b)

public int length(Node head) { int length = 0; if( head == null) return 0; Node temp = head.getNext(); while(temp != null) { temp = temp.getNext(); length++; } return length; }

c)

public int length(Node head) { int length = 0; if( head == null) return 0; Node temp = head.getNext(); while(temp != head && temp != null) { temp = head.getNext(); length++; } return length; }

d) None of the mentioned

### View Answer

3. What is the functionality of the following piece of code? Select the most appropriate

public void function(int data) { int flag = 0; if( head != null) { Node temp = head.getNext(); while((temp != head) && (!(temp.getItem() == data))) { temp = temp.getNext(); flag = 1; break; } } if(flag) System.out.println("success"); else System.out.println("fail"); }

a) Print success if a particular element is not found

b) Print fail if a particular element is not found

c) Print success if a particular element is equal to 1

d) Print fail if the list is empty

### View Answer

4. What is the time complexity of searching for an element in a circular linked list?

a) O(n)

b) O(nlogn)

c) O(1)

d) None of the mentioned

### View Answer

5. Which of the following application makes use of a circular linked list?

a) Undo operation in a text editor

b) Recursive function calls

c) Allocating CPU to resources

d) All of the mentioned

### View Answer

6. Choose the code snippet which inserts a node to the head of the list?

a)

public void insertHead(int data) { Node temp = new Node(data); Node cur = head; while(cur.getNext() != head) cur = cur.getNext() if(head == null) { head = temp; head.setNext(head); } else { temp.setNext(head); head = temp; cur.setNext(temp); } size++; }

b)

public void insertHead(int data) { Node temp = new Node(data); while(cur != head) cur = cur.getNext() if(head == null) { head = temp; head.setNext(head); } else { temp.setNext(head.getNext()); cur.setNext(temp); } size++; }

c)

public void insertHead(int data) { Node temp = new Node(data); if(head == null) { head = temp; head.setNext(head); } else { temp.setNext(head.getNext()); head = temp; } size++; }

d)

public void insertHead(int data) { Node temp = new Node(data); if(head == null) { head = temp; head.setNext(head.getNext()); } else { temp.setNext(head.getNext()); head = temp; } size++; }

### View Answer

7. What is the functionality of the following code? Choose the most appropriate answer.

public int function() { if(head == null) return Integer.MIN_VALUE; int var; Node temp = head; while(temp.getNext() != head) temp = temp.getNext(); if(temp == head) { var = head.getItem(); head = null; return var; } temp.setNext(head.getNext()); var = head.getItem(); head = head.getNext(); return var; }

a) Return data from the end of the list

b) Returns the data and deletes the node at the end of the list

c) Returns the data from the beginning of the list

d) Returns the data and deletes the node from the beginning of the list

### View Answer

8. What is the functionality of the following code? Choose the most appropriate answer.

public int function() { if(head == null) return Integer.MIN_VALUE; int var; Node temp = head; Node cur; while(temp.getNext() != head) { cur = temp; temp = temp.getNext(); } if(temp == head) { var = head.getItem(); head = null; return var; } var = temp.getItem(); cur.setNext(head); return var; }

a) Return data from the end of the list

b) Returns the data and deletes the node at the end of the list

c) Returns the data from the beginning of the list

d) Returns the data and deletes the node from the beginning of the list

### View Answer

9. Which of the following is false about a circular linked list?

a) Every node has a successor

b) Time complexity of inserting a new node at the head of the list is O(1)

c) Time complexity for deleting the last node is O(n)

d) None of the mentioned

### View Answer

10. Consider a small circular linked list. How to detect the presence of cycles in this list effectively?

a) Keep one node as head and traverse another temp node till the end to check if its ‘next points to head

b) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time

c) Cannot determine, you have to pre-define if the list contains cycles

d) None of the mentioned