Data Structure Questions and Answers – Sparse Array

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Sparse Array”.


1. Choose the appropriate code that counts the number of non-zero(non-null) elements in the sparse array.
A)

public int count()
{
        int count = 0;
        for (List cur = this.next; (cur != null); cur = cur.next)
        {
            count++;
        }
        return count;
}

B)

public int count()
{
        int count = 0;
        for (List cur = this; (cur != null); cur = cur.next)
        {
            count++;
        }
        return count;
}

C)

public int count()
{
        int count = 1;
        for (List cur = this.next; (cur != null); cur = cur.next)
        {
            count++;
        }
        return count;
}

D)

public int count()
{
    int count = 1;
    for (List cur = this.next; (cur != null); cur = cur.next.next)
    {
        count++;
    }
    return count;
}


Explanation: To count the non-null elements, use a simple for loop.

2. Suppose the contents of an array A are, A = {1, null, null, null, null, 10};
What would be the size of the array considering it as a normal array and a sparse array?

A) 6 and 6
B) 6 and 2
C) 2 and 6
D) 2 and 2

Explanation: A regular array includes null as an element, but a sparse array only recognises non-zero or non-null elements.

3. What is sparsity of a matrix?
A) The fraction of zero elements over the total number of elements
B) The fraction of non-zero elements over the total number of elements
C) The fraction of total number of elements over the zero elements
D) The fraction of total number of elements over the non-zero elements

Explanation: The proportion of zero elements in a matrix over the total number of zero elements is known as sparsity.

4. How would you store an element in a sparse matrix?
A)

public void store(int row_index, int col_index, Object val)
{
        if (row_index < 0 || row_index > N)
	{
            System.out.println("row index out of bounds");
			return;
	}
        if (col_index < 0 || col+index > N)
	{
            System.out.println("column index out of bounds");
			return;
	}
        sparse_array[row_index].store(col_index, val);
}

B)

public void store(int row_index, int col_index, Object val)
{
        if (row_index < 0 || row_index > N)
	{
            System.out.println("column index out of bounds");
			return;
	}
        if (col_index < 0 || col+index > N)
	{
            System.out.println("row index out of bounds");
			return;
	}
        sparse_array[row_index].store(col_index, val);
}

C)

public void store(int row_index, int col_index, Object val)
{
        if (row_index < 0 && row_index > N)
	{
            System.out.println("row index out of bounds");
			return;
	}
        if (col_index < 0 && col+index > N)
	{
            System.out.println("column index out of bounds");
			return;
	}
        sparse_array[row_index].store(col_index, val);
    }

D)

public void store(int row_index, int col_index, Object val)
{
        if (row_index < 0 && row_index > N)
	{
            System.out.println("column index out of bounds");
			return;
	}
        if (col_index < 0 && col+index > N)
	{
            System.out.println("row index out of bounds");
			return;
	}
        sparse_array[row_index].store(col_index, val);
}


Explanation: A sparse matrix’s rows function as sparse arrays, so the row with the specified col index is the array and the specified location where the element is stored.

5. What is the functionality of the following piece of code?

public Object function(int row_index, int col_index)
{
        if (row_index < 0 || col_index > N)
	{
            System.out.println("column index out of bounds");
			return;
	}
        return (sparse_array[row_index].fetch(col_index));
}

A) Store the element in the specified position
B)Get the element from the specified position
C) Alter the element in the specified position
D) Removes the element from the specified position

Explanation: The row defined by row index makes it an array, and the col index denotes the specified location in the SparseArray class’s fetch process.

6. Which of the following is the disadvantage of sparse matrices over normal matrices?
A) Size
B) Speed
C) Easily compressible
D) Algorithm complexity

Explanation: We’ll only compute operations on non-zero values since the sparse matrix contains zeroes. This increases the algorithm’s complexity since we must first identify the index of zero elements, and we must not use such indexes during computation. This is a drawback. Sparse matrices are easily compressible because they do not store the zero/null elements, requiring less memory space. Additionally, only the non zero elements must be computed, increasing computational speed.

7. What is a sparse array?
A) Data structure for representing arrays of records
B) Data structure that compactly stores bits
C) An array in which most of the elements have the same value
D) An array in which memory is allocated in run time

Explanation: They have a default value, which is normally 0 or null.

8. When do you use a sparse array?
A) When there are unique elements in the array
B) When the array has more occurrence of zero elements
C) When the data type of elements differ
D) When elements are sorted

Explanation: It doesn’t have to be zero; any default value, normally zero or null, will suffice.

9. What is the difference between a normal(naive) array and a sparse array?
A) Sparse array can hold more elements than a normal array
B) Sparse array is memory efficient
C) Sparse array is dynamic
D) A naive array is more efficient

Explanation: A naive implementation allocates space for the entire array size, while a sparse array (linked list implementation) only allocates space for non-default values.

10. Choose the code which performs the store operation in a sparse array.(Linked list implementation)
A)

public void store(int index, Object val)
{
       List cur = this;
       List prev = null;
 
       List node = new List(index);
       node.val = val;
 
       while (cur != null && cur.index < index)
       {
           prev = cur;
           cur = cur.next;
       }
 
       if (cur == null)
       {
           prev.next = node;
       } else
       {
           if (cur.index == index)
           {
               System.out.println("DUPLICATE");
               return;
           }
           prev.next = node;
           node.next = cur;
       }
       return;
}

B)

public void store(int index, Object val)
{
        List cur = this;
        List prev = null;
 
        List node = new List(index);
        node.val = val;
 
        while (prev != null && prev.index < index)
        {
            prev = cur;
            cur = cur.next;
        }
 
       C) if (cur == null)
        {
            prev.next = node;
        } else
        {
            if (cur.index == index)
            {
                System.out.println("DUPLICATE");
                return;
            }
            prev.next = node;
            node.next = cur;
        }
        return;
}

D)

public void store(int index, Object val)
{
    List cur = this;
    List prev = null;
 
    List node = new List(index);
    node.val = val;
 
    while (cur != null && prev.index < index)
    {
        cur = cur.next;
        prev = cur;
    }
 
    if (cur == null)
    {
        prev.next = node;
    } 
    else
    {
        if (cur.index == index)
    {
        System.out.println("DUPLICATE");
        return;
    }
    prev.next = cur;
    node.next = node;
    }
    return;
}


Explanation: Create a new node and navigate through the list until you find the correct location, then search the list for duplicates and nulls before inserting the node.

11. Which of the following performs the fetch operation?
A)

public Object fetch(int index)
{
        List cur = this.next;
        Object val = null;
        while (cur != null && cur.index != index)
        {
            cur = cur.next;
        }
        if (cur != null)
        {
            val = cur.val;
        } else
        {
            val = null;
        }
        return val;
}

B)

public Object fetch(int index)
{
        List cur = this;
        Object val = null;
        while (cur != null && cur.index != index)
        {
            cur = cur.next;
        }
        if (cur != null)
        {
            val = cur.val;
        } else
        {
            val = null;
        }
        return val;
}

C)

public Object fetch(int index)
{
        List cur = this;
        Object val = null;
        while (cur != null && cur.index != index)
        {
            cur = cur.index;
        }
        if (cur != null)
        {
            val = cur.val;
        } else
        {
            val = null;
        }
        return val;
}

D)

public Object fetch(int index)
{
    List cur = this.next;
    Object val = null;
    while (cur != null && cur.index != index)
    {
        cur = cur.index;
    }
    if (cur != null)
    {
        val = cur.val;
    } 
    else
    {
        val = null;
    }
    return val;
}


Explanation: You traverse the array until you hit the end or an index, then return the element at that index, or null otherwise.

A sparse array is a matrix with the majority of its elements being empty. There is no precise specification about how many elements in a matrix must be zero to be considered sparse, but one common criterion is that the number of non-zero elements equals the number of rows or columns. When the majority of the elements are nonzero, the matrix is said to be dense.

Leave a Reply

Your email address will not be published. Required fields are marked *