C949 Data Structures and Algorithms I

Correct Answer

A. a linked list

Explanation

A linked list is a collection of data in which each element, typically called a node, contains the data and a reference (or pointer) to the next element in the sequence. This structure allows for efficient insertion and removal of elements, as elements are not stored in contiguous memory locations like arrays, but instead are linked through pointers.

Why other options are wrong

B. an array

An array is a collection of elements stored in contiguous memory locations. It does not contain pointers to the next element but instead uses an index to access elements, making it fundamentally different from a linked list.

C. a node

A node is a single element of a linked list, which contains both data and a reference to the next node. However, the node itself is not a collection of data; it is a single unit in a linked list.

D. a record

A record is a data structure that can hold multiple fields of different types, but it is not specifically a collection in which each element points to the next. A record typically refers to an aggregate of related data items, whereas a linked list refers to a collection of nodes linked together.

Correct Answer

A. If the node to remove has two children, find the succNode, copy its value, and recursively remove the succNode

Explanation

In AVL tree removal, when a node to be deleted has two children, the standard approach is to find its successor (the smallest node in the right subtree), copy its value to the node to be deleted, and then recursively remove the successor node. This ensures the binary search tree property is maintained during deletion.

Why other options are wrong

B. If the node to remove is the root node with 1 child, the root and the child will trade places.

This is incorrect because in AVL trees, the node deletion involves removing the node and potentially rebalancing, not simply swapping with the child. The root will be removed and its child will take its place, but there are no "trading places."

C. If the node to remove is an internal node with only a left child, recursively remove the left child

This is incorrect because when removing a node with only a left child, the left child typically takes the place of the node being removed. The node does not have to be recursively removed; it is directly linked to the parent node.

D. Every tree node must be rebalanced after an internal node is removed.

This is incorrect because not every node needs to be rebalanced after the removal of an internal node. Rebalancing only occurs when an imbalance is detected, typically after the removal or insertion of nodes that disturb the AVL balance property. Rebalancing is performed starting from the point of deletion and going upwards to the root if necessary.

Correct Answer

B. Deque stores elements in a combination of contiguous and non-contiguous memory.

Explanation

Option B is incorrect. A deque (double-ended queue) typically stores elements in contiguous memory for efficient access and manipulation at both ends. It does not combine contiguous and non-contiguous memory. The term "non-contiguous memory" is more closely related to structures like linked lists.

Why other options are wrong

A. In deque, adding and removing elements happens at both ends of the container.

This is correct because a deque allows elements to be added or removed from both the front (beginning) and the back (end) of the container.

C. Deque is a double-ended queue.

This is correct because the term "deque" stands for "double-ended queue," which allows for efficient insertion and deletion from both ends.

D. Deque is a doubly linked collection of elements linked to other elements.

This is correct because many implementations of a deque use a doubly linked list structure where each element is linked to both its previous and next elements, allowing for efficient operations at both ends.

Correct Answer

A. O(n)

Explanation

In the worst case, deleting a node in a binary search tree can require O(n) time complexity. This happens when the tree is unbalanced, and the height of the tree is proportional to the number of nodes, causing a linear search to find the node to be deleted.

Why other options are wrong

B. O(log n)

This is the time complexity for a balanced binary search tree, where the tree height is logarithmic relative to the number of nodes. However, in the worst case (an unbalanced tree), the time complexity can degrade to O(n).

C. O(1)

This is incorrect because O(1) represents constant time complexity, which would apply to operations like accessing an array element by index, not deleting a node in a tree. Deleting a node in a binary search tree typically involves searching for the node and possibly re-arranging child nodes, which requires more than constant time.

Correct Answer

C. distributes data uniformly over the possible range of hash values

Explanation

A good hash function should distribute data evenly across the hash table, minimizing the number of collisions (when two keys map to the same index). A uniform distribution ensures that each bucket in the table is equally likely to be used, improving the efficiency of data retrieval and storage.

Why other options are wrong

A. returns a Double value

This is incorrect because the return type of a hash function is typically an integer value that represents an index in the hash table, not a double value. The index must be an integer to match the size of the table.

B. causes many collisions

This is incorrect because a good hash function minimizes collisions. Collisions occur when two keys hash to the same index, which reduces the efficiency of the hash table. A good hash function tries to avoid collisions as much as possible.

D. None of the above

This is incorrect because option C is the correct answer. A good hash function should aim to distribute the data uniformly across the hash table to ensure efficient performance.

Correct Answer

B. stack

Explanation

A stack is a data structure that operates on a Last In, First Out (LIFO) principle, meaning that the last element added is the first one to be removed. It is commonly used in function calls, undo operations, and parsing expressions.

Why other options are wrong

A. list

A list can allow for various access patterns, such as random access, and is not strictly LIFO or FIFO. It allows elements to be accessed or modified at any position, unlike a stack.

C. heap

A heap is a binary tree-based structure that satisfies the heap property, where the parent nodes are ordered with respect to their children. It is typically used for priority queues and does not follow the LIFO principle.

D. tree

A tree is a hierarchical data structure consisting of nodes and edges, with a root node and potential children. It does not follow the LIFO principle and allows for multiple access patterns, like traversal in various orders (pre-order, in-order, post-order).

Correct Answer

C. In-order

Explanation

In in-order traversal, the tree is traversed by first visiting the left child, then the current node, and finally the right child. This is typically used in binary search trees to retrieve values in ascending order.

Why other options are wrong

A. Pre-order

In pre-order traversal, the node is visited first, before its children (left then right), which is different from visiting the left child first.

B. Post-order

In post-order traversal, the node is visited after both its left and right children, which is the opposite of the in-order method.

D. Level-order

Level-order traversal processes the tree level by level, visiting nodes from top to bottom and left to right, and does not follow a parent-child relationship like in-order traversal.

Correct Answer

D. Preorder Traversal

Explanation

In preorder traversal, the node is visited before its children. The process for preorder traversal is to visit the node first, then recursively traverse its left subtree and right subtree. This is useful for operations like copying a tree or generating a prefix expression in expression trees.

Why other options are wrong

A. Postorder Traversal

This is incorrect because in postorder traversal, the node is visited after its children. The left and right subtrees are visited first, and the node itself is processed last.

B. Order Traversal

This is incorrect because "Order Traversal" is not a standard term in tree traversal algorithms. The standard terms are preorder, inorder, and postorder traversal.

C. Inorder Traversal

This is incorrect because in inorder traversal, the left child is visited first, then the node itself, and then the right child. The node is not visited first in this case.

Correct Answer

B. To retrieve the elements in ascending order

Explanation

In an in-order traversal of a binary search tree (BST), the nodes are visited in ascending order. This is because in a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. By visiting the left subtree first, then the node, and then the right subtree, we can obtain all elements in ascending order, making this traversal ideal for sorted data retrieval.

Why other options are wrong

A. To find the maximum value in the tree

This is incorrect because in-order traversal visits all the nodes in sorted order, but it does not specifically focus on finding the maximum value. To find the maximum value in a BST, you would need to traverse the rightmost nodes directly, not perform an in-order traversal.

C. To delete nodes from the tree

This is incorrect because in-order traversal is a method of visiting nodes and retrieving their values in a sorted order, not a method of deleting nodes. Deletion requires a separate process depending on the node’s position in the tree (leaf, one child, two children).

D. To count the number of nodes in the tree

This is incorrect because in-order traversal does not focus on counting nodes; it is intended for retrieving values in sorted order. While it could technically be used to count nodes by visiting each one, that is not its primary purpose.