Exam 2 Weekly Quizzes Flashcards
“If we are adding a new key to the hash table and the position at hashCode is already occupied by a different key, we can place the new key in the next available empty slot in the underlying array.”
This collision resolution technique is of type (select all that apply):
a - Open addressing
b - Direct addressing
c - Separate chaining
d - Linear probing
a,d
Which of the following statement(s) are true?
a - When collisions are resolved using linear probing, the Load factor can be greater than 1
b - When collisions are resolved using quadratic probing, the Load factor can be greater than 1
c - When collisions are resolved using separate chaining, the Load factor can be greater than 1
c
0 1 2 3 4 5 6 7 8 9
69 57 18 89
This hash table uses the following two hashing functions:
Main hash: Hash1 (key) = key % table size
Step hash: Hash2 (key) = 6 - (key % 6)
The new key 49 will be added at position i of the array, where:
i = 4
In the recursive sequential search of an array, which of the following design decisions will efficiently reduce the problem size with each recursive call?
a - We can remove the first element of the array and pass a smaller array to the next recursive call
b - We can increment the front index by 1 and pass it to the next recursive call together with the unchanged array
c - We can decrement the last index by 1 and pass it to the next recursive call together with the unchanged array
b,c
Algorithm fun(n):
if n <= 1:
return1
else if n%2 == 0:
return fun(n/2)
else:
return fun(n/2) + fun(n/2 + 1)
What is fun(5)?
3
Which of the following correctly implements a recursive method reverse(s), that returns new string where all characters of s appear in a reverse order? Check all correct answers.
public static String reverseA (String s) {
if (s.length() == 0)
return “”;
return s.charAt(0) + reverseA (s.substring(1)) ;
}
public static String reverseB (String s) {
if (s.length() == 0)
return “”;
return reverseB (s.substring(1)) + s.charAt(0);
}
public static String reverseC (String s) {
if (s.length() == 0)
return “”;
return s.charAt(s.length()-1) + reverseC (s.substring(0,s.length()-1)) ;
Reverse B, Reverse C
In each iteration of insertion sort we insert the first element of an unsorted partition into its proper place in the sorted partition.
But because this partition is already sorted, we could find the place for a new element using binary search in time O(log n).
If we do O(n) iterations in total, and in each iteration we do the search for the correct position in time O(log n), this will make the improved insertion sort run in time O(n log n). (T/F)
False
Consider Selection Sort and location N-1 in the array (where the array is indexed from 0 to N-1).
How is the item that goes into this position “selected?”
It is not compared at all – by the time we get to this item it is in the correct location by default.
Consider Shell Sort and specifically the last iteration of the outer loop. What is happening in this iteration of the outer loop?
A “full” Insertion Sort is being done
Comparison-based sorting has a lower bound of N log N. What does this statement mean?
There always will be a worst-case input for which the comparison-based sorting algorithm will perform at least N log N comparisons.
Given an array A consisting of multiple 0’s, 1’s and 2’s, and we want to sort it.
The algorithm should put all 0’s first, then all 1’s and all 2’s last.
Which of the algorithms below could sort A in time O(n)?
a -Insertion sort
b - Merge sort
c - Count sort
d - Selection sort
e - Ternary quicksort
c,e
We need to lexicographically sort the following array of strings:
A = {“bar”, “dad”, “are”, “dare”, “ba”, “da”}.
We run a non-randomized version of Quick Sort with the pivot at position 0.
What would this array look like after the first call to partition?
A = {‘ba”, “are”, “bar”, “dare”, “dad”, “da”}
