Computer Science A

Course Progress 0/0
Sprint View
Week 19 2015 FRQ 3

2015 FRQ 3

2 min read

FRQ Background

AP Computer Science A

2015 Free-Response Question 3 — SparseArray

A two-dimensional array can be represented in a sparse array format, which only stores the non-zero elements of the array.

Each non-zero element is represented by a SparseArrayEntry object.

public class SparseArrayEntry
{
   private int row;
   private int col;
   private int value;


   public SparseArrayEntry(int r, int c, int v)
   {
       row = r;
       col = c;
       value = v;
   }


   public int getRow()
   {
       return row;
   }


   public int getCol()
   {
       return col;
   }


   public int getValue()
   {
       return value;
   }
}




Sparse array:
public class SparseArray
{
   private int numRows;
   private int numCols;
   private List<SparseArrayEntry> entries;


   // constructors and other methods not shown
}

FRQ Question Part A

Write the method getValueAt, which returns the value of the sparse array at a given row and column. If there is no entry in the sparse array at the specified location, the method should return 0.

//Method Header
public int getValueAt(int row, int col)

public int getValueAt(int row, int col)
{
   for (SparseArrayEntry e : entries)
   {
       if (e.getRow() == row && e.getCol() == col)
       {
           return e.getValue();
       }
   }
   return 0;
}

Scoring Guidelines Part A

Part (a) getValueAt (3 points) focuses on:

  • Iterating/accessing the needed elements of entries safely (no bounds errors).
  • Correctly identifying whether an entry exists with matching (row, col).
  • Returning the entry’s value if found, otherwise returning 0

FRQ Question Part B

Write the method removeColumn, which removes an entire column from the sparse array. All entries in the specified column should be removed.

All entries in columns to the right of the removed column should have their column index decremented by 1.

The value of numCols should be updated accordingly. public void removeColumn(int col)

public void removeColumn(int col)
{
   int i = 0;


   while (i < entries.size())
   {
       SparseArrayEntry e = entries.get(i);


       if (e.getCol() == col)
       {
           entries.remove(i); // do NOT increment i here
       }
       else if (e.getCol() > col)
       {
           entries.set(i, new SparseArrayEntry(e.getRow(), e.getCol() - 1, e.getValue()));
           i++;
       }
       else
       {
           i++;
       }
   }


   numCols--;
}

Scoring Guidelines Part B

Part (b) removeColumn (6 points) focuses on:

  • Decrementing numCols exactly once.
  • Correctly scanning all entries (no bounds errors).
  • Removing entries whose column equals col.
  • For entries with column greater than col, replacing them with a new SparseArrayEntry whose column is decreased by 1 (same row and value).
  • End state must be correct: only the col entries removed; only the > col entries shifted; everything else unchanged (minor loop mistakes can still earn this “overall correctness” point).

Course Timeline