Searching

Question 1

How many compares are used for search hits in sequential search in the worst case?

Answer 1

N compares

Question 2

How many compares to insert into an inittally empty Linked List Symbol Table?

Answer 2

N^2 / 2

Question 3

How many compares does a search hit use in a BST?

Answer 3

2 ln N

Question 4

How many compares do insertions and search misses in a BST require?

Answer 4

2 ln N

Question 5

What is the height of a red-black BST?

Answer 5

2 lg N

Question 6

What is the average lenth of a path from root to node in a RB tree?

Answer 6

1.00 lg N

Question 7

Which operations take logarithmic time in the worst case in a RB BST?

Answer 7

• Search
• inesrt
• min
• max
• floor
• ceiling
• rank
• select
• delete min
• delete max
• range count

Question 8

What are the compares used for search and insert in the worst case for 2-3 trees?

Answer 8

lg N

Question 9

What is the average length of the lists in separate chaining?

Answer 9

N / M

Question 10

Why is the probability that the number of keys in a list is within a small constant factor of N/M, close to 1?

Question 11

What is the growth rate of the average length of the longest list in a separate chaining?

Answer 11

log N / log log N

Question 12

What are the number of compares for miss and insert in a Separate Chaining has table?

Answer 12

N/M

Question 13

How does get() work in sequential search in an unordered symbol table?

Answer 13

Scan through list, using equals() to compare search key with key in each node.

Question 14

How does put() work in a linked list implementation of an unordered symbol table?

Answer 14

Same as get(), however update value once match is found, else inserted at beginning.

Question 15

How does binary search work?

Answer 15

Compare search against key in middle half.
* If search < middle, search left, else right.

Question 16

How many compares does Binary Search in an ordered array use?

Answer 16

lg N + 1

Question 17

How many accesses does it take to insert a key into an ordered array, in the worst case?

Answer 17

2N

Question 18

What is the order of growth for get, contains, floor, ceiling, rank in an ordered array?

Answer 18

log N

Question 19

What is the order of growth for deleteMin, delete and put in an ordered array ST?

Answer 19

N

Question 20

How many accesses does it take to insert a key into an initially empty table?

Answer 20

N^2

Question 21

What is the worst case for search and insert, in sequential search? (Unordered linked lists)

Answer 21

N

Question 22

What is the worst case for search and insert in binary search (ordered arrays)?

Answer 22

lgN, 2N

Question 23

What are the pros and cons of SequentialSearchST?

Answer 23

• Best fow tiny ST’s
• Slow for large STs

Question 24

What are the pros and cons of BinarySearchST?

Answer 24

• Optimal search and space, order based
• Slow insert

Question 25

What are the pros and cons of BST?

Answer 25

• Easy implement, order based

Question 26

What are the pros and cons of RedBlack BSTs?

Answer 26

• Optimal search and insert, order based
• Space for links

Question 27

What are the pros and cons of Hash Tables?

Answer 27

• Fast search/insert for common data
• Need hash for each type, no order, space for links/empty

Question 28

What is the recursive relation of Binary Search?