Exam 2 Top Hats Flashcards
Consider some iterator, iter, which was created on a list of Integers.
Consider the code snippet below:
while (true) {
Integer X = iter.next();
System.out.println(“Next value is “ + X);
}
What will happen if this code segment is executed?
All of the values in the list will be printed, followed by an Exception
Consider a list, L, containing (in order): 10, 20, 30
Now consider the following code segment:
Iterator<Integer> one = L.iterator();
Iterator<Integer> two = L.iterator();
Integer X = one.next();
Integer Y = two.next();
What are the values X and Y?</Integer></Integer>
X = 10, Y = 10
What are the the worst-case runtimes of Contains(x), Add(x) and Remove(x) if we implemented Set ADT using an (unsorted) array
O(n), O(n), O(n)
Which of the following may work as a hash function for strings?
a - Return a random number.
b - Return 0 if the string is of even length and return 1 if it’s of odd length.
c - Add together all the ASCII values of the characters.
b,c
What are the the worst-case runtimes of Contains(x), Add(x) and Remove(x) if we implemented Set ADT using a sorted array?
O(log n), O(n), O(n)
Which tasks can be efficiently solved using the Hash Table implementation of Set ADT?
a - Removing duplicates from the array of integers
b - Quickly checking if student name is in the class roster
c - Testing if all the elements of a given array are unique
d - Given an array of people’s names and a given family name s - counting how many times s appears in the array.
a,b,c
Algorithm findArrayMax(A, n):
input: a NONEMPTY array, A with n elements
output: A’s maximum element
Recursive array max: stop condition?
if n == 1 return A[0]
Algorithm findArrayMax(A, n):
input: a NONEMPTY array, A with n elements
output: A’s maximum element
if n == 1:
return A[0]
*
Recursive array max: recursive step *
if A[n-2] < A[n-1]:
A [n-2] = A[n-1]
return findArrayMax(A, n-1)
else:
return findArrayMax(A, n-1)
You are implementing algorithm power(x,y) for computing xy.
What is your base case?
y = 1 and 0
If y == 1, return x
If y == 0, return 1
You are implementing algorithm power(x,y) for computing xy. (x and y are positive integers)
What is your recursive step?
power(x,y) = x*power(x,y-1)
Consider the recursive algorithms for computing factorial and for a search in an unsorted array (sequential search).
Which of the following claims are true?
a - The recursive versions of these algorithms are preferable to the iterative versions because the recursive versions are asymptotically faster.
b - The recursive versions of these algorithms are preferable to the iterative versions because the recursive versions have less overhead in their execution.
c - The iterative versions of these algorithms are preferable to the recursive versions because the iterative versions are asymptotically faster.
d - The iterative versions of these algorithms are preferable to the recursive versions because the iterative versions have less overhead.
d
Here is an algorithm for counting the number of times the item is found in a sorted array A:
pos = binarySearch(A, item)
if pos!== -1:
return 0
count = 1
i = pos+1
while (i < A.length):
if (A[i] == item):
count++
i++
else: break
i = pos-1
while (i >=0):
if (A[i] == item):
count++
i–
else: break
What is the time complexity of this algorithm?
O(n)
Consider the following code:
displayNode (Node current) {
if (current != null) {
print (current.data)
displayNode (current.next)
}
}
Let head be a head of a Linked List: 1->2->3->4
What will be printed after we call
displayNode (head)
1 2 3 4
Consider the following recursive step for the divide and conquer power function, pow(N):
int recAns = pow(x,N/2);
return (recAns*recAns);
When is the recursive case correct?
This recursive case is correct for some values of N
Consider the “sorted “ vs. the “unsorted partition” in the array in the middle of Insertion Sort. Which statements about the elements in the sorted partition are true?
a - The data in a sorted partition is sorted and each item at location k will stay at location k for the rest of the sort.
b - The data is sorted but the position of an element currently at location k can still change.
c - The data is not actually sorted yet and will become sorted only after the last iteration.
The data is sorted but the position of an element currently at location k can still change.
