EXAM Flashcards

1
Q

What is a hash function?

A

A function that can be used to map data of arbitrary size to fixed-size values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are 3 names for values returned by hash functions?

A
  1. Hash Values
  2. Hash Codes
  3. Digests
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are hash values used for?

A

Index fixed-size table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the table indexed by a hash function called?

A

Hash table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is it called when you index a hash table?

A

Hashing or Scatter Storage Addressing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is necessary to create a perfect hash function?

A

Table/map has to contain at least as many positions as number of elements being hashed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

With hashing what is collision?

A

Non-unique keys being made

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are 5 types of hashing?

A
  1. Division
  2. Folding
  3. Mid-square function
  4. Extraction
  5. Radix Transformation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Which hashing method is preferred if little is known about the keys?

A

Division

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are 2 kinds of Folding with Hashing?

A
  1. Shift Folding
  2. Boundary Folding
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are 2 methods for reducing collissions?

A
  1. Increase size of table
  2. Changing the hash function
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is bucket addressing with hashing?

A

Each element in a hash table can hold multiple elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What do Maps store?

A

Key Value Pairs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are key value pairs called?

A

Entries

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the difference between Maps and Dictionaries?

A

Maps must have unique keys, whereas dictionaries can have repeated keys

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a set?

A

A collection of distinct objects

17
Q

How are sets usually implemented?

18
Q

In a tree, what node has no parents?

19
Q

Which node has no children?

20
Q

What are the links between nodes in a tree called?

A

Edges/arcs

21
Q

What is the length of a path in a tree?

A

The number of edges

22
Q

What are the 2 categories of trees?

A
  1. Unordered
  2. Ordered
23
Q

What makes a binary tree a binary search tree?

A

All nodes to the left of the root are <= the root

24
Q

What is a red-black tree?

A

Self balancing search tree

25
What 2 features make a perfect binary tree?
1. All internal nodes have 2 children 2. All leaf nodes are on the same level
26
What 2 features make a complete binary tree?
1. All levels completely filled except possibly last level 2. All keys on last level are as far to the left as possible
27
What does it mean to traverse a tree?
Visit every node in the tree
28
What is "in-order" tree traversal?
1. Visit all nodes to the left of subtree 2. Visit Root 3. Visit all nodes to the right of subtree
29
What is "pre-order" tree traversal?
1. Visit root 2. Visit all nodes to left 3. Visit all nodes to the right
30
What is a graph?
A way of representing relationships between pairs of objects
31
What notation is used for undirected edges?
{ set notation }
32
What are 3 popular ways to represent graphs?
1. Edge list structure 2. Adjacency list structure 3. Adjacency matrix or Incidence matrix
33
What is the weight of an edge?
The distance between nodes
34
What are 2 different methods for traversing graphs?
1. Depth-first 2. Breadth-first
35
Which graph traversal method uses a stack?
Depth-first
36
Which graph traversal method uses a queue?
Breadth-first