Question 1

When data is being organized, a programmer's highest priority is to organize it in such a way that item insertion, deletion, and lookups (searches) are fast.

Accepted Answer

Organizing data for fast insertion, deletion, and lookups is a key priority in data organization for efficient data management.

Question 2

Because an array is not a random access data structure, we cannot use a binary search to effectively find and retrieve an item from an array list.

Accepted Answer

Arrays are random access data structures, allowing direct access to any item based on its index, which makes binary search an effective method for finding items in a sorted array.

Question 3

In an array, item insertion (especially if the array is sorted) and item deletion can be very time consuming, especially if the list size is very large.

Accepted Answer

In an array, especially a sorted one, inserting or deleting items requires shifting the elements to maintain order, which can be time-consuming for large lists.

Question 4

Item insertion and deletion in a linked list requires significant data movement.

Accepted Answer

In a linked list, insertion and deletion of items do not require moving the data elements themselves, but rather involve changing the pointers of the nodes before and/or after the node of interest.

Question 5

A sequential search is good only for very small lists because the average search length of a sequential search is half the size of the list.

Accepted Answer

Sequential search, also known as linear search, involves checking each element in the list one by one until the desired element is found or the end of the list is reached. On average, it will indeed take searching through half the size of the list to find an element, making it inefficient for large lists compared to more advanced search algorithms like binary search.

Question 6

Every node in a binary tree has at most three children.

Accepted Answer

Every node in a binary tree has at most two children.

Question 7

A binary tree is a dynamic data structure.

Accepted Answer

A binary tree is considered a dynamic data structure because it can grow or shrink during execution of a program, allowing for operations like insertion and deletion of nodes.

Question 8

After inserting an item in a binary search tree, the resulting binary tree must also be a binary search tree.

Accepted Answer

Inserting an item into a binary search tree, when done correctly, maintains the binary search tree property: for any given node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node.

Question 9

In a preorder traversal of a binary tree, for each node, first the node is visited, then the right subtree is visited, and then the left subtree is visited.

Accepted Answer

In a preorder traversal of a binary tree, for each node, first the node is visited, then the left subtree is visited, and finally the right subtree is visited.

Question 10

In a preorder traversal of a binary tree, after visiting a node and before moving to the right subtree, we must save a pointer to the node so that after visiting the right subtree, we can visit the left subtree.

Accepted Answer

In a preorder traversal of a binary tree, the order of visitation is: visit the node, then traverse the left subtree, and finally traverse the right subtree. There is no need to save a pointer to the node before moving to the right subtree because the left subtree is visited immediately after the node itself, before visiting the right subtree.

Question 11

As in the case of an inorder traversal, in a postorder traversal, the first node visited is the rightmost node of the binary tree.

Accepted Answer

In a postorder traversal, the nodes are visited in the order of left subtree, right subtree, and then the root node, meaning the first node visited is the leftmost node, not the rightmost.

Question 12

To specify a function as a formal parameter to another function, we specify the function type, followed by the function name as a pointer, followed by the parameter types of the function.

Accepted Answer

In C/C++, a function can be passed as a parameter by specifying its type, using a pointer to the function, and listing its parameter types.

Question 13

The performance of the search algorithm on a binary search tree depends on how large the binary tree is.

Accepted Answer

The performance of a search algorithm on a binary search tree depends on the tree's height, not just its size. A balanced tree has better performance than an unbalanced one.

Question 14

Because an AVL tree is a binary search tree, the search algorithm for an AVL tree is the same as the search algorithm for a binary search tree.

Accepted Answer

The search algorithm for an AVL tree is the same as for any binary search tree, as AVL trees maintain the binary search tree property, where for any given node, all values in the left subtree are less, and in the right subtree are greater. The AVL-specific balancing does not affect the search algorithm.

Question 15

Operations, such as finding the height, determining the number of nodes, checking whether the tree is empty, tree traversal, and so on, on AVL trees cannot be implemented the same way they are implemented on binary trees.

Accepted Answer

AVL trees are a type of binary search tree, and the basic operations like finding the height, determining the number of nodes, checking whether the tree is empty, and tree traversal can be implemented in a similar way as on regular binary trees. The difference lies in the need for AVL trees to maintain balance through rotations after insertions and deletions.

Question 16

After inserting (or deleting) a node from an AVL tree, the resulting binary tree does not have to be an AVL tree.

Accepted Answer

After inserting or deleting a node from an AVL tree, rebalancing operations are performed to ensure that the tree remains an AVL tree, maintaining its height-balanced property.

Question 17

To insert an item in an AVL tree, first we search the tree and find the place where the new item is to be inserted.

Accepted Answer

In an AVL tree, which is a type of self-balancing binary search tree, the insertion process starts by searching the tree to find the correct location where the new item should be inserted, maintaining the binary search tree property. After insertion, the tree might need to be rebalanced to ensure that it remains an AVL tree, adhering to the AVL balance condition.

Question 18

After inserting the node, the reconstruction can occur at any node on the path back to the root node.

Accepted Answer

In a balanced binary search tree (such as AVL or Red-Black Tree), after inserting a node, the tree may need to be rebalanced. This rebalancing (or reconstruction) can occur at any node along the path from the newly inserted node back up to the root, as the insertion can affect the balance factor or properties of any of these nodes.

Question 19

The performance of a binary search tree depends on the width of the tree.

Accepted Answer

The performance of a binary search tree primarily depends on its height, not its width. A balanced tree ensures minimal height, leading to efficient operations like search, insert, and delete.

Question 20

Each node should store the number of keys in the node, the records, and the pointer to subtrees.

Accepted Answer

In a B-tree, each node typically stores the number of keys it contains, the keys themselves (which act as records or pointers to records), and pointers to its child nodes (subtrees), facilitating efficient data organization and retrieval.

Quiz 11: Binary Trees and B-Trees