WGU C949 STUDY GUIDE

WGU C949 STUDY GUIDE

10 studiers today 4.2 (19 reviews) Students also studied Terms in this set (95) Western Governors UniversityD 333 Save WGU C949 Data Structures and Alg...102 terms bodiewoodPreview C949 Data Structures and Algorithm...173 terms AidenOSprague Preview C949 WGU Terminology 72 terms VeraButlerPreview WGU C 12 terms Ant ArrayA data structure that stores an ordered list of items, with each item is directly accessible by a positional index.Linked ListA data structure that stores ordered list of items in nodes, where each node stores data and has a pointer to the next node.Bianary Search TreeA data structure in which each node stores data and has up to two children, known as a left child and a right child.Hash TableA data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector).Hashingmapping each item to a location in an array (in a hash table).Chaininghandles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket.Hash keyvalue used to map an index bucketeach array element in a hash table ie A 100 elements hash table has 100 buckets modulo hash functioncomputes 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 searchingHash tables support fast search, insert, and remove.Requires on average O(1) Linear search requires O(N) modulo operator %common has function uses this. which computes the integer remainder when dividing two numbers.

Ex: For a 20 element hash table, a hash function of key % 20 will map keys to

bucket indices 0 to 19.Max-HeapA binary tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys. (Actually, a max-heap may be any tree, but is commonly a binary tree).*a max-heap's root always has the maximum key in the entire tree.Heap storageHeaps 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 insertAn 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 removeAlways 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) PercolatingThe upward movement of a node in a max-heap Min-HeapSimilar to a max-heap, but a node's key is less than or equal to its children's keys.

Heap - Parent and child indicesBecause heaps are not implemented with node structures and parent/child pointers, traversing from a node to parent or child nodes requires referring to nodes by index. The table below shows parent and child index formulas for a heap.ie 1) parent index for node at index 12? 5 *** ((12-1) // 2) = 5 or 12 //2 -1 = 5 2) child indices for a node at index 6? 13 & 14 ** 2 6 + 1 = 13 and 2 * 6 + 2 = 14 **Double# and add 1, double# and add 2 Node index Parent Index Child Indices

0 N/A 1, 2

1 0 3, 4

2 0 5, 6

3 1 7, 8

4 1 9, 10

5 2 11, 12

Heap - parent_indexparent_index = (node_index - 1) // 2 or node_index // 2 - 1 Heap - left_child_indexleft_child_index = 2 * node_index + 1 Heap - right_child_indexright_child_index = 2 * node_index + 2 Implementing priority queues with heaps.Both functions return the value in the root, but the Pop function removes the value and the Peek function does not. Pop is worst-case O(logN) and Peek is worst-case O(1).Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty, GetLength) happen in constant time O(1).Array based listA list ADT implemented using an array. An array-based list supports the common list ADT operations, such as append, prepend, insert after, remove, and search.Linked list vs ArrayIf 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.ListAn ADT for holding ordered data. Dups ok

Sequence type: A mutable container with ordered elements.

Underlying data structures: Array, linked list

Array in Javageneric class that supports different data types. declared as follows, where T is the data type.

TupleSequence type: An immutable container with ordered elements.

StackAn 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 operationsExample 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.Implementing a stack in python (Linear data structure) Can be implemented in Python using a class with a single LinkedList data member.The class has two methods, push() and pop().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.pop() removes the head of the stack's list by calling the LinkedList's remove_after() method and then returns the removed node.Implementing a queue in python (Linear data structure) Can also be implemented in Python using a class with a single LinkedList data member and class methods push() and pop().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.The pop() method removed the queue's head node and is identical to Stack's pop() method.