Deck 9: Searching and Hashing Algorithms

Question 1

The analysis of algorithms enables programmers to decide which algorithm to use for a specific application.

Answer 1

True

Question 2

Associated with each item in a data set is a special member that uniquely identifies the item in the data set.

Answer 2

True

Question 3

The keys of the items in a data set are used in such operations as searching, sorting, insertion, and deletion.

Answer 3

True

Question 4

In the analysis of an algorithm, the key comparisons refer to comparing the key of the search item with the position of an item in the list.

Question 5

The sequential search always starts at the last element in the list and continues until either the item is found in the list or the entire list is searched.

Question 6

If the sequential search is unsuccessful, -1 is returned.

Question 7

You cannot write a recursive algorithm to implement a sequential search algorithm.

Question 8

When analyzing a search algorithm, we count the number of key comparisons because this number gives us the most useful information.

Question 9

The number of key comparisons in a sequential search depends on the value of the search item.

Question 10

The best and worst cases are likely to occur most of the time that we apply the sequential search on a list.

Question 11

When performing a sequential search, we assume all list elements are equally likely to be the target.

Question 12

A list is ordered if its elements are ordered according to some criteria.

Question 13

The elements of a list are usually in descending order.

Question 14

From the binary search algorithm, it follows that every iteration of the while loop cuts the size of the search list by half.

Question 15

Open addressing can be implemented in several ways.

Question 16

In linear probing, starting at location t, we search the array sequentially to find the next available array slot.

Question 17

All insertions and searches in the random probing method use a different sequence of random numbers.

Question 18

Quadratic probing reduces primary clustering and probes all the positions in the table.

Question 19

Both random and quadratic probings eliminate primary clustering.

Question 20

If two nonidentical keys are hashed to the same home position then the same probe sequence is followed for both keys.

Question 21

The same probe sequence is used for two nonidentical keys because random probing and quadratic probing are functions of the original key.

Question 22

To implement hashing, we use four arrays.

Question 23

A new item can be inserted at the beginning of the linked list because the data in a linked list is in no particular order.

Question 24

If you have 1000 items, each requiring 1 word of storage, chaining requires a total of 4000 words of storage.

Question 25

The most important operation performed on a list is the ____.

A) search algorithm
B) insert algorithm
C) deletion algorithm
D) allocation or initialization algorithm

Question 26

The unique member of an item is called the ____ of the item.

A) index
B) primacy
C) primitive
D) key

Question 27

The sequential search is also called a ____ search.

A) non-linear
B) quadratic
C) linear
D) binomial

Question 28

The ____ is an item's location in the array.

A) counter
B) probe
C) index
D) key

Question 29

In a sequential search, if the search item is the first element of a list, we make ____ comparison(s).

A) one
B) two
C) three
D) n

Question 30

If the search item is the last element in the list, the algorithm makes ____ comparison(s).

A) one
B) two
C) three
D) n

Question 31

The search item is called the ____.

A) source
B) target
C) key
D) component

Question 32

A binary search can be performed only on ____.

A) unordered lists
B) arrays
C) comparable lists
D) ordered lists

Question 33

The binary search algorithm uses the ____ technique to search the list.

A) divide-and-conquer
B) divide-and-divide
C) conquer-and-resign
D) divide-and-resign

Question 34

Sequential and binary search algorithms are called ____ search algorithms.

A) cumulative
B) compartmentalized
C) comparison-based
D) key-based

Question 35

In hashing, the data is organized with the help of a table, called the ____.

A) key table
B) index table
C) hash table
D) relative table

Question 36

In ____, the data is stored within the hash table.

A) closed addressing
B) open addressing
C) inverted addressing
D) converted addressing

Question 37

In ____, we assume that the array is circular so that if the lower portion of the array is full, we can continue the search in the top portion of the array.

A) quadratic probing
B) adjacent probing
C) non-linear probing
D) linear probing

Question 38

When we check the array locations t, (t + 1) % HTSize, (t + 2) % HTSize, . . ., (t + j) % HTSize it is called the ____ of the hash table.

A) probe sequence
B) probe value
C) hash value
D) kindred value

Question 39

____ is when more and more new keys would likely be hashed to the array slots that are already occupied.

A) Globbing
B) Adjacency
C) Clustering
D) Affinity

Question 40

Linear probing causes clustering that is called ____.

A) secondary clustering
B) linear clustering
C) primary clustering
D) primitive clustering

Question 41

One way to improve linear probing is to skip array positions by a ____.

A) fixed constant
B) random constant
C) dynamic value
D) key-relative value

Question 42

The ____ method uses a random number generator to find the next available slot.

A) linear probing
B) random probing
C) quadratic probing
D) non-linear probing

Question 43

In the random probing method, the ith slot in the probe sequence is ____.

A) (h(X) % HTSize) + ri
B) (h(X) + HTSize) % ri
C) (h(X) % ri) + HTSize
D) (h(X) + ri) % HTSize

Question 44

In the ____ method, if a collision occurs with the hash function h, we use a series of hash functions, h₁, h₂, . . ., h_s.

A) overhashing
B) recomputing
C) rehashing
D) precomputing

Question 45

If the hash function causes a cluster at a particular home position and the cluster remains under these probings, it is called ____.

A) primary clustering
B) secondary clustering
C) tertiary clustering
D) random clustering

Question 46

Linear probing that uses the increment value as a function of the key is called ____.

A) quadratic hashing
B) non-linear hashing
C) key hashing
D) double hashing

Question 47

In double hashing, if a collision occurs at h(X), the probe sequence is generated by using the rule: ____

A) (h(X) + i * g (X)) % HTSize
B) (h(X) * i * g (X)) % HTSize
C) (h(X) * i + g (X)) % HTSize
D) (h(X) % i + g (X)) % HTSize

Question 48

When an item is deleted from the hash table indexStatusList at position, say k, we set indexStatusList[k] to ____.

A) -1
B) 0
C) 1
D) 2

Question 49

When an item is added to the hash table indexStatusList at position, say i, we set indexStatusList[i] to ____.

A) -1
B) 0
C) 1
D) 2