AP Computer Science A : Sequential

Study concepts, example questions & explanations for AP Computer Science A

varsity tutors app store varsity tutors android store

Example Questions

Example Question #1 : Sequential

Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?

Possible Answers:

public int contains(int[] arr, int val) {

      int success = -1;

      for(int i = 0; i < arr.length; i++) {

              if(arr[i] == val) {

                     success = val;

              }

       }

       return success;

}

public boolean contains(int[] arr, int val) {

       boolean success;

       for(int i = 0; i <= arr.length; i++) {

              if(arr[i] == val) {

                     success = true;

              } else {

                     success = false;

              }

       }

       return success;

}

public boolean contains(int[] arr, int val) {

       for(int i = 0; i < arr.length; i++) {

              if(arr[i] != val) {

                     return false;

              }

       }

       return true;

}

None of the other answers is correct

public boolean contains(int[] arr, int val) {

       for(int i = 0; i < arr.length; i++) {

              if(arr[i] == val) {

                     return true;

              }

       }

       return false;

}

Correct answer:

public boolean contains(int[] arr, int val) {

       for(int i = 0; i < arr.length; i++) {

              if(arr[i] == val) {

                     return true;

              }

       }

       return false;

}

Explanation:

The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.

Example Question #2 : Sequential

public static int foo(int[] arr, int x) {

    for(int i = 0; i < arr.length; i++) {

        if(arr[i] == x) {

            return i;

        }

    }

    return -1;

}

Given the method defined above, how many times is the word "Indubitably!" output by the code below?

int[] vals = {1,4,51,3,14,91,130,14};

for(int i = 0; i < 20; i++) {

    if(foo(vals,i%4) < 0) {

        System.out.println("Indubitably!");

    }

}

Possible Answers:

5

4

None

2

10

Correct answer:

10

Explanation:

To make this question much easier, first notice that the foo method implements a sequential search.  (This is a search that merely goes through each element of an array and sees if it equals the probe value.)  It returns the index if it is found.  Otherwise, it returns -1.  Now, in the code block in the question itself, the loop iterates for i = 0 to i = 19.  It will only execute a search, however, on the values 0...3.  This is because of the modulus operator.  Thus, it will do (from 0 to 19), 0...3 a total of five times.  Thus, it will probe for 1 and 3 five times—these are each in the array.  So, the word "Indubitably!" will be output a total of ten times.

Example Question #31 : Standard Operations & Algorithms

True or False. 

 

Sequential search is more efficient than Binary Search.

Possible Answers:

False

True

Correct answer:

False

Explanation:

Sequential search has a running time of O(N). Binary search has a running time of O(log(N)). Because sequential search has to go through each element in a list at least once it's less efficient. 

Learning Tools by Varsity Tutors

Incompatible Browser

Please upgrade or download one of the following browsers to use Instant Tutoring: