# 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

5. The given Graph is regular.

a) True

b) False

### View Answer

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

### View Answer

7. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.

a) 15

b) 3

c) 1

d) 11

### View Answer

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

### View Answer

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

### View Answer

10. What is the maximum number of edges in a bipartite graph having 10 vertices ?

a) 24

b) 21

c) 25

d) 16

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

4. What is the search complexity in direct addressing?

a) O(n)

b) O(logn)

c) O(nlogn)

d) O(1)

### View Answer

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

### View Answer

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

### View Answer

7. What is the load factor?

a) Average array size

b) Average key size

c) Average chain length

d) None of the mentioned

### View Answer

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

### View Answer

9. In simple uniform hashing, what is the search complexity?

a) O(n)

b) O(logn)

c) O(nlogn)

d) O(1)

### View Answer

10. In simple chaining, what data structure is appropriate?

a) Singly linked list

b) Doubly linked list

c) Circular linked list

d) Binary trees

### View Answer

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

### View Answer

2. Heap exhibits the property of a binary tree?

a) True

b) False

### View Answer

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

### View Answer

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

### View Answer

5. Heap can be used as…

a) Priority queue

b) Stack

c) A decreasing order array

d) None of the mentioned

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

## Set 5

1. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?

a) True

b) False

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

9. A Graph Structured Stack is a _____________

a) Undirected Graph

b) Directed Graph

c) Directed Acyclic Graph

d) Regular Graph

### View Answer

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

### View Answer

11. Graph Structured Stack finds its application in _____________

a) Bogo Sort

b) Tomita’s Algorithm

c) Todd–Coxeter algorithm

d) All of the mentioned

### View Answer

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