C949 Data Structures and Algorithms I

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

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

A. key % 20

Explanation

Using key % 20 ensures that the hash values produced will always be in the range of 0 to 19, which matches the 20 available buckets in the hash table. This mapping guarantees that no index will fall outside the bounds of the table, thus avoiding errors and ensuring an even distribution of keys across all the buckets.

Why other options are wrong

B. key % 10

This is incorrect because it only produces values from 0 to 9, utilizing only half of the available 20 buckets. This leads to underutilization of the hash table and higher chances of collisions within the limited set of indices.

C. key % 30

This option is incorrect because it can generate values up to 29, which exceeds the number of available buckets (0 to 19). Using this function would lead to out-of-bounds access errors and potentially crash the program or cause incorrect behavior.

D. key % 15

This is incorrect as it produces values from 0 to 14, leaving 5 buckets unused. Like option B, it results in poor space utilization and can increase the load factor of the active buckets, leading to performance degradation due to more collisions.

Correct Answer

A. a tail node and pointers to previous nodes

Explanation

To change a singly linked list into a doubly linked list, we need to modify each node to contain two pointers: one pointing to the next node (like in a singly linked list) and one pointing to the previous node. Additionally, the list requires a tail node to efficiently access the last node of the list. This allows for traversal in both directions: forward and backward.

Why other options are wrong

B. a second head node and reverse pointers

This is incorrect because a second head node is not necessary to transform a singly linked list into a doubly linked list. The main requirement is to introduce reverse pointers in each node, not an additional head.

C. pointers to adjacent nodes

This is incorrect because pointers to adjacent nodes would only describe a bidirectional traversal for a circular list or a more general structure but doesn't fully describe the necessary structure for a doubly linked list, which requires specific pointers for the next and previous nodes.

D. a two-dimensional array

This is incorrect because a two-dimensional array is a different data structure entirely. It has nothing to do with the structure of linked lists, singly or doubly.

Correct Answer

B. A loop that contains one or more other loops within it

Explanation

A nested loop is a loop that contains one or more loops inside it. These inner loops are executed for each iteration of the outer loop. Nested loops are commonly used in situations where you need to perform multiple iterations through a set of data, such as in matrix operations or algorithms that involve multiple dimensions.

Why other options are wrong

A. A loop that can only be used inside a function

This is incorrect. Nested loops can be used both inside functions and outside them. They are not limited to being inside functions.

C. A special type of infinite loop

A nested loop is not necessarily an infinite loop. An infinite loop is a loop that never terminates, which can occur in any type of loop, including nested loops if not properly controlled. However, nested loops themselves do not inherently lead to infinity.

D. A loop that iterates backwards

This is incorrect. While loops can iterate backwards (such as with a for loop), a nested loop is defined by the presence of one loop inside another, regardless of the direction of iteration.

Correct Answer

C. Worst case

Explanation

Big-O notation is used to describe the upper bound or the worst-case scenario in algorithm analysis. It characterizes the maximum amount of time or space an algorithm will require, helping developers understand how an algorithm will perform under the most demanding conditions. This allows for consistent performance guarantees, even in the least favorable situations.

Why other options are wrong

A. Average case

This is incorrect because average-case analysis considers the expected performance over all possible inputs, which is typically represented by different notations such as Theta (Θ). Big-O is not concerned with what usually happens, but rather with what could go wrong in the worst scenario.

B. Best case

This option is incorrect because best-case analysis focuses on the minimum possible resources an algorithm might need. It is represented by Omega (Ω) notation. Big-O, on the other hand, aims to provide a conservative estimate of performance, making best-case analysis irrelevant to its purpose.

D. Optimal case

This is incorrect because “optimal case” is not a standard term in algorithm analysis. The term might imply ideal performance but doesn’t correspond to any specific asymptotic notation like Big-O. Algorithm analysis is typically framed around best, worst, and average cases.

Correct Answer

D. both a stack and a queue

Explanation

A deque (double-ended queue) is a versatile data structure that allows insertion and removal of elements from both ends. This allows it to behave as both a stack (using push and pop operations from one end) and a queue (using enqueue and dequeue operations from the other end). Thus, it can substitute the behavior of both stacks and queues.

Why other options are wrong

A. neither a stack nor a queue

This is incorrect because a well-implemented deque can behave as both a stack and a queue, so this option does not apply.

B. a queue but not a stack

This is incorrect because a deque can function as both a stack and a queue, not just a queue.

C. a stack but not a queue

This is incorrect because a deque can also function as a queue, in addition to a stack, so this statement is not true.

Correct Answer

A. The running times of both are dependant on the input size (or input values).

Explanation

Both O(n) (linear time) and O(n²) (quadratic time) are dependent on the input size. In O(n), the time required grows linearly with the input size, meaning that as the input grows, the time to execute the operation increases proportionally. In O(n²), the time grows quadratically with the input size, meaning that the time increases at a much faster rate than the size of the input.

Why other options are wrong

B. The latter is dependant on the input size (or input values) but the former one is not.

This is incorrect because O(n) time complexity is also dependent on the input size. While the growth rate is linear, it is still impacted by the size of the input.

C. The running times of neither are dependant on the input size (or input values).

This is incorrect because both O(n) and O(n²) are time complexities that are inherently dependent on the input size. They describe how the running time scales as the input increases.

D. The former is dependent on the input size (or input values) but the latter one is not.

This is incorrect because both O(n) and O(n²) depend on the input size. The only difference is the rate at which the running time increases as the input size grows, but both are dependent on the input size.

Correct Answer

C. Node head = null;

Explanation

An empty linked list means that there are no nodes in the list. Assigning head = null indicates that the list has no elements and the head does not point to any node. This is the proper way to represent an initially empty linked list in most implementations.

Why other options are wrong

A. Node head = new Node();

This is incorrect because it creates a new node, which means the list contains one node. It is not empty—there is already one element allocated in memory.

B. Node head = Node;

This is incorrect because it is a syntactically invalid statement. Node is a type, not an instance or reference, so this assignment will cause a compilation error.

D. Node head = new Node(0);

This is incorrect because it creates a node with the value 0, which means the list is initialized with one node and is therefore not empty.

E. Node head = list;

This is incorrect and ambiguous. If list is not defined elsewhere, this code won’t compile. Even if list exists, it depends on the state of list and doesn’t guarantee an empty list.