Multiple choice question for engineering
Set 1
1. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600
b) 350
c) 650
d) 588
Answer
Answer: b [Reason:] Self Explanatory.
2. Convert the following infix expressions into its equivalent postfix expressions
(A + B ⋀D)/(E – F)+G
a) (A B D ⋀ + E F – / G +)
b) (A B D +⋀ E F – / G +)
c) (A B D ⋀ + E F/- G +)
d) None of the mentioned
Answer
Answer: a [Reason:] Applying the postfix expression evaluation.
3. Convert the following Infix expression to Postfix form using a stack
x + y * z + (p * q + r) * s, Follow usual precedence rule and assume that the expression is legal.
a) xyz*+pq*r+s*+
b) xyz*+pq*r+s+*
c) xyz+*pq*r+s*+
d) None of the mentioned
Answer
Answer: a [Reason:] Applying the postfix expression evaluation.
4. Which of the following statement(s) about stack data structure is/are NOT correct?
a) Linked List are used for implementing Stacks
b) Top of the Stack always contain the new node
c) Stack is the FIFO data structure
d) Null link is present in the last node at the bottom of the stack
Answer
Answer: c [Reason:] Stack follows LIFO.
5. Consider the following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the number of elements present in stack are
a) 1
b) 2
c) 3
d) 4
Answer
Answer: a [Reason:] Self Explanatory.
6. Which of the following is not an inherent application of stack?
a) Reversing a string
b) Evaluation of postfix expression
c) Implementation of recursion
d) Job scheduling
Answer
Answer: d [Reason:] Job Scheduling is not performed using stacks.
7. The type of expression in which operator succeeds its operands is?
a) Infix Expression
b) Prefix Expression
c) Postfix Expression
d) None of the mentioned
Answer
Answer: c [Reason:] Self Explanatory.
8. Assume that the operators +,-, X are left associative and ^ is right associative.
The order of precedence (from highest to lowest) is ^, X, +, -. The postfix expression for the infix expression a + b X c – d ^ e ^ f is
a) abc X+ def ^^ –
b) abc X+ de^f^ –
c) ab+c Xd – e ^f^
d) -+aXbc^ ^def
Answer
Answer: a [Reason:] Applying the postfix expression evaluation.
9. If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, what is the order of removal?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Answer
Answer: b [Reason:] Stack follows LIFO(Last In First Out).
Set 2
1. Which of the following statements for a simple graph is correct?
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) None of the mentioned
Answer
Answer: a [Reason:] In a walk if the vertices are distinct it is called a path, whereas if the edges are distinct it is called a trail.
2. In the given graph identify the cut vertices.
a) B and E
b) C and D
c) A and E
d) C and B
Answer
Answer: d [Reason:] After removing either B or C, the graph becomes disconnected.
3. For the given graph(G), which of the following statements is true?
a) G is a complete graph
b) G is not a connected graph
c) The vertex connectivity of the graph is 2
d) The edge connectivity of the graph is 1
Answer
Answer: c [Reason:] : After removing vertices B and C, the graph becomes disconnected.
4. What is the number of edges present in a complete graph having n vertices?
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient
Answer
Answer: b [Reason:] Number of ways in which every vertex can be connected to each other is nC2.
5. The given Graph is regular.
a) True
b) False
Answer
Answer: a [Reason:] In a regular graph, degrees of all the vertices are equal. In the given graph the degree of every vertex is 3.
6. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
a) True
b) False
Answer
Answer: b [Reason:] The sum of the degrees of the vertices is equal to twice the number of edges.
7. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
a) 15
b) 3
c) 1
d) 11
Answer
Answer: b [Reason:] By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.
8. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G’ (Complement of G) is ___________
a) (n*n-n-2*m)/2
b) (n*n+n+2*m)/2
c) (n*n-n-2*m)/2
d) (n*n-n+2*m)/2
Answer
Answer: a [Reason:] The union of G and G’ would be a complete graph so, the number of edges in G’= number of edges in the complete form of G(nC2)-edges in G(m).
9. Which of the following properties does a simple graph not hold?
a) Must be connected
b) Must be unweighted
c) Must have no loops or multiple edges
d) All of the mentioned
Answer
Answer: a [Reason:] A simple graph maybe connected or disconnected.
10. What is the maximum number of edges in a bipartite graph having 10 vertices ?
a) 24
b) 21
c) 25
d) 16
Answer
Answer: c [Reason:] Let one set have n vertices another set would contain 10-n vertices.
Total number of edges would be n*(10-n), differentiating with respect to n, would yield the answer.
11. Which of the following is true?
a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) None of the mentioned
Answer
Answer: b [Reason:] A graph must contain at least one vertex.
12. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
a) v=e
b) v = e+1
c) v + 1 = e
d) None of the mentioned
Answer
Answer: b [Reason:] for any connected graph with no cycles the equation holds true.
13. For which of the following combinations of the degrees of vertices would the connected graph be eulerian?
a) 1,2,3
b) 2,3,4
c) 2,4,5
d) 1,3,5
Answer
Answer: a [Reason:] A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.
14. A graph with all vertices having equal degree is known as a __________
a) Multi Graph
b) Regular Graph
c) Simple Graph
d) Complete Graph
Answer
Answer: b [Reason:] The given statement is the definition of regular graphs.
15. Which of the following ways can be used to represent a graph?
a) Adjacency List and Adjacency Matrix
b) Incidence Matrix
c) Adjacency List, Adjacency Matrix as well as Incidence Matrix
d) None of the mentioned
Answer
Answer: c [Reason:] The 3 listed methods can be used, the choice depends on the ease of use.
Set 3
1. What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
Answer
Answer: b [Reason:] A hash table is used to implement associative arrays which has a key-value pair, so the has table maps keys to values.
2. If several elements are competing for the same bucket in the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) None of the mentioned
Answer
Answer: c [Reason:] By definition
3. What is direct addressing?
a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) None of the mentioned
Answer
Answer: a [Reason:] Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
4. What is the search complexity in direct addressing?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
Answer
Answer: d [Reason:] Since every key has a unique array position, searching takes a constant time
5. What is a hash function?
a) A function has allocated memory to keys
b) A function that computes the location of the key in the array
c) A function that creates an array
d) None of the mentioned
Answer
Answer: b [Reason:] In a hash table, there are fewer array positions than the keys, so the position of the key in the array has to be computed, this is done using the hash function.
6. What can be the techniques to avoid collision?
a) Make the hash function appear random
b) Use the chaining method
c) Use uniform hashing
d) All of the mentioned
Answer
Answer: d [Reason:] Making the hash function random is not really a good choice, although it is considered one of the techniques to avoid collisions along with chaining and simple uniform hashing.
7. What is the load factor?
a) Average array size
b) Average key size
c) Average chain length
d) None of the mentioned
Answer
Answer: c [Reason:] In simple chaining, load factor is the average number of elements stored in a chain, and is given by the ratio of number of elements stored to the number of slots in the array.
8. What is simple uniform hashing?
a) Every element has equal probability of hashing into any of the slots
b) A weighted probabilistic method is used to hash elements into the slots
c) All of the mentioned
d) None of the mentioned
Answer
Answer: a [Reason:] In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.
9. In simple uniform hashing, what is the search complexity?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
Answer
Answer: d [Reason:] There are two cases, once when the search is successful and when it is unsuccessful, but in both the cases, the complexity is O(1+alpha) where 1 is to compute the hash function and alpha is the load factor.
10. In simple chaining, what data structure is appropriate?
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Binary trees
Answer
Answer: b [Reason:] Deletion becomes easier with doubly linked list, hence it is appropriate.
Set 4
1. In a max-heap, element with the greatest key is always in the which node?
a) Leaf node
b) First node of left sub tree
c) root node
d) First node of right sub tree
Answer
Answer: c [Reason:] This is one of the property of max-heap that root node must have key greater than its children.
2. Heap exhibits the property of a binary tree?
a) True
b) False
Answer
Answer: a [Reason:] Yes, Because the leaf nodes are present at height h or h-1 ,which is a property of complete binary tree.
3. What is the complexity of adding an element to the heap.
a) O(log n)
b) O(h)
c) a and b
d) None of the mentioned
Answer
Answer: c [Reason:] The total possible operation in re locating the new location to a new element will be equal to height of the heap.
4. The worst case complexity of deleting any arbitrary node value element from heap is
a) O(logn)
b) O(n)
c) O(nlogn)
d) O(n2)
Answer
Answer: a [Reason:] The total possible operation in deleting the existing node and re locating new position to all its connected nodes will be equal to height of the heap.
5. Heap can be used as…
a) Priority queue
b) Stack
c) A decreasing order array
d) None of the mentioned
Answer
Answer: a [Reason:] The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.
6.
If we implement heap as min-heap , deleting root node (value 1)from the heap. What would be the value of root node after second iteration if leaf node (value 100) is chosen to replace the root at start.
a) 2
b) 100
c) 17
d) 3
Answer
Answer: a [Reason:] As the root is deleted and node with value 100 is used as replaced one.There is a violation of property that root node must have value less than its children.So there will be shuffling of node with value 100 with node of value 2.And thus 2 becomes root. And it will remain to be at root after all the possible operations .So the value at root will be 2.
7.
If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right subtree . What value will be at leaf nodes of the right subtree of the heap.
a) 15 and 1
b) 25 and 1
c) 3 and 1
d) 2 and 3
Answer
Answer: a [Reason:] As 15 is less than 25 so there would be no violation and the node will remain at that position.So leaf nodes with value 15 and 1 will be at the position in right sub tree.
8. An array consist of n elements.We want to create a heap using the elements.The time complexity of building a heap will be in order of
a) O(n*n*logn)
b) O(n*logn)
c) O(n*n)
d) O(n *logn *logn)
Answer
Answer: b [Reason:] The total time taken will be N times the complexity of adding a single element to the heap .And adding a single element takes logN time,so That is equal to N*logN.
Set 5
1. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?
a) True
b) False
Answer
Answer: b [Reason:] For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.
2. The column sum in an incidence matrix for a simple graph is __________
a) depends on number of edges
b) always greater than 2
c) equal to 2
d) equal to the number of edges
Answer
Answer: c [Reason:] For every edge only the vertices with which it is connected would have the value 1 in the matrix, as an edge connects two vertices sum will always be 2.
3. What are the dimensions of an incidence matrix?
a) Number of edges*number of edges
b) Number of edges*number of vertices
c) Number of vertices*number of vertices
d) None of the mentioned statements
Answer
Answer: b [Reason:] Columns may represent edges and vertices may be represented by the rows.
4. The column sum in an incidence matrix for a directed graph having no self loop is __________
a) 0
b) 1
c) 2
d) equal to the number of edges
Answer
Answer: a [Reason:] Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.
5. Time complexity to check if an edge exists between two vertices would be ___________
a) O(V*V)
b) O(V+E)
c) O(1)
d) O(E)
Answer
Answer: d [Reason:] We have to check for all edges, in the worst case the vertices will have no common edge.
6. The graphs G1 and G2 with their incidences matrices given are Isomorphic.
e1 e2 e3 e4 e5 e6 v1 1 0 0 0 0 0 v2 1 1 0 0 0 1 v3 0 1 1 0 1 0 v4 0 0 1 1 0 0 v5 0 0 0 1 1 1 e1 e2 e3 e4 e5 e6 v1 0 0 1 0 0 0 v2 1 0 1 0 1 0 v3 1 1 0 1 0 0 v4 0 1 0 0 0 1 v5 0 0 0 1 1 1
a) True
b) False
Answer
Answer: a [Reason:] Two graphs are isomorphic if their Incidence Matrices differ only by permutation of columns and rows.
7. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?
a) n-1
b) values greater than n are possible
c) values less than n-1 are possible
d) Insufficient Information is given
Answer
Answer: a [Reason:] Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.
8. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.
a) 1
b) 2
c) 3
d) 4
Answer
Answer: c [Reason:] Path ADE, BDE and BCE are possible.
9. A Graph Structured Stack is a _____________
a) Undirected Graph
b) Directed Graph
c) Directed Acyclic Graph
d) Regular Graph
Answer
Answer: c [Reason:] A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.
10. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?
a) Source – 1, 8 Sink – 7,4
b) Source – 1 Sink – 8,4
c) Source – 1, 8 Sink – 4
d) None of the Mentioned
Answer
Answer: c [Reason:] Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.
11. Graph Structured Stack finds its application in _____________
a) Bogo Sort
b) Tomita’s Algorithm
c) Todd–Coxeter algorithm
d) All of the mentioned
Answer
Answer: b [Reason:] Tomita’s is a parsing algorithm which uses Graph Structured Stack in its implementation.
12. If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M.
a) True
b) False
Answer
Answer: b [Reason:] The answer would depend on the intermediate vertices also.
