C949 Data Structures and Algorithms I

Correct Answer

A. All descendants are greater than or equal to their ancestor

Explanation

In a min-heap, the characteristic property is that each parent node's key is less than or equal to the keys of its descendants. This ensures that the smallest element is always at the root. Min-heaps are often used in priority queues, where quick access to the smallest element is required.

Why other options are wrong

B. All descendants are less than their ancestor

This is incorrect because in a min-heap, the parent node must have a value that is smaller than or equal to its descendants, not the other way around.

C. All nodes have equal values

This is incorrect because a min-heap allows for distinct values and does not require all nodes to have the same value. The property is related to the comparison of parent and descendant nodes.

D. No specific order is maintained

This is incorrect because the defining characteristic of a min-heap is that it maintains a specific order — the parent node must always be less than or equal to its descendants, ensuring that the heap property is preserved.

Correct Answer

A. Both head and tail are pointed to the new element

Explanation

In a queue, when adding an element to an empty queue, both the head and tail pointers are updated to point to the new element. This ensures that both the front (head) and rear (tail) of the queue are correctly initialized with the newly added element. The queue would have only one element, and it serves as both the head and the tail.

Why other options are wrong

B. Tail is pointed to the new element, head remains null

This is incorrect because when the queue is empty, the head pointer should also point to the new element, not remain null.

C. None of these

This is incorrect because the correct behavior is explained in option A.

D. Head is pointed to the new element, tail remains null

This is incorrect because both head and tail should be set to the new element when the queue is empty. Leaving tail as null would make the queue unusable.

Correct Answer

B. |pop| method

Explanation

The pop() method is used to remove a key-value pair from a dictionary in most programming languages, including Python. It removes the specified key and returns the corresponding value. If the key is not found, an optional default value can be specified to avoid an error.

Why other options are wrong

A. |remove| method

This is incorrect because the remove() method is used in lists, not dictionaries. It removes an element from a list by value, not by key as required for dictionaries.

C. |delete| method

This is incorrect because the delete keyword is not a method in Python. While the del statement can delete a key-value pair from a dictionary, there is no delete method.

D. |get| method

This is incorrect because the get() method is used to retrieve the value associated with a specified key, not to remove items from a dictionary. It does not alter the dictionary.

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. 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.

Correct Answer

C. Record

Explanation

A record is a data structure that stores multiple subitems, also known as fields, each of which can have a different data type. A record is commonly used to store related data elements together as a single unit, such as a student’s name, age, and student ID in a database. The fields within a record are often associated with specific names, making the data more structured and easy to manage.

Why other options are wrong

A. Array

This is incorrect because an array is a data structure that stores elements of the same data type in a contiguous block of memory. Arrays don’t inherently store subitems with different names, and all elements are accessed by their index, not by name.

B. Matrix

This is incorrect because a matrix is a two-dimensional array, often used to represent data in rows and columns. While it stores elements in a grid-like structure, it does not inherently store subitems with different names.

D. Graph

This is incorrect because a graph is a data structure used to represent relationships between objects, where each object is a node, and the relationships are represented by edges. A graph doesn’t necessarily store subitems in the way a record does.

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

A. An integer counter that represents how many variables reference an object

Explanation

In Python, reference counting is a mechanism used by the interpreter to keep track of how many references point to an object. When an object's reference count drops to zero (i.e., no variable is referencing it), the object is automatically deallocated, freeing up memory.

Why other options are wrong

B. The amount of memory allocated to an object

This is incorrect because reference counting does not concern itself with the memory allocated to an object, but rather the number of references to the object. The memory management system handles memory allocation separately.

C. The number of attributes in a class

This is incorrect because the reference count has nothing to do with the number of attributes in a class. It is about how many variables reference an object.

D. The number of methods in a class

This is incorrect because the reference count is not related to the number of methods in a class. It is about how many variables are pointing to an object.