C949 Data Structures and Algorithms I

Correct Answer

D. rightmost node of the tree

Explanation

In a binary search tree (BST), the largest value is always found in the rightmost node. This is because, for each node in a BST, all values in the right subtree are greater than the node’s value. Therefore, as you move down the tree to the rightmost node, you encounter the largest value in the tree.

Why other options are wrong

A. leftmost node of the tree

This option is incorrect because the leftmost node in a binary search tree will always contain the smallest value. In a BST, values to the left of a node are smaller, so the leftmost node is the minimum, not the maximum.

B. leftmost node at level 1 of the tree

This option is incorrect because it refers to a specific node at a particular level, but the location of the largest value is not determined by the level or side of the tree. The largest value in a BST will always be in the rightmost node, not tied to any specific level.

C. root of the tree

This is incorrect because the root is just the starting point of the tree, and in a BST, the root does not necessarily contain the largest value. Values greater than the root will be in the right subtree, while values smaller will be in the left subtree.

Correct Answer

A. record

Explanation

A record is a data structure that holds multiple fields, each with its own name and associated value. Records are commonly used in databases and programming to group related data under one composite type, allowing for structured storage and easy retrieval based on field names.

Why other options are wrong

B. array

An array stores elements in a fixed, sequential order but does not associate each element with a name. Instead, elements are accessed via indices, making arrays unsuitable for storing named fields.

C. linked list

A linked list is a sequential data structure made of nodes, each pointing to the next. It does not associate names with data fields in the way a record does; it is used more for dynamic memory management and efficient insertions/removals.

D. binary tree

A binary tree is a hierarchical structure where each node has at most two children. While it can store structured data, it is not typically used for named fields like a record is.

Correct Answer

C. Compute the index of a bucket

Explanation

A hash function is a mathematical function that takes input (or 'key') and returns a fixed-size string or number, typically an index in a hash table. This index is used to determine where the value will be stored or retrieved. The main purpose of a hash function in data structures like hash tables is to compute the index for a bucket where the corresponding data will be stored.

Why other options are wrong

A. Compute the value to be stored

This is incorrect because the hash function does not compute the value itself, but rather the location (index) where the value will be stored. The value is typically inputted directly or computed by another function.

B. Compute the address of a bucket

This option is incorrect because the hash function does not directly compute the address. It computes an index, which can then be used to determine the appropriate bucket in a hash table, but it doesn’t handle memory addressing directly.

D. None of the above

This is incorrect because option C is the correct answer. A hash function is specifically used to compute the index of a bucket in hash-based data structures.

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

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

A. There is an edge connecting them.

Explanation

In graph theory, two vertices are considered adjacent if there is an edge directly connecting them. The adjacency of vertices is a structural property of the graph, independent of their visual representation. This means that if there is an edge between two vertices, they are adjacent regardless of their positions in a visual layout.

Why other options are wrong

B. They are far apart in the visual representation of the graph.

This is incorrect because the visual distance between two vertices does not affect their adjacency in terms of graph theory. Adjacency depends on whether there is an edge between the vertices, not on their graphical representation.

C. There is no edge connecting them.

This is incorrect because if there is no edge connecting the vertices, they are not adjacent. Adjacency specifically refers to vertices that are connected by an edge.

D. They are close to one another in the visual representation of the graph.

This is incorrect because the proximity of vertices in a visual representation is irrelevant to their adjacency. Adjacency depends purely on whether an edge exists between the vertices, not on how close they appear in a drawing of the graph.

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.

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

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.