WGU C949 STUDY GUIDE(MOST IMPORTANT QUIZ)

WGU C949 STUDY GUIDE(MOST IMPORTANT QUIZ)

Leave the first rating Students also studied Terms in this set (80) Western Governors UniversityC 949 Save WGU C949 Data Structures and Alg...102 terms bodiewoodPreview C949 WGU Terminology 72 terms VeraButlerPreview

WGU C949 STUDY GUIDE

Teacher 95 terms badunique321 Preview

C949 D

173 term Aid ArrayA data structure that stores an ordered list of items, 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.Binary 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 (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 %Computes the integer remainder when dividing two numbers in a hash table.

Ex: For a 20 element hash table, a hash function of key 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.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.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.

Data Structure Types: Array, linked list

TupleArray Type An immutable(fixed) 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.QueueAn 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 ListA 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 listsA linked list with links from each node to both next and previous nodes.

DequeShort 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

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

Underlying data structures: Linked list, Array

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

Underlying data structures: Binary search tree, Hash table

Priority queueA 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 areUnique and immutable.Dictionary methodD1[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 loopA for loop over a dict retrieves each key in the dict.