Data Strutctures Multiple Choice Question with Answers
Chapter: Non-LInear Data Structures ( Graphs)
1. Which of the following statements for a simple graph is correct?
A. Every path is a trail
B. Every trail is a path
C. Every trail is a path as well as every path is a trail
D. Path and trail have no relation
Answer: A. Every path is a trail
2. For the given graph(G), which of the following statements is true?
A. G is a complete graph
B. G is not a connected graph
C. The vertex connectivity of the graph is 2
D. none
Answer: C. The vertex connectivity of the graph is 2
3. What is the number of edges present in a complete graph having n vertices?
A. (n*(n+1))/2
B. (n*(n-1))/2
C. n
D. Information given is insufficient
Answer: B.(n*(n-1))/2
4. The given Graph is regular.
A. True
B. False
C. none
D. none
Answer: A.True
5. A connected planar graph having 6 vertices, 7 edges contains regions.
A. 15
B. 3
C. 1
D. 11
Answer: B.3
6. If a simple graph G, contains n vertices and m edges, the number of edges in the GraphG'(Complement of G) is
A. (n*n-n-2*m)/2
B. (n*n+n+2*m)/2
C. (n*n-n-2*m)/2
D. (n*n-n+2*m)/2
Answer: A.(n*n-n-2*m)/2
7. Which of the following properties does a simple graph not hold?
A. Must be connected
B. Must be unweighted
C. Must have no loops or multiple edges
D. Must have no multiple edges
Answer: A.Must be connected
8. What is the maximum number of edges in a bipartite graph having 10 vertices?
A. 24
B. 21
C. 25
D. 16
Answer: C.25
9. Which of the following is true?
A. A graph may contain no edges and many vertices
B. A graph may contain many edges and no vertices
C. A graph may contain no edges and no vertices
D. A graph may contain no vertices and many edges
Answer: B.A graph may contain many edges and no vertices
10. For a given graph G having v vertices and e edges which is connected and has no cycles, which ofthe following statements is true?
A. v=e
B. v = e+1
C. v + 1 = e
D. v = e-1
Answer: B.v = e+1
11. For which of the following combinations of the degrees of vertices would the connected graph beeulerian?
A. 1,2,3
B. 2,3,4
C. 2,4,5
D. 1,3,5
Answer: A.1,2,3
12. A graph with all vertices having equal degree is known as a
A. Multi Graph
B. Regular Graph
C. Simple Graph
D. Complete Graph
Answer: B.Regular Graph
13. Which of the following ways can be used to represent a graph?
A. Adjacency List and Adjacency Matrix
B. Incidence Matrix
C. Adjacency List, Adjacency Matrix as well as Incidence Matrix
D. No way to represent
Answer: C.Adjacency List, Adjacency Matrix as well as Incidence Matrix
14. The number of possible undirected graphs which may have self loops but no multiple edges andhave n vertices is
A. 2((n*(n-1))/2)
B. 2((n*(n+1))/2)
C. 2((n-1)*(n-1))/2)
D. 2((n*n)/2)
Answer: D.2((n*n)/2)
15. Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions.What will be the number of connected components?
A. 1
B. 2
C. 3
D. 4
Answer: B.2
16. Number of vertices with odd degrees in a graph having a eulerian walk is
A. 0
B. Can’t be predicted
C. 2
D. either 0 or 2
Answer: D.either 0 or 2
17. How many of the following statements are correct?
A. All cyclic graphs are complete graphs.
B. All complete graphs are cyclic graphs.
C. All paths are bipartite.
D. All cyclic graphs are bipartite.
Answer: B.All complete graphs are cyclic graphs.
18. What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
A. n-2
B. n
C. 2
Answer: A.n-2
19. What would the time complexity to check if an undirected graph with V vertices and E edges isBipartite or not given its adjacency matrix?
A. O(E*E)
B. O(V*V)
C. O(E)
D. O(V)
Answer: B.O(V*V)
20. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
A. (V*(V-1))/2
B. (V*(V+1))/2
C. (V+1)C2
D. (V-1)C2
Answer: A.(V*(V-1))/2
21. The topological sorting of any DAG can be done in time.
A. cubic
B. quadratic
C. linear
D. logarithmic
Answer: C.linear
22. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
A. Many Hamiltonian paths are possible
B. No Hamiltonian path is possible
C. Exactly 1 Hamiltonian path is possible
D. Given information is insufficient to comment anything
Answer: B.No Hamiltonian path is possible
23. Which of the given statement is true?
A. All the Cyclic Directed Graphs have topological sortings
B. All the Acyclic Directed Graphs have topological sortings
C. All Directed Graphs have topological sortings
D. All the cyclic directed graphs hace non topological sorting
Answer: D.All the cyclic directed graphs have non topological sorting
24. What is the value of the sum of the minimum in-degree and maximum out-degree of an DirectedAcyclic Graph?
A. Depends on a Graph
B. Will always be zero
C. Will always be greater than zero
D. May be zero or greater than zero
Answer: B. Will always be zero
Data Structures MCQ| Non Linear Data Structures – Graphs Searching, Sorting and Hashing Techniques
25. Where is linear searching used?
A. When the list has only a few elements
B. When performing a single search in an unordered list
C. Used all the time
D. When the list has only a few elements and When performing a single search in an unordered list
Answer: D.When the list has only a few elements and When performing a single search in an unordered list
26. What is the best case for linear search?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(1)
Answer: D.O(1)
27. What is the worst case for linear search?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(1)
Answer: C.O(n)
28. What is the best case and worst case complexity of ordered linear search?
A. O(nlogn), O(logn)
B. O(logn), O(nlogn)
C. O(n), O(1)
D. O(1), O(n)
Answer: D.O(1), O(n)
29. Which of the following is a disadvantage of linear search?
A. Requires more space
B. Greater time complexities compared to other searching algorithms
C. Not easy to understand
D. Not easy to implement
Answer: B.Greater time complexities compared to other searching algorithms
30. What is the advantage of recursive approach than an iterative approach?
A. Consumes less memory
B. Less code and easy to implement
C. Consumes more memory
D. More code has to be written
Answer: B.Less code and easy to implement
31. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
A. 5
B. 2
C. 3
D. 4
Answer: C.3
32. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(correspondingarray elements) in the first and second levels of recursion?
A. 90 and 99
B. 90 and 94
C. 89 and 99
D. 89 and 94
Answer: A.90 and 99
33. What is the worst case complexity of binary search using recursion?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: B.O(logn)
34. What is the average case time complexity of binary search using recursion?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: B.O(logn)
35. Which of the following is not an application of binary search?
A. To find the lower/upper bound in an ordered sequence
B. Union of intervals
C. Debugging
D. To search in unordered list
Answer: D.To search in unordered list
36. Binary Search can be categorized into which of the following?
A. Brute Force technique
B. Divide and conquer
C. Greedy algorithm
D. Dynamic programming
Answer: B.Divide and conquer
37. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the elementis found?
A. 1
B. 3
C. 4
D. 2
Answer: D.2
38. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the midvalues(corresponding array elements) generated in the first and second iterations?
A. 90 and 99
B. 90 and 100
C. 89 and 94
D. 94 and 99
Answer: A.90 and 99
39. What is the time complexity of binary search with iteration?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: B.O(logn)
40. What is an external sorting algorithm?
A. Algorithm that uses tape or disk during the sort
B. Algorithm that uses main memory during the sort
C. Algorithm that involves swapping
D. Algorithm that are considered ‘in place’
Answer: A.Algorithm that uses tape or disk during the sort
41. What is an internal sorting algorithm?
A. Algorithm that uses tape or disk during the sort
B. Algorithm that uses main memory during the sort
C. Algorithm that involves swapping
D. Algorithm that are considered ‘in place’
Answer: B.Algorithm that uses main memory during the sort
42. What is the worst case complexity of bubble sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: D.O(n2)
43. What is the average case complexity of bubble sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: D.O(n2)
44. Which of the following is not an advantage of optimised bubble sort over other sorting techniquesin case of sorted elements?
A. It is faster
B. Consumes less memory
C. Detects whether the input is already sorted
D. Consumes less time
Answer: C.Detects whether the input is already sorted
45. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How manyiterations will be done to sort the array?
A. 4
B. 2
C. 1
Answer: A.4
46. What is the best case efficiency of bubble sort in the improvised version?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: C.O(n)
47. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How manyiterations will be done to sort the array with improvised version?
A. 4
B. 2
C. 1
Answer: B.2
48. What is an in-place sorting algorithm?
A. It needs O(1) or O(logn) memory to create auxiliary locations
B. The input is already sorted and in-place
C. It requires additional storage
D. It requires additional space
Answer: A.It needs O(1) or O(logn) memory to create auxiliary locations
49. In the following scenarios, when will you use selection sort?
A. The input is already sorted
B. A large file has to be sorted
C. Large values need to be sorted with small keys
D. Small values need to be sorted with large keys
Answer: C.Large values need to be sorted with small keys
50. What is the worst case complexity of selection sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: D.O(n2)
51. What is the advantage of selection sort over other sorting techniques?
A. It requires no additional storage space
B. It is scalable
C. It works best for inputs which are already sorted
D. It is faster than any other sorting technique
Answer: A.It requires no additional storage space
52. What is the average case complexity of selection sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: D.O(n2)
53. What is the disadvantage of selection sort?
A. It requires auxiliary memory
B. It is not scalable
C. It can be used for small keys8
D. It takes linear time to sort the elements
Answer: B.It is not scalable
54. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sortrespectively are,
A. 5 and 4
B. 4 and 5
C. 2 and 4
D. 2 and 5
Answer: A.5 and 4
55. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The numberof iterations in selection sort and bubble sort respectively are,
A. 5 and 4
B. 1 and 4
C. 0 and 4
D. 4 and 1
Answer: D.4 and 1
56. What is the best case complexity of selection sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Answer: D.O(n2)
57. Shell sort is also known as
A. diminishing decrement sort
B. diminishing increment sort
C. partition exchange sort
D. diminishing insertion sort
Answer: B.diminishing increment sort
58. Statement 1: Shell sort is a stable sorting algorithm.Statement 2: Shell sort is an in-place sorting algorithm.
A. Both statements are true
B. Statement 2 is true but statement 1 is false
C. Statement 2 is false but statement 1 is true
D. none
Answer: B.Statement 2 is true but statement 1 is false
59. Shell sort is applied on the elements 27 59 49 37 15 90 81 39 and the chosen decreasing sequence of increments is (5,3,1). The result after the first iteration will be
A. 27 59 49 37 15 90 81 39
B. 27 59 37 49 15 90 81 39
C. 27 59 39 37 15 90 81 49
D. 15 59 49 37 27 90 81 39
Answer: C.27 59 39 37 15 90 81 49
60. Shell sort is an improvement on
A. insertion sort
B. selection sort
C. binary tree sort
D. quick sort
Answer: A.insertion sort
61. An array that is first 7-sorted, then 5-sorted becomes
A. 7-ordered
B. 5-ordered
C. both 2-ordered and 5-ordered
D. both 7-ordered and 5-ordered
Answer: D.both 7-ordered and 5-ordered
62. If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2k–1) are used in a Shell sortimplementation, then the best case time complexity will be
A. O(nlogn)
B. O(n)
C. O(n2)
D. O(logn)
Answer: A.O(nlogn)
63. Records R1, R2, R3,.. RN with keys K1, K2, K3,.. KN are said to be h-ordered, if
A. Ki <= Ki+h for 1<= i*h <= N
B. Kh <= Ki+h for 1<= i <= N
C. Ki <= Kh for 1<= i <= h
D. Ki <= Ki+h for 1<= i <= N-h
Answer: D.Ki <= Ki+h for 1<= i <= N-h
64. Which of the following is true?
A. Heap sort
B. Smooth sort
C. Quick sort
D. LSD radix sort
Answer: D.LSD radix sort
66. What is the worst case time complexity of LSD radix sort?
A. O(nlogn)
B. O(wn)
C. O(n)
D. O(n + w)
Answer: B.O(wn)
67. LSD radix sort requires passes to sort N elements.
A. (w/logR)
B. N(w/logR)
C. (w/log(RN))
D. (wN/log(N))
Answer: A.(w/logR)
68. Which of the following is false?
A. LSD radix sort is an integer sorting algorithm
B. LSD radix sort is a comparison sorting algorithm
C. LSD radix sort is a distribution sort
D. LSD radix sort uses bucket sort
Answer: B.LSD radix sort is a comparison sorting algorithm
69. Which of the following sorting algorithm is stable?
A. Heap sort
B. Selection sort
C. In-place MSD radix sort
D. LSD radix sort
Answer: D.LSD radix sort
70. Which of the following should be used to sort a huge database on a fixed-length key field?
A. Insertion sort
B. Merge sort
C. LSD radix sort
D. Quick sort
Answer: C.LSD radix sort
71. Which of the following is a combination of LSD and MSD radix sorts?
A. Forward radix sort
B. 3-way radix quick sort
C. Trie base radix sort
D. Flash sort
Answer: A.Forward radix sort
72. Which of the following is true for the LSD radix sort?
A. works best for variable length strings
B. accesses memory randomly
C. inner loop has less instructions
D. sorts the keys in left-to-right order
Answer: B.accesses memory randomly
73. Which scheme uses a randomization approach?
A. hashing by division
B. hashing by multiplication
C. universal hashing
D. open addressing
Answer: C.universal hashing
74. Which hash function satisfies the condition of simple uniform hashing?
A. h(k) = lowerbound(km)
B. h(k)= upperbound(mk)
C. h(k)= lowerbound(k)
D. h(k)= upperbound(k)
Answer: A.h(k) = lowerbound(km)
75. What is the hash function used in the division method?
A. h(k) = k/m
B. h(k) = k mod m
C. h(k) = m/k
D. h(k) = m mod k
Answer: B.h(k) = k mod m
76. What can be the value of m in the division method?
A. Any prime number
B. Any even number
C. 2p – 1
D. 2p
Answer: A.Any prime number
77. Which scheme provides good performance?
A. open addressing
B. universal hashing
C. hashing by division
D. hashing by multiplication
Answer: B.universal hashing
78. Using division method, in a given hash table of size 157, the key of value 172 be placed at position
A. 19
B. 72
C. 15
D. 17
Answer: C.15
79. How many steps are involved in creating a hash function using a multiplication method?
A. 1
B. 4
C. 3
D. 2
Answer: D.2
80. What is the hash function used in multiplication method?
A. h(k) = floor( m(kA mod 1))
B. h(k) = ceil( m(kA mod 1))
C. h(k) = floor(kA mod m)
D. h(k) = ceil( kA mod m)
Answer: A.h(k) = floor( m(kA mod 1))
81. What is the advantage of the multiplication method?
A. only 2 steps are involved
B. using constant
C. value of m not critical
D. simple multiplication
Answer: C.value of m not critical
82. What is the table size when the value of p is 7 in multiplication method of creating hash functions?
A. 14
B. 128
C. 49
D. 127
Answer: B.128
83. What is the average retrieval time when n keys hash to the same slot?
A. Theta(n)
B. Theta(n2)
C. Theta(nlog n)
D. Big-Oh(n2)
Answer: A.Theta(n)