WGU C949 Data Structures & Algorithms V4 FREQUENTLY TESTED QUESTIONS WITH CORRECT ANSWERS | BRAND NEW!

What is the 'Finiteness' characteristic of an algorithm?

An algorithm must have a finite number of steps and a defined endpoint, avoiding endless loops.

What is meant by 'Definiteness' in an algorithm?

Each step must have an exact, clear, and straightforward definition so it can be easily understood and executed.

What is the role of 'Input' in an algorithm?

Inputs are the values supplied to the algorithm from a predetermined range before processing begins.

What is the 'Output' of an algorithm?

The result produced after every step of the algorithm has been completed, with a clear relationship to the input.

What does 'Effectiveness' imply for an algorithm?

Each step must be doable and practicable within a finite time using fundamental operations and available resources.

What is the 'Generality' characteristic of an algorithm?

The ability of an algorithm to solve a group of issues or a variety of inputs within a defined domain, rather than just one specific case.

How is 'Modularity' defined in the context of algorithms?

Breaking a problem down into small, manageable steps or modules.

What defines the 'Correctness' of an algorithm?

When the given inputs consistently produce the desired output, indicating the design and analysis were accurate.

What is 'Maintainability' in algorithm design?

Designing an algorithm in a structured, straightforward way so that it can be redefined without requiring significant changes.

What does 'Robustness' refer to regarding algorithms?

The ability of an algorithm to define the problem clearly.

Why is 'Extensibility' important for an algorithm?

It ensures that other designers or programmers can easily use or build upon the existing algorithm.

What is a 'Brute Force' algorithm?

A straightforward approach that exhaustively tries all possible solutions; effective for small instances but inefficient for large ones.

How does a 'Recursive' algorithm function?

It breaks a problem into smaller, similar subproblems and repeatedly calls itself until reaching a base case.

What is the primary purpose of an 'Encryption' algorithm?

To transform data into a secure, unreadable form to ensure confidentiality and privacy.

What is a 'Backtracking' algorithm?

A trial-and-error technique that explores potential solutions and undoes choices that lead to incorrect outcomes.

What is the goal of a 'Searching' algorithm?

To find a specific target within a dataset, enabling efficient retrieval from collections.

What is the purpose of a 'Sorting' algorithm?

To arrange elements in a specific order, such as numerical or alphabetical, to improve organization and retrieval.

What does a 'Hashing' algorithm do?

Converts data into a fixed-size hash value to enable rapid access and retrieval in hash tables.

How does a 'Divide and Conquer' algorithm work?

It breaks a complex problem into smaller subproblems, solves them independently, and combines the results.

What is the strategy of a 'Greedy' algorithm?

Making locally optimal choices at each step in the hope of finding a global optimum.

What is the benefit of a 'Dynamic Programming' algorithm?

It stores and reuses intermediate results to avoid redundant computations, increasing efficiency.

What is a 'Randomized' algorithm?

An algorithm that utilizes randomness in its steps, often used when an approximate or probabilistic answer is sufficient.

What is the 'Base Case' in recursion?

The simplest instance of a problem that stops the recursion and is solved directly without further calls.

What is the 'Recursive Case' in recursion?

The part of the algorithm that breaks the problem into smaller instances and calls the function again.

What is the role of the 'Stack' in recursive algorithms?

It stores each recursive call; when the base case is reached, the stack unwinds as functions return their results.

What is the time complexity of a 'Linear Search'?

O(n), as it may need to check every element in the collection in the worst-case scenario.

When is it appropriate to use a 'Linear Search'?

When the collection is small, unsorted, or when simplicity is prioritized over performance.

What is the time complexity of linear search?

O(n)

What is the primary requirement for using binary search?

The array or list must be sorted.

What is the time complexity of binary search?

O(log n)

What is the best-case time complexity of linear search?

O(1), occurring when the target is the first element.

What is the worst-case time complexity of linear search?

O(n), occurring when the target is the last element or not present.

What is the best-case time complexity of binary search?

O(1), occurring when the target is the middle element.

When is interpolation search most effective?

When the data is uniformly distributed.

What is the average-case time complexity of interpolation search?

O(log log n)

How does Depth-First Search (DFS) explore a graph?

It explores as far as possible along one branch before backtracking.

How does Breadth-First Search (BFS) explore a graph?

It explores all neighbors at the present depth before moving to nodes at the next depth level.

What is the time complexity of both DFS and BFS?

O(V + E), where V is the number of vertices and E is the number of edges.

What is the core mechanism of Bubble Sort?

Repeatedly swapping adjacent elements if they are in the wrong order, 'bubbling' the largest element to the end.

What is the worst-case time complexity of Bubble Sort?

O(n^2)

What is the best-case time complexity of Bubble Sort with an optimized implementation?

O(n), occurring when the array is already sorted.

How does Selection Sort work?

It finds the minimum element in the unsorted portion and swaps it with the first unsorted element.

What is the time complexity of Selection Sort in all cases?

O(n^2)

When is Selection Sort particularly useful?

When memory writes are more expensive than comparisons.

How does Insertion Sort build a sorted list?

It builds the sorted list one element at a time by inserting each new element into its correct position within the already-sorted part.

What is the best-case time complexity of Insertion Sort?

O(n), occurring when the array is already sorted.

What is the worst-case time complexity of Insertion Sort?

O(n^2)

For what type of lists is Insertion Sort most efficient?

Small or nearly sorted lists.

What is the main advantage of binary search over linear search?

It has logarithmic time complexity, making it significantly faster for large datasets.

What happens if the interval becomes invalid (low > high) during a binary search?

The algorithm returns a 'not found' indication.

What is the primary characteristic of Merge Sort?

It is an efficient and stable sorting algorithm suitable for large datasets.

What is the worst-case time complexity of interpolation search?

O(n), occurring with highly skewed data distribution.

Which searching algorithm is best for small or unsorted collections?

Linear search.

What is the primary mechanism of Merge Sort?

It divides the list into halves, sorts each half recursively, and then merges the sorted halves.

What is the time complexity of Merge Sort in the worst case?

O(n log n)

What is a key disadvantage of Merge Sort regarding memory?

It requires additional space for the merging process.

How does Quicksort partition an array?

It selects a 'pivot' element and partitions the array into elements smaller and larger than the pivot.

What is the worst-case time complexity of Quicksort and why does it occur?

O(n^2); it occurs when the pivot selection is poor, leading to highly unbalanced partitions.

What data structure does Heap Sort utilize?

A binary heap.

Why is Heap Sort considered memory-efficient?

It is an in-place algorithm.

What is the primary use case for Counting Sort?

Sorting integers or items within a small, known range of possible values.

Is Counting Sort a comparative sorting algorithm?

No, it is a non-comparative sorting algorithm.

How does Radix Sort process data?

It processes individual digits of numbers, often starting from the least significant digit (LSD) or most significant digit (MSD).

What is the time complexity of Radix Sort?

O(n*k), where k is the number of digits in the largest number.

Under what condition is Bucket Sort most efficient?

When the input data is uniformly distributed.

What is the worst-case time complexity of Bucket Sort?

O(n^2), which occurs if all elements end up in a single bucket.

How does Shell Sort improve upon Insertion Sort?

It uses a gap sequence to sort elements far apart, gradually reducing the gap until a final insertion sort is performed.

What is Big O Notation used to describe?

The upper bound of an algorithm's time or space complexity, representing the worst-case scenario as input size grows.

What does O(1) constant time complexity mean?

The algorithm takes the same amount of time to execute regardless of the input size.

Which search algorithm typically exhibits O(log n) time complexity?

Binary search.

What happens to the runtime of an O(n) algorithm if the input size doubles?

The runtime also doubles.

What is the characteristic runtime behavior of O(n^2) algorithms?

The runtime increases quadratically; doubling the input size quadruples the runtime.

Which sorting algorithms are considered simple but inefficient for large datasets?

Bubble Sort, Selection Sort, and Insertion Sort.

Which sorting algorithms are generally preferred for large datasets?

Merge Sort, Quicksort, and Heap Sort.

What does O(2^n) exponential time complexity imply?

The runtime doubles with each additional element in the input, making it impractical for large inputs.

Why is Merge Sort considered stable?

It maintains the relative order of equal elements.

What is the primary advantage of using Big O Notation?

It allows for the comparison of algorithm efficiency independently of hardware or environmental factors.

What is the time complexity of an algorithm that generates all permutations of an input set?

O(n!) - Factorial Time

Why is factorial time complexity (O(n!)) considered impractical?

It is extremely poor and infeasible for even moderate input sizes.

What is the 'best case' in algorithm analysis?

The scenario where the algorithm performs the minimum possible number of operations.

Which case does Big O notation typically describe?

The worst-case complexity.

What is the 'average case' in algorithm analysis?

The scenario that represents the expected number of operations for a typical input.

Why are constant factors ignored in Big O notation?

Big O focuses on the growth rate as input size (n) increases, and constant multipliers do not affect the growth rate.

What is the rule for handling lower-order terms in Big O notation?

Drop them, as they become insignificant as n grows large.

How are logarithms with different bases treated in Big O notation?

They are considered equivalent because changing the base only introduces a constant factor, which is ignored.

Which grows faster: exponential functions or polynomial functions?

Exponential functions.

What is the time complexity of two nested loops, each running n times?

O(n^2)

What is the time complexity of two independent loops running sequentially, each n times?

O(n + n) which simplifies to O(n).

What is a data type in programming?

A classification that specifies the type of data a variable can hold, the operations allowed, and how it is stored in memory.

What are primitive data types?

The basic building blocks of data, such as integers, floating-point numbers, characters, and booleans.

What is an enumeration (enum)?

A data type that allows a variable to be a set of predefined constants, improving readability and type safety.

What are three primary advantages of using enums?

Readability, maintainability, and type safety.

What is a data structure?

A specific way of organizing and storing data so that it can be accessed and modified efficiently.

What is an Abstract Data Type (ADT)?

A theoretical model that defines the behavior and operations of a data structure from the user's perspective without specifying the implementation.

What is the defining characteristic of a Stack data structure?

Last-In-First-Out (LIFO) access.

What is the defining characteristic of a Queue data structure?

First-In-First-Out (FIFO) access.

What is a Hash Table?

A data structure that maps keys to values for efficient lookup.

What is a Linked List?

A series of connected nodes where each node contains data and a reference to the next node.

What does the 'dominant term' rule state in Big O notation?

Only the term with the highest growth rate is considered when determining complexity.

How does an enum improve code reliability?

It prevents assigning invalid values to variables by limiting them to a specific set of constants.