Question Bank for Grade 14 Computers

Which of the following are true statements about the binary search process? Check all that apply.

• The average case scenario Big O running time is O(log N).

• The target value must be contained within the list.

• The process checks the middle item for a match, and then looks to the right or to the left if it doesn't match, repeating this process until a match is found, or not.

• The precondition is that the list must be sorted.

Which of the following is considered an O(N log N) class sort for a worst case scenario?

• Insertion Sort

• Merge Sort

• Selection Sort

• Quick Sort

Which of these would be considered the worst case scenario for a linear search?

• The target value is not found in the list.

• The target value is found at the end of the list.

• The target value is found at the beginning of the list.

• The target value is found somewhere in the middle of the list.

Consider a list that contains eight integer values. If the list is sorted using the merge sort, how many total division operations will take place during the entire process?

Which of the following describes a selection sort?

• The "best value for each position" is found and swapped into place with each pass.

• The list is partitioned around a pivot point.

• Unsorted values are shifted into their "best position" in the list.

• Adjacent values are compared and swapped if out of order.

Which of the following descriptions of the Big O analysis categories is NOT correct?

•  

  An O(N log N) process is characterized by a divide and conquer process combined with an N based loop.

• An O(N2) process is characterized by a nested loop process based on the size of the data set.

• An O(1) process only works on a data set of 100 items or less.

• An O(N) process is characterized by a loop that spans the entire data set of size N.

Consider a list:

{ 3, 5, 8, 10, 14, 34, 78, 123, 513, 999 }

If a binary search for the value 34 is performed, how many comparison operations will be required to find it?

• 3

• 1

• 6

• 5

Assume there is a function defined swap( pass-by-reference int [] list, int position1, int position2 ) which swaps values in the array list at index position1 and index position2. What sorting routine is represented by the code shown?

• Bubble

• Selection

• Merge

• Quick

• Insertion

Consider a list:

{ 9, 2, 6, 8, -3, 7, 2, 15, 0, -1, 14, 99, -1 }

If a linear search for the value -1 is performed, what will be returned?

• 10

• 9

• 12

• -1

Consider a partially sorted list that is undergoing the insertion sort in ascending order, with the first four values already in sorted order:

{ 1, 5, 6, 7, 4, 2, 3 }

How many shifts must be performed to insert the value 4 into the correct position?

• 2

• 1

• 4

• 3