EXAM Flashcards
What is a hash function?
A function that can be used to map data of arbitrary size to fixed-size values
What are 3 names for values returned by hash functions?
- Hash Values
- Hash Codes
- Digests
What are hash values used for?
Index fixed-size table
What is the table indexed by a hash function called?
Hash table
What is it called when you index a hash table?
Hashing or Scatter Storage Addressing
What is necessary to create a perfect hash function?
Table/map has to contain at least as many positions as number of elements being hashed
With hashing what is collision?
Non-unique keys being made
What are 5 types of hashing?
- Division
- Folding
- Mid-square function
- Extraction
- Radix Transformation
Which hashing method is preferred if little is known about the keys?
Division
What are 2 kinds of Folding with Hashing?
- Shift Folding
- Boundary Folding
What are 2 methods for reducing collissions?
- Increase size of table
- Changing the hash function
What is bucket addressing with hashing?
Each element in a hash table can hold multiple elements
What do Maps store?
Key Value Pairs
What are key value pairs called?
Entries
What is the difference between Maps and Dictionaries?
Maps must have unique keys, whereas dictionaries can have repeated keys
What is a set?
A collection of distinct objects
How are sets usually implemented?
Trees
In a tree, what node has no parents?
The Root
Which node has no children?
Leaves
What are the links between nodes in a tree called?
Edges/arcs
What is the length of a path in a tree?
The number of edges
What are the 2 categories of trees?
- Unordered
- Ordered
What makes a binary tree a binary search tree?
All nodes to the left of the root are <= the root
What is a red-black tree?
Self balancing search tree
What 2 features make a perfect binary tree?
- All internal nodes have 2 children
- All leaf nodes are on the same level
What 2 features make a complete binary tree?
- All levels completely filled except possibly last level
- All keys on last level are as far to the left as possible
What does it mean to traverse a tree?
Visit every node in the tree
What is “in-order” tree traversal?
- Visit all nodes to the left of subtree
- Visit Root
- Visit all nodes to the right of subtree
What is “pre-order” tree traversal?
- Visit root
- Visit all nodes to left
- Visit all nodes to the right
What is a graph?
A way of representing relationships between pairs of objects
What notation is used for undirected edges?
{ set notation }
What are 3 popular ways to represent graphs?
- Edge list structure
- Adjacency list structure
- Adjacency matrix or Incidence matrix
What is the weight of an edge?
The distance between nodes
What are 2 different methods for traversing graphs?
- Depth-first
- Breadth-first
Which graph traversal method uses a stack?
Depth-first
Which graph traversal method uses a queue?
Breadth-first
