NEW
Font size
WorksheetsDSA QUIZ-2
Total questions: 25
Worksheet time: 12mins
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)
Ω (n2)
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
Which type of traversal of binary search tree outputs the value in sorted order?
a) Pre-order
b) In-order
c) Post-order
d) both a) & b)
A binary search tree is formed from the sequence 6, 9, 1, 2, 7, 14, 12, 3, 8, 18. The
minimum number of nodes required to be added in to this tree to form an extended binary tree is?
a) 3
b) 6
c) 8
d) 11
In a full binary tree, every internal node has exactly two children. A full binary tree
with 2n+1 nodes contains
a) n leaf node
b) n-1 internal nodes
c) n-1 leaf nodes
d) n internal nodes
the run time for traversing all the nodes of a binary search tree with n nodes and
printing them in an order is
a) O(nlog(n))
b) O(n)
c) O(√n)
d) O(log(n))
If n numbers are to be sorted in ascending order in O(nlogn) time, which of the
following tree can be used
a) Binary tree
b) Binary search tree
c) Max-heap
d) Min-heap
A threaded binary tree is a binary tree in which every node that does not have right
child has a thread to its
a) Pre-order successor
b) In-order successor
c) In-order predecessor
d) Post-order successor
In which of the following tree, parent node has a key value greater than or equal to
the key value of both of its children?
a) Binary search tree
b) Threaded binary tree
c) Complete binary tree
d) Max-heap
In-order traversing a tree resulted E A C K F H D B G; the pre-order traversal
would return.
A. FAEKCDBHG
B. FAEKCDHGB
C. EAFKHDCBG
D. FEAKDCHBG
If node N is a terminal node in a binary tree then its .........
A. Right tree is empty
B. Left tree is empty
C. Both left & right sub trees are empty
D. Root node is empty
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height
of a tree with a single node is 0.
A. 2
B. 3
C. 4
D. 5
Which of the below diagram is following AVL tree property?
a) only i
b) only i and ii
c) only ii
d) none of the mentioned
If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :
a) Less than 1
b) Less than n
c) Less than m
d) Less than n/2
When is it appropriate to use direct addressing?
A. When the array is comparatively large
B. When the universe U of keys is reasonably small
C. When the universe U of keys is reasonably large
D. When the array is comparatively small
What is the time complexity to delete an element from the direct address table?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)
null, null, 77, 16, null, 34, 93, 2, 51, 80
77, 16, 34, 93, 2, 51, 80
80, 51, 2 , 93, 34, null, 16, 77, null, null
80, 51, 2, 93, 34, 16, 77
