C949 Data Structures and Algorithms I

Correct Answer

C. Every node must have at most one parent.

Explanation

In a tree data structure, every node (except the root) must have exactly one parent. The root node does not have a parent, but all other nodes are connected to a single parent, ensuring that there is no ambiguity in the hierarchy. This is a fundamental property of trees.

Why other options are wrong

A. Every node must have at least one parent.

This is incorrect because the root node does not have any parent. While every other node must have a parent, the root node is the only exception.

B. Every node must have at least one child.

This is incorrect because leaf nodes (nodes with no children) are allowed in trees. Not every node must have children; in fact, many nodes, such as the leaves of the tree, have none.

D. Every node must have at most one child.

This is incorrect because trees can have nodes with more than one child. A node in a tree can have any number of children, but it will always have exactly one parent (unless it is the root). The concept of having "at most one child" is more characteristic of a linked list than a tree.

Correct Answer

C. Every node has zero, one or two children.

Explanation

In a tree, every node can have any number of children, not necessarily limited to zero, one, or two. This is true for general trees (where the number of children per node can vary). However, a binary tree does impose the rule of having at most two children per node. The statement in option C applies specifically to binary trees but is not true for all types of trees.

Why other options are wrong

A. There cannot be more than one path between two nodes.

This is a requirement for trees. A tree is an acyclic graph, meaning that there is exactly one path between any two nodes. This ensures that there are no loops or cycles in the structure.

B. Every node, except the root node, has a unique parent.

This is a requirement for trees as well. In a tree, there is exactly one parent for each node, and the root is the only node without a parent. This ensures that the structure remains hierarchical.

D. Every node is connected to every other node by some path.

This is true in a tree, as it is a connected structure. There must be a path between any two nodes, which ensures that the tree is a connected graph.

Correct Answer

A. back

Explanation

In a doubly linked list, each node has two pointers: one pointing to the next node (the next pointer) and one pointing to the previous node (the back pointer). This allows traversal in both directions, unlike a singly linked list, where traversal is only possible in one direction from the head to the tail.

Why other options are wrong

B. null

This option is incorrect because null is not a pointer but a value that indicates the end of the list or an absent reference. A doubly linked list has two pointers in each node: one for the next node and one for the previous node, neither of which is called "null."

C. center

This option is incorrect because center is not a standard term used in linked list terminology. The second pointer in a doubly linked list is typically called the "previous" or "back" pointer, not the "center."

D. binary

This option is incorrect because binary does not describe the second pointer in a doubly linked list. "Binary" refers to a system involving two states or values, but a doubly linked list involves two pointers, one for the next node and one for the previous node.

Correct Answer

C. Dictionary

Explanation

A dictionary is a collection of key-value pairs where each key is unique. The key is used to look up the associated value, making the dictionary an essential data structure in many programming languages, such as Python, Java, and C#. The uniqueness of keys ensures that there is no duplication of key-value pairs in the dictionary.

Why other options are wrong

A. Array

This is incorrect because an array stores elements in an ordered list indexed by integer values, not in key-value pairs. The concept of unique keys and associated values does not apply to arrays.

B. Object

This is incorrect because an object (in languages like JavaScript or C#) can store key-value pairs, but the term "object" does not specifically imply a collection of unique key-value pairs. It is a more general term that can refer to a broader structure.

D. Generic Values

This is incorrect because "generic values" refers to a broad concept that doesn't specifically represent a collection of unique key-value pairs. The term doesn't accurately describe any standard data structure for storing key-value pairs.

Correct Answer

C. Add an item to the stack.

Explanation

The push() method is used to add an item to the top of the stack. The stack operates on a Last-In, First-Out (LIFO) principle, so the most recently added item will be the first one to be removed. The push() operation places an element onto the stack without removing any existing elements, allowing the stack to grow.

Why other options are wrong

A. Get an item without deleting it from the stack

This describes the peek() or top() operation, which allows you to view the item at the top of the stack without removing it. The push() method is for adding items to the stack, not viewing them.

B. Get the total items in the stack

This is not the purpose of push(). The total number of items in the stack can typically be obtained by a size() or similar method.

D. Take an item out of the stack

This describes the pop() method, which removes and returns the item at the top of the stack, not the push() method.

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. Hash(x) = x % tableSize

Explanation

The modulus operator ensures that the result of the hash function is always within the bounds of the table size. By calculating x % tableSize, the function maps any integer to a valid index in the hash table, ranging from 0 to tableSize - 1. This is a standard and efficient approach in hashing for distributing keys uniformly across the available slots.

Why other options are wrong

A. Hash(x) = x

This is incorrect because it does not limit the hash value to a valid index within the table. If x is greater than or equal to the table size, this function will produce out-of-bounds indices, which will cause runtime errors or undefined behavior in the program.

C. Hash(x) = x % (tableSize-1)

While this may seem similar to the correct answer, it’s incorrect because it doesn’t ensure that all possible slots from 0 to tableSize - 1 are utilized. Using tableSize - 1 could exclude the last slot and cause uneven distribution or underutilization of the hash table.

D. Hash(x) = x / tableSize

This is incorrect because division in this context doesn’t ensure that the result is within the bounds of the table. Integer division would significantly reduce the hash space and cluster multiple values into the same index, especially for small values of x, causing poor distribution and more collisions.

Correct Answer

A. a reference to another node

Explanation

In a node object, typically used in linked data structures such as linked lists, the next field is used to point to the next node in the sequence. This reference allows the structure to be traversed sequentially, as each node connects to the next through its next field.

Why other options are wrong

B. the data portion of the node

The data portion of a node is stored in a separate field, often named data or value. The next field specifically holds the reference to another node, not the actual data.

C. a reference to the beginning of the list

Only the head pointer of a linked list maintains a reference to the beginning of the list. The next field in a node does not point to the start but to the following node in the chain.

D. none of the above

This is incorrect because A correctly describes the function of the next field in a node object used in linked lists.

Correct Answer

D. given a key, return the value of the dictionary entry with the given key

Explanation

A key feature of the dictionary Abstract Data Type (ADT) is that it allows you to retrieve values efficiently given a key. In a dictionary, each key is associated with a value, and given a key, you can return the corresponding value using operations like get() or similar in programming languages. This operation is fundamental to the dictionary's purpose of mapping keys to values.

Why other options are wrong

A. remove the last item in the dictionary

This is not typically a core operation of the dictionary ADT. While you can remove items from a dictionary, the idea of removing the "last item" is more relevant to data structures like stacks or lists, which have an inherent ordering of elements. Dictionaries, however, are key-value pairs and may not maintain a specific order.

B. given a key and value, remove the entry with given key and value from the dictionary

Although this is a valid operation (like remove() or delete()), it is not the primary operation associated with the dictionary ADT. The key operation is usually retrieving the value given the key rather than removing an entry.

C. given a value, remove the entry that contains the value

This is not typical for a dictionary ADT. Dictionaries are primarily based on keys, not values. Removing an entry based on a value could be more complex and is less common than removing by key.