WGU C949 (MOST IMPORTANT QUIZ)C949 WGU C949 - Data Structures and Algorithms Pre-Assessment | FREQUENTLY TESTED QUESTIONS WITH CORRECT ANSWERS | BRAND NEW!

Array

A data structure that stores an ordered list of items, each item is directly accessible by a positional index.

Linked List

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

Binary Search Tree

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

Hash Table

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

Hashing

mapping each item to a location in an array (in a hash table).

Chaining

handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket.

Hash key

value used to map an index

bucket

Each array element in a hash table

(A 100 elements hash table has 100 buckets)

modulo hash function

Computes a bucket index from the items key.

It will map (num_keys / num_buckets) keys to each bucket.

ie... keys range 0 to 49 will have 5 keys per bucket.

50 / 10 = 5

hash table searching

Hash tables support fast search, insert, and remove.

Requires on average O(1)

Linear search requires O(N)

modulo operator %

Computes the integer remainder when dividing two numbers in a hash table.

Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket indices 0 to 19.

Max-Heap

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

Heap storage

Heaps are typically stored using arrays. Given a tree representation of a heap, the heap's array form is produced by traversing the tree's levels from left to right and top to bottom. The root node is always the entry at index 0 in the array, the root's left child is the entry at index 1, the root's right child is the entry at index 2, and so on.

Max-heap insert

An insert into a max-heap starts by inserting the node in the tree's last level, and then swapping the node with its parent until no max-heap property violation occurs.

The upward movement of a node in a max-heap is sometime called percolating.

Complexity O(logN)

Max-heap remove

Always a removal of the root, and is done by replacing the root with the last level's last node, and swapping that node with its greatest child until no max-heap property violation occurs.

Complexity O(logN)

Percolating

The upward movement of a node in a max-heap

Min-Heap

Similar to a max-heap, but a node's key is less than or equal to its children's keys.

Linked list vs Array

If a program requires fast insertion of new data, a linked list is a better choice than an array.

Abstract Data Type (ADT)

A data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented.

List

An ADT for holding ordered data.

Data Structure Types: Array, linked list

Tuple

Array Type

An immutable(fixed) container with ordered elements.

Stack

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

*Last-in First-Out

Underlying data structures: Linked list

Push(stack, x), pop(stack), peek(stack), IsEmpty(stack), GetLength(stack)

*Pop & peek should not be used on a empty stack.

Stack operations

Example starting with stack: 99, 77 (top is 99).

Push(stack, x)

Inserts x on top of stack

Push(stack, 44). Stack: 44, 99, 77

Pop(stack)

Returns and removes item at top of stack

Pop(stack) returns: 99. Stack: 77

Peek(stack)

Returns but does not remove item at top of stack

Peek(stack) returns 99. Stack still: 99, 77

IsEmpty(stack)

Returns true if stack has no items

IsEmpty(stack) returns false.

GetLength(stack)

Returns the number of items in the stack

GetLength(stack) returns 2.

Queue

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

*first-in first-out ADT.

Underlying data structures: Linked list, Array, Vector

The Queue class' push() method uses the LinkedList append() method to insert elements in a queue.

Both the Stack and Queue pop() methods operate exactly the same by removing the head element and returning the removed element.

Linked List

A linear data structure, much like an array, that consists of nodes, where each node contains data as well as a link to the next node, but does not use contiguous memory.

Doubly-linked lists

A linked list with links from each node to both next and previous nodes.

Deque

Short for double-ended queue. An ADT in which items can be inserted and removed at both the front and back.

Underlying data structures: Linked list

Bag

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

Underlying data structures: Linked list, Array

Set

An ADT for a collection of distinct items. (No Duplicates)

Underlying data structures: Binary search tree, Hash table

Priority queue

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

Underlying data structures: Heap

Dictionary (Map)

A dictionary is an ADT that associates (or maps) keys with values.

Underlying data structures: Binary search tree, Hash table

Dictionary keys are

Unique and immutable.

Dictionary method

D1[key].remove(value)

dict.items()

returns a view object that yields (key, value) tuples.

dict.keys()

returns a view object that yields dictionary keys.

dict.values()

returns a view object that yields dictionary values.

Dict for loop

A for loop over a dict retrieves each key in the dict.

dict methods

my_dict.clear()

Removes all items from the dictionary

my_dict = {'Bob': 1, 'Jane': 42}

my_dict.clear()

print(my_dict)

{}

my_dict.get(key, default)

Reads the value of the key entry from the dict. If the key does not exist in the dict, then returns default.

my_dict = {'Bob': 1, 'Jane': 42}

print(my_dict.get('Jane', 'N/A'))

print(my_dict.get('Chad', 'N/A'))

42

N/A

my_dict1.update(my_dict2)

Merges dictionary my_dict with another dictionary my_dict2. Existing entries in my_dict1 are overwritten if the same keys exist in my_dict2.

my_dict = {'Bob': 1, 'Jane': 42}

my_dict.update({'John': 50})

print(my_dict)

{'Bob': 1, 'Jane': 42, 'John': 50}

my_dict.pop(key, default)

Removes and returns the key value from the dictionary. If key does not exist, then default is returned.

my_dict = {'Bob': 1, 'Jane': 42}

val = my_dict.pop('Bob')

print(my_dict)

{'Jane': 42}

Underlying data structures: Binary search tree, Hash table

Set, Dictionary(Map)

Underlying data structures: Heap

Priority queue

Underlying data structures: Linked list, Array

Bag, Queue, List

Underlying data structures: Linked list

Deque, Stack

Common operations for ADT List

Append, Prepend, InsertAfter, Print, PrintReverse, Sort, Remove, Search, IsEmpty, GetLength

Common operations for ADT Queue, Stack, Deque

Push, Pop, Peak, IsEmpty, GetLength

Float

Data type is a single-precision 32-bit floating point. Use a float (instead of double) if you need to save memory in large arrays of floating point numbers.

Double

A data type is a double-precision 64-bit floating point. For decimal values, this data type is generally the default choice.

Byte

Data type is an 8-bit signed two's complement integer. The byte data type is useful for saving memory in large arrays.

Range(5)

0 1 2 3 4

Every integer from 0 to 4

Assignment vs comparison

= vs ==

garbage collection

It reclaims memory from data structures implemented using linked allocations. Python is a managed language, meaning objects are deallocated automatically by the Python runtime, and not by the programmer's code. When an object is no longer referenced by any variables, the object becomes a candidate for deallocation.

Python will deallocate objects with a reference count of 0. However, the time between an object's reference count becoming 0 and that object being deallocated may differ across different Python runtime implementations.

Reference Count

An integer counter that represents how many variables reference an object. When an object's count is 0, that object is no longer referenced.

Memory allocation

The process of an application requesting and being granted memory.

Binary Search

An algorithm that searches a SORTED LIST for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.

constructor

The __init__ method, commonly known as a constructor, is responsible for setting up the initial state of the new instance.

Null

A special value indicating a pointer points to nothing.

Graph

A data structure for representing connections among items, and consists of vertices connected by edges.

Graph is a data structure that consists of following two components:

A vertex (vertices) represents an item (node) in a graph. An edge represents a connection between two vertices in a graph.

vertex

item in a graph. A finite set of vertices also called as nodes

V -> Number of Vertices

edge

a connection between two vertices in a graph. A finite set of ordered pair of the form (u, v)

E -> Number of Edges

Binary Search Tree

In a list, each node has up to one successor. In this tree, each node has up to two children, known as a left child and a right child.

Leaf

A tree node with no children.

Internal node

A node with at least one child.

Parent

A node with a child is said to be that child's parent.

Node's ancestors

include the node's parent, the parent's parent, etc., up to the tree's root.

Root

The one tree node with no parent (the "top" node).

Depth, level, and height (binary tree)

The link from a node to a child is called an edge.

A node's depth is the number of edges on the path from the root to the node. The root node thus has depth 0.

All nodes with the same depth form a tree level.

A tree's height is the largest depth of any node. A tree with just one node has height 0.

A binary tree is full if:

every node contains 0 or 2 children.

A binary tree is complete if:

all levels except possibly the last are completely full, and the last level has all its nodes to the left side

A binary tree is perfect if:

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

Tree traversal

An algorithm visits all nodes in the tree once and performs an operation on each node.

BST inorder traversal

Visits all nodes in a BST from smallest to largest, which is useful for example to print the tree's nodes in sorted order. Starting from the root, the algorithm recursively prints the left subtree, the current node, and the right subtree.

Left -> Root -> Right

Preorder traversal

Root -> Left -> Right

Binary Search Tree

An especially useful form of binary tree, which has an ordering property that any node's left subtree keys ≤ the node's key, and the right subtree's keys ≥ the node's key.

*When searching, search always starts at the root

Pop()

Stack: 99, 77, 66

The pop() removes the head of the stack's list by calling the LinkedList's remove_after() method and then returns the removed node.

Pop(stack) returns: 99. Stack: 77

Queue: queue: 43, 12, 77

The pop() method removed the queue's head node and is identical to Stack's pop() method.

Pop(queue) returns: 43. Queue: 12, 77

Priority Queue:

Removes and returns the item at the front of the queue, which has the highest priority.

Push()

Stack: numStack 7, 5

push() adds a node to the top of the stack's list by calling LinkedList's prepend() method.

*New elements are place on the top of the stack, not at the bottom of the stack. push(numStack, 8) = 8, 7, 5

Queue: queue: 43, 12, 77

push() adds a node to the end of the queue's list by calling LinkedList's append() method.

*New elements are added to the end of a queue.

Push(queue, 56). Queue: 43, 12, 77, 56

Priority Queue:

The priority queue push operation inserts an item such that the item is closer to the front than all items of lower priority, and closer to the end than all items of equal or higher priority.

Fast sorting algorithm

A sorting algorithm that has an average runtime complexity of O(N logN) or better.

Bubble sort algorithm

*Look for something that swaps so the result can "bubble" to the top. best used when the data is small

Sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. Bubble sort uses nested loops. Given a list with N elements, the outer i-loop iterates N times.

Because of the nested loops, bubble sort has a runtime of O(N2). Bubble sort is often considered impractical for real-world use because many faster sorting algorithms exist.

Figure 11.20.1: Bubble sort algorithm.

BubbleSort(numbers, numbersSize) {

for (i = 0; i < numbersSize - 1; i++) {

for (j = 0; j < numbersSize - i - 1; j++) {

if (numbers[j] > numbers[j+1]) {

temp = numbers[j]

numbers[j] = numbers[j + 1]

numbers[j + 1] = temp

}}

Merge sort algorithm

**Look for something that continually splits a list in half.

A sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of 1 element is reached, as list of 1 element is already sorted.

mergedNumbers[mergePos] = numbers[rightPos]

Quickselect algorithm

**Look for keywords "Pivot" and/or "Split"

selects the kth smallest element in a list. Ex: Running quickselect on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5.

The best case and average runtime complexity of quickselect are both O(N). In the worst case, quickselect may sort the entire list, resulting in a runtime of O(N2).

Figure 11.21.1: Quickselect algorithm.

// Selects kth smallest element, where k is 0-based Quickselect(numbers, first, last, k) {

if (first >= last)

return numbers[first]

lowLastIndex = Partition(numbers, first, last)

if (k <= lowLastIndex)

return Quickselect(numbers, first, lowLastIndex, k)

return Quickselect(numbers, lowLastIndex + 1, last, k)

}

Big-O Complexity Chart

Best to worst

O(1)

O(log n)

O(n)

O(n log n)

O(n^2)

O(2^n)

O(nl)

python keywords

false, class, finally, is, raise, none, continue, for, lamda, return, true, def, from, nonlocal, try, and, del, global, not, while, as, elif, if, or, with, assert, else, import, pass, yield, break, except, in, print