exam prep

Question 1

data structure: linked list

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 1

insert: O(1)
- O(n) if sorted

remove: O(n) at position
- O(1) if removing front (maybe a queue)

search: O(n)

access: O(n)

(averages are the same)

Question 2

data structure: array

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 2

insert: depends
- O(1) if unsorted (and know the index where inserting)
- O(n) if unsorted. if resizing

remove: O(n)

search: O(n)
- O(logn) if sorted

access: O(1)

(averages are all the same)

Question 3

data structure: stack

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 3

insert: O(1)

remove: O(1)

search: O(n) (but not really applicable)

access: O(n)
- O(1) from the top

(averages are all the same)

Question 4

data structure: hash table

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 4

insert: O(n)
- avg: O(1)

remove: O(n)
- avg O(1)

search: O(n)
- avg O(1)

access: N/A

Question 5

data structure: binary search tree

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 5

insert: O(n)

remove: O(n)

search: O(n)

access: O(n)

(averages are O(logn) for all)

Question 6

data structure: avl tree

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 6

O(logn) for everything

Question 7

data structure: 2-3 tree / b-tree

list the worst case time complexity for:
insertion, removal, search, access/peak

(what about averages?)

Answer 7

O(logn) for everything

Question 8

what does a compression map do?

Answer 8

a compression map takes a hash code and maps it into a specific range (to fit in your table)

• using modulo is a simple form of a compression map

Question 9

To minimize collisions, patterns in the keys should NOT…

Answer 9

result in patterns in the hash values

Question 10

there are two parts of a hash function…

Answer 10

1. hash code
   - maps key to an integer (if it isn’t one already)
2. compression map
   - maps hash code to fit in the range of our table

Question 11

2 properties of a good hash function:

Answer 11

• minimizes collisions
• fast to compute

Question 12

the load factor of a hash table is:

Answer 12

number of entries (n)

—– divided by —–

size of array (N)

Question 13

collision resolution

what’s the first step?

then what?

Answer 13

1. minimize collisions by creating a good hash function
   - the polynomial hash map is good at turning words into uniformly distributed integers
   - To break up patterns, use an array whose length is prime
2. implement an effective collision strategy

Question 14

what are the 2 collision strategies that we learned?

Answer 14

1. open addressing

• simple search pattern:
  
  • if h(k) already occupied, check the next spot
  • treat array as circular if necessary
• variant search pattern:
  
  • check h(k) + d, h(k) + 2d, h(k) + 3d, . . . for some step size d that is relatively prime to N

(two numbers are relatively prime if they share no common divisors other than 1)

acceptable for low load factors ( < 0.75 )

2. separate chaining

• linked list that corresponds to each index in the table

this strategy allows for load factors > 1

Question 15

in order to achieve the favourable performance a hash table can have, a hash table needs what 3 properties?

Answer 15

a hash table requires:

• a good hash function,
• a good collision resolution strategy, and
• a reasonable load factor

Question 16

in a hash table ordered traversal takes _________ time, although this is rarely used for hash tables

Answer 16

O(n logn)

1. traverse entire table and copy keys into separate array - O(n)
2. sort - O(n logn)

Question 17

what is a leaf or terminal node?

Answer 17

a node with no children

Question 18

sibling nodes all have the same _______ node

Answer 18

parent

Question 19

In a post-order traversal, all ______ nodes are acted on before their _______ node

Answer 19

child, parent

Question 20

A pre-order traversal is also called a ___________ search

Answer 20

depth-first

Question 21

A _____ binary tree is one in which every row has the maximum number of nodes

Answer 21

perfect (i think)

Question 22

a perfect binary tree of height h contains _________ nodes

(what’s the formula)

Answer 22

2^(h+1) − 1

Question 23

how do you access the parent of a node in a binary heap?

Answer 23

(k-1) / 2

Question 24

how do you access the left and right child of a node in a binary heap?

Answer 24

left: k * 2 + 1
right: k * 2 + 2

Question 25

T or F: an empty tree is still technically a tree

Answer 25

True

Question 26

The running time of getMedianValue() in a full BST

Answer 26

O(1)

Question 27

After inserting the following values, in order, into a BST, this will be the height of tree. [10,8,20,2,9,30,22,27]

Answer 27

4

Question 28

This node is *promoted* when 8 is deleted. 10 8 20 2 9 30

Answer 28

9

Question 29

The new root after deleting 10 10 8 20 2 9 30

Answer 29

20

Question 30

for sweaty tryhards: To increase the likelihood of a balanced BST, one could preprocess an array of values using this O(nlog(n)) operation/algorithm to allow for more strategic insertions

Answer 30

merge sort processing before middle-outward inserts

Question 31

This operation is performed when a node with 2 keys receives a new key, causing a promotion of a key up to its parent

Answer 31

a (node) split

Question 32

what does this node method do? boolean ___?_____() { return children[0] == null; }

Answer 32

check's if it's a leaf node

Question 33

A structure that consists of nodes (or vertices) connected by edges, where each edge links a pair of nodes.

Answer 33

a graph or tree

Question 34

The node at the top of a tree data structure

Answer 34

root

Question 35

A single node, or a structure consisting of a root node with at most two children, where each child is itself the root of this kind of structure

Answer 35

binary tree

Question 36

Given a BST with n nodes, what is the worst-case running time for the getHeight() method? (asymptotic notation)

Answer 36

O(n)

Question 37

The addition of these references can help reduce stack overflows when searching/inserting into particularly deep trees

Answer 37

parent node references

Question 38

Although it maintains an O(h) search/insert runtime, when comparing full tree types, this tree grows quickly in height compared to others, resulting in a slightly less efficient runtime

Answer 38

bst

Question 39

what is the time complexity for calling retrieveMax() on a heap?

Answer 39

O(logn) O(1) to get value. then O(logn) to adjust tree