AP Computer Science a Quiz: Implementing Array Algorithms
5 questions · exam conditions
0:00
Implementing Array AlgorithmsQuestion 1 of 5

Implement an algorithm to sort the following array in ascending order using insertion sort (no built-in sort): int[] a. Constraints: 0≤n≤1040 \le n \le 10^4. After sorting, a must be in nondecreasing order. Example: [4,1,3] -> [1,3,4]. Which method correctly sorts the array?

public static void insertionSort(int[] a){
  for(int i=1;i<a.length;i++){
    int key=a[i];
    int j=i-1;
    while(j>=0 && a[j]>key){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=key;
  }
}

public static void insertionSort(int[] a){
  for(int i=1;i<a.length;i++){
    int key=a[i];
    int j=i-1;
    while(j>0 && a[j]>key){
      a[j+1]=a[j];
      j--;
    }
    a[j]=key;
  }
}

public static void insertionSort(int[] a){
  for(int i=0;i<a.length;i++){
    int min=i;
    for(int j=i+1;j<a.length;j++) if(a[j]<a[min]) min=j;
    int t=a[i]; a[i]=a[min]; a[min]=t;
  }
}

public static void insertionSort(int[] a){
  for(int i=1;i<=a.length;i++){
    int key=a[i];
    int j=i-1;
    while(j>=0 && a[j]>key){ a[j+1]=a[j]; j--; }
    a[j+1]=key;
  }
}
← Back to quizzes

AP Computer Science a Quiz

AP Computer Science a Quiz: Implementing Array Algorithms

Practice Implementing Array Algorithms in AP Computer Science a with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Implementing Array Algorithms, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science a.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

Implement an algorithm to sort the following array in ascending order using insertion sort (no built-in sort): int[] a. Constraints: 0≤n≤1040 \le n \le 10^4. After sorting, a must be in nondecreasing order. Example: [4,1,3] -> [1,3,4]. Which method correctly sorts the array?

  1. public static void insertionSort(int[] a){
  for(int i=1;i<a.length;i++){
    int key=a[i];
    int j=i-1;
    while(j>=0 && a[j]>key){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=key;
  }
}
    (correct answer)
  2. public static void insertionSort(int[] a){
  for(int i=1;i<a.length;i++){
    int key=a[i];
    int j=i-1;
    while(j>0 && a[j]>key){
      a[j+1]=a[j];
      j--;
    }
    a[j]=key;
  }
}

  3. public static void insertionSort(int[] a){
  for(int i=0;i<a.length;i++){
    int min=i;
    for(int j=i+1;j<a.length;j++) if(a[j]<a[min]) min=j;
    int t=a[i]; a[i]=a[min]; a[min]=t;
  }
}

  4. public static void insertionSort(int[] a){
  for(int i=1;i<=a.length;i++){
    int key=a[i];
    int j=i-1;
    while(j>=0 && a[j]>key){ a[j+1]=a[j]; j--; }
    a[j+1]=key;
  }
}
Explanation: This question tests AP Computer Science A skills: implementing array algorithms, specifically the insertion sort algorithm. Insertion sort builds a sorted portion from left to right by inserting each element into its correct position among previously sorted elements. In this problem, students must implement insertion sort with correct loop bounds and element shifting logic. Choice A is correct because it starts from index 1, uses j>=0 to allow insertion at index 0, properly shifts elements right while searching for the insertion position, and inserts at j+1 after the loop. Choice B is incorrect because the while condition j>0 prevents insertion at index 0, causing incorrect sorting when the key should be the smallest element. To help students: Trace through the algorithm with small arrays, showing how the sorted portion grows. Emphasize the importance of boundary conditions in loops.

Question 2

Simulate a line at a help desk using an array-based queue. Implement enqueue (add to back) and dequeue (remove from front) for up to 10410^4 operations. Use a circular buffer with int[] data and indices front, size (no java.util.Queue). Which code correctly dequeues one element and returns it, or returns -1 if empty?

  1. public int dequeue(){
  if(size==0) return -1;
  int val=data[front];
  front=(front+1)%data.length;
  size--;
  return val;
}
    (correct answer)
  2. public int dequeue(){
  if(size==0) return -1;
  int val=data[front];
  front=front+1;
  size--;
  return val;
}

  3. public int dequeue(){
  if(size==0) return -1;
  front=(front+1)%data.length;
  size--;
  return data[front];
}

  4. public int dequeue(){
  if(size==0) return -1;
  int val=data[front];
  size--;
  return val;
}
Explanation: This question tests AP Computer Science A skills: implementing array algorithms, specifically circular buffer queue operations. A circular buffer uses modulo arithmetic to wrap around array boundaries, efficiently utilizing fixed-size arrays for queue operations. In this problem, students must implement dequeue operation that removes and returns the front element while maintaining the circular buffer structure. Choice A is correct because it saves the value at front before updating, uses modulo arithmetic (front+1)%data.length to handle wraparound, and decrements size to maintain queue state. Choice C is incorrect because it updates front before saving the value, returning the wrong element (the one after the front). To help students: Visualize circular buffers with diagrams showing how front and rear pointers move. Practice tracing through enqueue and dequeue operations with small arrays.

Question 3

Given the following array, find the index of the first occurrence of target using binary search on a sorted array that may contain duplicates. Input: sorted int[] a (0≤n≤1050 \le n \le 10^5), int target. Output: smallest index i with a[i]==target, else -1. Example: a=[1,2,2,2,5], target=2 -> 1. Which method is correct?

  1. public static int firstIndex(int[] a,int target){
  int lo=0, hi=a.length-1, ans=-1;
  while(lo<=hi){
    int mid=(lo+hi)/2;
    if(a[mid]==target){ ans=mid; hi=mid-1; }
    else if(a[mid]<target) lo=mid+1;
    else hi=mid-1;
  }
  return ans;
}
    (correct answer)
  2. public static int firstIndex(int[] a,int target){
  int lo=0, hi=a.length-1;
  while(lo<=hi){
    int mid=(lo+hi)/2;
    if(a[mid]==target) return mid;
    if(a[mid]<target) lo=mid+1; else hi=mid-1;
  }
  return -1;
}

  3. public static int firstIndex(int[] a,int target){
  int lo=0, hi=a.length-1, ans=-1;
  while(lo<=hi){
    int mid=(lo+hi)/2;
    if(a[mid]==target){ ans=mid; lo=mid+1; }
    else if(a[mid]<target) lo=mid+1;
    else hi=mid-1;
  }
  return ans;
}

  4. public static int firstIndex(int[] a,int target){
  int lo=0, hi=a.length;
  int ans=-1;
  while(lo<=hi){
    int mid=(lo+hi)/2;
    if(a[mid]>=target){ ans=mid; hi=mid-1; }
    else lo=mid+1;
  }
  return (a[ans]==target)? ans : -1;
}
Explanation: This question tests AP Computer Science A skills: implementing array algorithms, specifically modified binary search for finding first occurrence in arrays with duplicates. When duplicates exist, standard binary search may find any occurrence, but finding the first requires continuing the search in the left half even after finding a match. In this problem, students must modify binary search to always find the leftmost occurrence of the target. Choice A is correct because when target is found, it saves the position in ans but continues searching left (hi=mid-1) to find earlier occurrences, ensuring the first index is returned. Choice B is incorrect because it returns immediately upon finding any occurrence, which may not be the first one in arrays with duplicates. To help students: Trace through examples with multiple duplicates to show why continuing left is necessary. Emphasize how binary search can be modified for different requirements.

Question 4

Given a sorted int[] ids (ascending, distinct) with 0≤n≤1050 \le n \le 10^5, write a method that returns the index of target using binary search, or -1 if not found. No built-in search. Example: ids=[2,5,8,10], target=8 -> 2. Which implementation is correct?

  1. public static int find(int[] ids,int target){
  int lo=0, hi=ids.length-1;
  while(lo<=hi){
    int mid=(lo+hi)/2;
    if(ids[mid]==target) return mid;
    if(ids[mid]<target) lo=mid+1; else hi=mid-1;
  }
  return -1;
}
    (correct answer)
  2. public static int find(int[] ids,int target){
  int lo=0, hi=ids.length;
  while(lo<=hi){
    int mid=(lo+hi)/2;
    if(ids[mid]==target) return mid;
    if(ids[mid]<target) lo=mid+1; else hi=mid-1;
  }
  return -1;
}

  3. public static int find(int[] ids,int target){
  int lo=0, hi=ids.length-1;
  while(lo<hi){
    int mid=(lo+hi)/2;
    if(ids[mid]==target) return mid;
    if(ids[mid]<target) lo=mid; else hi=mid;
  }
  return -1;
}

  4. public static int find(int[] ids,int target){
  for(int i=0;i<ids.length;i++) if(ids[i]==target) return i;
  return -1;
}
Explanation: This question tests AP Computer Science A skills: implementing array algorithms, specifically binary search on sorted arrays. Binary search is a divide-and-conquer algorithm that efficiently finds elements by repeatedly halving the search space. In this problem, students must implement binary search with correct boundary conditions and index calculations. Choice A is correct because it properly initializes hi to ids.length-1, uses the correct loop condition lo<=hi, and updates boundaries correctly (lo=mid+1 and hi=mid-1) to avoid infinite loops. Choice B is incorrect because it initializes hi to ids.length, which could cause an ArrayIndexOutOfBoundsException when accessing ids[mid]. To help students: Draw diagrams showing how lo, hi, and mid change during execution. Practice with arrays of different sizes, including edge cases like single-element arrays.

Question 5

Perform a 2D array operation: write a method that returns the transpose of an int[][] m with r rows and c columns (1≤r,c≤2001 \le r,c \le 200). The result must be a new array with c rows and r columns where result[j][i] = m[i][j]. Example: [[1,2,3],[4,5,6]] -> [[1,4],[2,5],[3,6]]. Which code is correct?

  1. public static int[][] transpose(int[][] m){
  int r=m.length, c=m[0].length;
  int[][] t=new int[c][r];
  for(int i=0;i<r;i++)
    for(int j=0;j<c;j++)
      t[j][i]=m[i][j];
  return t;
}
    (correct answer)
  2. public static int[][] transpose(int[][] m){
  int r=m.length, c=m[0].length;
  int[][] t=new int[r][c];
  for(int i=0;i<r;i++)
    for(int j=0;j<c;j++)
      t[j][i]=m[i][j];
  return t;
}

  3. public static int[][] transpose(int[][] m){
  int r=m.length, c=m[0].length;
  int[][] t=new int[c][r];
  for(int i=0;i<=r;i++)
    for(int j=0;j<c;j++)
      t[j][i]=m[i][j];
  return t;
}

  4. public static int[][] transpose(int[][] m){
  int r=m.length, c=m[0].length;
  int[][] t=new int[c][r];
  for(int i=0;i<r;i++)
    for(int j=0;j<c;j++)
      t[i][j]=m[j][i];
  return t;
}
Explanation: This question tests AP Computer Science A skills: implementing array algorithms, focusing on 2D array manipulation and matrix operations. Matrix transpose swaps rows and columns, requiring careful attention to dimension changes and index mapping. In this problem, students must create a new array with swapped dimensions and correctly map elements from m[i][j] to t[j][i]. Choice A is correct because it creates the result array with dimensions [c][r] (swapped from original [r][c]) and correctly assigns t[j][i]=m[i][j] for all valid indices. Choice B is incorrect because it creates the result array with wrong dimensions [r][c] instead of [c][r], causing ArrayIndexOutOfBoundsException when accessing t[j][i] for j>=r. To help students: Use concrete examples with non-square matrices to highlight dimension changes. Draw the mapping between original and transposed positions.