Q6Cisp430

Front 1

What is the best definition of a collision in a hash table?

Back 1

Two entries with different keys have the same exact hash value.

Front 2

Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?

Back 2

Interchange sorts

Front 3

Suppose we are sorting an array of eight integers using heapsort, and we have just finished one of the reheapifications downward. The array now looks like this: 6 4 5 1 2 7 8How many reheapifications downward have been performed so far?

Back 3

2

Front 4

Suppose that you place 180 items in a hash table with an array size of 200. What is the the average number of table elements that you expect to have examined during a successful search for a double hashing?

Back 4

2.56

Front 5

The following is the specification of the table’s never_used member function.

// bool never_used(size_t index) const// Precondition: index < CAPACITY.// Postcondition: If data[index] has never// been used, then the return value is true.// Otherwise the return value is false.What would be the best implementation for the inline never_used member function?

Back 5

template bool Table::never_used(size_t index) const{ return (data[index].key == NEVER_USED);}

Front 6

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using double hashing (with hash2(key)returning the value 1 + (key % 101)), where will the 411 be placed in the table?

Back 6

7

Front 7

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[1] list?

Back 7

1623

Front 8

What are the advantages of hashing over performing a binary search?

Back 8

Hashing can be fast in the average case. Adding and deleting elements is easier in a container that provides hashing, because a binary search requires that the items remain sorted.

Front 9

How are collisions resolved in open-address hashing?

Back 9

Collisions are resolved by placing the item in the next open spot of the array.

Front 10

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[0] list?

Back 10

0 and 811

Front 11

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using linear probing and a division hash function, where will the 0 be placed in the table?

Back 11

1

Front 12

If we will be able to arrange the key in an order, what is the advantage to keep each linked list of the table sorted from smallest key to largest key?

Back 12

If the lists are kept in order, then a search can stop as soon as it reaches a key that is greater than the target

Front 13

One common way of ordering records is to choose one special field, which is then called the ______________ , and to sort the records according to that ___________ .

Back 13

key field, key field

Front 14

What is the worst-case running times for a selectionsort?

Back 14

quadratic

Front 15

Provide two ways to use pointer arithmetic to print the ninth element of an array data

Back 15

cout << (data + 9)[0];cout << (data + 6)[3];

Front 16

What would be the best statement about quicksort and mergesort?

Back 16

The running time of the quicksort depends on the pivot element. The running time of mergesort does not depend on the array elements, but on the array length.

Front 17

What is the worst-case running times for a mergesort ?

Back 17

O ( n log n)

Front 18

What is the average-case running times for a quicksort ?

Back 18

O ( n log n)

Front 19

An entire array can be sorted by a series of swaps. Any sorting algorithm that is based on swapping is referred to as an ________________________.

Back 19

interchange sort

Front 20

If we have a data array as following, what is the "cout << ++((data + 5)[1]); " displayed?

Back 20

21

Front 21

What is the worst-case time for binary search finding a single item in an array?

Back 21

Logarithmic time

Front 22

What is the worst-case time for quicksort to sort an array of n elements?

Back 22

O(n²)

Front 23

What is the worst-case time for heapsort to sort an array of n elements?

Back 23

O(n log n)

Front 24

In our new table class (section 12.3), the array is still a fixed size. So why do we need the copy constructor, destructor, and overloaded assignment operator?

Back 24

The ADT does use dynamic memory (the linked lists).

Front 25

What are the stopping cases in the recursive binary search function?

Back 25

When size becomes zero, or when the target is found.

Front 26

The following is the specification of the table’s is_present member function.// CONSTANT MEMBER FUNCTIONS for the table class:bool is_present(int key) const// Postcondition: The return value is true if there is a record in the table with the// specified key. Otherwise, the return value is false.What would be the best implementation for the is_present member function?

Back 26

template bool table::is_present(int key) const{ bool found; std::size_t index; assert(key >= 0); find_index(key, found, index); return found;}

Front 27

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using linear probing and a division hash function, where will the 103 be placed in the table?

Back 27

0

Front 28

What would be the best insert member function for the chaining version (section 12.3) of the table?

Back 28

template void Table :: insert(const RecordType& entry){ main_savitch_6B::node *cursor; cursor = find_ptr(entry.key); //returns a pointer to a node with the specified key (or returns NULL if there is no such node) if (cursor == NULL) { list_head_insert (data[hash(entry.key)], entry); ++used; } else cursor->setdata(entry);}

Front 29

Suppose that we place 180 items in a hash table with an array size of 200. What is the load factor?

Back 29

0.9

Front 30

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using double hashing (with hash2(key)returning the value 1 + (key % 101)), where will the 308 be placed in the table?

Back 30

5

Front 31

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using linear probing and a division hash function, where will the 205 be placed in the table?

Back 31

102

Front 32

We want to place 1000 elements in a hash table, and we’d like an average search to examine just two table elements. How big does the table’s array need to be for a double hashing?

Back 32

1250

Front 33

What is the worst-case running times for a quicksort ?

Back 33

O( n2 )

Front 34

If we have a data array as following, what is the meaning of "selectionsort((data + 4), 2); "?

Back 34

Sorts data[4] through data[5]

Front 35

Which statement of the following is the most appropriate one?

Back 35

All the sorting algorithms presented in chapter 13 apply to any type of values sorted according to any reasonable ordering relation. The array values do not need to be integers.

Front 36

Suppose that data is an array of 1000 integers. What would be a single quicksort (section 13.2) function call that will sort the 100 elements data[222] through data[321]?

Back 36

quicksort((data + 222), 100);

Front 37

If we have a data array as following, what is the meaning of "selectionsort((data + 5), 4); "?

Back 37

Sorts data[5] through data[8

Front 38

Which one of the following is a correct statement?

Back 38

Divide-and-conquer works best with two equally sized subproblems,each of which is solved with a recursive call

Front 39

If we have a data array as following, what would be the data array after going through the third run of an insertionsort?

Back 39

Front 40

Which recursive sorting technique always makes recursive calls to sort subarrays that are about half the size of the original array?

Back 40

merge sort

Front 41

What additional requirement is placed on an array, so that binary search may be used to locate an entry?

Back 41

The array must be sorted.

Front 42

Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here: 1 2 3 4 5 0 6 7 8 9Which statement is correct? (Note: Our selectionsort picks largest items first.)

Back 42

The algorithm might be either selectionsort or insertionsort.

Front 43

In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?

Back 43

n - 1

Front 44

Compute the H(9) value (H is the halving function)?

Back 44

4

Front 45

When is a serial search an acceptable choice?

Back 45

A serial search is acceptable when you are searching a small array only a few times.

Front 46

Suppose that a hash table is full and you try to insert a new entry. What happens if the new entry’s key is not already in the table?

Back 46

If the key was not already present, then the assertion tests whether size( ) < CAPACITY is true, and this assertion fails, halting the program.

Front 47

Why does a binary search function require parameters of the first array index and the size of the array?

Back 47

Because of the recursive calls in a binary search, the array is repeatedly split in half. The first and size parameters keep track of the portion of the array that is currently being searched.

Front 48

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using double hashing (with hash2(key)returning the value 1 + (key % 101)), where will the 205 be placed in the table?

Back 48

102

Front 49

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[800] list?

Back 49

empty

Front 50

The following is the specification of the table’s is_vacant member function. // bool is_vacant(size_t index) const// Library facilities used: stdlib.h// Precondition: index < CAPACITY.// Postcondition: If data[index] is not now// being used, then the return value is true.// Otherwise the return value is false.What would be the best implementation for the inline is_vacant member function?

Back 50

template inline bool Table:: is_vacant(size_t index) const{ Return (data[index].key < 0);}

Front 51

Suppose that a hash table is full and you try to insert a new entry. What happens if the new entry’s key is already in the table?

Back 51

If the key was already present, then the record with that key is overwritten.

Front 52

Compute the H(8) value (H is the halving function)?

Back 52

4

Front 53

Which statement of the following is the most appropriate one?

Back 53

Selectionsort and insertionsort have quadratic running times in both the worst case and the average case. This is comparatively slow. However, if the arrays to be sorted are short, or if the sorting program will only be used a few times, then they are reasonable algorithms to use. Insertionsort is particularly good if the array is nearly sorted beforehand.

Front 54

What would be the best statement about heapsort and selectionsortt?

Back 54

Heapsort uses a heap to store, locate, and swap values, which results in a much more efficient implementation than selectionsort does.

Front 55

An array contain the following elements, 5 19 13 36 23 2, what would be all the steps of each iteration of insertionsort, using the largest element version of swapping?

Back 55

Front 56

What would be the best statement about mergesort, quicksort and heapsort?

Back 56

The mergesort and heapsort have a worst-case running time that is O(n log n). The heapsortt and quicksort do not require an additional array

Front 57

What would be the big O notation for a merges sort recursive sorting?

Back 57

O(n log n)

Front 58

What is the average-case running times for a mergesort ?

Back 58

O ( n log n)

Front 59

If we have a data array as following, what would be a temp array after going through the second run of a mergesort?

Back 59

Front 60

If we have a data array as following, what is the meaning of "selectionsort((data + 2), 5); "?

Back 60

Sorts data[2] through data[6]

Front 61

What kind of initialization needs to be done for an open-address hash table?

Back 61

The key at each array location must be initialized.

Front 62

Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

Back 62

Elements in each half of the array are sorted amongst themselves.

Front 63

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10Which statement is correct?

Back 63

The pivot could be either the 7 or the 9.

Front 64

How can clustering of elements in linear probing can be solved?

Back 64

Double hashing can solve this problem by using a second hash function to resolve a collision.

Front 65

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[3] list?

Back 65

3247

Front 66

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[4] list?

Back 66

empty

Front 67

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using linear probing and a division hash function, where will the 411 be placed in the table?

Back 67

3

Front 68

We want to place 1000 elements in a hash table, and we’d like an average search to examine just two table elements. How big does the table’s array need to be for a linear probing?

Back 68

1500

Front 69

Suppose that you place 180 items in a hash table with an array size of 200. What is the the average number of table elements that you expect to have examined during a successful search for a linear probing?

Back 69

5.50

Front 70

Compute the H(7) value (H is the halving function)?

Back 70

3

Front 71

Suppose that you place 180 items in a hash table with an array size of 200. What is the the average number of table elements that you expect to have examined during a successful search for a chained hashing?

Back 71

1.45

Front 72

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using linear probing and a division hash function, where will the 2 be placed in the table?

Back 72

4

Front 73

A small array, which is actually part of a larger array, is called a ______________.

Back 73

subarray

Front 74

If we have a data array as following, what would be the array after going through the first positions interchange of a quicksort?

Back 74

Front 75

Which statement of the following is the most appropriate one?

Back 75

In divide-and-conquer sorting methods, the values to be sorted are split into two approximately equal groups, the groups are sorted by a recursive call, and then the two sorted groups are combined into the final sorted list. Mergesort and quicksort are examples of divide-and-conquer sorting algorithms.

Front 76

An array contain the following elements, 5 19 13 36 23 2, what would be all the steps of each iteration of selectionsort, using the largest element version of swapping?

Back 76

Front 77

Why is mergesort a good choice for sorting a large file?

Back 77

A large file may be sorted effectively by mergesort by dividing the file into several pieces, and merging the sorted pieces into a single file. The individual pieces can be removed after the file is sorted.

Front 78

What is the average-case running times for a selectionsort?

Back 78

quadratic

Front 79

If we have a data array as following, what would be the array after going through the third positions interchange of a quicksort?

Back 79

Front 80

If we have a data array as following, what would be the data array after going through the second run swap function of a selectionsort?

Back 80

Front 81

In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which function has a better implementation because of this difference?

Back 81

Two or more of the above functions

Front 82

Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

Back 82

42

Front 83

Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here: 2 4 5 7 8 1 3 6Which statement is correct? (Note: Our selectionsort picks largest items first.)

Back 83

The algorithm is not selectionsort, but it might be insertionsort.

Front 84

Compute the H(1) value (H is the halving function)?

Back 84

1

Front 85

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[400] list?

Back 85

empty

Front 86

What would be a problem with linear probing?

Back 86

Linear probing can result in clustering of elements when several different keys are hashed to the same location. Insertions and searching take longer as clustering gets worse.

Front 87

The following is a pseudocode for Serial Search// Searches for a desired item in the n array elements starting at a[first]Set a size_t variable i to 0, and set a boolean variable found to false.while ((i < n) && !found) { if (a[first+i] is the desired item) found = true; else ++i; }if (found) The desired item is in a[first+i]. else The desired item does not appear in the n items starting at a[first].What would be the most appropriate implementation of the serialSearch function?

Back 87

void searilSearch(const int a[ ], size_t first, size_t size, int target, bool& found, size_t& location){ size_t i; bool found; i = 0; found = false; while ((i < size) && !found) { if (a[first+i] == target) { found = true; location = first+i; } else ++i; }}

Front 88

What would be a good pair of twin primes between 1200 and 1250, with the upper prime having the form 4k+3 for some k?

Back 88

There is a twin prime pair at 1229 and 1231.

Front 89

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using double hashing (with hash2(key)returning the value 1 + (key % 101)), where will the 2 be placed in the table?

Back 89

2

Front 90

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using linear probing and a division hash function, where will the 308 be placed in the table?

Back 90

2

Front 91

Compute the H(2) value (H is the halving function)?

Back 91

1

Front 92

Use the insert function defined in section 12.3 to place six items in a hash table with a table size of 811. Use the keys 811, 0, 1623, 2435, 3247, and 2, which key(s) will be stored at data[2] list?

Back 92

2 and 2435.

Front 93

What is the average-case running times for a insertionsort?

Back 93

quadratic

Front 94

If we have a data array as following, what would be the data array after going through the first run of an insertionsort?

Back 94

Front 95

If we have a data array as following, what would be the array after going through the second positions interchange of a quicksort?

Back 95

Front 96

If we have a data array as following, what is the "cout << (data + 3)[1]; " displayed?

Back 96

5

Front 97

Why is mergesort not a good choice for sorting arrays?

Back 97

Mergesort is not a good choice for sorting arrays because of the additional memory required for the temporary array in the merge step.

Front 98

If we have a data array as following, what is the "cout << (data + 5)[2]; " displayed?

Back 98

11

Front 99

If we have a data array as following, what would be the data array after going through the second run of an insertionsort?

Back 99

Front 100

Which one of the following is a correct statement?

Back 100

The selectionsort algorithm performs the same number of operations no matter what values are in the array that it sorts.

Front 101

What kind of initialization needs to be done for an chained hash table?

Back 101

The head pointer of each chain must be set to NULL.

Front 102

When is insertionsort a good choice for sorting an array?

Back 102

The array has only a few items out of place.

Front 103

What is the worst-case time for mergesort to sort an array of n elements?

Back 103

O(n log n)

Front 104

What are the possible template parameters?a. a data typeb. a constant data valuec. a functiond. a constructor

Back 104

a, b, and c

Front 105

What is the worst-case, average-case, and best-case running time for a successful serial search?

Back 105

Worst case: O(n). Average case: O(n). Best case: O(1).

Front 106

Why doesn’t the new table (section 12.5) need a copy constructor, destructor, or assignment operator?

Back 106

A copy constructor, destructor, and assignment operator are needed only when a class makes direct use of dynamic memory. The new table class uses dynamic memory, but only through the vector class, which is another great reason to use the STL classes.

Front 107

We want to place 1000 elements in a hash table, and we’d like an average search to examine just two table elements. How big does the table’s array need to be for a chained hashing?

Back 107

500

Front 108

An empty hash table has a capacity of 103, and you insert six entries with keys 103, 0, 205, 308, 411, and 2. Using double hashing (with hash2(key)returning the value 1 + (key % 101)), where will the 0 be placed in the table?

Back 108

0

Front 109

Consider the chaining version of the table that we have described (section 12.3). What value will the constructor place in each component of data?

Back 109

NULL

Front 110

Compute the H(4) value (H is the halving function)?

Back 110

3

Front 111

If we have a twin prime pair at 1229 and 1231, what would be a good size for a hash table that uses double hashing and has a capacity around 1225?

Back 111

1231

Front 112

When should a programmer use a struct rather than a class?

Back 112

Programmers tend to use a struct only when all the members are public.

Front 113

What is the best-case running times for a insertionsort?

Back 113

linear

Front 114

If we have a data array as following, what is the meaning of "selectionsort(data , 2); "?

Back 114

Sorts data[0] through data[1]

Front 115

What would be the best statement about quicksort?

Back 115

When there is good splitting in quicksort, the resulting time is O(n log n). When there is bad splitting in quicksort, the result can be quadratic time.

Front 116

If we have a data array as following, what would be the data array after going through the third run swap function of a selectionsort?

Back 116

Front 117

What is the best-case running times for a quicksort ?

Back 117

O ( n log n)

Front 118

What is the worst-case running times for a insertionsort?

Back 118

quadratic

Front 119

What is the best-case running times for a selectionsort?

Back 119

quadratic

Front 120

If we have a data array as following, what would be a temp array after going through the first run of a mergesort?

Back 120