adplus-dvertising
frame-decoration

Question

Any decision tree that sorts n elements has height ..............

a.

Ω(log n)

b.

Ω(n)

c.

Ω(n log n)

d.

Ω(n2)

Answer: (c).Ω(n log n)

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Any decision tree that sorts n elements has height ..............

Similar Questions

Discover Related MCQs

Q. Red-black trees are one of many Search tree schemes that are "balanced” in order to guarantee that basic dynamic-set operations take ............. time in the worst case.

Q. Dijkstra’s algorithm is based on

Q. Match the following with respect to algorithm paradigms:
List-I                              List-II
a. Merge sort                 i. Dynamic Programming
b. Huffman coding       ii. Greedy approach
c. Optimal polygon triangulation iii. Divide and conquer
d. Subset sum problem          iv. Back tracking

Codes:
     a   b  c   d

Q. Abstraction and encapsulation are fundamental principles that underlie the object oriented approach to software development. What can you say about the following two statements?

I. Abstraction allows us to focus on what something does without considering the complexities of how it works.
II. Encapsulation allows us to consider complex ideas while ignoring irrelevant detail that would confuse us.

Q. Which of the following statement(s) with regard to an abstract class in JAVA is/are TRUE?

I. An abstract class is one that is not used to create objects.
II. An abstract class is designed only to act as a base class to be inherited by other classes.

Q. With respect to a loop in the transportation table, which one of the following is not correct?

Q. At which of the following stage(s), the degeneracy do not occur in transportation problem?
(m, n represents number of sources and destinations respectively)

(a) While the values of dual variables ui and vj cannot be computed.
(b) While obtaining an initial solution, we may have less than m + n -1 allocations.
(c) At any stage while moving towards optimal solution, when two or more occupied cells with the same minimum allocation become unoccupied simultaneously.
(d) At a stage when the no. of +ve allocation is exactly m + n - 1.

Q. Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation cannot be implemented in O(1) time ?

Q. Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a – c| ≤ 1 or |b–d| ≤ 1. The number of edges in this graph is

Q. The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is

Q. Consider the following statements :

S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.

Which of the following is correct ?

Q. Given the following prefix expression:

* + 3 + 3 ↑ 3 + 3 3 3

What is the value of the prefix expression?

Q. A priority queue is implemented as a max-heap. Initially, it has five elements. The level-order traversal of the heap is as follows:

20, 18, 15, 13, 12

Two new elements ‘10’ and ‘17’ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:

Q. If there are n integers to sort, each integer has d digits, and each digit is in the set  {1, 2, …, k}, radix sort can sort the numbers in:

Q. Match the following:

a. Prim’s algorithm                  i. O(V^2E)
b. Bellman-Ford algorithm     ii. O(VE lgV)
c. Floyd-Warshall algorithm   iii. O(E lgV)
d. Johnson’s algorithm           iv. O(V^3)

Where V is the set of nodes and E is the set of edges in the graph.

Codes :
     a    b   c   d

Q. Constructors have ............. return type.

Q. Method over-riding can be prevented by using final as a modifier at ...............

Q. Which of the following is a correct statement?

Q. Which of the following is not a correct statement?

Q. Given the following statements:

(a) To implement Abstract Data Type, a programming language require a syntactic unit to encapsulate type definition.
(b) To implement ADT, a programming language requires some primitive operations that are built in the language processor.
(c) C++, Ada, Java 5.0, C#2005 provide support for parameterised ADT.

Which one of the following options is correct?