ada viva qustions v t u.pdf (Size: 361.83 KB / Downloads: 2)
1) What is the time complexity of linear search?
Θ(n)
2) What is the time complexity of binary search?
Θ(log2n)
3) What is the major requirement for binary search?
The given list should be sorted.
4) What is binary search?
It is an efficient method of finding out a required item from a given list,
provided the list is in order.
The process is:
1. First the middle item of the sorted list is found.
2. Compare the item with this element.
3. If they are equal search is complete.
4. If the middle element is greater than the item being searched, this process
is repeated in the upper half of the list.
5. If the middle element is lesser than the item being searched, this process is
repeated in the lower half of the list.
5) What is parental dominance?
The key at each node is greater than or equal to the keys at its children.
6) What is heap?
A heap can be defined as a binary tree with keys assigned to its nodes
( one key per node) provided the following two conditions are met:
1 The tree’s shape requirement – The binary tree is essentially complete ( or
simply complete), that is, all its levels are full except possibly the last level,
where only some rightmost leaves may be missing.
2. The parental dominance requirement – The key at each node is greater than
or equal to the keys at its children.
2
7) What is height of Binary tree?
It is the longest path from the root to any leaf.
8) What is the time complexity of heap sort?
Θ( n logn)
9) What is Merge Sort?
Merge sort is an O (n log n) comparison-based sorting algorithm.
Where the given array is divided into two equal parts. The left part of the array
as well as the right part of the array is sorted recursively. Later, both the left
part and right part are merged into a single sorted array.
10) Who invented Merge Sort?
John Von Neumann in 1945.
11) On which paradigm is it based?
Merge-sort is based on the divide-and-conquer paradigm.
12) What is the time complexity of merge sort?
n log n.
13) What is the space requirement of merge sort?
Space requirement: Θ(n) (not in-place).
14) When do you say an algorithm is stable and in place?
Stable – if it retains the relative ordering.
In – place if it does not use extra memory.
15 ) Name the design strategy used in Selection Sort.
Brute force
16) Define Brute force strategy.
Brute force is a straight forward approach to solving a problem, usually
directly based on the problem’s statement and definitions of the concepts
involved.
3
17) What is the time complexity of Selection Sort algorithm?
(n2
)
18) Is Selection Sort Inplace?
Yes.
19) Is Selection Sort stable?
Yes.
20) Why is the name Selection Sort?
Algorithm selects the smallest number in the array and places it in its final
position the sorted array