Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Sparse Array

1 - Question

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

View Answer

Answer: c
Explanation: They are set to a default value, usually 0 or null.




2 - Question

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

View Answer

Answer: b
Explanation: It need not necessarily be zero, it could be any default value, usually zero or null.




3 - Question

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

View Answer

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




4 - Question

 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;
        }
 
        if (cur == null)
        {
            prev.next = node;
        } else
        {
            if (cur.index == index)
            {
                System.out.println("DUPLICATE");
                return;
            }
            prev.next = node;
            node.next = cur;
        }
        return;
}

c)

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)
        {
			cur = cur.next;
            prev = cur;
        }
 
        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;
}
View Answer

Answer: a
Explanation: Create a new node and traverse through the list until you reach the correct position, check for duplicate and nullity of the list and then insert the node.




5 - Question

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;
}
View Answer

Answer: b
Explanation: You travers through the array until the end is reached or the index is found and return the element at that index, null otherwise.




6 - Question

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;
}

 

View Answer

Answer: a
Explanation: A simple ‘for loop’ to count the non-null elements.




7 - Question

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

View Answer

Answer: b
Explanation: A normal array considers null also as an element, but in the sparse array only a non-zero or a non-null element is considered.




8 - Question

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

View Answer

Answer: a
Explanation: Sparsity of a matrix is the fraction of number of zero elements over the total number of zero elements.




9 - Question

 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);
}

 

View Answer

Answer: a
Explanation: Each row in a sparse matrix acts as a sparse array, hence this row with the specified col_index is the array and the specified position where the element is stored.




10 - Question

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

View Answer

Answer: b
Explanation: The fetch method of SparseArray class is called , the row specified by row_index makes it an array and the col_index denotes the specified position.




11 - Question

Which of the following is the disadvantage of sparse matrices over normal matrices?
a) Size
b) Speed
c) Easily compressible
d) Algorithm complexity

View Answer

Answer: d
Explanation: As the sparse matrix contains zeroes we will compute operations only on non zero values. This increases the complexity of algorithm as we need to identify index of zero elements first and during computation we should not take those index. It is a disadvantage. Sparse matrix is easily compressible by not storing the zero/null elements, they require less memory space, also only the non zero elements have to be computed, hence computational speed increases.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners