A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Download Blue-Pelican Java Answers/Tests/Keys...
4XL]RQ/HVVRQ
Answers 39-1
1. What Big O value does a time complexity analysis of the following code yield? for[int j = 0; j < n; j++] { for[k = 0; k < n + 100; k++] { …some code… } } 2. What Big O value does a time complexity analysis of the following code yield? for[int j = 0; j < n - 20; j+= 22] { for[k = n; k > 0; k--] { …some code… } }
3. What Big O value does a time complexity analysis of the following code yield? for[int j = 1; j 0; j/=2] { …some code… }
5. What is the Big O value for a sequential [linear] search of a list of names? 6. What is the Big O value for a binary search of an ordered list?
.H\WR4XL]RQ/HVVRQ
Answers 39-2
1. What Big O value does a time complexity analysis of the following code yield? for[int j = 0; j < n; j++] { for[k = 0; k < n + 100; k++] { …some code… } } 2 Q 2. What Big O value does a time complexity analysis of the following code yield? for[int j = 0; j < n - 20; j+= 22] { for[k = n; k > 0; k--] { …some code… } } 2 Q 3. What Big O value does a time complexity analysis of the following code yield? for[int j = 1; j 0; j/=2] { …some code… } 2 ORJQ 5. What is the Big O value for a sequential [linear] search of a list of names? 2 Q 6. What is the Big O value for a binary search of an ordered list? 2 ORJQ
4XL]RQ/HVVRQ 6HOHFWLRQDQG,QVHUWLRQ6RUWV
Answers 41-1
1. Identify which of the following is a Selection Sort and which is an Insertion Sort. public static void sort[int a[ ] ] { int x, j; boolean keepGoing; for[int k = 1; k < a.length; k++] { x = a[k]; j = k –1; keepGoing = true; while[[j >= 0] && keepGoing] { if [x < a[j] ] { a[j + 1] = a[j]; j--; if[j == -1] { a[0] = x; } } else { keepGoing = false; a[j + 1] = x; } } } }
public static void sort[int a[ ]] { int min, minIndex;
for[int i = 0;i < a.length; ++i] { min = a[i]; minIndex = i; for [int j = i + 1; j < a.length; ++j] { if [a[j] < min] //salient feature { min = a[j]; minIndex = j; } } a[minIndex] = a[i]; a[i] = min; }
}
2. Write code that swaps the contents of the LQW variables [ and \.
.H\WR4XL]RQ/HVVRQ 6HOHFWLRQDQG,QVHUWLRQ6RUWV
Answers 41-2
1. Identify which of the following is a Selection Sort and which is an Insertion Sort. public static void sort[int a[ ] ] { int x, j; boolean keepGoing; for[int k = 1; k < a.length; k++] { itemToInsert = a[k]; j = k –1; keepGoing = true; while[[j >= 0] && keepGoing] { if [x < a[j] ] { a[j + 1] = a[j]; j--; if[j == -1] { a[0] = x; } } else { keepGoing = false; a[j + 1] = x; } } } ,QVHUWLRQ6RUW }
public static void sort[int a[ ]] { int min, minIndex;
}
for[int i = 0;i < a.length; ++i] { min = a[i]; minIndex = i; for [int j = i + 1; j < a.length; ++j] { if [a[j] < min] //salient feature { min = a[j]; minIndex = j; } } a[minIndex] = a[i]; a[i] = min; }
6HOHFWLRQ6RUW
2. Write code that swaps the contents of the LQW variables [ and \. LQWWHPS [ [ \ \ WHPS
4XL]RQ/HVVRQ 4XLFNDQG0HUJH6RUWV
Answers 41-3
1. Of the two descriptions below, identify which is a Merge Sort and which is Quick Sort. This sort begins by placing each element into its own individual list. Then each pair of adjacent lists is combined into one sorted list. This continues until there is one big, final, sorted list.
This sort begins by breaking the original list into two partitions [sections] based on the value of some “pivot value.” One partition will eventually contain all the elements with values greater than the pivot value. The other will eventually contain all the elements with values less than or equal to the pivot value. Repeat this process on each partition.
2. Of the two methods below, identify which is a Merge Sort and which is a Quick Sort. public static void sort [int a[ ], int left, int right] { if [right = = left] return; int middle = [left + right] /2; sort[a, left, middle]; sort[a, middle + 1, right]; combine[a, left, middle, right]; }
public static void sort[int a[ ], int left, int right] { if [left >= right] return; int k = left; int j = right; int centVal = a[ [left + right] / 2 ]; while [ k < j ] { while [a[k] < centVal] { k++; } while [ centVal < a[j] ] { j--; } if [ k = right] return; int k = left; int j = right; int centVal = a[ [left + right] / 2 ]; while [ k < j ] { while [a[k] < centVal] { k++; } while [ centVal < a[j] ] { j--; } if [ k