# Data Structures MCQ| Non Linear Data Structures – Graphs

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

A. True

B. False

C. none

D. none

A. 15

B. 3

C. 1

D. 11

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

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

A. 24

B. 21

C. 25

D. 16

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

A. v=e

B. v = e+1

C. v + 1 = e

D. v = e-1

A. 1,2,3

B. 2,3,4

C. 2,4,5

D. 1,3,5

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

## 13. Which of the following ways can be used to represent a graph?

B. Incidence Matrix

D. No way to represent

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

A. 1

B. 2

C. 3

D. 4

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

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

A. n-2

B. n

C. 2

A. O(E*E)

B. O(V*V)

C. O(E)

D. O(V)

A. (V*(V-1))/2

B. (V*(V+1))/2

C. (V+1)C2

D. (V-1)C2

A. cubic

C. linear

D. logarithmic

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

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

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(1)

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(1)

A. O(nlogn), O(logn)

B. O(logn), O(nlogn)

C. O(n), O(1)

D. O(1), O(n)

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

A. 5

B. 2

C. 3

D. 4

A. 90 and 99

B. 90 and 94

C. 89 and 99

D. 89 and 94

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(n2)

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

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

A. 1

B. 3

C. 4

D. 2

A. 90 and 99

B. 90 and 100

C. 89 and 94

D. 94 and 99

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(n2)

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

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(n2)

A. O(nlogn)

B. O(logn)

C. O(n)

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

A. 4

B. 2

C. 1

A. O(nlogn)

B. O(logn)

C. O(n)

D. O(n2)

A. 4

B. 2

C. 1

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

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

A. O(nlogn)

B. O(logn)

C. O(n)

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

A. O(nlogn)

B. O(logn)

C. O(n)

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

A. 5 and 4

B. 4 and 5

C. 2 and 4

D. 2 and 5

A. 5 and 4

B. 1 and 4

C. 0 and 4

D. 4 and 1

A. O(nlogn)

B. O(logn)

C. O(n)

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

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

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

A. O(nlogn)

B. O(n)

C. O(n2)

D. O(logn)

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

A. Heap sort

B. Smooth sort

C. Quick sort

A. O(nlogn)

B. O(wn)

C. O(n)

D. O(n + w)

A. (w/logR)

B. N(w/logR)

C. (w/log(RN))

D. (wN/log(N))

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

## 69. Which of the following sorting algorithm is stable?

A. Heap sort

B. Selection 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

D. Quick sort

D. Flash 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

## 73. Which scheme uses a randomization approach?

A. hashing by division

B. hashing by multiplication

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)

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

## 77. Which scheme provides good performance?

B. universal hashing

C. hashing by division

D. hashing by multiplication

A. 19

B. 72

C. 15

D. 17

A. 1

B. 4

C. 3

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

A. 14

B. 128

C. 49

D. 127

A. Theta(n)

B. Theta(n2)

C. Theta(nlog n)

D. Big-Oh(n2)