This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “KD Tree”.

**1. Each level in a k-d tree is made of?**

A) dimension only**B) cutting and dimension**

C) color code of node

D) size of the level

Explanation: A k-d tree’s levels are made up of dimensions and cutting. For addition, deletion, and searching, cutting and measurements are used.

**2. What is the worst case of finding the nearest neighbour?****A) O(N)**

B) O(N log N)

C) O( log N)

D) O(N^{3})

Explanation: In a k-d tree, the worst-case analysis of finding the nearest neighbour is found to be O. (N).

**3. What is the run time of finding the nearest neighbour in a k-d tree?**

A) O(2+ log N)

B) O( log N)**C) O(2 ^{d} log N)**

D) O( N log N)

Explanation: In a kd tree, the time it takes to locate the nearest neighbour is O(2d log N), where 2d is the time it takes to search the neighbourhood.

**4. How many prime concepts are available in nearest neighbour search in a kd tree?**

A) 1

B) 2**C) 3**

D) 4

Explanation: There are three key rules to keep in mind when looking for your next-door neighbour. Partial performance, pruning, and traversal order are all factors.

**5. Reducing search space by eliminating irrelevant trees is known as?****A) pruning**

B) partial results

C) freeing space

D) traversing

Explanation: Pruning is the process of removing trees that are no longer useful. The best results are held and updated with partial results. Traversal is the process of visiting all of a tree’s nodes.

**6. Several kinds of queries are possible on a k-d called as?**A) partial queries

**B) range queries**

C) neighbour queries

D) search queries

Explanation: On a k-d tree, many range queries are possible. Partial match queries are one of the range queries.

**7. What is the time taken for a range query for a perfectly balanced tree?**

A) O(N)

B) O(log N)**C) O(√N+M)**

D) O(√N)

Explanation: The range question for a perfectly balanced k-d tree will take O(N+M) in the worst case to report M matches.

**8. The 2d search tree has the simple property that branching on odd levels is done with respect to the first key.****A) True**

B) False

Explanation: In a 2-d tree, branching on odd levels is done in relation to the first key, and branching on even levels is done in relation to the second key.

**9. Who invented k-d trees?**

A) Arne Andersson**B) Jon Bentley**

C) Jon Von Newmann

D) Rudolf Bayer

Explanation: K-d trees were discovered by Jon Bentley. Rudolf Bayer discovered a grove of red black trees. AA- trees were discovered by Arne Andersson.

**10. What will be the correct sequence of insertion for the following k-d tree?**

A) (30,40),(5,25),(70,70),(10,12),(50,30),(35,45)

B) (40,30),(5,25),(12,10),(70,70),(30,50),(45,35)**C) (30,40),(5,25),(10,12),(70,70),(50,30),(35,45)**

D) (40,30),(25,5),(12,10),(70,70),(50,30),(45,35)

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.

**11. In what time can a 2-d tree be constructed?**

A) O(N)**B) O(N log N)**

C) O(N^{2})

D) O(M log N)

Explanation: In O(N log N) time, a perfectly balanced 2-d tree can be created. This is a mathematically calculated value.

**12. Insertion into a 2-d tree is a trivial extension of insertion into a binary search tree.****A) true**

B) false

Explanation: In a two-dimensional tree, element insertion is close to that of a binary search tree. As a result, it’s a straightforward extension of the binary search tree.

**13. In a two-dimensional search tree, the root is arbitrarily chosen to be?**

A) even**B) odd**

C) depends on subtrees

D) 1

Explanation: The root of a two-dimensional k-d tree (i.e., 2-d tree) is randomly chosen to be an odd degree, and this holds true for all 2-d trees.

**14. Which of the following is the simplest data structure that supports range searching?**

A) Heaps

B) binary search trees

C) AA-trees**D) K-d trees**

Explanation: K-d trees are the most basic data structure that supports range searching and has a reasonable run time.

1**5. In a k-d tree, k originally meant?****A) number of dimensions**

B) size of tree

C) length of node

D) weight of node

Explanation: Initially, 2-d trees were created. Then, 3-d trees, 4-trees etc., where k meant the number of dimensions.

The k-d tree (short for k-dimensional tree) is a data structure for organising points in a k-dimensional space that partitions space. K-d trees are a useful data structure for a variety of applications, including multidimensional search (e.g. range searches and nearest neighbour searches) and point cloud development. Binary space partitioning trees are a subset of k-d trees.