C950 Data Structures and Algorithms II

Correct Answer

C. O(log n)

Explanation

In a balanced Binary Search Tree (BST), the smallest element is always found at the leftmost node. Because the tree is balanced, the maximum height is log n, meaning the number of steps to reach the leftmost node is proportional to log n. Hence, the worst-case time complexity to find the smallest data is O(log n).

Why other options are wrong

A. O(n)

This is incorrect because O(n) represents the complexity of traversing every node, which would only apply to an unbalanced tree that degenerates into a list. In a balanced BST, the traversal depth is log n.

B. O(n²)

This is incorrect because O(n²) typically relates to algorithms with nested loops, such as some sorting algorithms. A BST search operation never requires that level of repeated traversal or iteration.

D. O(n log n)

This is incorrect as O(n log n) is commonly seen in divide-and-conquer algorithms like merge sort or heap sort. Finding the smallest element in a BST is a straightforward path-following operation and does not require such complexity.

Correct Answer

 A. fsu::Vectorfsu::String v(10, "Hello");

Explanation

The correct syntax for creating a vector object of type fsu::String with 10 elements, each initialized to the value "Hello", is fsu::Vector<fsu::String> v(10, "Hello");. This constructor takes two arguments: the number of elements and the value to initialize each element with. Since "Hello" is a string literal that matches the type of fsu::String, this statement is valid and correctly initializes all 10 elements.

Why other options are wrong

B. fsu::Vectorfsu::String v(10);

This is incorrect because while this does create a vector of size 10, it does not initialize each element with "Hello". Instead, it initializes the elements with the default constructor of fsu::String, likely creating empty strings.

C. fsu::Vectorfsu::String v("Hello", 10);

This is incorrect due to the incorrect order and type of arguments. The vector constructor expects the size as the first argument, not a string. This would result in a compiler error or unexpected behavior.

D. fsu::Vectorfsu::String v(10, new fsu::String("Hello"));

This is incorrect because using new here introduces a pointer, which doesn't match the expected type fsu::String. Additionally, this causes unnecessary dynamic memory allocation and does not properly initialize the vector elements with the intended string value.

Correct Answer

C. fsu::g_copy (d.Begin(), d.End(), v.Begin())

Explanation

To copy elements from a deque (d) to a vector (v), the generic fsu::g_copy function requires an iterator to the beginning of the deque (d.Begin()) and the beginning of the vector (v.Begin()) where the elements should be copied to. The correct call is fsu::g_copy(d.Begin(), d.End(), v.Begin()), which copies all elements from the deque to the vector.

Why other options are wrong

A. fsu::g_copy (d.Begin(), d.End(), v);

This is incorrect because v is a vector, not an iterator. The g_copy function requires the destination to be an iterator, not the container itself. v.Begin() should be used instead.

B. fsu::g_copy (d.Begin(), d.End(), v, v + d.Size);

This option is incorrect because the destination should be an iterator pointing to the start of the vector, not the range (v to v + d.Size). The range-based copy would not work as expected in this context.

D. fsu::g_copy (d.Begin(), d.End(), v.Begin(), v.End());

This option is incorrect because the fourth argument (v.End()) specifies the end of the destination container, which is unnecessary for copying a fixed number of elements from d into v. The correct call should only include the starting iterator of the destination container.

E. None of the other choices

This is incorrect because option C is the correct approach for this task.

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

Explanation

An algorithm is a step-by-step set of instructions that define the procedure to solve a problem. These instructions provide a clear path of execution, guiding how the problem should be approached and resolved. Algorithms can be applied to a wide range of problems and are typically designed to be efficient and correct.

Why other options are wrong

A. data

While data is involved in algorithms, the core of an algorithm is the set of instructions used to manipulate or process the data, not the data itself. The algorithm defines the steps that operate on the data.

B. objects

Objects are instances of classes in object-oriented programming, but they are not the primary focus of an algorithm. An algorithm is about solving a problem using instructions, not manipulating objects per se.

D. classes

Classes are blueprints for creating objects in object-oriented programming, and while algorithms can be implemented in classes, the algorithm itself consists of instructions, not the classes.

Correct Answer

B. A mechanism to track the current state

Explanation

Recursive functions inherently rely on the system call stack to keep track of each function's state, including local variables and return addresses. Therefore, an explicit mechanism to track state is not required by the programmer — it is handled automatically. What is essential are the base case, the parameter passing for progression, and the system stack for function management.

Why other options are wrong

A. A base case to terminate recursion

 This is incorrect as the wrong answer because a base case is absolutely essential in recursion. Without it, the function would call itself indefinitely, leading to a stack overflow. It provides the stopping condition that ensures the recursion eventually terminates.

C. The use of a stack to manage function calls

This is incorrect because the function call stack is used automatically by the language runtime to keep track of recursive calls. Without it, the program wouldn’t be able to remember the point to return to after each recursive call completes. This stack behavior is what allows recursive calls to return correctly.

D. A way to pass parameters to the recursive calls

This is incorrect because recursion typically relies on passing parameters to change the state or progress toward the base case. Without the ability to pass parameters, recursive functions would have no way of adjusting their behavior or state across different calls.

Correct Answer

B. Iteration

Explanation

Iteration refers to the process of repeatedly executing a block of code multiple times. This is commonly done in programming using loops such as for, while, or do-while loops. Iteration allows for the execution of a set of instructions a specific number of times or until a condition is met.

Why other options are wrong

A. Recursion

Recursion refers to a process where a function calls itself in order to solve a problem. While it involves repeating an action, recursion differs from iteration because it is a function calling itself rather than using a loop to repeat an action.

C. Abstraction

Abstraction is a concept in programming where complex details are hidden, and only essential features are presented. It does not involve repeating actions multiple times.

D. Encapsulation

Encapsulation refers to the concept of bundling data and methods that operate on that data into a single unit or class. It does not involve repeating actions in programming.

Correct Answer

B. A Set is unordered and does not allow duplicates, unlike lists which are ordered.

Explanation

A Set is a data structure that stores unique elements and does not allow duplicates. Sets are typically unordered, meaning the elements are not stored in any specific sequence. Unlike lists or arrays, which maintain the order of insertion, a Set does not preserve this order. Sets are ideal when the uniqueness of elements is a primary concern, such as in situations where duplicates should be avoided.

Why other options are wrong

A. A Set allows duplicate elements, while lists do not.

This is incorrect because one of the defining features of a Set is that it does not allow duplicates. Lists, on the other hand, can contain duplicate elements.

C. A Set is a type of array that can only hold integers.

This is incorrect because a Set is a different type of data structure and is not an array. Additionally, Sets can hold any data type, not just integers.

D. A Set is a collection that maintains the order of elements.

This is incorrect because Sets are unordered collections, meaning they do not maintain the order in which elements are added.

Correct Answer

B. LowerBound(e) + Insert(i, e)

Explanation

When inserting into a sorted data structure, the most efficient approach involves locating the correct position where the element belongs to maintain order. The LowerBound(e) function efficiently finds the first position where e can be inserted without violating the sort order, often using a binary search algorithm (O(log n) complexity). This is more efficient than a linear search and ensures proper positioning for insertion.

Why other options are wrong

A. Find(e) + Insert(i, e)

This is incorrect because Find(e) searches for the element e in the structure, which is not helpful if e is not already present. It will not tell you where to insert e, only whether it exists, and its position if it does.

C. Search(e) + Insert(i, e)

This option is vague and incorrect in context. The term Search is not specific in standard sorted containers or algorithms, and its complexity is unclear. It’s typically a generic or linear approach, which is less efficient than LowerBound.

D. Includes(e) + Insert(i, e)

Includes is generally used to check for containment in a set or sequence, not to determine insertion position. It provides a boolean result (true/false), not an iterator or index for insertion, so it’s inefficient and unhelpful for ordered insertion.