WGU C949 Exam Review C949 WGU C949 - Data Structures and Algorithms Pre-Assessment | FREQUENTLY TESTED QUESTIONS WITH CORRECT ANSWERS | BRAND NEW!

Algorithm

A set of instructions followed step by step to solve a problem

Characteristics of an Algorithm

1. Clear & unambiguous

2. Well-defined inputs

3. Well-defined outputs

what will be produced?

4. Finite-ness

5. Feasible

6. Language independent

Factors of an Algorithm

1. Modularity (can be broken down)

2. Correctness

3. Maintainability (no major changes when redefining the algorithm)

4. Functionality

5. Robustness (ability to define problem clearly)

6. User friendly

7. Simplicity

8. Extensibility (Future developers can understand it & build upon it)

Which factor takes the ability to easily update an algorithm into consideration?

maintainability

What is a high-level consideration in an algorithm’s design?

simplicity

Prior analysis

things you'd consider before implementing an algorithm, such as processing speed

Post analysis

happens after implementation

Types of Algorithms

-Brute-force algorithm

-Searching algorithm

-Sorting algorithm

-Recursive algorithm

-Backtracking algorithm

-Divide & conquer algorithm

-Greedy algorithm

-Dynamic programming algorithm

-Randomized algorithm

Brute Force Algorithm

an algorithm that tries all possible solutions in order then chooses the best one

Example of searching algorithms

linear search and binary search

Linear Search Algorithm

Starts from the beginning of a list & checks each element until the search key is found or the end of the list is reached.

Data can be sorted or unsorted

Binary Search Algorithm

starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated

Sorting Algorithms

Bubble Sort

Selection Sort

Insertion Sort

Quick Sort

Merge Sort

RADIX

Bubble Sort Algorithm

Compares elements that are side by side & determine if the left element is greater than the right element. If so, it swaps them and continues to compare elements until it reaches the end of the list. The largest # is "bubbled" to the top of the list

Selection Sort Algorithm

finds the lowest value in an array & moves it to the front of an array

Uses a sorted & unsorted list

*nested loop

Insertion Sort Algorithm

Takes 2 elements & moves them to a sorted list, sorts them least to greatest, then goes back to the unsorted list & keeps moving elements down to the sorted list, making swaps 1 at a time until the list is fully sorted.

Quicksort Algorithm

Quicksort divides the array into 2 parts low & high)

All values in the low partition are <= to the pivot value

All values in the high partition are >= to the pivot value

Merge Sort Algorithm

Breaks data into small groups, puts the groups in order, then combines groups until all are in order

*divide & conquer algorithm

What function is used with a merge sort?

recursion

Radix Sort

distributes the elements into buckets based on each digit's value. By repeatedly sorting the elements by their significant digits, from the least significant to the most significant, Radix Sort achieves the final sorted order.

greedy algor

finds the best solution at a give moment

Data structure

A way of storing, organizing, and performing operations on data

Nonlinear Data Structures

Elements are not in sequential order

Ex: tree & graph

Linear Data structure

Elements are in sequential order and adjacent elements are attached

List examples of data structures

1. Record

2. Array

3. Linked list

4. Binary Tree

5. Hash table

6. Heap

7. Graph

Record

a data structure that stores subitems

Array

a data structure that is ordered and indexed. It's elements are mutable, but must be of the same data type. Duplicates are allowed

Linked list

ordered list of items stored in nodes

each node stores data & pointer to (or the address of) the next node

elements are linked using pointers

T/F: Linked list have slower access times than arrays

True because they are not indexed

Binary Tree

a data structure in which each node stores data and has up to two children

the top node is the root

parts of a binary tree

root - the top node (no parent)

node - each child

leaf - a node with no child

internal node - has at least 1 child

edge

The link (line) from a node to a child in a graph

depth

The # of edges on the path from the root to the node

The root node has depth 0

level

Nodes with the same depth form a tree level

height

The largest depth of any node

A tree w/ 1 node as height 0

Hash Table

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

what are elements in a hash table called?

bucket

how long does it take to search a well-designed hash table on average?

O(1)

Full Binary Tree

Each node has 0 or 2 children

Complete Binary Tree

a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

Perfect Binary Tree

all internal nodes have 2 children and all leaf nodes are at the same level

Max Heap

a tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys

Min Heap

a tree that maintains the simple property that a node's key is less than or equal to the node's childrens' keys

graph

a data structure for representing connections among items

A vertex (or node) represents an item in a graph

An edge represents a connection b/w vertices

What operations are performed on a data structure?

accessing or updating stored data

searching for specific data

inserting new data

removing data

What is a class in OOP?

A blueprint for creating objects(instances)

Which characteristic of an algorithm is independent in nature?

Uses an agnostic code repository

Means it is language independent (multiple programming languages can implement it)

Time complexity

amount of time needed to execute code

includes an algorithms worst case

Space complexity

Quantity of space (in memory) required to solve a problem & produce an output

auxiliary space complexity

the space complexity not including the input data

What is the best case time complexity?

O(1)

element is at the beginning of list

what is the average case time complexity?

O(n)

element is in the middle

what is the worst case time complexity?

O(n)

element is at the end or not in the list

Abstract Data Type (ADT)

A data type whose properties are specified without prior knowledge of how they'll work

What is a high-level consideration in an algorithm’s design?

simplicity

What is the primary method used to search for an item in a sorted array?

binary search

Which algorithm requires data sorting as its first step?

binary search

Which data type do heap sorts work with?

tree-based structure

Which search algorithm has the best performance when the data set is sorted?

interval search

What is the advantage that a linked list has over an array?

grows and shrinks as needed

What would be the best data structure for a hash table with simple chaining?

doubly linked list

Which characteristic of a class allows it to be used as an abstract data type (ADT)?

It consists of variables and methods.

what does .pop() do for a stack

removes the 1st element from the top of the list

what does .pop() do for a queue

Popfront - Remove the list item from the front of the list

Pop back - Remove the list item from the back of the list

inorder traversal

left subtree, root, right subtree

preorder traversal

root, left subtree, right subtree

What uses the first in first out method

queue

what uses the last in first out method

stack

stack

Linear data structure where insertions & deletions are allowed only at the end (the top)

queue

Items are inserted at the end of the queue and removed from the front of the queue

Priority Queue

a queue in which the highest-priority elements are removed first; within a priority value, the earliest arrival is removed first.

what does the dequeue operation do

Removes & returns the item at the front of the queue

what does the enqueue operation do

Adding to the back (the end) of the line (queue)

what function removes all items from a list?

clear()

what function removes the 1st instance of a specified element?

remove()

what tool is used to implement a deque ADT

collections

Time complexity for bubble sort

O(n^2)

what kind of function would you see with bubble sort?

nested loop

Time complexity for merge sort

O(n log n)

Time complexity for selection sort

O(n^2)

Big O Notation

describes how the runtime of an algorithm grows as the input size grows

Determining big O: when adding terms what order term is kept?

Highest

Determining big O: when multiplying terms what happens to constants?

They are omitted

What runtime is O(1)

Constant

What runtime is O(log n)

Logarithmic

What runtime is O(n)

Linear

What runtime is O(n log n)

Loglinear

What runtime is O(n^2)

Quadratic

What runtime is O(c^n)

Exponential

Which tool in Python is used to implement a deque ADT?

collections

Which data structure is used to implement a dictionary data type?

hash table

Which operator is a type of assignment operator?

+=

3 multiple choice options

how do you determine the runtime of nested loops in big-O notation?

summing the runtime of the inner loop over each outer loop iteration

compression

transforms data to use fewer bits

set abstract data type

collection of distinct elements

what happens if you try to add an element to a set that already exists in the set?

there is no effect

T/F: Every set is a subset of itself.

true

T/F: For all elements in set X to also be in set Y, Y must have at least the same number of elements in X.

true

set - difference

The difference of sets X and Y, denoted as X \ Y, is a set that contains every element that is in X but not in Y, and no additional elements.

set - intersection

The intersection of sets X and Y, denoted as X ∩ Y, is a set that contains every element that is in both X and Y, and no additional elements.