Data Structure and Algorithm Analysis
Questions 91 to 100
91.

For the
bubble sort algorithm, what is the time complexity of the best/worst case?
(assume that the computation stops as soon as no more swaps in one pass)


92.

For the
quick sort algorithm, what is the time complexity of the best/worst case?


93.

In an
arbitrary tree ( not a search tree) of order M. Its size is N, and its height
is K. The computation time needed to find a data item on T is


94.

When we
organize our data as an ordered list, what is the time complexity of
inserting/deleting a data item to/from the list?


95.

Five
statements about Btrees are below. Four of them are correct. Which one is INCORRECT?


96.

For any
Btree of height H (H>1), after inserting a new key, is it possible for a
key, K, which was located in a leafnode to move up to the root in this
regard which of the following is correct?


97.

When we say
the order of a tree is M, we mean


98.

T is a
search tree of order M, its size is N, and its height is K. The computation
time needed to INSERT/DELETE a data item on T is


99.

Suppose
that we have a data file containing records of famous people, and we need to
build a hash table to find a record from the person's birthday. The size of
the hash table is 4096. The following are hash functions which convert a
birthday to an integer. Which of the following function is the best?


100.

What is
collision resolution with open addressing?

Answers
91.

Answer : (a)
Reason: Best Case is the one in which it is already
sorted, and hence it takes O(n) time, otherwise it takes O(n^{2})
time.

92.

Answer : (d)
Reason: The worst case here is, if the list is
already sorted in descending order and we want to sort it in ascending order.
In this case it takes O(n^{2}) time. Otherwise it takes O( n * log(n)
) time.

93.

Answer : (c)
Reason: As the size is N, we have to traverse almost
entire tree to look for a node ( because it is not a binary search tree). And
hence it takes O(N) time.

94.

Answer : (b)
Reason: Because we have to search for
deletion/insertion both in the ordered list. And the algorithm takes O(n) in
this case[ best option in the given options].

95.

Answer : (c)
Reason: As Btree is not a binary tree, but a
balanced mway tree

96.

Answer : (e)
Reason: Yes, this is the best option given because,
if the insertion in a node causes the node to contain the keys equal to order
of the tree, then the middle key of the node will be passed to one level up
(it can be a root also ). A common mistake is to tick D. But, the condition
stated in D is too strong. We were only asking whether a key can move up to
the root, and we were not asking whether a key can become a new root!

97.

Answer : (c)
Reason: Here in the answer ‘can’ is most important.
That is “every nonleaf node ‘can’
have at most M subtrees”

98.

Answer : (e)
Reason: In this case it is a search tree ( BST ).
And hence the search time is proportional to the height of the tree. This
answer assumes that M < K If M >> K, you could answer B However, M
is a fixed number, but K grows when the size of data grows. Therefore, e is a
better answer.

99.

Answer : (d)
Reason: With the answer ‘a’ some of the entries in
the hash table, say 30004000, are never used. A similar problem also applies
to ‘b’, ‘e’. In the answer ‘c’, 4096 is a bad choice. It should a prime
number.

100.

Answer : (c)
Reason: The meaning of the open addressing it self
is to look and probe for unoccupied and open location to place the incoming
key.

Great and Useful Article.
ReplyDeleteJava Online Course
Java Online Training
Java EE training
Java Course in Chennai
Java Training in Chennai
Java Training Institutes in Chennai
Java Interview Questions
Java Interview Questions