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?
B) O(N log N)
C) O( log N)
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(2d 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?
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?
B) partial results
C) freeing space
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?
B) O(log 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.
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?
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?
B) O(N log N)
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.
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?
C) depends on subtrees
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?
B) binary search 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.
15. 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.