Deck 18: Searching and Sorting Algorithms

Question 1

Define a key comparison.

Answer 1

A key comparison is a comparison between the key of the search item and the key of an item in the list.

Question 2

The sequential search algorithm requires that the list be sorted.

Answer 2

False

Question 3

Binary search requires a sorted list.

Answer 3

True

Question 4

If L is a sorted list of size 1024, at most ____ comparisons are needed to determine whether x is in L using binary search.

Question 5

For a comparison tree, how many leaf nodes are there for a list containing five items? In other words, how many permutations are there?

Question 6

Both the quick sort and the merge sort algorithms sort a list by partitioning it.

Question 7

The merge sort algorithm partitions the list by ____.

Question 8

What does these terms refer to:

- $\gg$ asymptotic:

Question 9

What does these terms refer to:

- $\gg$ Big-O:

Question 10

What does these terms refer to:

- $\gg$ binary search:

Question 11

What does these terms refer to:

- $\gg$ binary tree:

Question 12

What does these terms refer to:

- $\gg$ branch:

Question 13

What does these terms refer to:

- $\gg$ bubble sort:

Question 14

What does these terms refer to:

- $\gg$ comparison-based search algorithm:

Question 15

What does these terms refer to:

- $\gg$ comparison tree:

Question 16

What does these terms refer to:

- $\gg$ heap sort:

Question 17

What does these terms refer to:

- $\gg$ insertion sort:

Question 18

What does these terms refer to:

- $\gg$ key:

Question 19

What does these terms refer to:

- $\gg$ leaf:

Question 20

What does these terms refer to:

- $\gg$ merge sort:

Question 21

What does these terms refer to:

- $\gg$ node:

Question 22

What does these terms refer to:

- $\gg$ path:

Question 23

What does these terms refer to:

- $\gg$ pivot:

Question 24

What does these terms refer to:

- $\gg$ quick sort:

Question 25

What does these terms refer to:

- $\gg$ root:

Question 26

What does these terms refer to:

- $\gg$ selection sort:

Question 27

What does these terms refer to:

- $\gg$ sequential search:

Question 28

What does these terms refer to:

- $\gg$ target: