EXAM

Question 1

What is a hash function?

Answer 1

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

Question 2

What are 3 names for values returned by hash functions?

Answer 2

1. Hash Values
2. Hash Codes
3. Digests

Question 3

What are hash values used for?

Answer 3

Index fixed-size table

Question 4

What is the table indexed by a hash function called?

Answer 4

Hash table

Question 5

What is it called when you index a hash table?

Answer 5

Hashing or Scatter Storage Addressing

Question 6

What is necessary to create a perfect hash function?

Answer 6

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

Question 7

With hashing what is collision?

Answer 7

Non-unique keys being made

Question 8

What are 5 types of hashing?

Answer 8

1. Division
2. Folding
3. Mid-square function
4. Extraction
5. Radix Transformation

Question 9

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

Answer 9

Division

Question 10

What are 2 kinds of Folding with Hashing?

Answer 10

1. Shift Folding
2. Boundary Folding

Question 11

What are 2 methods for reducing collissions?

Answer 11

1. Increase size of table
2. Changing the hash function

Question 12

What is bucket addressing with hashing?

Answer 12

Each element in a hash table can hold multiple elements

Question 13

What do Maps store?

Answer 13

Key Value Pairs

Question 14

What are key value pairs called?

Answer 14

Entries

Question 15

What is the difference between Maps and Dictionaries?

Answer 15

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

Question 16

What is a set?

Answer 16

A collection of distinct objects

Question 17

How are sets usually implemented?

Answer 17

Trees

Question 18

In a tree, what node has no parents?

Answer 18

The Root

Question 19

Which node has no children?

Answer 19

Leaves

Question 20

What are the links between nodes in a tree called?

Answer 20

Edges/arcs

Question 21

What is the length of a path in a tree?

Answer 21

The number of edges

Question 22

What are the 2 categories of trees?

Answer 22

1. Unordered
2. Ordered

Question 23

What makes a binary tree a binary search tree?

Answer 23

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

Question 24

What is a red-black tree?

Answer 24

Self balancing search tree

Question 25

What 2 features make a perfect binary tree?

Answer 25

1. All internal nodes have 2 children
2. All leaf nodes are on the same level

Question 26

What 2 features make a complete binary tree?

Answer 26

1. All levels completely filled except possibly last level
2. All keys on last level are as far to the left as possible

Question 27

What does it mean to traverse a tree?

Answer 27

Visit every node in the tree

Question 28

What is “in-order” tree traversal?

Answer 28

1. Visit all nodes to the left of subtree
2. Visit Root
3. Visit all nodes to the right of subtree

Question 29

What is “pre-order” tree traversal?

Answer 29

1. Visit root
2. Visit all nodes to left
3. Visit all nodes to the right

Question 30

What is a graph?

Answer 30

A way of representing relationships between pairs of objects

Question 31

What notation is used for undirected edges?

Answer 31

{ set notation }

Question 32

What are 3 popular ways to represent graphs?

Answer 32

1. Edge list structure
2. Adjacency list structure
3. Adjacency matrix or Incidence matrix

Question 33

What is the weight of an edge?

Answer 33

The distance between nodes

Question 34

What are 2 different methods for traversing graphs?

Answer 34

1. Depth-first
2. Breadth-first

Question 35

Which graph traversal method uses a stack?

Answer 35

Depth-first

Question 36

Which graph traversal method uses a queue?

Answer 36

Breadth-first