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
n2 spanning trees
n(n – 2) spanning trees
n(n + 1) spanning trees
nn 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(log2n)
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 log2n
n log2n < t (n) < nC2
t (n) = nC2
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?
log2 n
log(4/3) n
log3 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