AP Computer Science A : Standard Operations & Algorithms
Study concepts, example questions & explanations for AP Computer Science A
All AP Computer Science A Resources
Example Questions
Example Question #21 : Operations On Data Structures
int[] arr = {0,0,0,0,0,0,0,0,0,0};
int arrFill = 0;
int val;
// In here, n items are added. ArrFill is n. Presume that n <= 9
// The variable val now contains a new value to be added
Which of the following blocks of code push a new value into arr as though it were a stack?
arr[arrFill - 1] = val;
arrFill++;
arr[arrFill] = val;
arrFill++;
arr[0] = val;
arrFill++;
None of the others
arr[arrFill + 1] = val;
arrFill++;
arr[arrFill] = val;
arrFill++;
Let us presume that the array arr looks like the following list of integers:
{4,51,41,0,0,0,0,0,0,0}
Presume that our new value is 77.
A stack could either push on to the beginning and move everything back one, giving you something like:
{77,4,51,41,0,0,0,0,0,0}
However, none of the options do this. (No, not even the one that uses the index 0. This one does not add on to the array so much as replace the first element of it.)
So, the other option is to put it on the "end" of the list. The variable arrFill is being used for this purpose. If it is 3, this means that it is the value of the fourth element. Thus, you can set arr[4] = 77 (where 4 really is arrFill).
This will give you:
{4,51,41,77,0,0,0,0,0,0}
You also need to add one to the value of arrFill.
The other options do not correctly address the array. They either are too large or too small by one.
Example Question #12 : Computer Science
True or False.
The worst case for insertion into an ArrayList is O(N).
False
True
True
Insertion into an ArrayList is typically O(1). However, since an ArrayList uses an array as its underlying data structure, there can be a need to resize the underlying array. Resizing an array requires creating a new array and copying all the data from the old array to the new array which takes O(N) time.
Example Question #22 : Computer Science
Which of the following defines a method that successfully deletes an item from an array of integers?
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i1=0,i2 = 0; i1 < a.length; i1++) {
if(i1 == delIndex) {
delete a[i1];
}
}
return ret;
}
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i1=0,i2 = 0; i1 < a.length; i1++) {
if(i1 != delIndex) {
ret[i2] = a[i1];
i2++;
}
}
return ret;
}
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
for(int i = 0; i <= delIndex; i++) {
if(i == delIndex) {
delete a[i];
break;
}
}
return a;
}
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i = 0; i <= delIndex; i++) {
ret[i] = a[i];
}
return ret;
}
None of these work correctly
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i1=0,i2 = 0; i1 < a.length; i1++) {
if(i1 != delIndex) {
ret[i2] = a[i1];
i2++;
}
}
return ret;
}
Of course, this is an inefficient way to do such a delete, but arrays are rather "locked" data structures in that their size cannot change without a reassignment. (You could, of course keep track of the last "used" index. However, that is a different implementation, not reflected here.) The correct answer is the one that carefully goes through the original array, copying those contents into the new array skipping the one value that is not wanted.
Example Question #1 : Deletions
public static boolean remove(int[] arr, int val) {
boolean found = false;
int i;
for(i = 0; i < arr.length && !found; i++) {
if(arr[i] == val) {
found = true;
}
}
if(found) {
for(int j = i; j < arr.length;j++) {
arr[j - 1] = arr[j];
}
arr[arr.length - 1] = 0;
}
return found;
}
For the code above, what will be the content of the variable arr at the end of execution, if the method is called with the following values for its parameters:
arr = {3,4,4,5,17,4,3,1}
val = 4
{3, 4, 5, 17, 4, 3, 1}
{3, 5, 17, 3, 1}
None of the other answers
{3, 4, 5, 17, 4, 3, 1, 0}
{3, 5, 17, 3, 1, 0, 0, 0}
{3, 4, 5, 17, 4, 3, 1, 0}
This code simulates the removal of a value from an array by shifting all of the elements after that one so that the array no longer contains the first instance of that value. So, for instance, this code takes the original array {3,4,4,5,17,4,3,1} and notices the first instance of 4: {3,4,4,5,17,4,3,1}. Next, it starts shifting things to the left. Thus, some of the steps will look like this:
{3,4,4,5,17,4,3,1}
{3,4,5,5,17,4,3,1}
{3,4,5,17,17,4,3,1}
...
{3,4,5,5,17,4,1,1}
Then, at the very end, it sets the last element to 0:
{3,4,5,17,4,3,1,0}
Example Question #22 : Operations On Data Structures
int[] arr = new int[20];
int x = 6,i=2;
for(int j = 0; j < x; j++) {
arr[j] = j * 40 + 20;
}
for(int j = x; j > i; j--) {
arr[j] = arr[j - 1];
}
arr[i] = 20;
for(int j = 0; j < x; j++) {
System.out.print(arr[j] + " ");
}
What is the output for the code above?
None of the others
20 60 20 100 140 180
20 60 20 100 140 180 220
20 60 20 100 100 100
20 60 20 140 180 220
20 60 20 100 140 180
It is easiest to understand this by a bit of code parsing:
First, there is the loop: for(int j = 0; j < x; j++) { // ...
This will fill the array with 20 + 0, 20 + 40, 20 + 80, ... Thus, it will be:
20, 60, 100, 140, 180, 220
Next, there is the array: for(int j = x; j > i; j--) { // ...
This basically shifts everything after index i backward by 1. Thus you have:
20, 60, 100,100, 140, 180, 220
Next, you set arr[2] equal to 20:
20, 60, 20,100, 140, 180, 220
Finally you output each of the first 6 elements. Be careful here. Notice that it is from j = 0 to x - 1!
Thus, the answer is:
20 60 20 100 140 180
This algorithm basically implements a simple kind of array deletion.
Example Question #22 : Computer Science
Which of the following defines a method that successfully deletes an item from an array of integers?
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i1=0,i2 = 0; i1 < a.length; i1++) {
if(i1 == delIndex) {
delete a[i1];
}
}
return ret;
}
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i1=0,i2 = 0; i1 < a.length; i1++) {
if(i1 != delIndex) {
ret[i2] = a[i1];
i2++;
}
}
return ret;
}
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
for(int i = 0; i <= delIndex; i++) {
if(i == delIndex) {
delete a[i];
break;
}
}
return a;
}
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i = 0; i <= delIndex; i++) {
ret[i] = a[i];
}
return ret;
}
None of these work correctly
public static int[] del(int[] a,int delIndex) {
if(a == null || delIndex < 0 || delIndex >= a.length) {
return null;
}
int[] ret = new int[a.length - 1];
for(int i1=0,i2 = 0; i1 < a.length; i1++) {
if(i1 != delIndex) {
ret[i2] = a[i1];
i2++;
}
}
return ret;
}
Of course, this is an inefficient way to do such a delete, but arrays are rather "locked" data structures in that their size cannot change without a reassignment. (You could, of course keep track of the last "used" index. However, that is a different implementation, not reflected here.) The correct answer is the one that carefully goes through the original array, copying those contents into the new array skipping the one value that is not wanted.
Example Question #1 : Deletions
public static boolean remove(int[] arr, int val) {
boolean found = false;
int i;
for(i = 0; i < arr.length && !found; i++) {
if(arr[i] == val) {
found = true;
}
}
if(found) {
for(int j = i; j < arr.length;j++) {
arr[j - 1] = arr[j];
}
arr[arr.length - 1] = 0;
}
return found;
}
For the code above, what will be the content of the variable arr at the end of execution, if the method is called with the following values for its parameters:
arr = {3,4,4,5,17,4,3,1}
val = 4
{3, 4, 5, 17, 4, 3, 1}
{3, 5, 17, 3, 1}
None of the other answers
{3, 4, 5, 17, 4, 3, 1, 0}
{3, 5, 17, 3, 1, 0, 0, 0}
{3, 4, 5, 17, 4, 3, 1, 0}
This code simulates the removal of a value from an array by shifting all of the elements after that one so that the array no longer contains the first instance of that value. So, for instance, this code takes the original array {3,4,4,5,17,4,3,1} and notices the first instance of 4: {3,4,4,5,17,4,3,1}. Next, it starts shifting things to the left. Thus, some of the steps will look like this:
{3,4,4,5,17,4,3,1}
{3,4,5,5,17,4,3,1}
{3,4,5,17,17,4,3,1}
...
{3,4,5,5,17,4,1,1}
Then, at the very end, it sets the last element to 0:
{3,4,5,17,4,3,1,0}
Example Question #22 : Operations On Data Structures
int[] arr = new int[20];
int x = 6,i=2;
for(int j = 0; j < x; j++) {
arr[j] = j * 40 + 20;
}
for(int j = x; j > i; j--) {
arr[j] = arr[j - 1];
}
arr[i] = 20;
for(int j = 0; j < x; j++) {
System.out.print(arr[j] + " ");
}
What is the output for the code above?
None of the others
20 60 20 100 140 180
20 60 20 100 140 180 220
20 60 20 100 100 100
20 60 20 140 180 220
20 60 20 100 140 180
It is easiest to understand this by a bit of code parsing:
First, there is the loop: for(int j = 0; j < x; j++) { // ...
This will fill the array with 20 + 0, 20 + 40, 20 + 80, ... Thus, it will be:
20, 60, 100, 140, 180, 220
Next, there is the array: for(int j = x; j > i; j--) { // ...
This basically shifts everything after index i backward by 1. Thus you have:
20, 60, 100,100, 140, 180, 220
Next, you set arr[2] equal to 20:
20, 60, 20,100, 140, 180, 220
Finally you output each of the first 6 elements. Be careful here. Notice that it is from j = 0 to x - 1!
Thus, the answer is:
20 60 20 100 140 180
This algorithm basically implements a simple kind of array deletion.
Example Question #23 : Computer Science
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
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) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
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;
}
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;
}
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 #1 : 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!");
}
}
2
4
None
10
5
10
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.
All AP Computer Science A Resources
