Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
42 Cards in this Set
- Front
- Back
|
______ is a data structure accompanied by a set of access functions |
Abstract data type |
|
|
Complexity analysis measures what? |
- The time required - The arithmetic operations required - Memory/space required |
|
|
The results of complexity analysis are affected by? |
- Processor speed - Ram and disk access time - Code produced by compiler |
|
|
Define: - Sequential search - Binary search - Interpolation Search |
- Starts at the beginning of the list and compares each successive items until a matched is found or it reaches the end of the list. (O(n)) - Works on already sorted array. Keeps halving subarrays until a match is found, or subdivision is impossible. (O(lg n)) - A variant of binary search, midpoint is set to where item is likely to be found (O(lg lg n)) |
|
|
What is considered when analyzing sorts? |
- Number of comparisons - Data movements |
|
|
Define the following sorting algorithms: - Bubble sort - Selection sort - Insertion sort |
- Compares successive pairs of items, swapping them if out of order (O(n^2)) - Starts by selecting the smallest item above the current item in the array and swaps them. (O(n^2)) - Starts by comparing the second item in the array, and swaps them if they are out of place. the left part of the array is always sorted. (O(n^2) for worst case O(n) for best case ) |
|
|
Define the following sorting algorithms: - Merge Sort - Quick sort |
- Divides the array into 2 equal sized subarrays and sorts it into a temp array. copies it back after. (O(n lg n )) - |
|
|
- Lists are classified as _____ data structures - Lists are ______ that supports operations such as add, insert, delete e.t.c |
- Linear - Abstract data types |
|
|
- Define arrays - Define Linked lists |
- linear, random data structures whose elements are accessed by unique identifiers called index's - Linear data structure that consists of 0 or more nodes, where each node has a data and a pointer to the next |
|
|
When a node is freed what has to be done? |
- Garbage collection (done for you in java) |
|
|
____ lists are where the last node points to the first one. |
Circular linked list. |
|
|
_____ is a table usually implemented with a 2D array, However space could be saved by using _____ and _______. |
- Sparse table - 1D arrays - Linked lists |
|
|
- ____ are linear data structures that follows a LIFO policy - ____ are linear data structures that follows a FIFO policy |
- Stacks
- Queues |
|
|
- Push and pop (also enqueue and dequeue) are ______ operations - Stacks can only be accessed at the _____, while Queues can be accessed at the _____ and ____. |
- Constant time operations - Top - Head and tail |
|
|
- A tree is a ______ structure - A tree is a collection of what? - A set of trees is called a ____ - The height of a tree is the _______ |
- Hierarchical - Vertices: Nodes ( contains data and information on the next). - Edges: Contains 2 vertices together - Forest - The distance from the root node the furtherest node away. |
|
|
How are binary search tree (ordered binary trees) organized? |
- Every left child of the parent node is less than or equal to the parent. - Every right child of the parent is greater than the parent. |
|
|
- Nodes with no children are called _____ - The height is a tree in the best case, when it is minimized is ___, and ____ in the worst case - What is the complexity for searching a well balanced tree? |
- Leaf nodes - lg(n ) - n-1 - O(lg n) |
|
|
What are the 2 types of traversals? |
- Depth-first: Recursively visits every node on the far left or right - Breadth-first: starts at the highest level visiting every node on each level from left to right |
|
|
What is the difference between depth-first in order, pre-order, and post-order? |
- In-order visits the nodes in ascending order - Pre-order processes the node first, before going into the left and right subtrees - Post-order processes the left subtree first then the right then the nodes |
|
|
How do you delete from a tree that has 2 children? |
- Find the smallest node on the right subtree and "splice" it out |
|
|
How do you find the balance of a tree? |
Balance = right height - left height |
|
|
Define the following Terminologies: - Ancestor node: - Son node: - Outside subtree: |
- This happens in case 3 of inserting into AVL tree - Ancestor node: Parent of pivot node. - Son node: Child node of the pivot node, on the part to inserted node. - Outside node: if the pivot node is negative the left-subtree is the outside subtree, vise versa. |
|
|
How do you add a node to the inside-subtree? |
- Double rotation - Set the sons left or right child to grandsons right or left child and put off to the side - Rotate grandson, and set child pointer to son - Rotate grandson with pivot. - Adjust balances |
|
|
How do you do a right rotation? |
- Set the sons right child to pivots left child and put it off to one side - Set son node as left pointer of ancestor node - Set pivot node as right child of son node - Adjust balances |
|
|
When adding to the outside tree, the _____ should be pointing to the ______ at the end When adding to the inside tree, the _____ should be pointing to the ______ and the ___ at the end |
- Ancestor, son node - Grandson, pivot, son node |
|
|
What are graphs? Graphs are a generalization of ______ structures |
- Graphs are data structure that can have many predecessors and many successors - Linear |
|
|
A graph consists of a non empty set of ______ and a possible non empty set of edges that _____ |
Vertices, edges that connects the vertices |
|
|
- If the edge pair is unordered, the graph is said to be an ______ - Two vertices are connected if _______ - When is an edge incident on a vertex? |
- Undirected graph - An edge directly connects them - If the vertex is one of the edges endpoint |
|
|
what is a complete graph what is a simple path?
|
All the vertices are connected All vertices are connected different except for first or last |
|
|
A ______ is a cycle that begins and end at the same vertex, with no edges repeated A ______ graph a digraph containing no cycles |
- Circuit - Acyclic graph |
|
|
What is the complexity analysis for DFS? |
- O(|V| + |E|) for adjacency list - O(V^2) for adjacency matrix |
|
|
what is a greedy algorithm, and give an example |
- Dijkstra's algorithm - Greedy algorithm is one that always tries to find the best solution when trying to find an answer |
|
|
What is the complexity analysis for Dijkstra's algorithm? What is the complexity analysis if heaps are used on the algorithm? If negative weights are used, then use _____ algorithm |
- O(|V^2|) - O((|E| + |V|) lg|V|) - Fords |
|
|
What are minimum spanning trees? How are minimum spanning trees created? |
- Are trees with minimum sum of edge weights - Using DFS and BFS |
|
|
What is a topological order? ___/__ vertex is a vertex with no outgoing edges |
- Linear ordering of vertices - Sink/ minimum |
|
|
Hash table are classified as ____ Search operation in hash table takes ____ |
- Set structures (No predecessor or successor) - Constant time O(1) |
|
|
______ is when each position in the table is a reference to a linked list ______ is when each position is a block of memory big enough to hold several items |
- Separate chaining - Bucket addressing - They are both not space efficient |
|
|
What is the quadratic probing function? What method is used to avoid secondary clustering? Define coalesced chaining |
- (i-1)^i-1 *((i+1)/2)^2 - Double hashing - Combines link fields(used to point to another entry in the table) with probing, -1 indicates end of chain. |
|
|
- How do you calculate _______? - Average # of reads - Load factor - Hashing efficiency |
- Average = Total # of reads/ words - Load factor = words/ table size - Hashing efficiency = load factor / average |
|
|
-What are the properties of a max heap? - What is the complexity analysis? |
- A max heap is a binary tree where the value of each node is greater than the value of its children. min heap is opposite. - A perfectly balanced tree, where all the leaf nodes at the bottom are pushed to the left part of tree. - O(lg n) |
|
|
How do you get the _____ position of a node in HEAPSORT - Left child - Right child - parent |
- Left child = 2i + 1 - Right child = 2i +2 - Parent = (i-1) / 2 |
|
|
B tree is a ______ B trees are good for sorting data in ________ If the leaf node to add is full, it must be _____, B trees grows ______ |
- Multiway balanced tree. - Secondary storage - Split, upwards |
