Deck 16: Sorting, Searching, and Algorithm Analysis

Question 1

One can sort an array a[ ] as follows.Start by observing that at stage 0,the array segment consisting of the single element a[0] is sorted.Now suppose that at the stage k,the segment a[0..k] is sorted.Take the element a[k+1],and call it X.By moving some of the elements in a[0..k] one place to the right,create a place to put X in so that now a[0..k+1] is sorted.The algorithm that uses this strategy is called

A) bubble sort
B) insertion sort
C) selection sort
D) Quicksort

Answer 1

B

Question 2

The bubble sort algorithm works by

A) repeatedly comparing adjacent items and swapping them so smaller values come before larger values
B) repeatedly locating the smallest value in the unsorted portion of the array and moving it toward the lower end of the array
C) repeatedly taking the first value in the unsorted portion of the array and placing it at its proper place in the part of the array that is already sorted
D) partitioning the unsorted portion of the array into two sublists and a pivot and recursively sorting the two sublists

Answer 2

A

Question 3

When applied to an array a[ ] of integers,the pseudo code
Boolean sort = true
Int k = 0
While sort == true and k < a.length-1
If a[k] > a[k+1] Then
Sort = false
End If
K = k +1
End While

A) will sort the array a[ ] in ascending (nondecreasing)order
B) will sort the array a[ ] in descending (nonincreasing.order
C) will determine if the array is arranged in ascending order
D) will determine if the array is arranged in descending order

Answer 3

C

Question 4

A search for an item X in an array starts at the lower end of the array,and then looks for X by comparing array items to X in order of increasing subscript.Such a method is called

A) lower to upper search
B) sequential search
C) binary search
D) selection search

Question 5

The selection sort algorithm works by

A) repeatedly comparing adjacent items and swapping them so smaller values come before larger values
B) repeatedly locating the smallest value in the unsorted portion of the array and moving it toward the lower end of the array
C) repeatedly taking the first value in the unsorted portion of the array and placing it at its proper place in the part of the array that is already sorted
D) partitioning the unsorted portion of the array into two sublists and a pivot and recursively sorting the two sublists

Question 6

Consider the following implementation of insertion sort:
Public static void insertionSort(int [ ] array){
Int unsortedValue;// The first unsorted value
Int scan;// Used to scan the array
// The outer loop steps the index variable through
// each subscript in the array,starting at 1.This
// is because element 0 is considered already sorted.
For (int index = 1;index < array.length;index++){
// The first element outside the sorted segment is
// array[index].Store the value of this element
// in unsortedValue
UnsortedValue = array[index];
// Start scan at the subscript of the first element
// outside the sorted segment.
Scan = index;
// Move the first element outside the sorted segment
// into its proper position within the sorted segment.
While (scan > 0 && array[scan-1] > unsortedValue){
Array[scan] = array[scan - 1];
Scan --;
}
// Insert the unsorted value in its proper position
// within the sorted segment.
Array[scan] = unsortedValue;
}
}
This method uses the < and > operators to compare array subscripts,as when index is compared against the length of the array,a.length.The method also uses these operators to compare array elements against each other,for example,in an expression such as a[scan-1] >unSortedValue.What would happen if we change every < operator to >,and change every > operator to < ?

A) Instead of sorting in ascending order,the method would sort in descending order
B) The method would throw an array index out of bounds exception
C) The method would return,leaving the array unmodified
D) The method would modify the array,but the array would likely not be sorted correctly

Question 7

The role of the partition(array,start,end)method in Quicksort

A) is to sort the segment of the array between start and end
B) is to identify the position of the largest value in the part of the array that lies between start and end
C) is to split the array into two sorted sublists on either side of the pivot element
D) None of the above

Question 8

The binary search algorithm

A) cannot be used to search an array that is not sorted
B) does twice as much work as sequential search on the average case
C) must be written using recursion
D) is slower than sequential search when the item being searched for is not in the array

Question 9

Assuming a method
Int findMax(int array[ ],int last)that returns the subscript of the largest value in the portion of an array whose elements are at 0 through last (inclusive),a method for sorting an array in ascending order can be written as follows:
Void sort(int array[ ]){
For (int last = array.length-1;last >=1;last --){
Int maxPos = findMax(array,last);
// Code is missing
}
}
If a method
Void swap(int array[ ],int pos1,int pos2)can be used to swap the contents of two array entries,then the logic for the missing code is

A) swap(array,maxPos,last);
B) swap(array,maxPos,last-1.;
C) swap(array,array[maxPos],array[last].;
D) sway(array,array[maxPos],array[last-1].;

Question 10

An array a[ ] of N elements is being sorted using the insertion sort algorithm.The algorithm is at the last stage,with the segment of the array in positions 0 through N-2 already sorted.How many array elements will a[N-1] have to be compared to,before it can be placed into its proper position?

A) Just one
B) Could be any number of elements between 1 and N-1 (inclusive.
C) Could be any number of elements between 1 and N (inclusive.
D) N-1

Question 11

The Quicksort algorithm works by

A) repeatedly comparing adjacent items and swapping them so smaller values come before larger values
B) repeatedly locating the smallest value in the unsorted portion of the array and moving it toward the lower end of the array
C) repeatedly taking the first value in the unsorted portion of the array and placing it at its proper place in the part of the array that is already sorted
D) partitioning the unsorted portion of the array into two sublists and a pivot and recursively sorting the two sublists

Question 12

Consider the code
Static void doQuickSort(int array[ ],int start,int end){
Int pivotPoint;
If (start < end){
PivotPoint = partition(array,start,end);
DoQuickSort(array,start,pivot-1);
DoQuickSort(array,pivot+1,end);
}
}
In this code,the value pivotPoint returned by partition

A) is the value of the array element that is greater than each element of the first sublist,and less or equal to each element of the second sublist
B) is the position of the array element that is greater than each element of the first sublist,and less or equal to each element of the second sublist
C) is the element X such that half the elements of the array are less than X,and half the elements of the array are greater or equal to X
D) None of the above

Question 13

To compare String objects for the purpose of sorting,a programmer should

A) use the comparison operator <
B) use the comparison operator < =
C) use the compareTo method of the Comparable interface
D) use the relational operator < to compare references to the String objects

Question 14

The compareTo method of the Comparable interface

A) returns true when the calling object is "less than" the object passed as the parameter
B) returns a negative integer when the calling object is "less than" the object passed as the parameter
C) returns zero when the calling object fails to equal the object passed as parameter
D) None of the above

Question 15

The insertion sort algorithm works by

A) repeatedly comparing adjacent items and swapping them so smaller values come before larger values
B) repeatedly locating the smallest value in the unsorted portion of the array and moving it toward the lower end of the array
C) repeatedly taking the first value in the unsorted portion of the array and placing it at its proper place in the part of the array that is already sorted
D) partitioning the unsorted portion of the array into two sublists and a pivot and recursively sorting the two sublists

Question 16

The following implementation of QuickSort
Static void doQuickSort(int array[ ],int start,int end){
Int pivotPoint;
PivotPoint = partition(array,start,end);
DoQuickSort(array,pivot+1,end);
DoQuickSort(array,start,pivot-1);
}

A) will correctly sort the array if the partition method is written correctly
B) will give incorrect results because the two recursive calls are called in the wrong order
C) will sort the array in descending rather than ascending order
D) will be terminated by the system for making too many recursive calls

Question 17

Assuming a method
Int findMax(int array[ ],int last)that returns the subscript of the largest value in the portion of an array whose elements are at 0 through last (inclusive),a recursive method for sorting in ascending order a portion of an array between 0 and last,inclusive,can be written as follows:
Void rSort(int array[ ],int last){
If (last >= 1){
// Missing code
}
}
If a method
Void swap(int array[ ],int pos1,int pos2)can be used to swap the contents of two array entries,then the logic for the missing code is

A) findMax(array,array.length-1);rSort(array,array.length-1);
B) int p = findMax(array,array.length-1.;rSort(array,p.;
C) int p = findMax(array,last.;swap(array,p,last.;rSort(array,last-1.;
D) rSort(array,last-1.;int p = findMax(array,last.;swap(array,p,last.;

Question 18

The method findMax shown below is supposed to return the position of the largest
Value in the portion of an array between 0 and last,inclusive:
Int findMax(int array[ ],int last){
Int maxPos = 0;
For (int k = 1;k < = last;k++){
// Code is Missing
}
Return maxPos;
}
The missing code is

A) if (array[k] > maxPos)return maxPos;
B) if (array[k] > array[maxPos].return maxPos;
C) if (array[k] > array[maxPos].maxPos = k;
D) if (array[k] > array[maxPos].k = maxPos;

Question 19

An array of 4 elements is being sorted in ascending order using the insertion sort algorithm.How many comparisons will insertion sort perform if the array was originally sorted in descending order?

A) 2 comparisons
B) 4 comparisons
C) 6 comparisons
D) None of the above

Question 20

If a[ ] is an array of integers,the pseudo code
Int k = 0
Int m = 1
While m < a.length
If a[m] < a[k] Then
K = m
End If
M = m+1
End While
Describes a strategy for

A) sorting an array in ascending order
B) sorting an array in descending order
C) implementing a part of the logic for bubble sort
D) determining the location of the smallest value in the array

Question 21

The Quicksort algorithm

A) is in O(n)in the worst case
B) is in O(n log n.in the worst case
C) is in O(n log n.in the average case
D) is in O(log n.in the average case

Question 22

The best way to measure the goodness of an algorithm is

A) to write a computer program that uses the algorithm and time its execution
B) to write a computer program that uses the algorithm and run it on the hardest and largest inputs
C) to look at its worst case and average case complexity functions
D) to look at the sum of its execution time and the space it uses

Question 23

A contigous segment of an array is given by specifying two subscripts,lower and upper.Which of the following expressions gives the subscript of the array element that is three quarters of the way from lower to upper?

A) lower + 3 * upper /4
B) lower /3 + upper
C) (upper - lower.* 3 /4
D) lower + (upper - lower.* 3 / 4

Question 24

The addition of two integers

A) is always a basic step
B) is a basic step in algorithms that use addition to define more complex operations such as multiplication
C) is a basic step if there is a fixed bound on the size of the integers
D) All of the above

Question 25

On the average,performing a sequential search on an array of N elements will require

A) N comparisons
B) N-1 comparisons
C) N/2 comparisons
D) None of the above

Question 26

A computational problem is

A) a problem that can be solved using an algorithm
B) one that arises in the writing of computer programs
C) one that arises when a program runs out of memory,or has some other kind of runtime error
D) None of the above

Question 27

A basic step is

A) an operation that can be executed within a constant amount of time
B) an operation that is used only in the simplest algorithms
C) one that is implemented in a library package
D) None of the above

Question 28

A search for an item X in a portion of a sorted array works by repeatedly selecting the middle item and comparing it to X.If X is not found there,the search method selects either the portion of the array to the left of the middle item,or the portion of the array to the right of the middle item,and continues the search.This method is called

A) sequential search
B) binary search
C) selection search
D) None of the above

Question 29

The method int getPosition(int array[],int X)is designed to return the position of X within the array.If X is not in the array,the method may return either -1 or array.length.Which of the following is a correct implementation for this method?

A) int k = 0;
While (array[k] != X){k ++};return k;
B) int k = 0;
While (k < array.length.{if (array[k] != X.return -1;else return k;}
C) int k = 0;
While (k < array.length && array[k] != X.{ k++;} return k;
D) int k = 0;
While (k < array.length && array[k] != X.{ k++;return k;}

Question 30

Let F be an algorithm with complexity function f(n),and let G be an algorithm with complexity function g(n).If the ratio f(n)/g(n)converges to 0 as n increases to infinity,then

A) the algorithm F is asymptotically faster than G
B) the algorithm G is asymptotically faster than F
C) the two algorithms are asymptotically equivalent in efficiency
D) None of the above

Question 31

The two criteria most often used to measure the efficiency of an algorithm are

A) efficiency and style
B) space and time
C) style and time
D) execution and speed

Question 32

If an array is known to be sorted,it can be searched very quickly by using

A) sequential search
B) binary search
C) selection search
D) None of the above

Question 33

Let F be an algorithm with complexity function f(n),and let G be an algorithm with complexity function g(n).If the ratio f(n)/g(n)converges to 2 as n increases to infinity,then

A) the two algorithms are equivalent in efficiency and there is no clear winner
B) implementations of F will require twice as much time as implementations of G
C) we can deduce that F runs in linear time while G runs in quadratic time
D) implementations of F will require twice as much space as implementations of G

Question 34

Let F be an algorithm with complexity function f(n),and let G be an algorithm with complexity function g(n).If the ratio f(n)/g(n)converges to infinity as n increases to infinity,then

A) the algorithm F is asymptotically faster than G
B) the algorithm G is asymptotically faster than F
C) the two algorithms are asymptotically equivalent in efficiency
D) None of the above

Question 35

If an algorithm with an input size of n has a nested loop,and both loops make a complete pass over the input,then the performance of the algorithm will be

A) constant time
B) linear time
C) logarithmic time
D) quadratic time

Question 36

Linear time is the class of all complexity functions that are in

A) O(1)
B) O(n.
C) O(n log n.
D) O(log n.

Question 37

If lower is the first subscript in a contiguous portion of an array,and upper is the last subscript,then the array item in the middle of that array portion is at subscript

A) (lower + upper)/2
B) (lower - upper./2
C) lower + upper/2
D) (upper - lower./2

Question 38

A contiguous segment of an array is specified using two subscripts,lower and upper.Which expression gives the position of the element in the middle of the array segment?

A) lower + upper / 2
B) lower /2 + upper
C) (upper - lower./2
D) lower + (upper - lower./ 2

Question 39

Suppose that we are searching for an item X in an array sorted in descending order.If we find that X is smaller than the middle item of the array,then we should continue our search in the half of the array whose elements

A) have higher subscripts than the middle of the array
B) have lower subscripts than the middle of the array
C) have the same subscript as the middle of the array
D) None of the above

Question 40

The best method for searching an array that is not sorted is

A) sequential search
B) binary search
C) selection search
D) None of the above

Question 41

Binary Search is in the complexity class

A) O(1)
B) O(log n.
C) O(n.
D) O(n log n.

Question 42

Sequential Search is in the complexity class

A) O(1)
B) O(log n.
C) O(n.
D) O(n log n.

Question 43

For a computational problem,the input size

A) is the number of times the program requests input from the user
B) is the number of loop iterations required to read the input
C) is the amount of memory needed to store the input
D) None of the above

Question 44

Let F be an algorithm with complexity function f(n),and let G be an algorithm with complexity function g(n).If there exists a positive constant K such that the ratio f(n)/g(n)is less or equal to K for all n greater or equal to 1,then

A) the two algorithms are asymptotically equivalent
B) the algorithm F is asymptotically no worse than G
C) the algorithm F is asymptotically no better than G
D) Nothing intelligent can be said about the relative performance of the two algorithms.

Question 45

The worst case complexity function f(n)of an algorithm

A) is the maximum execution time measured when a program with n inputs is executed
B) occurs when the load on the system is heaviest
C) is always harder to compute than the average case complexity
D) is the maximum number of basic steps performed in solving a problem instance with input size n

Question 46

The worst case complexity function is a good measure to use when

A) the load on the system is heaviest
B) we want a guarantee on the performance of an algorithm
C) the best case complexity would lead to incorrect results
D) we want to create an efficient algorithm