Suffix Array Test - Sanfoundry

1. Which of the following is the disadvantage of sparse matrices over normal matrices?

Algorithm complexity

Easily compressible

Size

Speed

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

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

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

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

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

3. Which of the following performs the fetch operation?

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

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

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

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

4. When do you use a sparse array?

When the data type of elements differ

When there are unique elements in the array

When elements are sorted

When the array has more occurrence of zero elements

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

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

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

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

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

6. 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?

2 and 6

6 and 6

6 and 2

2 and 2

7. What is a sparse array?

Data structure that compactly stores bits

An array in which most of the elements have the same value

An array in which memory is allocated in run time

Data structure for representing arrays of records

8. What is sparsity of a matrix?

The fraction of zero elements over the total number of elements

The fraction of total number of elements over the non-zero elements

The fraction of total number of elements over the zero elements

The fraction of non-zero elements over the total number of elements

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

Store the element in the specified position

Removes the element from the specified position

Get the element from the specified position

Alter the element in the specified position

10. What is the difference between a normal(naive) array and a sparse array?

A naive array is more efficient

Sparse array can hold more elements than a normal array

Sparse array is dynamic

Sparse array is memory efficient

Start practicing “1000 MCQs on Data Structure”, and once you are ready, you can take tests on all topics by attempting our “Data Structure Test Series”.

« Prev - Sparse Array Test

» Next - Matrix Test