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. Binary Decision Diagram is a type of __________
a) Multigraph
b) Cyclic Graph
c) Directed Acyclic Graph
d) Directed Acyclic Word Graph

Answer: c [Reason:] An Inverter is a directed graph which is used to solve Boolean expressions, hence have no loops.

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

Answer: a [Reason:] A Binary Decision Diagram is used to represent a Boolean function.

3. In a Binary Decision Diagram, how many types of terminal exists?
a) 1
b) 2
c) 3
d) 4

Answer: b [Reason:] In a BDD, 2 terminals namely terminal-0 and terminal-1 exists.

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

Answer: c [Reason:] It is used to distinguish between the 2 values without explicitly writing.

5. How many nodes are required to create a Binary Decision Tree having 4 variables ?
a) 24
b) 24-1
c) 25
d) 25-1

Answer: d [Reason:] Binary Decision Trees are complete Binary Trees of level V + 1, here V is the number of variables.

6. Two or more And Inverter Graphs can represent same function.
a) True
b) False

Answer: a [Reason:] And Inverter Graphs are not canonical in nature.

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

Answer: d [Reason:] The given statement forms the attributes of the And Inverter Graph.

8. And Inverter Graph is a type of __________
a) Multigraph
b) Cyclic Graph
c) Directed Acyclic Graph
d) Directed Acyclic Word Graph

Answer: c [Reason:] And Inverter is a directed graph which is used to solve boolean expressions, hence have no loops.

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

Answer: a [Reason:] The conversion from the network logic is faster and more scalable than in the case of the Binary Decision Diagram.

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

Answer: d [Reason:] This is the property of the binary decision diagrams.

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

Answer: d [Reason:] This type of tree traversal will not use stack or queue.

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

Answer: a [Reason:] As there are majority of pointers with null value going wasted we use threaded binary trees.

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

Answer: a [Reason:] It contains additional 2 pointers over normal binary tree node structure.

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

Answer: a [Reason:] If preorder or postorder is used then the respective predecessor and successor info is stored.

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

Answer: a [Reason:] Those are the three representations of binary threaded trees.

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

Answer: a [Reason:] They are properties of double and single threaded binary trees respectively.

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

Answer: a [Reason:] Property of inorder threaded binary tree is left node with inorder predecessor and right node with inorder successor information are stored.

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

Answer: a [Reason:] The nodes extreme left and right are pointing to nothing which could be also used efficiently.

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

Answer: d [Reason:] Every Directed Acyclic Graph has one or more topological ordering whereas Cyclic and Undirected graphs can’t be ordered topologically.

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

Answer: a [Reason:] The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).

3. Topological sort starts from a node which has?
a) Maximum Degree
b) Minimum Degree
c) Any degree
d) None of the mentioned

Answer: b [Reason:] Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.

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

Answer: d [Reason:] Topological sort tells what task should be done before a task can be started. It also detects cycle in the graph which is why it is used in the Operating System to find the deadlock.

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

Answer: c [Reason:] The topological sort of a graph can be unique if we assume the graph as a single linked list and we can have multiple topological sort order if we consider a graph as a complete binary tree.

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

Answer: c [Reason:] We can implement topological sort by both BFS and DFS. In BFS, we use queue as data structure and in DFS, we use Linked list (if recursive) or Stack (if not recursive) as data structure.

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

Answer: a [Reason:] In pre-order traversal of trees, we process the root first and then child from left to right.

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

Answer: c [Reason:] As the definition of topological sorting suggests, it is the way to do tasks in prescribed order. So, if he does topological sorting, it will be easy for him to recognize what should be the order to visit different places.

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

Answer: a [Reason:] A hamiltonian path exists in a Directed Acyclic Graph when all pairs of consecutive vertices are in sorted order and are connected by edges. In such a case, there exists a unique topological sorting order.

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

Answer: d [Reason:] There can be at most, n*n edges in an undirected graph.

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

Answer: b [Reason:] Euler’s Identity says V – E + R = 1+ number of connected components.

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

Answer: d [Reason:] If the start and end vertices for the path are same the answer would be 0 otherwise 2.

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

Answer: b [Reason:] statements iii) and v) are correct.

5. All paths and cyclic graphs are bipartite graphs.
a) True
b) False

Answer: b [Reason:] Only paths and even cycles are bipartite graphs.

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

Answer: a [Reason:] Only the first and the last vertex would have degree 1, others would be of degree 2.

7. All trees with n vertices consists of n-1 edges.
a) True
b) False

Answer: a [Reason:] A trees is acyclic in nature.

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

Answer: d [Reason:] All three graphs are Complete graphs with 4 vertices.

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

Answer: a [Reason:] The resultant graph would be a Bipartite Graph having {A,C,E} and {D, B} as its subgroups.

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)

Answer: b [Reason:] A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.

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

Answer: d [Reason:] Suitable for architectures such as Knuth’s MIX and MMIX and this algorithm was proposed by Donald Knuth.

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);
}```

Answer: a [Reason:] This provides a single lookup index and the values are dependent on the the number of elements(N) in the array.

3. Given delta 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

Answer: b [Reason:] Trace with respect to the make_delta function, always note that the last element is always 0.

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

```public static int unisearch(int key)
{
int i = delta - 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;
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 - 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

Answer: c [Reason:] Unlike the usual binary search which a low, high and a mid variable and every time comparing the key with the mid value, the comparing index is obtained from the lookup delta table, choosing the left or right side of the array is same as with the normal binary search.

5. What is the time complexity of uniform binary search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: b [Reason:] With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.

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

Answer: b [Reason:] Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8

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)