DSA QUIZ-2

Which of the following is not a stable sorting algorithm?

• Bubble Sort

• Merge Sort

• Insertion Sort

• Selection Sort

Running merge sort on an array of size n which is already sorted is

• O(n)

• O(logn)

• O(n logn)

• O(n^2)

Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general?

• Insertion sort

• Heap Sort

• Selection sort

• None

The lower bound on the number of comparisons performed by comparison-based sorting algorithm is

• Ω (1)

• Ω (n)

• Ω (nlogn)

• Ω (n²)

Which of the following is not a limitation of binary search algorithm?

• must use a sorted array

• requirement of sorted array is expensive when a lot of insertion and deletions are needed

• there must be a mechanism to access middle element directly

• binary search algorithm is not efficient when the data elements more than 1500.

State True or False for internal sorting algorithms.

i) Internal sorting are applied when the entire collection if data to be sorted is small enough that the sorting can take place within main memory.

ii) The time required to read or write is considered to be significant in evaluating the performance of internal sorting.

• i-True, ii-True

• i-True, ii-False

• i-False, ii-True

• i-False, ii-False

The height of a BST is given as h. Consider the height of the tree as the no. of edges in the longest path from root to the leaf. The maximum no. of nodes possible in the tree is?

• 2^(h-1) -1

• 2^(h+1) -1

• 2^h +1

• 2^(h-1) +1

Suppose a binary tree is constructed with n nodes, such that each node has exactly

either zero or two children. The maximum height of the tree will be?

• (n+1)/2

• (n-1)/2

• n/2 -1

• (n+1)/2 -1

Which of the following statement about binary tree is CORRECT?

• a) Every binary tree is either complete or full

• b) Every complete binary tree is also a full binary tree

• c) Every full binary tree is also a complete binary tree

• d) A binary tree cannot be both complete and full

Suppose we have numbers between 1 and 1000 in a binary search tree and want to

search for the number 363. Which of the following sequence could not be the

sequence of the node examined?

• a) 2, 252, 401, 398, 330, 344, 397, 363

• b) 924, 220, 911, 244, 898, 258, 362, 363

• c) 925, 202, 911, 240, 912, 245, 258, 363

• d) 2, 399, 387, 219, 266, 382, 381, 278, 363