# Multiple choice question for engineering

## Set 1

1. Binary Decision Diagram is a type of __________

a) Multigraph

b) Cyclic Graph

c) Directed Acyclic Graph

d) Directed Acyclic Word Graph

### View Answer

2. In which of the following case does a Binary Decision Diagram is used for?

a) Representation of Boolean Functions

b) String Matching

c) Searching

d) Sorting of number

### View Answer

3. In a Binary Decision Diagram, how many types of terminal exists?

a) 1

b) 2

c) 3

d) 4

### View Answer

4. In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line.

a) dashed, bold

b) bold, dashed

c) dotted, bold

d) dotted, bold

### View Answer

5. How many nodes are required to create a Binary Decision Tree having 4 variables ?

a) 2^{4}

b) 2^{4-1}

c) 2^{5}

d) 2^{5-1}

### View Answer

6. Two or more And Inverter Graphs can represent same function.

a) True

b) False

### View Answer

7. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.

a) AND, AND, average

b) AND, OR, longest

c) OR, OR, shortest

d) AND, AND, longest

### View Answer

8. And Inverter Graph is a type of __________

a) Multigraph

b) Cyclic Graph

c) Directed Acyclic Graph

d) Directed Acyclic Word Graph

### View Answer

9. The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.

a) True

b) False

### View Answer

10. Which of the following logical operation can be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?

a) Conjunction

b) Disjunction

c) Negation

d) All of the mentioned

### View Answer

## Set 2

1. What is a threaded binary tree traversal?

a) a binary tree traversal using stacks

b) a binary tree traversal using queues

c) a binary tree traversal using stacks and queues

d) a binary tree traversal without using stacks and queues

### View Answer

2. What are the disadvantages of normal binary tree traversals?

a) there are many pointers which are null and thus useless

b) there is no traversal which is efficient

c) complexity in implementing

d) improper traversals

### View Answer

3. What may be the content of a node in threaded binary tree?

a) leftchild_pointer, left_tag, data, right_tag, rightchild_pointer

b) leftchild_pointer, left_tag

c) leftchild_pointer, left_tag, right_tag, rightchild_pointer

d) leftchild_pointer, left_tag, data

### View Answer

4. What are null nodes filled with in a threaded binary tree?

a) inorder predecessor for left node and inorder successor for right node information

b) right node with inorder predecessor and left node with inorder successor information

c) they remain null

d) some other values randomly

### View Answer

5. The null left pointer pointing to predecessor and null right pointer pointing to successor. how many types of threaded tree are possible with this convention?

a) inorder, postorder, preorder traversals

b) inorder

c) postorder

d) preorder

### View Answer

6. What are double and single threaded trees?

a) when both left, right nodes are having null pointers and only right node is null pointer respectively

b) having 2 and 1 node

c) using single and double linked lists

d) using heaps and priority queues

### View Answer

7. What is wrong with below code for inorder traversal of inorder threaded binary tree:

inordertraversal(threadedtreenode root): threadedtreenode q = inorderpredecessor(root) while(q!=root): q=inorderpredecessor(q) print q.data

a) inordersuccessor instead of inorderpredecessor must be done

b) code is correct

c) it is code for post order

d) it is code for pre order

### View Answer

8. What is inefficient with the below threaded binary tree picture?

a) it has dangling pointers

b) nothing inefficient

c) incorrect threaded tree

d) space is being used more

### View Answer

## Set 3

1. Topological sort can be applied to which of the following graphs?

a) Undirected Cyclic Graphs

b) Directed Cyclic Graphs

c) Undirected Acyclic Graphs

d) Directed Acyclic Graphs

### View Answer

2. Most Efficient Time Complexity of Topological Sorting 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. Topological sort starts from a node which has?

a) Maximum Degree

b) Minimum Degree

c) Any degree

d) None of the mentioned

### View Answer

4. What can be the applications of topological sorting?

a) Finding prerequisite of a task

b) Finding Deadlock in an Operating System

c) Finding Cycle in a graph

d) All of the mentioned

### View Answer

5. Topological sort of a Directed Acyclic graph is?

a) Always unique

b) Always Not unique

c) Sometimes unique and sometimes not unique

d) None of the mentioned

### View Answer

6. Topological sort can be implemented by?

a) Using Depth First Search

b) Using Breadth First Search

c) Using Depth and Breadth First Search

d) None of the mentioned

### View Answer

7. Topological sort is equivalent to which of the traversals in trees?

a) Pre-order traversal

b) Post-order traversal

c) In-order traversal

d) Level-order traversal

### View Answer

8. A man wants to go different places in the world. He has listed them down all. But there are some places where he wants to visit before some other places. What application of graph can he use to determine that?

a) Depth First Search

b) Breadth First Search

c) Topological Sorting

d) Dijkstra’s Shortest path algorithm

### View Answer

9. When the topological sort of a graph is unique?

a) When there exists a hamiltonian path in the graph

b) In the presence of multiple nodes with indegree 0

c) In the presence of single node with indegree 0

d) None of the mentioned

### View Answer

## Set 4

1. The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is ________

a) 2^{((n*(n-1))/2)}

b) 2^{((n*(n+1))/2)}

c) 2^{((n-1)*(n-1))/2)}

d) 2^{((n*n)/2)}

### View Answer

2. Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?

a) 1

b) 2

c) 3

d) 4

### View Answer

3. Number of vertices with odd degrees in a graph having a eulerian walk is ________

a) 0

b) Can’t be predicted

c) 2

d) either 0 or 2

### View Answer

4. How many of the following statements are correct?

i) All cyclic graphs are complete graphs.

ii) All complete graphs are cyclic graphs.

iii) All paths are bipartite.

iv) All cyclic graphs are bipartite.

v) There are cyclic graphs which are complete.

a) 1

b) 2

c) 3

d) 4

### View Answer

5. All paths and cyclic graphs are bipartite graphs.

a) True

b) False

### View Answer

6. What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.

a) n-2

b) n

c) 2

d) 0

### View Answer

7. All trees with n vertices consists of n-1 edges.

a) True

b) False

### View Answer

8. Which of the following graphs are isomorphic to each other?

a) fig 1 and fig 2

b) fig 2 and fig 3

c) fig 1 and fig 3

d) fig 1, fig 2 and fig 3

### View Answer

9. In the given graph which edge should be removed to make it a Bipartite Graph?

a) A-C

b) B-E

c) C-D

d) D-E

### View Answer

10. What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?

a) O(E*E)

b) O(V*V)

c) O(E)

d) O(V)

### View Answer

## Set 5

1. When is the uniform binary search an optimization over the usual binary search?

a) A table lookup is generally faster than an addition and a shift

b) Many searches will be performed on the same array

c) Many searches will be performed on several arrays of the same length

d) All of the mentioned

### View Answer

2. Which of the following is a suitable lookup table that can be used in the uniform binary search?(N is the number of elements in the array and the delta array is global)

a)

public static void make_delta(int N) { int power = 1; int i = 0; do { int half = power; power <<= 1; delta[i] = (N + half) / power; } while (delta[i++] != 0); }

b)

public static void make_delta(int N) { int power = 0; int i = 0; do { int half = power; power <<= 1; delta[i] = (N + half) / power; } while (delta[i++] != 0); }

c)

public static void make_delta(int N) { int power = 1; int i = 0; do { int half = power; power >>= 1; delta[i] = (N + half) / power; } while (delta[i++] != 0); }

d)

public static void make_delta(int N) { int power = 1; int i = 0; do { int half = power; power <<= 1; delta[i] = (N - half) / power; } while (delta[i++] != 0); }

### View Answer

3. Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?

a) 4, 3, 1, 0

b) 5, 3, 1, 0

c) 4, 2, 1, 1

d) 5, 2, 1, 1

### View Answer

4. Choose the appropriate code snippet that performs uniform binary search.

a)

public static int unisearch(int key) { int i = delta[0] - 1; int j = 0; while (true) { if (key == arr[i]) return i; else if (delta[j] == 0) return -1; else { if (key < arr[i]) i += delta[++j]; else i -= delta[++j]; } } }

b)

public static int unisearch(int key) { int i = delta[1] - 1; int j = 0; while (true) { if (key == arr[i]) return i; else if (delta[j] == 0) return -1; else { if (key < arr[i]) i -= delta[++j]; else i += delta[++j]; } } }

c)

public static int unisearch(int key) { int i = delta[0] - 1; int j = 0; while (true) { if (key == arr[i]) return i; else if (delta[j] == 0) return -1; else { if (key < arr[i]) i -= delta[++j]; else i += delta[++j]; } } }

d) None of the mentioned

### View Answer

5. What is the time complexity of uniform binary search?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

6. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}

How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)

a) 4

b) 3

c) 5

d) 6

### View Answer

7. How can Jump Search be improved?

a) Start searching from the end

b) Begin from the kth item, where k is the step size

c) Cannot be improved

d) Step size should be other than sqrt(n)

### View Answer

8. Which of the following false about Jump Search?

a) Jump Search is better than Linear Search

b) Useful when jumping back is more costly than jumping forward

c) Jump Search is worse than Binary Search

d) None of the mentioned