DSA

DATA STRUCTURES AND ALGORITHMS
1) Fill in the blank with the most appropriate option:
Jack was given two non-negative functions f1 and f2. The function f1 (n) =O(f2(n)) if and only
if there exist a positive constant K and no such that?
Please choose a correct answer.

a) f1(n) ≤ K*f2 (n)
b) f1(n) = K*f2(n)
c) f1(n) ≥ K*f2(n)
d) f1(n) 1 = K*f2(n)
Answer : a) f1(n) ≤ K*f2 (n)
2) Sam has a problem K. The problem K is NP-complete if K is NP-hard. Which of the

following conditions satisfy this?
Please choose a correct answer.
a) K:NP
b) K directly proportional to NP
c) KENP
d) K=NP
Answer : d) K=NP
3) A hash table has 12 buckets and uses linear probing to insert values. The hash function is
K mod 8 and the key values are combined. The elements 11, 17, 14, 21, 31, 28, 51, 18 were
inserted into the hash table in that order, which location holds the 18.
a) 1
b) 4
c) 7
d) 2
Answer : 2
4) Consider the following sorting algorithm.
procedure ( Sort var a as array )
if (n = - 1) return a
Var 11
as
array - a[0] ... a[n/2]
var 12
as array = a[n/241] ... a[n]
Sort( 11 )
Sort( 12 )
return mergeArrays ( 11, 12 )
end procedure
Predict the name of the sorting algorithm from the following options.
Answer : Merge Sort Algorithm
5) Thomas has written an algorithm to sort an array. The algorithm is given below. Help
Thomas to get the running time required for this algorithm.
Choose from the following options:
list: array of items
n: size of list
for i = 1 to n - 1
min = 1 for j = 1+1 to n if list[j] ‹ list[min] then min - 33
end if end for
if indexMin 1 = i then swap list[min] and 1ist[1] end if end for
end procedure
a) O( log2 n) (logbase2)
b) O( n 10g2 n) (logbase2)
c) O(n)
d) O(n2)
Answer : d) O(n2) or O(n^2)
6. what will be the outcome of the below algorithm:
1. Begin from the first element, then perform a comparison with the following
element in the array.
2. If the present element is larger than the following element of the array, then
swap their positions.
3. If the present element is lesser than the following element of the array, shift
to the next element, and again repeat step 1.
Searching a particular
a) Reversing the given list
b) Sorting the list of given numbers
c) Addition of first N Numbers
d) searching a particular
Answer: b) Sorting the list of given numbers
7. What is the complexity of a binary search algorithm?

a) O(log n).
b) O(n log n)
c) O(n)
d) O(n2)
Answer: a) O(log n)
8. In linear search algorithm, the worst case manifests in which of the following
situations?
a) When item is the last element in the array
b) When item is the last element in the array or When item is not in the array
at all
c) None of the given options
Answer: b) When item is the last element in the array or When item is not in
the array at all
9. Which of the following solutions would you get when you apply Prim's
algorithm on a graph?
a) Traveling salesman problem
b) Graph coloring problem
c) Transitive closure of a graph
d) Minimum cost spanning tree
Answer: d) Minimum cost spanning tree
10. As a schedular, Operating System has to schedule different jobs that are
coming for processing. OS has to refine the precedence of each job for
scheduling. Which queue is used for storing and scheduling these jobs?
a) Linear Queue
b) Circular Queue
c) Dequeue
d) Priority Queue
Answer: d) Priority Queue
11. you want to store the following data of N students and porform the
operations like searching and sorting Which of the following you will use for
the same?
Answer: Array of Structures.
12. Which of the following solutions would you get when you apply Prim's
algorithm on a graph?
Answer: Minimum Spanning Tree (MST)
13. Which one of the following is an application of Stack Data Structure?
a) Managing function calls
b) The stock span problem
c) Arithmetic expression evaluation
d) All of the above
Answer: d) All of the above
14. Which one of the following is an application of Queue Data Structure?
a) When a resource is shared among multiple consumers.
b) When data is transferred asynchronously (data not necessarily received at
same rate as sent) between two processes
c) Load Balancing
d) All of the above
15. Which of the following sorting algorithms can be used to sort a random
linked list with minimum time complexity?
a) Insertion Sort
b) Quick Sort
c) Heap Sort
d) Merge Sort
Answer: d) Merge Sort
16. Which of the following is true about linked list implementation of stack?
a) In push operation, if new nodes are inserted at the beginning of linked list,
then in pop operation, nodes must be removed from end.
b) In push operation, if new nodes are inserted at the end, then in pop
operation, nodes must be removed from the beginning.
c) Both of the above
d) None of the above
Answer: a) In push operation, if new nodes are inserted at the beginning of
linked list, then in pop operation, nodes must be removed from end.
17. Which of the following is an advantage of adjacency list representation
over adjacency matrix representation of a graph?
a) In adjacency list representation, space is saved for sparse graphs.
b) DFS and BSF can be done in O(V+ E) time for adjacency list representation.
These operations take O(V^2) time in adjacency matrix representation. Here is
V and E are number of vertices and edges respectively.
c) Adding a vertex in adjacency list representation is easier than adjacency
matrix representation.
d) All of the above
18. Which of the following sorting algorithms follows the divide-and-conquer
approach?
a) Insertion sort
b) Bubble sort
c) Quick sort
Answer: c) Quick sort
19. A binary tree can be traversed in
a) Inorder
b) Preorder
c) Postorder
d) All of the above
20. Stack works on the principle of
a) last In First Out
b) Last In First Out
c) First In Middle Out
d) None of the Above
Answer: a) Last in First Out
21. When determining the efficiency of an algorithm, how would you measure
the space factor?
a) By counting the maximum memory needed by the algorithm
b) By counting the minimum memory owned by algorithm
c) By counting the average memory needed by the algorithm
d) By counting the maximum disk space made by the the algorithm
Answer: a) By counting the maximum memory needed by the algorithm
22. What is the complexity of a bubble sort algorithm?
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n)
Answer: c) O(n2)
23. You want to store n integer numbers inputed by the user and perform the
actions like searching and sorting on those numbers. Which of the following
you will use to store the data?
a) Structure
b) Union
c) Variable
d) Arrays
Answer: d) Arrays
24. The common term used to adding data item to a stack.
a) Insert
b) Commit
c) Push
Answer: c) push
25. what an extra key inserted at the end of the array is called?
a) Transposition
b) Stop key
c) Sentinel
d) Not sure
Answer: c) Sentinel

DSA

Uploaded by

Copyright:

Available Formats

DSA

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DSA

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES AND ALGORITHMS

1) Fill in the blank with the most appropriate option:

Please choose a correct answer.

Answer : a) f1(n) ≤ K*f2 (n)

2) Sam has a problem K. The problem K is NP-complete if K is NP-hard. Which of the

Answer : Merge Sort Algorithm

7. What is the complexity of a binary search algorithm?

You might also like