**Contents**hide

We have compiled very important and most repeated questions for **Data Structure Online MCQs** which are asked in academic as well as in different exams. Most importantly our **Online MCQs** will help you to evaluate and check your knowledge of computer and IT basics. These **Computer Knowledge MCQs** will help you to crack any competitive or academic exams.

Youth For Pakistan has provided an excellent opportunity for the students to prepare for their ** Computer Knowledge Online MCQs **test. These Online

**Computer**

**Knowledge MCQs**cover all the topics including MS Powerpoint, MS Word, MS Excel, Information Technology, Hardware, Internet, Operating Systems, Keyboard Shortcuts, Network, Data Structure, DBMS, Security, Abbreviations, Computer Graphics, Output, Memory, Electronics, Input, Marketing, File Location, File Extensions, Software, Programming, Computer Basics, Windows, Binary, Discrete Mathematics, Data Communication, Compiler and OOPS.

The questions about computers are asked in almost every test whether it is for admission to some institutes or for recruitment purposes.

**Data Structure Online MCQs with Answers**

We strongly recommend to all of our visitors that they attempt these **Data Structure Online MCQs **tests more than one time after completing the preparation so that they can prepare for the **Data Structure MCQs** in the best possible way.

1. In a graph if e=(u,v) means ___________

u is adjacent to v but v is not adjacent to u.

e begins at u and ends at v

u is node and v is an edge.

both u and v are edges.

None of these

Correct Ans: e begins at u and ends at v

2. A _________ is an acyclic digraph, which has only one node with indegree 0, and other nodes have in-degree 1.

Directed tree

Undirected tree

Dis-joint tree

Direction oriented tree

None of these

Correct Ans: Directed tree

3. A graph is said to be ___________ if the vertices can be split into two sets V1 and V2 such there are no edges between two vertices of V1 or two vertices of V2.

Partite

Bipartite

Rooted

Bisects

None of these

Correct Ans: Bipartite

4. In the _________ traversal we process all of a vertex’s descendants before we move to an adjacent vertex.

Depth First

Breadth First

Width First

Depth Limited

None of these

Correct Ans: Depth First

5. A directed graph is ___________ if there is a path from each vertex to every other vertex in the digraph.

Weakly connected

Strongly Connected

Tightly Connected

Linearly Connected

None of these

Correct Ans: Strongly Connected

6. An adjacency matrix representation of a graph cannot contain information of :

nodes

edges

direction of edges

parallel edges

None of these

Correct Ans: parallel edges

7. A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are

more than n

more than n+1

more than (n+1)/2

more than n(n-1)/2

None of these

Correct Ans: more than n(n-1)/2

8. A digraph is strongly connected under what condition?

A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v .

A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa.

A digraph is strongly connected if for at least one pair of vertex u, v e V, u can reach v and vice versa.

A digraph is strongly connected if at least one third pair of vertices u, v e V, u can reach v and vice versa.

None of these

Correct Ans: A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa.

9. Forward edge is:

(u, v) where u is a proper descendent of v in the tree.

(u, v) where v is a proper descendent of u in the tree.

(u, v) where v is a proper ancestor of u in the tree.

u, v) where u is a proper ancestor of v in the tree.

None of these

Correct Ans: (u, v) where v is a proper descendent of u in the tree.

10. Cross edge is :

(u, v) where u and v are not ancestor of one another

(u, v) where u is ancestor of v and v is not descendent of u.

(u, v) where u and v are not ancestor or descendent of one another

(u, v) where u and v are either ancestor or descendent of one another.

None of these

Correct Ans: (u, v) where u and v are not ancestor or descendent of one another

11. What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)

Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2)

Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2)

Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)

None of these

Correct Ans: Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2)

12. The relationship between number of back edges and number of cycles in DFS is,

Both are equal

Back edges are half of cycles

Back edges are one quarter of cycles

There is no relationship between no. of edges and cycles

None of these

Correct Ans: There is no relationship between no. of edges and cycles

13. Which is true statement in the following?

Kruskal algorithm is multiple source technique for finding MST.

Kruskal’s algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV)

Both of above

Kruskal’s algorithm (choose best non-cycle edge) is better than Prim’s (choose best Tree edge) when the graph has relatively few edges )

None of these

Correct Ans: Kruskal’s algorithm (choose best non-cycle edge) is better than Prim’s (choose best Tree edge) when the graph has relatively few edges )

14. What algorithm technique is used in the implementation of Kruskal solution for the MST?

Greedy Technique

Divide-and-Conquer Technique

Dynamic Programming Technique

The algorithm combines more than one of the above techniques

None of these

Correct Ans: Greedy Technique

15. Dijkstra’s algorithm :

Has greedy approach to find all shortest paths

as both greedy and Dynamic approach to find all shortest paths

Has greedy approach to compute single source shortest paths to all other vertices

Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.

None of these

Correct Ans: Has greedy approach to compute single source shortest paths to all other vertices

16. The number of edges in a simple, n-vertex, complete graph is

n*(n-2)

n*(n-1)

n*(n-1)/2

n*(n-1)*(n-2)

None of these

Correct Ans: n*(n-1)/2

17. A graph ‘G’ with ‘n’ nodes is bipartite if it contains

n edges

a cycle of odd length

no cycle of odd length

n2 edges

None of these

Correct Ans: no cycle of odd length

18. The spanning tree of connected graph with 10 vertices contains

9 edges

11 edges

10 edges

9 vertices

None of these

Correct Ans: 9 edges

19. Graphs are represented using

Adjacency tree

Adjacency linked list

Adjacency graph

Adjacency queue

None of these

Correct Ans: Adjacency linked list

20. Let A be an adjacency matrix of a graph G, the ijth entry in the matrix A power k gives expected number of collections involving a particular key x is

the number of paths of length is k from vertex vi to vertex vj

shortest path of k edges from vertex vi to vertex vj

length of a Eulerian path from vertex vi to vj

length of a hamiltonian cycle from vertex vi to vj

None of these

Correct Ans: shortest path of k edges from vertex vi to vertex vj

21. If every node u in G is adjacent to every other node v in G, A graph is said to be

isolated

complete

finite

strongly connected

None of these

Correct Ans: complete

22. Which of the following is useful in traversing a given graph by breadth first search?

stacks

set

List

Queue

None of these

Correct Ans: Queue

23. The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is

4

3

2

1

None of these

Correct Ans: 2

24. The minimum number of edges required to create a cyclic graph of n vertices is

n

n-1

n+1

2n

None of these

Correct Ans: n

25. Graph traversal is different from a tree traversal, because

trees are not connected

graphs may have loops.

trees have root.

None is true as tree is a subset of graph.

None of these

Correct Ans: trees have root.

26. All possible spanning trees of graph G

have same number of edges and vertices.

have same number of edges and but not vertices.

have same number of vertices but not edges.

depends upon algorithm being used.

None of these

Correct Ans: have same number of edges and vertices.

27. A complete graph can have

n^{2} spanning trees

n^{(n – 2)} spanning trees

n^{(n + 1)} spanning trees

n^{n} spanning trees

None of these

Correct Ans: n^{(n – 2)} spanning trees

28. A connected graph T without any cycles is called ________

free graph

no cycle graph

non cycle graph

circular graph

None of these

Correct Ans: free graph

29. Graph G is _________ if for any pair u, v of nodes in G there is a path from u to v or path from v to u.

Laterally connected

Widely Connected

Unliterally connected

Literally connected

None of these

Correct Ans: Unliterally connected

30. In a graph if e=[u,v], then u and v are called

endpoints of e

adjacent nodes

neighbours

all of the above

None of these

Correct Ans: all of the above

31. A _________ indicates the end of the list.

Guard

Sentinel

End pointer

Last pointer

None of these

Correct Ans: Sentinel

32. A run list is _______

small batches of records from a file

number of elements having same value

number of records

number of files in external storage

None of these

Correct Ans: small batches of records from a file

33. The dummy header in linked list contain _______

first record of the actual data

last record of the actual data

pointer to the last record of the actual data

middle record of the actual data

None of these

Correct Ans: first record of the actual data

34. Which of the following is two way lists?

Grounded header list

Circular header list

Linked list with header and trailer nodes

List traversed in two directions

None of these

Correct Ans: List traversed in two directions

35. The situation when in a linked list START=NULL is ______

Underflow

Overflow

Houseful

Saturated

None of these

Correct Ans: Underflow

36. A linked list in which the last node of Linked list points to the first is called a _________.

Doubly Linked List

Circular Linked List

Singly Linked List

All of the above

None of these

Correct Ans: Circular Linked List

37. Time require to find any element of the linked list is _______.

O(n)

O(1)

O(log n)

O(n-1)

None of these

Correct Ans: O(n)

38. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list could be used ?

Array Implementation of List

Singly Linked List

Circular Doubly Linked List

Doubly Linked List

None of these

Correct Ans: Circular Doubly Linked List

39. Consider a linked list of n elements. What is the time taken to insert an element after element pointed by same pointer ?

O(n)

O(log n)

O(n-1)

O(1)

None of these

Correct Ans: O(1)

40. Consider the Singly linked list having n elements. What will be the time taken to add an node at the end of linked list if Pointer is initially pointing to first node of the list.

O(1)

O(n-1)

O(n)

O(n^2)

None of these

Correct Ans: O(n-1)

41. If the given input array is sorted or nearly sorted, which of the following algorithm gives the best performance?

Insertion sort

Selection sort

Quick sort

Merge sort

None of these

Correct Ans: Insertion sort

42. Which of the following is not a non comparison sort?

Counting sort

Bucket sort

Radix sort

Shell sort

None of these

Correct Ans: Shell sort

43. Read the following statements carefully and pick the right most option.

I. A linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem.

II. An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.

Both (I) and (II) are TRUE

Both (I) and (II) are FALSE

Only (I) is true but (II) depends upon the instance size.

(I) is TRUE but (II) is FALSE

(I) is FALSE and (II) is TRUE.

Correct Ans: (I) is TRUE but (II) is FALSE

44. A node of a directed graph G having no out-degree and a positive in-degree is called

Source node

Sink node

Sibling node

Null node

In-node

Correct Ans: Source node

45. For the LCBB solution of knapsack problem with the data (p1–p4) = (10,10,12,18) and (w1–w4) = (2, 4, 6, 9) and m = 18, then the values of u(1) and ?(1) respectively are

-38, -44

-44, -38

-44, -32

-32, -44

-32, -38.

Correct Ans: -32, -44

46. The following is a weighted binary tree, then what is the weighted array for the TVS problem?

<img ‘https://img.fresherslive.com/mock-test-images/2016/dec/03/sebiassistantmanagersystemsmock1/computerknowledge/q197.png’ class=’imgresp’>

[9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4]

[9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6]

[9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 7, 4]

[9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4]

[9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0].

Correct Ans: [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4]

47. For the quick sort algorithm, what is the time complexity of the best/worst case?

best case: O(n)

worst case: O(n*n)

best case: O(n)

worst case: O(n*log(n))

best case: O(n*log(n))

worst case: O(n*log(n))

best case: O(n*log(n))

worst case: O(n*n)

best case: O(n*log(n))

worst case: O(n*n*n).

Correct Ans: best case: O(n*log(n))

worst case: O(n*n)

48. For the bubble sort algorithm, what is the time complexity of the best/worst case? (assume that the computation stops as soon as no more swaps in one pass)

best case: O(n)

worst case: O(n*n)

best case: O(n)

worst case: O(n*log(n))

best case: O(n*log(n))

worst case: O(n*log(n))

best case: O(n*log(n))

worst case: O(n*n)

best case: O( 1)

worst case: O( n ).

Correct Ans: best case: O(n)

worst case: O(n*n)

49. Consider Stack is implemented using the array.

#define MAX 10

struct STACK

{

int arr[MAX]

int top = -1;

}

In this implementation of stack maximum value of top which cannot cause overflow will _________.

Any other

9

10

11

None of these

Correct Ans: 9

50. Consider Stack is implemented using the array.

#define MAX 10

struct STACK

{

int arr[MAX]

int top = ___________;

}

What will be the initial value with which top is initialized.

0

-1

Garbage

1

None of these

Correct Ans: -1

51. An item that is read as input can be either pushed to a stack and later popped and printed, or printed directly. Which of the following will be the output if the input is the sequence of items 1, 2, 3, 4, 5 ?

5 4 3 1 2

3 4 5 1 2

3 4 5 2 1

1 5 2 3 4

None of these

Correct Ans: 3 4 5 2 1

52. Stack A has 3 Elements in it Say X,Y and Z with X on top.

1) Stack B is empty.

2) An Element popped out from Stack A can be printed immediately or pushed to stack B.

3) An Element popped out from Stack B can only be printed.

In this arrangement, which of the following permutations of X,Y,Z are not possible ?

Y X Z

Z X Y

Y Z X

Z Y X

None of these

Correct Ans: Z X Y

53. If memory for the run-time stack is only 150 cells(words), how big can N be in Factorial(N) before stack overflow?

12

66

60

26

None of these

Correct Ans: 66

54. Consider following Scenario –

1) The five items : P,Q,R,S and T are inserted into stack A one after another starting from T in reverse order

2) The stack is popped three times and each element is inserted into another stack B.

3) Then two elements are deleted from the stack B and pushed back onto the stack A.

What are the topmost elements of stack A and Stack B respectively?

R P

R Q

Q R

Q P

None of these

Correct Ans: Q P

55. Convert the following infix expression to postfix expression –

B * C – C + D / A / ( E + E )

B C * C – D A / E E + / +

B C C * – D A / E E + / +

B C C – * D A / E E + / +

B C C – * D / A E E + / +

None of these

Correct Ans: B C * C – D A / E E + / +

56. Convert the following infix expression to postfix expression –

A / B ^ C + D * E – A * C

A B C / ^ D E * + A C * –

A B C ^ / D * E + A C * –

A B C ^ / D E * + A * C –

A B C ^ / D E * + A C * –

None of these

Correct Ans: A B C ^ / D E * + A C * –

57. Evaluate Postfix expression from given infix expression.

A + B * (C + D) / F + D * E

AB+CD*F/+D*E

ABCD+*F/+DE*+

ABCD+*/F+DE*

AB+CD*F/+DE*

None of these

Correct Ans: ABCD+*F/+DE*+

58. Find the odd out

Prim’s Minimal Spanning Tree Algorithm

Kruskal’s Minimal Spanning Tree Algorithm

Floyd-Warshall’s All pair shortest path Algorithm

Dijkstra’s Minimal Spanning Tree Algorithm

None of these

Correct Ans: Floyd-Warshall’s All pair shortest path Algorithm

59. In conversion from prefix to postfix using stack data-structure, if operators and operands are pushed and popped exactly once, then the run-time complexity is ?

?(1)

?(n)

?(log n)

?(n^2)

None of these

Correct Ans: ?(n)

60. If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?

?(n), ?(n)

?(n), ?(1)

?(1), ?(n)

?(1), ?(1)

None of these

Correct Ans: ?(1), ?(1)

61. Which of the below given sorting techniques has highest best-case runtime complexity ?

quick sort

selection sort

insertion sort

bubble sort

None of these

Correct Ans: selection sort

62. Which of these algorithmic approach tries to achieve localized optimum solution ?

Greedy approach

Divide and conquer approach

Dynamic approach

All of the above

None of these

Correct Ans: Greedy approach

63. Time complexity of Depth First Traversal of is

?(|V|+|E|)

?(|V|)

?(|E|)

?(|V|*|E|)

None of these

Correct Ans: ?(|V|+|E|)

64. Match the following ?

(1) Bubble Sort —— (A) ?(n)

(2) Shell Sort —— (B) ?(n^2)

(3) Selection Sort —— (C) ?(n log n)

1 ? A, 2 ? B, 3 ? C

1 ? B, 2 ? C, 3 ? A

1 ? A, 2 ? C, 3 ? B

1 ? B, 2 ? A, 3 ? C

None of these

Correct Ans: 1 ? B, 2 ? C, 3 ? A

65. A stable sorting algorithm

does not crash.

does not run out of memory.

does not change the sequence of appearance of elements

does not exists

None of these

Correct Ans: does not change the sequence of appearance of elements

66. Re-balancing of AVL tree costs

?(1)

?(log n)

?(n)

?(n^2)

None of these

Correct Ans: ?(log n)

67. In the deletion operation of max heap, the root is replaced by

next available value in the left sub-tree.

next available value in the right sub-tree.

any random value from the heap.

last element of the last level

None of these

Correct Ans: last element of the last level

68. Linked list search complexity is

O(1)

O(n)

O(log n)

O(log log n)

None of these

Correct Ans: O(n)

69. Time required to merge two sorted lists of size m and n, is

?(m | n)

?(m + n)

?(m log n)

?(n log m)

None of these

Correct Ans: ?(m + n)

70. What is not true about insertion sort?

Exhibits the worst case performance when the initial array is sorted in reverse order.

Worst case and average case performance is ?(n^2)

Can be compared to the way a card player arranges his card from a card deck.

all of the above

None of these

Correct Ans: None of these

71. Maximum number of nodes in a binary tree with height k, where root is height 0, is

2^k ? 1

2^(k+1) ? 1

2^(k-1) + 1

2^k + 1

None of these

Correct Ans: 2^(k+1) ? 1

72. A procedure that calls itself is called

illegal call

reverse polish

recursive

all of the above

None of these

Correct Ans: recursive

73. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder transversal sequence of the resultant tree ?

7 5 1 0 3 2 4 6 8 9

0 2 4 3 1 6 5 9 8 7

0 1 2 3 4 5 6 7 8 9

9 8 6 4 2 3 0 1 5 7

None of these

Correct Ans: 0 1 2 3 4 5 6 7 8 9

74. Consider the following declaration of a two-dimensional array in C :

Char a[100][100]

Assuming that the main memory is byte-addressable and that array is stored starting from memory address 0, the address of a [40] [50] is

4040

4050

5040

5050

None of these

Correct Ans: 4050

75. Prim’s algorithm is a method available for finding out the minimum cost of a spanning tree. Its time complexity is given by:

O(n*n)

O(n logn)

O(n)

O(1)

None of these

Correct Ans: O(n*n)

76. The complexity of linear search algorithm of an array of n elements is:

O log(n)

O (n)

O nlog(n)

O(nXn)

None of these

Correct Ans: O (n)

77. The Eigen vectors of a real symmetric matrix corresponding to different Eigen values are:

Orthogonal matrix

Singular matrix

Non-singular matrix

Inverse matrix

None of these

Correct Ans: Orthogonal matrix

78. Graph having every pair of vertices connected is called:

Cycle graph

Complete graph

Peterson graph

Is a Tree

None of these

Correct Ans: Complete graph

79. An undirected graph is Eulerian if and only if all vertices of G are of the sum of the degrees of all nodes is:

Same degree

ODD degree

Need not be ODD

is twice number of edges

None of these

Correct Ans: ODD degree

80. Give the name of the Linear list in which elements can be added at ends but not in the middle:

Array

Queue

Tree

Circular Queue

None of these

Correct Ans: Queue

81. Binary search algorithm employs the strategy of.

Divide and Conquer technique

Dynamic Programming

Branch & Bound technique

Greedy Strategy

None of these

Correct Ans: Divide and Conquer technique

82. The number of nodes in a complete binary tree of height n:

2n-1-1

2n-1+1

2n+1-1

2n+1+1

None of these

Correct Ans: 2n+1-1

83. Which of the following connected simple graph has exactly one spanning tree?

Complete graph

Hamiltonian graph

Euler graph

all of the above

None of these

Correct Ans: all of the above

84. Consider the following statements for priority queue :

S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.

S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.

Which of the following is correct?

Both S1 and S2 are incorrect.

S1 is correct and S2 is incorrect.

S1 is incorrect and S2 is correct.

Both S1 and S2 are correct.

None of these

Correct Ans: Both S1 and S2 are correct.

85. Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true?

Weight (u, v) < 12 Weight (u, v) = 12 Weight (u, v) > 12

Weight (u, v) >= 12

None of these

Correct Ans: Weight (u, v) > 12

86. Leaves of which of the following trees are at the same level?

Binary tree

B-tree

AVL-tree

Expression tree

None of these

Correct Ans: B-tree

87. Skolmization is the process of

bringing all the quantifiers in the beginning of a formula in FDL

removing all the universal quantifiers

removing all the existential quantifiers

all of the above

None of these

Correct Ans: removing all the existential quantifiers

88. Which of the following permutations can be obtained in the output using a stack of size 3 elements assuming that input, sequence is 1, 2, 3, 4, 5 ?

3, 2, 1, 5, 4

5, 4, 3, 2, 1

3, 4, 5, 2, 1

3, 4, 5, 1, 2

None of these

Correct Ans: 5, 4, 3, 2, 1

89. Let T(n) be the function defined by T(n) = 1 and T(n) = 2T (n/2) + n, which of the following is TRUE ?

T(n) = O(log n)

T(n) = O(log_{2}n)

T(n) = O(n)

T(n) = O(n^2)

None of these

Correct Ans: T(n) = O(n)

90. The time complexities of some standard graph algorithms are given. Match each algorithm with its time complexity ?

(n and m are no. of nodes and edges respectively)

a. Bellman Ford Algorithm ——- 1. O (m log n)

b. Kruskals algorithm ——- 2. O (n3)

c. Floyd Warshall Algorithm ——- 3. O(mn)

d. Topological sorting ——- 4. O(n + m)

Codes : a b c d

3 1 2 4

2 4 3 1

3 4 1 2

2 1 3 4

None of these

Correct Ans: 3 1 2 4

91. Enumeration is a process of

Declaring a set of numbers

Sorting a list of strings

Assigning a legal values possible for a variable

Sequencing a list of operators

None of these

Correct Ans: Assigning a legal values possible for a variable

92. Given an empty stack, after performing push (1), push (2), Pop, push (3), push (4), Pop, Pop, push(5), Pop, what is the value of the top of the stack ?

4

3

2

1

None of these

Correct Ans: 1

93. A hash function f defined as f (key) = key mod 13, with linear probing is used to insert keys 55, 58, 68, 91, 27, 145. What will be the location of 79 ?

1

2

3

5

None of these

Correct Ans: 5

94. In which tree, for every node the height of its left subtree and right subtree differ almost by one ?

Binary search tree

AVL tree

Threaded Binary Tree

Complete Binary Tree

None of these

Correct Ans: AVL tree

95. The worst case time complexity of AVL tree is better in comparison to binary search tree for

Search and Insert Operations

Search and Delete Operations

Insert and Delete Operations

Search, Insert and Delete Operations

None of these

Correct Ans: Search, Insert and Delete Operations

96. Given a binary search trees for a set of n=5 keys with the following probabilities :

i 0 1 2 3 4 5

p 0.15 0.10 0.05 0.10 0.20

qi 0.05 0.10 0.05 0.05 0.05 0.10

The expected optimal cost of the search is

2.65

2.7

2.75

2.8

None of these

Correct Ans: 2.75

97. Linked Lists are not suitable for _____.

Binary Search

Polynomial Manipulation

Insertion

Radix Sort

None of these

Correct Ans: Binary Search

98. A simple graph G with n ? vertices is connected if the graph has

(n ? 1) (n ? 2)/2 edges

more than (n ? 1) (n ? 2)/2 edges

less than (n ? 1) (n ? 2)/2 edges

? ^{k}_{(i=1)} C(ni, 2) edges

None of these

Correct Ans: more than (n ? 1) (n ? 2)/2 edges

99. Consider the In-order and Post-order traversals of a tree as given below :

In-order : j e n k o p b f a c l g m d h i

Post-order : j n o p k e f b c l m g h i d a

The Pre-order traversal of the tree shall be

a b f e j k n o p c d g l m h i

a b c d e f j k n o p g l m h i

a b e j k n o p f c d g l m h i

j e n o p k f b c l m g h i d a

None of these

Correct Ans: a b e j k n o p f c d g l m h i

100. Consider the following statements :

(i) A graph in which there is a unique path between every pair of vertices is a tree.

(ii) A connected graph with e = v ? 1 is a tree.

(iii) A graph with e = v ? 1 that has no circuit is a tree.

Which of the above statements is/are true ?

(i) & (iii)

(ii) & (iii)

(i) & (ii)

All of the above

None of these

Correct Ans: All of the above

101. The efficient data structure to insert/delete a number in a stored set of numbers is

Queue

Linked list

Doubly linked list

Binary tree

None of these

Correct Ans: Doubly linked list

102. The min. number of nodes in a binary tree of depth d (root at level 0) is

2^d ? 1

2^d + 1 ? 1

d + 1

d

None of these

Correct Ans: d + 1

103. Suppose that the splits at every level of Quicksort are in proportion 1-? to ?, where 0 < ? < = 0.5 is a constant. The number of elements in an array is n. The maximum depth is approximately

0.5 ? Ig n

0.5 (1 ? ?) Ig n

? (Ig n)/(Ig ?)

? (Ig n)/Ig (1 ? ?)

None of these

Correct Ans: ? (Ig n)/Ig (1 ? ?)

104. The amortized time complexity to perform ______ operation(s) in Splay trees is O(Ig n).

Search

Search & Insert

Search & Delete

Search,Insert & Delete

None of these

Correct Ans: Search,Insert & Delete

105. Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is

2451

4950

4851

9900

None of these

Correct Ans: 4851

106. B+ trees are preferred to binary trees in databases because

Disk capacities are greater than memory capacities

Disk access is much slower than memory access

Disk data transfer rates are much less than memory data transfer rates

Disks are more reliable than memory

None of these

Correct Ans: Disk access is much slower than memory access

107. Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determine if there are two elements with sum less than 1000 in s. which of the following statements is true?

t (n) is 0 (1)

n < t (n) < n log_{2}n

n log_{2}n < t (n) < ^{n}C_{2}

t (n) = ^{n}C_{2}

None of these

Correct Ans: t (n) is 0 (1)

108. The most appropriate matching for the following pairs is:

X: depth first search ——- 1: heap

Y: breadth-first search ——- 2: queue

Z: sorting ——- 3: stack

X—1 Y—2 Z-3

X—3 Y—1 Z-2

X—3 Y—2 Z-1

X—2 Y—3 Z-1

None of these

Correct Ans: X—3 Y—2 Z-1

109. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?

LASTIN = LASTPOST

LASTIN = LASTPRE

LASTPRE = LASTPOST

All of the above

None of these

Correct Ans: None of these

110. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

<img ‘https://img.fresherslive.com/mock-test-images/2016/dec/03/sebiassistantmanagersystemsmock1/computerknowledge/q133.png’ class=’imgresp’>

rear node

front node

not possible with a single pointer

node next to front

None of these

Correct Ans: rear node

111. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

1) Selection of the smallest element

2) Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

A heap can be used but not a balanced binary search tree

A balanced binary search tree can be used but not a heap

Both balanced binary search tree and heap can be used

Neither balanced binary search tree nor heap can be used

None of these

Correct Ans: A balanced binary search tree can be used but not a heap

112. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

2

3

4

6

None of these

Correct Ans: 3

113. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ?

i) preorder and postorder

ii) inorder and postorder

iii) preorder and inorder

iv) level order and postorder

(i) only

(ii), (iii)

(iii) only

(iv) only

None of these

Correct Ans: (ii), (iii)

114. Consider the function f defined below.

struct item

{

int data;

struct item * next;

};

int f(struct item *p)

{

return (

(p == NULL) ||

(p->next == NULL) ||

(( P->data <= p->next->data) && f(p->next))

);

}

For a given linked list p, the function f returns 1 if and only if

the list is empty or has exactly one element

the elements in the list are sorted in non-decreasing order of data value

the elements in the list are sorted in non-increasing order of data value

not all elements in the list have the same data value.

None of these

Correct Ans: the elements in the list are sorted in non-decreasing order of data value

115. Postorder traversal of a given binary search tree, T produces the following sequence of keys

10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

None of these

Correct Ans: 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

116. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i. 9679, 1989, 4199 hash to the same value

ii. 1471, 6171 has to the same value

iii. All elements hash to the same value

iv. Each element hashes to a different value

i only

ii only

i and ii only

iii or iv

None of these

Correct Ans: i and ii only

117. Level order traversal of a rooted tree can be done by starting from the root and performing

preorder traversal

in-order traversal

depth first search

breadth first search

None of these

Correct Ans: breadth first search

118. The best data structure to check whether an arithmetic expression has balanced parentheses is a

queue

stack

tree

list

None of these

Correct Ans: stack

119. Suppose you are given an array s[1…n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence

do, where 1 < k <= n:

reverse (s, 1, k);

reverse (s, k + 1, n);

reverse (s, 1, n);

Rotates s left by k positions

Leaves s unchanged

Reverses all elements of s

Rotates s right by k positions

None of these

Correct Ans: Rotates s left by k positions

120. The time complexity of the following C function is (assume n > 0)

int recursive (mt n)

{

if (n == 1)

return (1);

else

return (recursive (n-1) + recursive (n-1));

}

0(n)

0(nlogn)

0(n^2)

0(2^n)

None of these

Correct Ans: 0(2^n)

121. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

union only

intersection, membership

membership, cardinality

union, intersection

None of these

Correct Ans: union, intersection

122. Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

<img ‘https://img.fresherslive.com/mock-test-images/2016/dec/03/sebiassistantmanagersystemsmock1/computerknowledge/q121.png’ class=’imgresp’>

P, Q, R, S, T, U

P, Q, R, U, S, T

P, Q, R, U, T, S

P, Q, T, R, U, S

None of these

Correct Ans: P, Q, R, U, S, T

123. Consider the following C program segment

struct CellNode

{

struct CelINode *leftchild;

int element;

struct CelINode *rightChild;

}

int Dosomething(struct CelINode *ptr)

{

int value = 0;

if (ptr != NULL)

{

if (ptr->leftChild != NULL)

value = 1 + DoSomething(ptr->leftChild);

if (ptr->rightChild != NULL)

value = max(value, 1 + DoSomething(ptr->rightChild));

}

return (value);

}

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

The number of leaf nodes in the tree

The number of nodes in the tree

The number of internal nodes in the tree

The height of the tree

None of these

Correct Ans: The height of the tree

124. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)

top1 + top2 = MAXSIZE

(top1= MAXSIZE/2) or (top2 = MAXSIZE)

top1= top2 -1

None of these

Correct Ans: top1= top2 -1

125. Consider the following three claims

I) (n + k)^m = ?(n^m), where k and m are constants

II) 2^(n + 1) = 0(2^n)

III) 2^(2n + 1) = 0(2^n)

Which of these claims are correct?

I and II

I and III

II and III

I, II and III

None of these

Correct Ans: I and II

126. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

log 2 n

n/2

log 2 n – 1

n

None of these

Correct Ans: n

127. Consider the following C function.

float f(float x, int y)

{

float p, s; int i;

for (s=1, p=1, i=1; i < y; i ++)

{

p*= x/i;

s+=p;

}

return s;

}

For large values of y, the return value of the function f best approximates

x^y

e^x

ln(1 + x)

x^x

None of these

Correct Ans: e^x

128. Consider the following graph

<img ‘https://img.fresherslive.com/mock-test-images/2016/dec/03/sebiassistantmanagersystemsmock1/computerknowledge/q115.png’ class=’imgresp’>

Among the following sequences

I) a b e g h f

II) a b f e h g

III) a b f h g e

IV) a f g h b e

Which are depth first traversals of the above graph?

I, II and IV only

I and IV only

II, III and IV only

I, III and IV only

None of these

Correct Ans: I, III and IV only

129. The problem 3-SAT and 2-SAT are

both in P

both NP complete

NP-complete and in P respectively

undecidable and NP-complete respectively

None of these

Correct Ans: NP-complete and in P respectively

130. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

n

n^2

nlogn

n(log^2)n

None of these

Correct Ans: nlogn

131. The usual ?(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

remain ?(n^2)

become ?(n(log n)^2)

become ?(n log n)

become ?(n)

None of these

Correct Ans: remain ?(n^2)

132. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ?

n(n-l)/2

2^n

n!

2^(n(n-1)/2)

None of these

Correct Ans: 2^(n(n-1)/2)

133. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct?

d(r, u) < d (r, v) d(r, u) > d(r, v)

d(r, u) <= d (r, v) d(r, u) >= d(r, v)

None of these

Correct Ans: d(r, u) <= d (r, v) 134. Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true? {u,v} must be an edge in G, and u is a descendant of v in T {u,v} must be an edge in G, and v is a descendant of u in T If {u,v} is not an edge in G then u is a leaf in T If {u,v} is not an edge in G then u and v must have the same parent in T None of these Correct Ans: If {u,v} is not an edge in G then u is a leaf in T 135. Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false? Every minimum spanning tree of G must contain emin If emax is in a minimum spanning tree, then its removal must disconnect G No minimum spanning tree contains emax G has a unique minimum spanning tree None of these Correct Ans: No minimum spanning tree contains emax 136. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

n(X+ Y)

3Y + 2X

n(X + Y)-X

Y + 2X

None of these

Correct Ans: n(X + Y)-X

137. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

7 5 1 0 3 2 4 6 8 9

0 2 4 3 1 6 5 9 8 7

0 1 2 3 4 5 6 7 8 9

9 8 6 4 2 3 0 1 5 7

None of these

Correct Ans: 0 1 2 3 4 5 6 7 8 9

138. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

?(n log n)

?(n)

?(log n)

?(1)

None of these

Correct Ans: ?(1)

139. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

d e b f g c a

e d b g f c a

e d b f g c a

d e f g b c a

None of these

Correct Ans: d e b f g c a

140. The following postfix expression with single digit operands is evaluated using a stack:

8 2 3 ^ / 2 3 * + 5 1 * –

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

6, 1

5, 7

3, 2

1, 5

None of these

Correct Ans: 6, 1

141. Which of the following sorting algorithms has the lowest worst-case complexity?

Merge sort

Bubble sort

Quick sort

Selection sort

None of these

Correct Ans: Merge sort

142. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3

None of these

Correct Ans: 5

143. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

2^h -1

2^(h-1) – 1

2^(h+1) -1

2*(h+1)

None of these

Correct Ans: 2^(h+1) -1

144. What is the time complexity of the following recursive function:

int DoSomething (int n)

{

if (n <= 2)

return 1;

else

return (DoSomething (floor(sqrt(n))) + n);

}

?(n)

?(nlogn)

?(logn)

?(loglogn)

None of these

Correct Ans: ?(loglogn)

145. In the following C function, let n >= m.

int gcd(n,m)

{

if (n%m ==0) return m;

n = n%m;

return gcd(m,n);

}

How many recursive calls are made by this function?

?(logn)

?(n)

?(loglogn)

?(sqrt(n))

None of these

Correct Ans: ?(logn)

146. A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

3

4

5

6

None of these

Correct Ans: 5

147. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

Dijkstra’s algorithm starting from S.

Warshall’s algorithm

Performing a DFS starting from S.

Performing a BFS starting from S.

None of these

Correct Ans: Performing a BFS starting from S.

148. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

8, _, _, _, _, _, 10

1, 8, 10, _, _, _, 3

1, _, _, _, _, _,3

1, 10, 8, _, _, _, 3

None of these

Correct Ans: 1, 8, 10, _, _, _, 3

149. Consider the following C code segment:

int IsPrime(n)

{

int i,n;

for(i=2;i<=sqrt(n);i++)

if(n%i == 0)

{printf(“Not Prime\n”); return 0;}

return 1;

}

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

T(n) = O(sqrt(n)) and T(n) = ?(sqrt(n))

T(n) = O(sqrt(n)) and T(n) = ?(1)

T(n) = O(n) and T(n) = ?(sqrt(n))

T(n) = O(sqrt(n)) and T(n) = ?(sqrt(n) – 1)

None of these

Correct Ans: T(n) = O(sqrt(n)) and T(n) = ?(1)

150. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

At least 2n – c comparisons, for some constant c, are needed.

At most 1.5n – 2 comparisons are needed.

At least nLog2n comparisons are needed.

At least n^2Logn comparisons are needed.

None of these

Correct Ans: At most 1.5n – 2 comparisons are needed.

151. Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

There is a minimum spanning tree containing e.

If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.

Every minimum spanning tree has an edge of weight w .

e is present in every minimum spanning tree.

None of these

Correct Ans: e is present in every minimum spanning tree.

152. Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

?(logn)

?(LogLogn )

?(n)

?(nLogn)

None of these

Correct Ans: ?(LogLogn )

153. Consider the following C program segment where CellNode represents a node in a binary tree:

struct CellNode

{

struct CellNOde *leftChild;

int element;

struct CellNode *rightChild;

};

int GetValue(struct CellNode *ptr)

{

int value = 0;

if (ptr != NULL)

{

if ((ptr->leftChild == NULL) &&

(ptr->rightChild == NULL))

value = 1;

else

value = value + GetValue(ptr->leftChild)

+ GetValue(ptr->rightChild);

}

return(value);

}

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

None of these

Correct Ans: the number of leaf nodes in the tree

154. Consider the following algorithm for searching for a given number x in an unsorted – array A[1..n] having n distinct values:

1) Choose an i uniformly at random from 1..n;

2) If A[i] = x then Stop else Goto 1;

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

n

n-l

2n

(n / 2)

None of these

Correct Ans: n

155. 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?

log_{2} n

log_{(4/3)} n

log_{3} n

log_{(3/2)} n

None of these

Correct Ans: log_{(3/2)} n

156. The running time of the following algorithm

Procedure A(n)

If n <= 2 return(1) else return A(sqrt(n));

is best described by

O(n)

O(log n)

O(log log n)

O(1)

None of these

Correct Ans: O(log log n)

157. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

n/2

(n-1)/3

(n-1)/2

(2n+1)/3

None of these

Correct Ans: (2n+1)/3

158. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

?(n)

?(logn)

?(log*n)

?(n^2)

None of these

Correct Ans: ?(logn)

159. Consider the following functions:

f(n) = 2^n

g(n) = n!

h(n) = n^logn

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

f(n) = O(g(n)); g(n) = O(h(n))

f(n) = ?(g(n)); g(n) = O(h(n))

g(n) = O(f(n)); h(n) = O(f(n))

h(n) = O(f(n)); g(n) = ?(f(n))

None of these

Correct Ans: h(n) = O(f(n)); g(n) = ?(f(n))

160. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

<img ‘https://img.fresherslive.com/mock-test-images/2016/dec/03/sebiassistantmanagersystemsmock1/computerknowledge/q83.png’ class=’imgresp’>

MNOPQR

NQMPOR

QMNPRO

QMNPOR

None of these

Correct Ans: QMNPRO