C949 Data Structures and Algorithms I

Correct Answer

B. Iterating through each element in an array to find the maximum value

Explanation

Iterating through each element in an array requires examining each element once, so it has a linear time complexity of O(n), where n is the number of elements in the array.

Why other options are wrong

A. Searching for an element in a sorted array using binary search

Binary search operates in O(log n) time complexity, as it repeatedly divides the search space in half.

C. Inserting an element into a balanced binary search tree

Inserting an element into a balanced binary search tree has a time complexity of O(log n) due to the logarithmic height of the tree.

D. Calculating the factorial of a number using recursion

Calculating the factorial using recursion is O(n), but this scenario is often optimized to avoid recursion's overhead, making it potentially O(n), although this depends on the implementation.

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. 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. uniquely identify a row

Explanation

A unique key in a database is specifically designed to uniquely identify a row in a table. This ensures that no two rows in the table can have the same value for this key, making it possible to distinguish each row based on that key. It is a fundamental concept in database normalization and helps maintain data integrity.

Why other options are wrong

A. identify a set of rows

This is incorrect because a unique key is intended to identify a single row, not a set of rows. If multiple rows share the same value, that would violate the uniqueness constraint.

B. be shared among several rows

This is incorrect because a unique key must not be shared among rows. If it were shared, it would no longer be unique, and its purpose as an identifier would be compromised.

D. be unique for each column

This is incorrect because a unique key can apply to a single column or a combination of columns, but it is not necessary to have a unique key for each column in a table. A unique key applies at the row level, not the column level.

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

B. A parent node key is lower than or equal of its children keys

Explanation

In a Min-Heap, the key of the parent node is always less than or equal to the keys of its children. This structure ensures that the smallest key is always at the root, and that no child has a key smaller than its parent.

Why other options are wrong

A. A parent node key is always greater than both of its children keys

This is incorrect because it describes a Max-Heap, not a Min-Heap. In a Max-Heap, the parent has a key greater than or equal to its children, which is the opposite of the Min-Heap property.

C. A parent node key is always smaller than both of its children keys

This is incorrect because a parent node in a Min-Heap only needs to be less than or equal to its children, not strictly smaller. Equal values are allowed.

D. A parent node key is always higher than left child's key

This is incorrect for a Min-Heap, as the parent's key must be less than or equal to both children, not greater than any of them.

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

Explanation

A Stack is a data structure that operates on a Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. It is typically implemented with operations like push (to add an element) and pop (to remove the most recently added element). Stacks are perfect for situations where this order of operations is required.

Why other options are wrong

B. ArrayList

An ArrayList is a resizable array implementation and does not inherently follow the LIFO principle. It provides random access to elements via indices, so while it can be used to store elements, it is not designed for LIFO behavior.

C. LinkedList

A LinkedList is a doubly linked list that can be used to implement various data structures, including stacks. While it can be used for LIFO behavior, its general-purpose implementation is more flexible than a dedicated Stack, which is specifically optimized for LIFO operations.

D. HashSet

A HashSet is an unordered collection of elements that does not maintain any specific order, including LIFO. It is used for storing unique elements without caring about the order in which they were added or removed. Therefore, it is not suitable for implementing LIFO behavior.

Correct Answer

A. Doubly-linked list

Explanation

A doubly-linked list is a type of linked list in which each node contains two references: one to the next node and one to the previous node. This bidirectional linking allows traversal in both forward and reverse directions, making operations like backward iteration and deletion more efficient than in singly-linked lists.

Why other options are wrong

B. Hierarchical tree traversal

Tree traversal isn't a linked list structure and does not inherently allow straightforward linear forward and backward traversal like a doubly-linked list. Traversals such as in-order or post-order have their own structure and directionality based on the tree hierarchy.

C. Circular linked list

A circular linked list connects the last node back to the first, forming a loop. While you can traverse endlessly forward in such a list, traditional circular linked lists (especially singly circular ones) do not allow reverse traversal unless explicitly implemented with backward pointers.

D. Singly-linked list

A singly-linked list only has forward references. Each node points to the next node, and there's no backward reference to support reverse traversal, making backward movement difficult without auxiliary structures.