Data
structures and algorithms multiple choice questions with answers,
important interview questions in data structures, data structures
questions for entrance exams, frequently asked questions in data
structures and algorithms, GATE questions in data structures with
explained answers
Data Structures and Algorithms Multiple Choice Questions
SET 10
1. Consider
a perfect binary tree of height 5. Which of the following are the minimum and
maximum number of nodes in the right sub-tree of the root?
a) 32
b) 31
c) 16
d) 9
Click here to view answer and explanation
Ans : (b)
|
Answer: (b) 31
A
perfect binary tree is a
binary tree in which all interior nodes have two children and all leaves have the same depth or same level. In this tree each level
contains the maximum number of nodes, ie., every level is completely full of
nodes.
The
number of nodes in a perfect binary tree = 2h+1-1
As
per the question, we need to find the number of nodes in the right sub-tree
alone. Also, the right sub-tree is at height less than that of original tree.
Hence, the number of nodes = 2h-1.
For a perfect binary tree, the minimum and
maximum number of nodes will be 2h+1-1. Hence, for the right
sub-tree alone, they are 2h-1.
|
2. Rank the
following functions by increasing order of growth; (For example, the correct
ordering of n2, n4, n, n3 is n, n2, n3, n4.)
|
f1
= (n!)1/n
|
f2
= ((n)n)1/2
|
|
f3
= log nn
|
f4
= n log n
|
a) f1, f2, f3, f4
b) f1, f3, f4, f2
c) f1, f2, f4, f3
d) f2, f1, f3, f4
Click here to view answer and explanation
Ans : (b)
|
Answer: (b) f1,
f3, f4, f2
|
3. What is a
collision in a hash table implementation of a symbol table? Choose the most
appropriate one.
a) Two key-value
pairs that have equal keys but different values.
b) Two key-value
pairs that have different keys and hash to different indices.
c) Two key-value
pairs that have different keys but hash to the same index.
d) Two key-value
pairs that have equal keys but hash to different indices.
Click here to view answer and explanation
Ans : (c)
|
Answer: (c) Two
key-value pairs that have different keys but hash to the same index
A
collision occurs when two key-value pairs have different keys but hash to the
same index.
|
4. A linear-probing
hash table of length 10 uses the hash function h(x) = x mod 10. After inserting
six integer keys into an initially empty hash table, the array of keys is:
Which of the following
insertion sequences resulting in the above hash table? Assume that the length
of the hash table does not change during the insertions.
a) 46, 42, 34, 52,
23, 33
b) 34, 42, 23, 52,
33, 46
c) 46, 34, 42, 23,
52, 33
d) 42, 46, 33, 23,
34, 52
Click here to view answer and explanation
Ans : (c)
|
Answer: (c) 46,
34, 42, 23, 52, 33
46
mod 10 = 6. Key 46 is stored at index 6
34
mod 10 = 4. Key 34 is stored at index 4
42
mod 10 = 2. Key 42 is stored at index 2
23
mod 10 = 3. Key 23 is stored at index 3
52
mod 10 = 2. Index 2 not empty. Linear hash the key ( (i+1) mod 10).
(52+1)
mod 10 = 3. Index 3 not empty. Linear probe the key until find an index which
is empty. The next free index is 5. Hence, key 52 is stored at index 5.
33
mod 10 = 3. Index 3 not empty. Linear probe to find the next free space.
Key
33 is stored at index 7.
|
5. Which of the
following algorithms is parsimonious?
a) Insertion sort
b) Selection sort
c) Heap sort
d) All of the above
Click here to view answer and explanation
Ans : (a)
|
Answer: (a) Insertion
sort
A
sorting algorithm is said to be parsimonious if it never compare the same
pair of input values twice (Assuming that all input values are distinct).
Insertion
sort is parsimonious.
|
*************************
Interview questions and answers in data structure and algorithms
DSA quiz questions with answers explained
Solved true or false questions in DSA
Practice questions in data structures
Data structures and algorithms GATE exam questions
Why insertion sort is a parsimonious algorithm?
What is parsimonious sorting algorithm?
What is the time complexity of converting min heap into a max heap?
