WGU C949 Terminology (2023/2024) Already Passed

WGU C949 Terminology (2023/2024) Already Passed record data structure that stores subitems, with a name associated with each subitem array a data structure that stores an ordered list of items, with each item is directly accessible by a positional index homogeneous data elements linked list data structure that stores *ordered* list of items in nodes, where each node stores data and has a pointer to the next node; can have multiple subitems binary tree A data structure that consists of nodes, with one root node at the base of the tree, and two nodes (left child and right child) extending from the root, and from each child node can have no children, single left or right, or both right and left hash table data structure that stores *unordered* items by mapping (or hashing) each item to a location in an array 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 data structure for representing connections among items, and consists of vertices connected by edges vertice part of a graph the represents an item in a graph edge part of a graph that represents a connection between to vertices in a graph what is an advantage of a linked list over an array? when inserting a new item at the beginning it causes no shift to the data ADT (Abstract data Type) data type described by predefined user operations, such as "insert data at rear", without indication how each operation is implemented list ADT for holding ordered data stack ADT which items are only inserted on or removed from the top of a stack LIFO Queue ADT in which items are inserted at the end of the queue and removed from the front of the queue FIFO deque ("deck") ADT in which items can be removed at both the front and back Bag ADT for stroing items in which the order does not matter and duplicate items are allowed Set ADT for collection of distinct items common underlying DS: Binary search tree, hash table Priority Queue a queue in which the highest-priority elements are removed first; within a priority value, the earliest arrival is removed first. common underlying DS: heap Dictionary (map) ADT that associates (or maps) keys with values common underlying DS: has table, binary search tree List, Bag ADTs with array, linked list as common underlying DS Stack, Queue, Deque ADTs with linked list as their only common underlying DS Peek ADT operation for a queue that returns but does not remove item at the front of the queue identity unique identifier that describes the object // symbol for floored division tuple behaves similar to a list but is immutable -- once created the els can not be chagned const array/list for i in range(0) sets i to 0 during the first iteration of the for loop, i to 1 during the second iteration, and finally i to 2 on the third iteration. The value within the parentheses is not included in the generated sequence. range(5, -6, -1) code for every int form 5 down to -5 range(10, 21, 2) code for every 2nd int from 10 to 20 polymorphism functional behavior depends on the argument types dynamic typing used to determine the type of objects as a program executes; Python Static Typing requires the programmer to define the type of every variable and every function parameter in a program's source code; C, C++ class keyword that can be used to create a user-defined type of object containing groups of related vars and fxns creates a new type of object __init__ instantiation of a class automatically calls this method defined in the class def this is also known as the constructor memory allocation the process of an app req and being granted memory garbage collection reference count is an integer count that reps how many vars ref an obj; when an obj ref count = 0 the obj is no longer referenced and is sent here ternary type of operation condition ? (T)Block1: (F)Block2 assignment type of operation for setting a var comparison type of operation for comparing data <, > ... equality type of operation == !== short data type long data type linked allocation A data structured contains the name, size, and starting block/cluster address of a file. A table is used to identify the address of each piece of the file. Storage is allocated using pointers to new locations as needed. mid-values deque A ______ is a "doubled-ended queue" List ADT that has elements of the same type so that the elements can be retrieved based on index or position (high + low)/2 mid-values calculation for binary search. toCeil() It is automatically available for garbage collection What is the effect on the object regarding garbage collection? Computing obj = new Computing(); obj = null mutable open to or capable of change, fickle immutable (adj.) not subject to change, constant unique and immutable Characteristics of keys in associative dictionary data type DictName[key].remove(value) method used to take a value out of a dictionary J.FileInputStream Java method used to read bytes from standard file Add(int index, Object x) command that inserts object x at position index in a list quick sort recursively breaks down a problem into two or more subproblems of the same or related type O(n^2) Bubble sort && Insertion sort time complexity bucket sort Best: O(n+k) Avg: O(n+k) Worst: O(n^2) Space: O(nk) for uniformly distributed nums across a range to be sorted bubble sort for i from 0 to N -1 if a[i] > a[i+1] swap(a[i], a[i +1] end for Bubble Sort Algorithm def shortSort(alist): exchanges = True passnum = len(alist)-1 while passnum > 0 and exchanges: exchanges = False for i in range(passnum): if alist[i]>alist[i+1]: exchanges = True temp = alist[i] alist[i] = alist[i+1] alist[i+1] = temp passnum = passnum-1 Quick Sort Algorithm int partition( void *a, int low, int high ) { int left, right; void *pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) { /* Move left while item < pivot */ while( a[left] <= pivot_item ) left++; /* Move right while item > pivot */ while( a[right] > pivot_item ) right--; if ( left < right ) SWAP(a,left,right); } /* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; } O(1) Big-O FindMin(x, y) { if (x < y) { return x } else { return y } } O(logn) Big-O BinarySearch(numbers, N, key) { mid = 0 low = 0 high = N - 1 while (high >= low) { mid = (high + low) / 2 if (numbers[mid] < key) { low = mid + 1 } else if (numbers[mid] > key) { high = mid - 1 } else { return mid } } return -1 // not found } Constant O(5) has a _____ runtime complexity. log-linear o(N log N) has a ________ runtime complexity. quadratic O(N + N^2) linear serach O(N) selection sort O(n^2) log_2(key) BinarySearch number of times to find num X is on both sides of equation What makes a function recursive? sorted a list passed to binary_search needs to be... shell sort Starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. gap value Z+ representing the distance between elements in an interleaved list; specifies the number of interleaved lists