C949 Data Structures and Algorithms I

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

A. Because the nodes are connected in both directions

Explanation

A doubly-linked list has nodes that store references to both their previous and next elements. This bidirectional linking allows traversal in either direction, which is especially helpful for algorithms like insertion sort that may need to look back at previous elements to find the correct insertion point. This structure supports efficient backward traversal.

Why other options are wrong

B. Because the list can be traversed in any direction

While this might seem close to the truth, it's too vague and doesn’t explain the actual reason. A list cannot be traversed in any direction unless it's implemented in a way to allow that—like in a doubly-linked list. Saying it can be traversed in any direction doesn't highlight the key mechanism (the bi-directional links) that enables the backward traversal.

C. Because it is more efficient to sort in reverse order

This is incorrect because the efficiency of sorting in reverse order is not what enables backward traversal. The capability to go backward is a result of the structure of the doubly-linked list, not an optimization or decision about sorting direction. Sorting can be done in either direction depending on the algorithm design, but the list’s structure determines if backward traversal is possible.

D. Because of the programming language used

The programming language does not influence the traversal direction of a data structure. It's the data structure's design (in this case, the doubly-linked list) that dictates the traversal capabilities. Regardless of the language, a singly-linked list only allows forward traversal, while a doubly-linked list supports both forward and backward traversals.

Correct Answer

A. You need to execute a loop within another loop

Explanation

Nested loops are loops that exist within another loop. They are commonly used when you need to perform an operation that involves multiple levels of iteration, such as iterating over a 2D array or performing operations on every combination of elements in two lists. The outer loop controls the number of iterations for the outer task, and the inner loop handles iterations for the inner task.

Why other options are wrong

B. The outer loop depends on the inner loop

This is incorrect because in a nested loop, the outer loop does not necessarily depend on the inner loop. Each loop runs independently, although the inner loop may depend on the outer loop's iteration. However, this is not the defining feature of nested loops.

C. There is only one loop, but it has complex conditions

This is incorrect because nested loops refer specifically to having more than one loop inside another. Complex conditions within a single loop do not define nested loops; that would involve adding conditions or logic inside the loop, but it doesn’t involve multiple loops.

D. None of the above

This is incorrect because option A correctly defines when nested loops are used.

Correct Answer

B. reclamation of storage that is no longer referenced

Explanation

Reference counting is a technique used in memory management where each object has a counter that tracks how many references exist to it. When the count drops to zero, the object is no longer in use and can be safely reclaimed. This method helps in automatically deallocating memory that is no longer being referenced.

Why other options are wrong

A. tracking parameter use

This is incorrect because reference counting is not specifically about tracking parameter use. It deals with memory management and object life cycles, not the use of parameters in a function or method.

C. allocating memory

This is incorrect because reference counting does not handle memory allocation directly. Memory allocation is handled separately through mechanisms like malloc or new. Reference counting focuses on managing the deallocation process when objects are no longer needed.

D. accessing nonlocal variables

This is incorrect because reference counting does not relate to accessing nonlocal variables. It is concerned with managing the lifetime of objects in memory, not how variables are accessed in different scopes.

Correct Answer

A. Hierarchical

Explanation

A tree data structure represents a hierarchical relationship, where the root node is at the top, and each node (except for the root) has a parent node. This relationship resembles a tree structure, where parent-child relationships dictate the flow of data or control, forming a hierarchy of nodes.

Why other options are wrong

B. Internal

This is incorrect because "internal" does not describe the relationship between the root and its child nodes. It might be used in a different context, but it does not specifically refer to the structure of the tree itself.

C. Complete

This is incorrect because "complete" refers to a specific type of binary tree where all levels are filled, except possibly the last, which is filled from left to right. It does not describe the general relationship between the root and child nodes.

D. Inheritance

This is incorrect because "inheritance" is a concept used in object-oriented programming to describe the relationship between classes, not in the context of tree data structures. It does not describe the structural relationship of nodes in a tree.

Correct Answer

C. Binary search trees

Explanation

In-order traversal of a binary search tree (BST) visits nodes in ascending order because the left subtree of any node contains values smaller than the node, and the right subtree contains values larger. This traversal method ensures that the nodes are processed in increasing order, which is why in-order traversal yields a sorted listing of elements in a binary search tree.

Why other options are wrong

A. Heaps

This is incorrect because heaps do not guarantee sorted order when traversed in any order. A heap only ensures that a parent node satisfies the heap property, which means in a max-heap, the parent's key is larger than the children's, and in a min-heap, the parent's key is smaller. This does not necessarily result in a sorted list.

B. Binary trees

This is incorrect because binary trees do not have any specific ordering property. In-order traversal of a binary tree will not necessarily yield a sorted list since there is no constraint on how the nodes are arranged within the tree.

D. None of the others

This is incorrect because the correct answer is binary search trees, where in-order traversal yields a sorted list.

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

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

C. 4 children

Explanation

In a B-tree of degree 5, each internal node can have at most 5 children. However, a B-tree's internal nodes must have at least ⌈degree/2⌉ children. For a B-tree of degree 5, this means the node must have at least 3 children. Therefore, the maximum number of children an internal node (other than the root) can have is 4, because the maximum number of children for any internal node is one less than the degree of the tree.

Why other options are wrong

A. 2 children

This is incorrect because, in a B-tree of degree 5, an internal node can have at most 4 children, not 2. Having only 2 children would violate the minimum children requirement for internal nodes.

B. 5 children

This is incorrect because although the degree of the B-tree is 5, an internal node can have a maximum of 4 children. A node with 5 children would be full and would split into two nodes.

D. 3 children

This is incorrect because 3 children is the minimum number of children an internal node in a B-tree of degree 5 can have, but it is not the maximum number of children.

E. 1 child

This is incorrect because B-trees require that internal nodes have at least 3 children (in a degree 5 B-tree). Therefore, having only 1 child would not be valid for an internal node.