CS8391 DATA STRUCTURES

CS8391 Data Structures

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

2. What is the best case for linear search?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(1)

Answer: d

3. What is the worst case for linear search?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(1)

Answer: c

4. What is the best case and worst case complexity of ordered linear search?

a) O(nlogn), O(logn)

b) O(logn), O(nlogn)
1 www.studymaterialz.in
 CS8391 DATA STRUCTURES

c) O(n), O(1)

d) O(1), O(n)

Answer: d

5. a) Print the duplicate elements in the array

b) Print the element with maximum frequency

c) Print the unique elements in the array

d) Prints the element with minimum frequnecy

Answer: a

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

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

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

2 www.studymaterialz.in
 CS8391 DATA STRUCTURES

9. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding
array 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

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

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

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

13. Binary Search can be categorized into which of the following?

a) Brute Force technique

3 www.studymaterialz.in
 CS8391 DATA STRUCTURES

b) Divide and conquer

c) Greedy algorithm

d) Dynamic programming

Answer: b

14. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element
is found?

a) 1

b) 3

c) 4

d) 2

Answer: d

15. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid
values(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

16. What is the time complexity of binary search with iteration?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

Answer: b

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

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

19. What is the worst case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

Answer: d

20. What is the average case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

Answer: d

21. Which of the following is not an advantage of optimised bubble sort over other sorting techniques
in 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

5 www.studymaterialz.in
 CS8391 DATA STRUCTURES

22. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How many
iterations will be done to sort the array?

a) 4

b) 2

c) 1

d) 0

Answer: a

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

24. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many
iterations will be done to sort the array with improvised version?

a) 4

b) 2

c) 1

d) 0

Answer: b

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

26. In the following scenarios, when will you use selection sort?
6 www.studymaterialz.in
 CS8391 DATA STRUCTURES

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

27. What is the worst case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

Answer: d

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

29. What is the average case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

Answer: d

30. What is the disadvantage of selection sort?

a) It requires auxiliary memory

b) It is not scalable

c) It can be used for small keys

7 www.studymaterialz.in
 CS8391 DATA STRUCTURES

d) It takes linear time to sort the elements

Answer: b

31. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort
respectively are,

a) 5 and 4

b) 4 and 5

c) 2 and 4

d) 2 and 5

Answer: a

32. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number
of 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

33. What is the best case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

Answer: d

34. Shell sort is also known as _____________

a) diminishing decrement sort

b) diminishing increment sort

c) partition exchange sort

d) diminishing insertion sort

Answer: b
8 www.studymaterialz.in
 CS8391 DATA STRUCTURES

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

Answer: b

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

37. Which condition will correctly implement the while loop?

a) k >= j && y < elements[k- span]

b) k >= span || y < elements[k + span]

c) k >= j || y < elements[k + span]

d) k >= span && y < elements[k- span]

Answer: d

38. Shell sort is an improvement on ____

a) insertion sort

b) selection sort

c) binary tree sort

d) quick sort

Answer: a

39. An array that is first 7-sorted, then 5-sorted becomes _________

9 www.studymaterialz.in
 CS8391 DATA STRUCTURES

a) 7-ordered

b) 5-ordered

c) both 2-ordered and 5-ordered

d) both 7-ordered and 5-ordered

Answer: d

40. If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2k–1) are used in a Shell sort implementation,
then the best case time complexity will be ________

a) O(nlogn)

b) O(n)

c) O(n2)

d) O(logn)

Answer: a

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

42. Which of the following is true?

a) Shell sort’s passes completely sort the elements before going on to the next-smallest gap while Comb
sort’s passes do not completely sort the elements

b) Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap like in
Comb sort

c) Comb sort’s passes completely sort the elements before going on to the next-smallest gap like in Shell sort

d) Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap while
Comb sort’s passes completely sort the elements

Answer: a

43. Which of the following is the distribution sort?

a) Heap sort
10 www.studymaterialz.in
 CS8391 DATA STRUCTURES

b) Smooth sort

c) Quick sort

d) LSD radix sort

Answer: d

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

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

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

47. Which of the following sorting algorithm is stable?

a) Heap sort

b) Selection sort

c) In-place MSD radix sort

d) LSD radix sort

11 www.studymaterialz.in
 CS8391 DATA STRUCTURES

Answer: d

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

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

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

51. Which scheme uses a randomization approach?

a) hashing by division

b) hashing by multiplication

c) universal hashing

d) open addressing

Answer: c

52. Which hash function satisfies the condition of simple uniform hashing?

12 www.studymaterialz.in
 CS8391 DATA STRUCTURES

a) h(k) = lowerbound(km)

b) h(k)= upperbound(mk)

c) h(k)= lowerbound(k)

d) h(k)= upperbound(k)

Answer: a

53. a) 14963

b) 14392

c) 12784

d) 14452

Answer: d

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

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

56. Which scheme provides good performance?

a) open addressing

b) universal hashing

c) hashing by division

d) hashing by multiplication

13 www.studymaterialz.in
 CS8391 DATA STRUCTURES

Answer: b

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

58. How many steps are involved in creating a hash function using a multiplication method?

a) 1

b) 4

c) 3

d) 2

Answer: d

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

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

14 www.studymaterialz.in
 CS8391 DATA STRUCTURES

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

62. What is the value of h(k) for the key 123456?

Given: p=14, s=2654435769, w=32

a) 123

b) 456

c) 70

Answer: d

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

15 www.studymaterialz.in