Explore topic-wise InterviewSolutions in .

Correct CHOICE is (a) CREATE one node pointing to a STACK

For explanation: When an operand is encountered, create one node trees and push it on to the stack. When an operator is encountered, POP the pointers from last two trees from the stack.

Right answer is (d) free

Easiest EXPLANATION - In Binary TREES, NODES are created by calling MALLOC and they are deleted by calling free.

The correct CHOICE is (a) postfix expression

For explanation: A postfix expression is CONVERTED into an expression TREE by READING one symbol at a TIME and constructing a tree respectively.

The correct ANSWER is (B) false

For explanation: All INFIX, prefix and postfix EXPRESSIONS can be made into an expression tree using appropriate ALGORITHMS.

Correct choice is (d) O(√N)

The BEST I can EXPLAIN: The average depth of a BINARY expression TREE is mathematically found to be O(√N).

Correct CHOICE is (b) INFIX EXPRESSION

For EXPLANATION: It is an infix expression because the FORMAT of an infix expression is given by operand-operator-operand.

The correct CHOICE is (c) BINARY tree

The BEST explanation: The EXPRESSION tree is a binary tree. It contains operands at leaf nodes and REMAINING nodes are filled with operators. The operands and the operators can be arranged in any order (ascending, descending).

Correct CHOICE is (b) only operators

Best EXPLANATION: The nodes other than leaves always contain only operators. There cannot be any OPERAND in those nodes.

Right option is (b) Jon BENTLEY

Explanation: Jon Bentley found k-d trees. Rudolf BAYER found RED black trees. Arne ANDERSSON found AA- trees.

Correct answer is (a) True

To EXPLAIN: BRANCHING on ODD LEVELS is done with respect to the FIRST key and branching on even levels is done with respect to the second key in a 2-d tree.

The correct answer is (C) O(√N+M)

Easy EXPLANATION - For a perfectly balanced k-d tree, the RANGE QUERY could TAKE O(√N+M) in the worst case to report M matches.

Right answer is (b) range queries

The EXPLANATION is: Several range queries are POSSIBLE on a k-d tree. ONE of the range queries is KNOWN as a partial match query.

Correct answer is (a) pruning

The best explanation: Pruning is eliminating irrelevant trees. Partial RESULTS are KEEPING best results and UPDATING. TRAVERSAL is visiting all the nodes of a TREE.

Correct answer is (c) 3

Easiest explanation - THREE IMPORTANT concepts are available in finding the nearest NEIGHBOUR. They are partial results, PRUNING, traversal ORDER.

Right answer is (c) O(2^d log N)

To EXPLAIN: The run TIME of finding the nearest neighbour in a KD TREE is given as O(2^d log N) where 2^d is the time taken to search the neighbourhood.

Correct answer is (a) O(N)

The EXPLANATION is: The worst CASE ANALYSIS of finding the nearest neighbour in a k-d tree is mathematically FOUND to be O(N).

Right answer is (C) (30,40),(5,25),(10,12),(70,70),(50,30),(35,45)

EXPLANATION: The correct sequence of INSERTION of the above GIVEN TREE is (30,40),(5,25),(10,12),(70,70),(50,30),(35,45). The insertion is given by, first left, then right.

The correct answer is (d) K-d TREES

Explanation: K-d trees are the simplest DATA structure that supports RANGE SEARCHING and also it achieves the respectable running time.

Correct answer is (b) odd

For explanation: In a TWO- dimensional k-d TREE (i.e.) 2-d tree, the root is arbitrarily CHOSEN to be an odd level and it APPLIES to all 2-d TREES.

Correct answer is (a) true

Best explanation: Insertion of elements in a 2-d tree is SIMILAR to that of a BINARY SEARCH tree. HENCE, it is a trivial EXTENSION of the binary search tree.

The correct answer is (b) O(N LOG N)

Easy explanation - A PERFECTLY balanced 2-d tree can be CONSTRUCTED in O(N log N) TIME. This value is computed mathematically.

Right choice is (b) false

To explain: EFFICIENCY of bin depends upon the LOCATION and size of QUERY and candidates. ALSO, the smaller is the query rectangle the BETTER is the query efficiency.

Correct choice is (b) O(m)

EASY explanation - The process of insertion BECOMES faster in the CASE when the number of CANDIDATES are equally DISTRIBUTED among the bins. In such a case the query operation becomes O(m). It is practically faster than deletion in this case.

Right option is (b) O(m)

The best I can EXPLAIN: The process of DELETION becomes faster in a case when the number of candidates are equally distributed AMONG the bins. In such a case the QUERY operation becomes O(m). It is practically SLOWER than insertion in this case.

The correct CHOICE is (d) study of algorithms RELATED to geometry

For explanation: COMPUTATIONAL geometry deals with the study of algorithms which can be expressed in TERMS of geometry. Bin data structure is an example of it.

Right CHOICE is (a) O(1)

The EXPLANATION is: The WORST case in a bin INSERT operation occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(1).

The correct choice is (b) O(n)

EASIEST explanation - The WORST CASE in a BIN delete operation OCCURS when all the candidates are concentrated in one bin. So in this case the time complexity is O(n).

Correct answer is (B) O(n)

Best explanation: The worst case in a BIN query occurs when all the candidates are concentrated in ONE bin. So in this case the time COMPLEXITY is O(n).

The correct option is (a) true

For explanation: BIN is an EXAMPLE of a RANGE query data structure. It is because it efficiently answers any number of queries on any subset of the input.

Right answer is (c) to have efficient region query

The best I can explain: Bin DATA STRUCTURE allows us to have efficient region queries. A FREQUENCY of bin is increased by one each time a data point falls into a bin.

Right answer is (b) the TWO cities should have a two-way connection

The best I can EXPLAIN: If the two towns are in the same COUNTRY and have a two-way road connection between them, it satisfies equivalence property.

The CORRECT CHOICE is (c) O(N log N)

Easy EXPLANATION - The total time spent for N-1 merges in a dynamic EQUIVALENCE problem is mathematically found to be O(N log N).

Right choice is (a) leaf to root

To explain: One of the lemmas STATE that, in the Union/Find algorithm, the ranks of the NODES on a path will increase MONOTONICALLY from leaf to root.

Correct CHOICE is (c) N/2^r

For EXPLANATION: Each NODE of a RANK r is the root of a subtree of at least 2^r. THEREFORE, there are at most N/2^r disjoint subtrees.

Correct choice is (a) true

The best explanation: By the INDUCTION hypothesis, each tree has at LEAST 2^r – 1 descendants, giving a total of 2^r and ESTABLISHING the lemma.

Correct choice is (B) O(LOG N)

For EXPLANATION: If the Unions are PERFORMED by HEIGHT, the depth of any tree is calculated to be O(log N).

Right choice is (d) PATH COMPRESSION

Explanation: Path compression is one of the EARLIEST forms of self-adjustment used in extremely important strategies USING theoretical explanations.

Correct option is (a) A(1,i) = i+1 for i>=1

Easy EXPLANATION - The Ackermann’s function is defined as A(1,i) = i+1 for i>=1. This FORM in TEXT grows FASTER and the inverse is SLOWER.

Right CHOICE is (C) Find operation

The best explanation: Path compression ALGORITHM is performed during find operation and is independent of the strategy used to perform unions.