C950 Data Structures and Algorithms II

Correct Answer

B. Linked List

Explanation

A linked list is a linear data structure where elements, called nodes, are stored in separate objects, each containing a reference (pointer) to the next element in the sequence. This allows for dynamic memory allocation and easy insertion or deletion of elements. Unlike arrays, linked lists do not require contiguous memory locations, and each node can point to the next.

Why other options are wrong

A. Pointer

A pointer is a variable that stores the address of another variable, often used to reference elements in data structures like linked lists. However, it is not itself a data structure.

C. Parameter

A parameter is a value passed into a function or method. It is not a data structure but rather a concept in programming related to function calls.

D. Array

An array is a collection of elements stored in contiguous memory locations. It is not a linked structure like a linked list, where each element is an object pointing to the next one.

Correct Answer

A. O(n)

Explanation

In the worst case, a sequential search must examine every element in the array to find the target (or determine it is not present). This results in a linear number of comparisons, giving it a time complexity of O(n). The search scales proportionally with the number of elements.

Why other options are wrong

B. O(n²)

This runtime suggests nested loops or operations where the number of steps grows quadratically. Sequential search involves a single loop through the array, not multiple nested iterations.

C. O(n/2)

Although on average a sequential search might find the element halfway through the array, Big-O notation ignores constant factors. Thus, O(n/2) simplifies to O(n) in asymptotic analysis and is not the correct way to express the worst case.

D. O(log n)

This applies to algorithms like binary search that divide the search space. Sequential search does not do this—it checks each element one by one—so logarithmic time is not applicable.

Correct Answer

C. O(n)

Explanation

In-order traversal of a binary search tree (BST) involves visiting each node once in a left-root-right order. Regardless of whether the tree is balanced or skewed, every node must be visited exactly once. Therefore, in the worst case, when the tree is completely unbalanced or even in the best case, the traversal takes linear time — O(n).

Why other options are wrong

A. O(log n)

This is incorrect because O(log n) represents the depth of a balanced BST, not the time it takes to traverse all nodes. Traversal involves visiting every node, not just searching or inserting, so log(n) is an underestimate of the actual time.

B. O(1)

This is incorrect because O(1) suggests constant time regardless of input size. Since in-order traversal requires visiting each of the n nodes, it can never be done in constant time.

D. O(n log n)

This is wrong because it implies that each of the n nodes requires log(n) time to process, which isn't the case. Each node is visited once and in constant time during traversal, leading to a total time of O(n), not O(n log n).

Correct Answer

D. Amortized O(1)

Explanation

The PushBack operation for a dynamic array, like fsu::Vector<T>, typically has an amortized time complexity of O(1). This is because most of the time, the operation involves adding an element to the end of the array in constant time. However, when the array reaches its capacity, it needs to be resized, which takes O(size) time. Since resizing happens less frequently as the array grows, the average cost of each PushBack operation is O(1) over time.

Why other options are wrong

A. Amortized O(size)

This is incorrect because the resizing operation does not happen for every push but rather at specific intervals, so the amortized time complexity does not scale linearly with the size of the vector.

B. None of the above

This is incorrect because amortized O(1) is the correct answer, and it is included in the options.

C. O(1)

This is incorrect because although the PushBack operation is O(1) on average, it can sometimes be O(size) when a resize is necessary. Therefore, it is not O(1) in all cases but rather amortized O(1).

E. O(size)

This is incorrect because the PushBack operation is typically O(1) except during resizing, which happens less frequently, making the overall time complexity amortized O(1).

Correct Answer

D. Correctness

Explanation

While correctness is an important characteristic of an algorithm in practice, it is not a formal requirement of an algorithm as defined in computer science. The key requirements of an algorithm are:

Effectiveness: Every step must be basic enough to be carried out in a finite amount of time by a human or machine.

Finiteness: An algorithm must eventually terminate after a finite number of steps.

Definiteness: The steps of the algorithm must be clearly defined and unambiguous.

Correctness, on the other hand, refers to whether the algorithm produces the correct output for all inputs, which is a goal or property but not a formal requirement in the strict definition of an algorithm.

Why other options are wrong

A. Effectiveness

Effectiveness is a requirement of an algorithm because it ensures that each step of the algorithm is simple and executable, either by a human or a machine.

B. Finiteness

Finiteness is a critical requirement because an algorithm must eventually terminate, ensuring that it doesn't run indefinitely.

C. Definiteness

Definiteness is another fundamental requirement. Each step of the algorithm must be precisely defined, ensuring that there is no ambiguity in the instructions.

Correct Answer

A. A way of representing the hierarchical nature of a structure in a graphical form.

Explanation

A tree structure is a hierarchical data structure that consists of nodes connected by edges, representing relationships between elements. It is commonly used in computer science to represent various types of hierarchical data, such as organizational charts, file systems, and family trees. The tree starts with a root node, and each node can have child nodes, forming a branching structure.

Why other options are wrong

B. A way of demonstrating that all living things descended from plants.

This is unrelated to the concept of a tree structure in computer science. It refers to a biological concept of evolutionary relationships, not a data structure.

C. A way of demonstrating evolution.

While trees can represent evolutionary relationships (evolutionary trees), this is not the focus of the data structure tree used in computing. Evolutionary trees are a biological concept, not a computational one.

D. A logical structure that is only used in Biology.

This is incorrect because tree structures are widely used in computing, not just biology. They represent hierarchical relationships in many different contexts, such as computer file systems, databases, and more.

Correct Answer

C. It guarantees that the algorithm can be understood and executed without confusion.

Explanation

Definiteness refers to the clarity of the steps involved in an algorithm. Every step in the algorithm must be precisely defined, leaving no ambiguity in its execution. This ensures that the algorithm can be executed correctly and efficiently, and can be implemented without confusion. Without definiteness, an algorithm may be misinterpreted or fail to execute as intended, leading to incorrect results or inefficiencies.

Why other options are wrong

A. It ensures that algorithms can be executed in any programming language.

While definiteness is crucial for the correct execution of an algorithm, it does not ensure that an algorithm can be executed in any programming language. An algorithm's implementation may depend on the language used, but definiteness makes sure the algorithm's logic is clear regardless of the language.

B. It allows for multiple interpretations of the instructions.

This is the opposite of definiteness. Definiteness ensures that the instructions are precise and not open to interpretation.

D. It simplifies the algorithm by reducing the number of steps.

Definiteness doesn't necessarily simplify an algorithm or reduce its steps. It focuses on making the algorithm's steps clear and unambiguous, regardless of their complexity or number.

Correct Answer

A. They allow focusing on higher-level operations and algorithms

Explanation

Abstract Data Types (ADTs) improve programmer efficiency because they allow programmers to focus on higher-level operations and algorithms without needing to worry about the implementation details of the underlying data structures. ADTs provide an abstraction that hides the complexity of data structure implementation, making it easier to work with data and solve problems.

Why other options are wrong

B. They require understanding the underlying data structures

While understanding the underlying data structures is useful, the main benefit of ADTs is that they abstract away these details, allowing the programmer to focus on the problem at hand rather than on the data structure itself.

C. They involve complicated implementations

ADTs themselves are designed to simplify implementation by abstracting the complexity of data structures. They do not necessarily involve complicated implementations, but rather, they provide a simpler interface to interact with the data.

D. They need frequent updating of code

ADTs, once defined, provide a stable interface for interaction. They do not necessarily require frequent updating of code. The purpose of an ADT is to provide a reliable and consistent way of interacting with data.

Correct Answer

A. Public components allow external access, while private components protect internal data.

Explanation

In an Abstract Data Type (ADT), public components are the methods and functions that are accessible to the outside world. They define the interface through which users interact with the data structure, enabling them to perform operations like insert, delete, push, pop, or traverse depending on the ADT. On the other hand, private components refer to the internal structure and implementation details that are hidden from the user. These private elements protect the integrity of the data and ensure that the ADT operates in a controlled and predictable manner, preventing external manipulation that could lead to inconsistencies or errors.

Why other options are wrong

B. Private components are only for internal use, while public components are used for data storage.

This is incorrect because private components are not used for data storage but for internal logic and management of the data. Public components provide access to the data but are not used for direct storage.

C. Public components are for data manipulation, while private components are for user interaction.

This is incorrect because public components are used for interaction with the ADT and manipulation of its data, while private components handle the internal workings of the ADT, not user interaction.

D. Both components serve the same purpose in an ADT.

This is incorrect because public and private components serve different roles. Public components provide an interface for external use, while private components handle the internal implementation details of the ADT.