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
Ans : A

Explanation: 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. What is the maximum number of possible non zero values in an

adjacency matrix of a simple graph with n vertices?
A. (n*(n-1))/2
B. (n*(n+1))/2
C. n*(n-1)
D. n*(n+1)
View Answer
Ans : C

Explanation: Out of n*n possible values for a simple graph the diagonal values will always
be zero.

3. Which of the following is an advantage of adjacency list representation

over adjacency matrix representation of a graph?
A. In adjacency list representation, space is saved for sparse graphs.
B. DFS and BSF can be done in O(V + E) time for adjacency list
representation. These operations take O(V^2) time in adjacency matrix
representation. Here is V and E are number of vertices and edges respectively.
C. Adding a vertex in adjacency list representation is easier than adjacency
matrix representation.
D. All of the above
View Answer
Ans : D

Explanation: No explanation.
4.A connected planar graph having 6 vertices, 7 edges contains
_____________ regions.
A. 15
B. 3
C. 1
D. 11
View Answer
Ans : B

Explanation: By euler’s formula the relation between vertices(n), edges(q) and regions(r) is
given by n-q+r=2.

5.On which of the following statements does the time complexity of

checking if an edge exists between two particular vertices is not,
depends?
A. Depends on the number of edges
B. Depends on the number of vertices
C. Is independent of both the number of edges and vertices
D. It depends on both the number of edges and vertices
View Answer
Ans : C

Explanation:To check if there is an edge between to vertices i and j, it is enough to see if

the value of A[i][j] is 1 or 0, here A is the adjacency matrix.

6. The degree sequence of a simple graph is the sequence of the degrees

of the nodes in the graph in decreasing order. Which of the following
sequences can not be the degree sequence of any graph?
   I. 7, 6, 5, 4, 4, 3, 2, 1
   II. 6, 6, 6, 6, 3, 3, 2, 2
   III. 7, 6, 6, 4, 4, 3, 2, 2
   IV. 8, 7, 7, 6, 4, 2, 1, 1
A. I and II
B. III and IV
C. IV only
D. II and IV
View Answer
Ans : D

Explanation: No explanation

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

vertices?
A. 24
B. 21
C. 25
D. 16
View Answer
Ans : C

Explanation: 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.

8. Possible number of labelled simple Directed, Pseudo and Multigarphs

exist having 2 vertices?
A. 3, Infinite, 4
B. 4, 3, Infinite
C. 4, Infinite, infinite
D. 4, Infinite, Infinite
View Answer

9.The most efficient algorithm for finding the number of connected

components in an undirected graph on n vertices and m edges has time
complexity.
   (A)   \theta(n)
   (B)   \theta(m)
   (C)   \theta(m + n)
   (D)   \theta(mn)
A. A
B. B
C. C
D. D
View Answer
Ans : C

Explanation: Connected components can be found in O(m + n) using Tarjan's algorithm.

Once we have connected components, we can count them.

10. What is time complexity to check if a string(length S1) is a substring

of another string(length S2) stored in a Directed Acyclic Word Graph,
given S2 is greater than S1?
A. O(S1)
B. O(S2)
C. O(S1+S2)
D. O(1)
View Answer
Ans : A

Explanation:For each check of a word of length S1, we need to follow at most S1 edges.
11. 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
Ans : B

Explanation: Number of ways in which every vertex can be connected to each other is nC2.

12. 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
Ans : B

Explanation: The sum of the degrees of the vertices is equal to twice the number of edges.
13. 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
Ans : A

Explanation: 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).

14. 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
Ans : A

Explanation: A simple graph maybe connected or disconnected.

15. 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
Ans : B

Explanation: A graph must contain at least one vertex.

16. 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
Ans : B

Explanation: For any connected graph with no cycles the equation holds true.

17. 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
Ans : A

Explanation: A graph is eulerian if either all of its vertices are even or if only two of its
vertices are odd.

18. 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
Ans : B

Explanation: The given statement is the definition of regular graphs.Explanation: The given
statement is the definition of regular graphs.

19. 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
Ans :C

Explanation: The 3 listed methods can be used, the choice depends on the ease of use.
20. The time complexity to calculate the number of edges in a graph
whose information in stored in form of an adjacency matrix is ____________
A. O(V)
B. O(E2)
C. O(E)
D. O(V2)
View Answer
Ans : D

Explanation: As V entries are 0, a total of V2-V entries are to be examined.

1. The no of external nodes in a full binary tree with n internal nodes is?
A. n
B. n+1
C. 2n
D. 2n + 1
View Answer
Ans : B

Explanation: The no of external nodes in a full binary tree with n internal nodes is n+1.

2. Which of the following is a true about Binary Trees?

A. Every binary tree is either complete or full.
B. Every complete binary tree is also a full binary tree.
C. Every full binary tree is also a complete binary tree.
D. No binary tree is both complete and full.
E. None of the above
View Answer
Ans : E

Explanation: A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree)
is a tree in which every node other than the leaves has two children. A complete binary tree
is a binary tree in which every level, except possibly the last, is completely filled, and all
nodes are as far left as possible. A) is incorrect.
3. A Binary Tree can have
A. Can have 2 children
B. Can have 1 children
C. Can have 0 children
D. All of the above
View Answer
Ans : D

Explanation: A Binary Tree can have 0, 1, 2 children

4.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
Ans : D

Explanation: This is an application of stack.

5.The difference between the external path length and the internal path
length of a binary tree with n internal nodes is?
A. 1
B. n
C. n + 1
D. 2n
View Answer
Ans : D

Explanation:The difference between the external path length and the internal path length of
a binary tree with n internal nodes is 2n.

6. In a complete k-ary tree, every internal node has exactly k children or

no child. The number of leaves in such a tree with n internal nodes is:
A. nk
B. (n – 1) k+ 1
C. n( k – 1) + 1
D. n(k – 1)
View Answer
Ans : C

Explanation: For an k-ary tree where each node has k children or no children, following
relation holds L = (k-1)*n + 1 Where L is the number of leaf nodes and n is the number of
internal nodes.

7.Height of Height of a binary tree is

A. MAX( Height of left Subtree, Height of right subtree)+1
B. MAX( Height of left Subtree, Height of right subtree)
C. MAX( Height of left Subtree, Height of right subtree)-1
D. None of the above
View Answer
Ans : A

Explanation: Height of Height of a binary tree is MAX( Height of left Subtree, Height of right
subtree)+1.

8. Which of the following options is an application of splay trees ?

A. cache Implementation
B. networks
C. send values
D. receive values
View Answer
Ans : A

Explanation: Splay trees can be used for faster access to recently accessed items and
hence used for cache implementations.

9. Suppose a complete binary tree has height h>0. The minimum no of

leaf nodes possible in term of h is?
A. 2h -1
B. 2h -1 + 1
C. 2h -1
D. 2h +1
View Answer
Ans : C
Explanation: Suppose a complete binary tree has height h>0. The minimum no of leaf
nodes possible in term of h is 2h -1.

10. A weight-balanced tree is a binary tree in which for each node. The
number of nodes in the left sub tree is at least half and at most twice the
number of nodes in the right sub tree. The maximum possible height
(number of nodes on the path from the root to the farthest leaf) of such a
tree on n nodes is best described by which of the following?
A. log2 n
B. log4/3 n
C. log3 n
D. log3/2 n
View Answer
Ans : D

11)   How are the elements with the same priority get processed according to the Priority Queue
mechanism?

a. Before the processing of other elements with lower priority

b. After the processing of other elements with highest priority
c. On the basis of 'First-Come-First Served' priority
d. None of the Above
ANSWER: On the basis of 'First-Come-First Served' priority

12)   Which linear structure has a provision of Last-In-First-Out (LIFO) mechanism for its elemen

a. Stack
b. Queue
c. Both a & b
d. None of the above
13)   Which function plays an important role in returning the address of memory block allocated
locate / store  a node especially while declaring ' top ' in the linked representation of the Stack?

a. galloc ()
b. falloc ()
c. malloc ()
d. calloc ()
ANSWER: malloc ()

14)   Stacks do not find their applicability for ____________.

a. Simplification of an arithmetic expression in postfix form

b. Recursion Implementation
c. Conversion of Infix to its equivalent Postfix Form
d. Allocation of Resources by an Operating System

ANSWER: Allocation of Resources by an Operating System

15)   Which step is associated with an initialization process while converting a recursive into no
recursive algorithm?

a. Declaration of Stack
b. Pushing of all local variables and parameters into the stack
c. Assigning the values of formal parameters
d. Popping of return address
ANSWER: Declaration of Stack
16)   How do the nested calls of the function get managed?

a. Through Queues
b. Through Stacks
c. Through Trees
d. Through Graphs
ANSWER: Through Stacks
!

17)   How many elements are present in the stack if the variable top exhibits pointing towards th
topmost element in the Array?
- Published on 28 Aug 15

a. top +1
b. top - 1
c. zero
d. infinite
ANSWER: top +1

18)   What should be the growing direction of two stacks while implementing them in a similar a
as to reduce the overflow chances?

a. Forward
b. Backward
c. Opposite
d. None of the above
ANSWER: Opposite
  Which is the correct algorithmic sequence for the conversion of an expression from Infix to Pr

A. Change of every '(' (opening bracket) by ')' (closing bracket) and vice-versa.
B. Reversal of an infix expression.
C. Conversion of the modified expression into postfix form.
D. Reversal of postfix expression.
- Published on 28 Aug 15

a. A, B, C, D

b. C, A, D, B

c. B ,A, C, D

d. D, B, A, C

ANSWER: B ,A, C, D

22)   Which direction of scanning is suitable for the evaluation of a prefix expression?

-

a. Left to Left

b. Right to Right

c. Left to Right

d. Right to Left

ANSWER: Right to Left

23)   When is the pop operation on Stack considered to be an error?

a. Only when the stack is empty

b. Only when the stack is full

c. When the stack is neither empty nor full

d. Cannot be predicted

ANSWER: Only when the stack is empty

24)   What does the push operation top = top +1 indicate while representing the stack in one -
dimensional array?
- a. Stack Growing

b. Stack Shrinking

c. Stack Stability

d. Stack Instability

ANSWER: Stack Growing, array shrinking

25)   What happens if an expression tree reads the symbol in the form of an Operand?

a. One node tree is created and a pointer is pushed towards it on the stack.

b. Pointer is pop to two trees in order to generate a new tree with root as its operator.

c. Both a & b

d. None of the Above

ANSWER: One node tree is created and a pointer is pushed towards it on the stack.
26)   Which of the following techniques represents the precise sequence of an In - Order Traver
Binary Tree?

a. Visit the Root, Traverse Left Subtree, Traverse Right Subtree

b. Traverse Left Subtree, Visit the Root, Traverse Right Subtree

c. Traverse Left Subtree, Traverse Right Subtree, Visit the Root

d. None of the Above

ANSWER: Traverse Left Subtree, Visit the Root, Traverse Right Subtree

27)   Which balance factor is stored in the new field introduced by an AVL tree for the represent
a node?
-

a. Length

b. Height

c. Width

d. Information

ANSWER: Height

28)   How is an insertion of a node into an AVL tree carried out?

a. By treating an AVL tree as a binary search tree

b. By updating the balance factors working upward from insertion point to the root

c. Both a & b

d. None of the Above

ANSWER: Both a & b

29)   Which value is assigned to leaf of game tree if the board position corresponds to the ' draw
result for the player?
-

a. 1

b. 0

c. -1

d. None of the above

ANSWER: 0

30)   Which is the correct sequential order of constructing a binary tree for the expression a + b
* e  ?

A. Moving the operator at the center of the group.

B. Inversion of the Structure.
C. Grouping of elements as per the sequence of Evaluation.

a. A, B, C

b. B, C, A
c. B, A, C

d. C, A, B

ANSWER: C, A, B
PSEUDOCODE vs. CODE Characteristics of Good Pseudocode: + Shows the key concepts and the key
computation steps of the Algorithm, avoiding too much details. + Avoids dependency on any specific
prog. language. + Allows determining the correctness of the Algorithm. + Allows choosing a suitable
data-structures for an efficient implementation and complexity analysis.