WGU DSA1 C949 V3 FREQUENTLY TESTED QUESTIONS WITH CORRECT ANSWERS | BRAND NEW!

ID bubble sort

'swap', 'exchange' keywords so result 'bubbles' to the top

ID bucket sort

distributes values into buckets, then buckets are sorted

ID binary search

continually halving

ID merge sort

continually splits a list in half

ID quick sort

'pivot'

ID radix sort

sorting by least/most significant digits

Insertion Sort big O

n^2

Merge Sort big O

n log n

Quick Sort big O

n log n

Radix Sort big O

nk

Selection Sort big O

n^2

Shell Sort big O

(n log n)^2

Binary Search big O

worst: log n

avg: log n

best: 1

Heap Sort big O

n log n

Array big O

Access: 1

Search: n

Insert: n

Delete: n

worst-case

Stack/Queue/LinkedList big O

Access: n

Search: n

Insert: 1

Delete: 1

worst-case

Hash Table big O

Access: 1 or n/a

Search: n

Insert: n

Delete: n

best is 1 for everything

Binary Search Tree big O

worst: n

best: log n

B-Tree big O

log n

Red-Black Tree big O

log n

AVL Tree big O

log n

Efficiency

algo performs task quickly and uses minimal resources

Correctness

must produce the correct and accurate output for all valid inputs

Clarity

should be easy to understand and comprehend, making it maintainable and modifiable

Scalability

should handle larger data sets and problem sizes without a significant decrease in performance

Reliability

should consistently deliver correct results under different conditions and environments

Optimality

striving for the most efficient solution within given constraints

Robustness

capable of handling unexpected inputs or errors gracefully

Adaptability

can be applied to a range of related problems with minimal adjustments

Simplicity

simple as possible while meeting requirements, avoids unnecessary complexity

record

stores subitems, often called fields, with a name associated with each subitem.

array

stores an ordered list of items, where each item is directly accessible by a positional index.

linked list

stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.

binary tree

each node stores data and has up to two children, known as a left child and a right child.

hash table

stores unordered items by mapping (or hashing) each item to a location in an array.

heap

A max-heap is a tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys. A min-heap is a tree that maintains the simple property that a node's key is less than or equal to the node's childrens' keys.

graph

data structure for representing connections among items, and consists of vertices connected by edges. A vertex represents an item in a graph. An edge represents a connection between two vertices in a graph.

list

ADT - holding ordered data

under: array, linked list

dynamic array

A dynamic array is an ADT for holding ordered data and allowing indexed access.

under: array

stack

ADT in which items are only inserted on or removed from the top of a stack.

under: linked list

queue

ADT in which items are inserted at the end of the queue and removed from the front of the queue.

under: linked list

deque

ADT in which items can be inserted and removed at both the front and back.

under: linked list

bag

ADT for storing items in which the order does not matter and duplicate items are allowed.

under: array, linked list

set

ADT for collection of distinct items

under: bst, hash table

priority queue

each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.

under: heap

dict / map

ADT that associates (or maps) keys with values.

under: hash table, bst

growth rate function order

1

log n

n

n log n

n^2

2^n

constant time

O(1)

logarithmic time

O(log n)

linear time

O(n)

log-linear time

O(n log n)

quadratic time

O(N^2)

exponential time

O(c^n)

bubble sort big O

n^2