Binary Search Trees
44 Questions
3 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Which of the following is a common property checked while using loop invariants to prove correctness?

  • Termination
  • Maintenance
  • Optimization
  • Initialization (correct)

In a complete binary tree, how are the nodes filled?

  • Randomly
  • Right to left
  • Left to right (correct)
  • From the bottom level to the top

What is the worst-case time complexity of Quicksort?

  • O(n^2) (correct)
  • O(n log n)
  • O(n)
  • O(1)

Which of the following functions is O(n^2)?

<p>f(n) = 2n^2 + 3n + 1 (C)</p> Signup and view all the answers

Which of the following statements about Binary Search Trees (BST) is true?

<p>C. They always provide O(log n) performance for totally sorted data. (B)</p> Signup and view all the answers

What is the primary difference between a Binary Tree and a Binary Search Tree (BST)?

<p>B. In BST, all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root. (D)</p> Signup and view all the answers

What is the height of a valid Binary Search Tree (BST) with 7 nodes, built with totally sorted data?

<p>B. 6 (C)</p> Signup and view all the answers

Which of the following trees is a self-balancing tree?

<p>AVL Tree (C)</p> Signup and view all the answers

Which of the following statements about O-notation is true?

<p>O-notation provides an upper bound on the growth rate of a function. (C)</p> Signup and view all the answers

What is the key subroutine in the Quicksort algorithm?

<p>Partition (A)</p> Signup and view all the answers

In Radix Sort, the sorting begins with the digit at which position?

<p>Least significant digit (B)</p> Signup and view all the answers

Which of the following statements about Binary Search Trees (BST) is true?

<p>None of the above. (D)</p> Signup and view all the answers

What is the primary difference between a Binary Tree and a Binary Search Tree (BST)?

<p>In BST, all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root. (D)</p> Signup and view all the answers

What is the height of a valid Binary Search Tree (BST) with 7 nodes, built with totally sorted data?

<p>6 (A)</p> Signup and view all the answers

Which of the following traversal methods visits the root node last, followed by the left and right subtrees?

<p>Postorder (B)</p> Signup and view all the answers

What is the time complexity of Quicksort in the best case?

<p>O(n log n) (C)</p> Signup and view all the answers

Which of the following is NOT a characteristic of a Max-Heap?

<p>The value of any node is greater than or equal to the values of its children (C)</p> Signup and view all the answers

Which of the following is the correct formula to calculate the number of nodes in a complete binary tree of height h?

<p>$2^{h+1} - 1$ (D)</p> Signup and view all the answers

Which of the following trees is a self-balancing tree?

<p>AVL Tree (D)</p> Signup and view all the answers

Which of the following sorting algorithms is NOT stable?

<p>Heap Sort (C)</p> Signup and view all the answers

What is the time complexity of the BuildMaxHeap procedure?

<p>O(n) (B)</p> Signup and view all the answers

What is the expected time complexity of searching in a randomly built Binary Search Tree (BST)?

<p>O(log n) (C)</p> Signup and view all the answers

Which of the following statements about Binary Search Trees (BST) is true?

<p>D. None of the above. (D)</p> Signup and view all the answers

What is the primary difference between a Binary Tree and a Binary Search Tree (BST)?

<p>B. In BST, all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root. (B)</p> Signup and view all the answers

What is the height of a valid Binary Search Tree (BST) with 7 nodes, built with totally sorted data?

<p>B. 6 (D)</p> Signup and view all the answers

Which of the following is a characteristic of a Max-Heap?

<p>The value of the root node is the largest in the heap (C)</p> Signup and view all the answers

What is the time complexity of the BuildMaxHeap procedure?

<p>O(n) (D)</p> Signup and view all the answers

Which of the following statements about O-notation is true?

<p>O-notation represents the worst-case time complexity of an algorithm (A)</p> Signup and view all the answers

In Radix Sort, the sorting begins with the digit at which position?

<p>Least significant digit (A)</p> Signup and view all the answers

Which of the following trees is NOT a self-balancing tree?

<p>Splay Tree (C)</p> Signup and view all the answers

Which of the following statements about O-notation is true?

<p>O-notation provides an upper bound on the growth rate of a function. (C)</p> Signup and view all the answers

What is the FIRST step in the substitution method for solving recurrences?

<p>Guess the form of the solution. (D)</p> Signup and view all the answers

The Master Method is applicable to recurrences of which form?

<p>T(n) = aT(n/b) + f(n) (D)</p> Signup and view all the answers

Which of the following statements about Binary Search Trees (BST) is true?

<p>C. They always provide $O(\log n)$ performance for totally sorted data. (C)</p> Signup and view all the answers

What is the primary difference between a Binary Tree and a Binary Search Tree (BST)?

<p>B. In BST, all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root. (B)</p> Signup and view all the answers

What is the height of a valid Binary Search Tree (BST) with 7 nodes, built with totally sorted data?

<p>B. 6 (A)</p> Signup and view all the answers

Which of the following trees is a self-balancing tree?

<p>2-3 Tree (B)</p> Signup and view all the answers

What is the time complexity of Quicksort in the worst case?

<p>O(n^2) (B)</p> Signup and view all the answers

What does it mean for a sorting algorithm to be stable?

<p>It preserves the relative order of equal elements (B)</p> Signup and view all the answers

In a Max-Heap, what is the value of the root node?

<p>Largest in the heap (D)</p> Signup and view all the answers

Which of the following trees is a self-balancing tree?

<p>AVL Tree (D)</p> Signup and view all the answers

Which of the following statements about Binary Search Trees (BST) is true?

<p>BSTs maintain a sorted order of elements. (A)</p> Signup and view all the answers

What is the primary difference between a Binary Tree and a Binary Search Tree (BST)?

<p>Binary Trees can have any order of elements, while BSTs maintain a sorted order. (C)</p> Signup and view all the answers

What is the time complexity of the BuildMaxHeap procedure?

<p>O(n) (B)</p> Signup and view all the answers

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser