68 Questions
What is the key property of a binary search tree?
Value at node is smaller in the right subtree and larger in the left subtree
What is the time complexity of searching in a balanced binary tree with n nodes?
$O(\log(n))$ time
What is the height of a degenerate binary tree with n nodes?
Height = $O(n)$
What is the terminology used for a node with no child?
Leaf
What is the terminology used for a node with no parent?
Root
In a binary tree, what is the maximum number of children a node can have?
2
What is the time complexity of searching in a degenerate binary tree with n nodes?
$O(n)$ time
What type of binary tree is useful for searches due to its $O(\log(n))$ time complexity?
Balanced binary tree
What is the time complexity for insertion in a balanced binary search tree?
$O(\log n)$
When performing deletion in a binary search tree, what is the time complexity for a balanced tree?
$O(\log n)$
What is the purpose of tree rotations in maintaining balance in a binary search tree?
To maintain or restore the balance of the tree
What is the purpose of a heap in data structures?
To implement priority queues
What is the time complexity for removing the minimum element from a heap?
$O(\log n)$
What is the height of a heap storing $n$ keys?
$O(\log n)$
Which type of tree is a generalization of 2/3 trees?
B-tree
What is the purpose of parse trees in computer science?
To represent hierarchical data
In which traversal method is the root visited before the subtrees?
Pre-order traversal
What is the goal of tree traversal in data structures?
To visit every node of the tree
What algorithm is used for building a heap in data structures?
Floyd’s Method
What is the maximum number of children a node can have in a binary tree?
2
What is the time complexity of searching in a degenerate binary tree with $n$ nodes?
$O(n)$
In a binary search tree, what property is maintained where the value at each node is smaller in the left subtree and larger in the right subtree?
Binary property
What is the height of a degenerate binary tree with $n$ nodes?
$O(n)$
What is the time complexity for insertion in a balanced binary search tree?
$O(\log(n))$
What is the terminology used for a node with no child in a tree?
Leaf
What is the time complexity of searching in a balanced binary tree with $n$ nodes?
$O(\log(n))$
What type of binary tree has a height of $O(\log(n))$ for $n$ nodes?
Balanced binary tree
What is the time complexity of insertion in a balanced binary search tree?
O(log(n))
What is the terminology used for a node with no parent?
Root
What is the height of a degenerate binary tree with n nodes?
$n$
What is the time complexity of searching in a degenerate binary tree with n nodes?
O(n)
In a binary tree, what is the maximum number of children a node can have?
2
What is the height of a heap storing $n$ keys?
$O(log(n))$
What is a key property (invariant) that is maintained in a binary search tree?
Smaller values in left subtree, larger values in right subtree
What is the goal of tree traversal in data structures?
Visit every node of a tree
What type of binary tree is useful for searches due to its $O(log(n))$ time complexity?
Balanced binary search tree
What is the purpose of parse trees in computer science?
Represent textual programs as tree structures
What is the key property of a binary search tree?
Maintains ordering of elements
In a binary search tree, what is the time complexity of searching in a degenerate binary tree with $n$ nodes?
$O(n)$
What is the maximum number of children a node can have in a binary tree?
Unlimited
What is the key property of a binary search tree?
Value at each node is smaller in the left subtree and larger in the right subtree
What is the height of a degenerate binary tree with $n$ nodes?
$O(n)$
What is the time complexity of searching in a balanced binary tree with $n$ nodes?
$O( ext{log}(n))$
What is the time complexity for insertion in a balanced binary search tree?
$O( ext{log}(n))$
What type of binary tree has a height of $O( ext{log}(n))$ for $n$ nodes?
Balanced binary tree
What is the time complexity of inserting a new value into a balanced binary search tree?
$O(\log(n))$
In a binary search tree, what is the time complexity of searching in a degenerate tree with $n$ nodes?
$O(n)$
What is the key property (invariant) maintained in a binary search tree?
Smaller values in the left subtree, larger values in the right subtree
What is the goal of tree traversal in data structures?
Visit every node of a tree
What is the time complexity for removing the minimum element from a heap?
$O(\log(n))$
Which type of tree is a generalization of 2/3 trees?
B-trees
What is the terminology used for a node with no child in a tree?
Leaf node
What algorithm is used for building a heap in data structures?
Floyd’s Method
What is the primary goal of sorting?
To arrange elements in ascending or descending order
Which sorting algorithm is the simplest?
Bubble Sort
What is the time complexity of bubble sort in the worst case?
$O(n^2)$
In bubble sort, what happens if E1 is greater than E2?
They are swapped
What is the primary advantage of merge sort over bubble sort?
Merge sort has a better time complexity
Which sorting algorithm involves 'bubbling up' and 'counting down'?
Bubble Sort
What is the primary disadvantage of bubble sort?
Inefficient for large datasets
What is the time complexity of bubble sort?
O($n^2$)
What is the time complexity of selection sort?
O($n^2$)
In the analysis of bubble sort, how many times does the inner loop execute on average for each execution of the outer loop?
About $n/2$ times
How many times does the outer loop execute in the selection sort algorithm?
$n-1$ times
What is the work done in the inner loop of the selection sort algorithm?
Constant (swap two array elements)
What is the purpose of the outer loop in the selection sort algorithm?
To iterate through the array and select the smallest element
What is the purpose of the inner loop in the bubble sort algorithm?
To compare adjacent elements in the array
What is the time complexity of the algorithm to remove the minimum element from a heap?
O(log$n$)
Study Notes
Binary Search Tree Properties
- A binary search tree maintains the property that the value at each node is smaller in the left subtree and larger in the right subtree.
- The time complexity of searching in a balanced binary tree with n nodes is O(log(n)).
- The time complexity of searching in a degenerate binary tree with n nodes is O(n).
Tree Terminology
- A node with no child is called a leaf node.
- A node with no parent is called the root node.
Binary Tree Properties
- The maximum number of children a node can have in a binary tree is 2.
- The height of a degenerate binary tree with n nodes is n-1.
Heap Properties
- The time complexity for removing the minimum element from a heap is O(log(n)).
- The height of a heap storing n keys is O(log(n)).
- The purpose of a heap in data structures is to provide efficient sorting and priority queue operations.
Tree Traversal
- The purpose of tree traversal is to visit nodes in a specific order.
- The goal of tree traversal is to access or modify nodes in the tree.
- The pre-order traversal method visits the root node before the subtrees.
Binary Search Tree Operations
- The time complexity for insertion in a balanced binary search tree is O(log(n)).
- The time complexity for deletion in a balanced binary search tree is O(log(n)).
- Tree rotations are used to maintain balance in a binary search tree.
Other Data Structures
- Parse trees are used in computer science to represent the syntactic structure of source code.
- B-Tree is a generalization of 2/3 trees.
- Heapsort is an algorithm used for building a heap in data structures.
Sorting Algorithms
- The primary goal of sorting is to arrange elements in a specific order.
- Bubble sort is the simplest sorting algorithm.
- The time complexity of bubble sort is O(n^2) in the worst case.
- The primary advantage of merge sort over bubble sort is its efficiency.
- The primary disadvantage of bubble sort is its slow performance.
- Selection sort involves finding the minimum element and swapping it with the first element.
Test your knowledge of tree data structures with this quiz. Explore concepts such as nodes, children, binary trees, terminology, and binary search trees. This quiz covers fundamental aspects of trees in computer science and data structures.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
