Category: Data Structure Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Queue using Stacks”.

1. A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What are the total number of stacks required for this operation?(you can reuse the stack)
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: The addFront and removeFront operations can be performed using one stack itself as push and pop are supported (adding and removing element from top of the stack) but to perform addRear and removeRear you need to pop each element from the current stack and push it into another stack, push or pop the element as per the asked operation from this stack and in the end pop elements from this stack to the first stack.

2. You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).
a) O(m)
b) O(n)
c) O(m*n)
d) Data is insufficient
Answer: a
Clarification: To perform deQueue operation you need to pop each element from the first stack and push it into the second stack. In this case you need to pop ‘m’ times and need to perform push operations also ‘m’ times. Then you pop the first element from this second stack (constant time) and pass all the elements to the first stack (as done in the beginning)(‘m-1’ times). Therfore the time complexity is O(m).

3. Consider you have an array of some random size. You need to perform dequeue operation. You can perform it using stack operation (push and pop) or using queue operations itself (enQueue and Dequeue). The output is guaranteed to be same. Find some differences?
a) They will have different time complexities
b) The memory used will not be different
c) There are chances that output might be different
d) No differences
Answer: a
Clarification: To perform operations such as Dequeue using stack operation you need to empty all the elements from the current stack and push it into the next stack, resulting in a O(number of elements) complexity whereas the time complexity of dequeue operation itself is O(1). And there is a need of a extra stack. Therefore more memory is needed.

4. Consider you have a stack whose elements in it are as follows.
5 4 3 2 << top
Where the top element is 2.
You need to get the following stack
6 5 4 3 2 << top
The operations that needed to be performed are (You can perform only push and pop):
a) Push(pop()), push(6), push(pop())
b) Push(pop()), push(6)
c) Push(pop()), push(pop()), push(6)
d) Push(6)
Answer: a
Clarification: By performing push(pop()) on all elements on the current stack to the next stack you get 2 3 4 5 << top.Push(6) and perform push(pop()) you’ll get back 6 5 4 3 2 << top. You have actually performed enQueue operation using push and pop.

5. A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)
a) O(m) and O(n)
b) O(1) and O(n)
c) O(n) and O(1)
d) O(n) and O(m)
Answer: b
Clarification: addFront is just a normal push operation. Push operation is of O(1). Whereas addRear is of O(n) as it requires two push(pop()) operations of all elements of a stack.

6. Why is implementation of stack operations on queues not feasible for a large dataset (Asssume the number of elements in the stack to be n)?
a) Because of its time complexity O(n)
b) Because of its time complexity O(log(n))
c) Extra memory is not required
d) There are no problems
Answer: a
Clarification: To perform Queue operations such as enQueue and deQueue there is a need of emptying all the elements of a current stack and pushing elements into the next stack and vice versa. Therfore it has a time complexity of O(n) and the need of extra stack as well, may not be feasible for a large dataset.

7. Consider yourself to be in a planet where the computational power of chips to be slow. You have an array of size 10.You want to perform enqueue some element into this array. But you can perform only push and pop operations .Push and pop operation both take 1 sec respectively. The total time required to perform enQueue operation is?
a) 20
b) 40
c) 42
d) 43
Answer: d
Clarification: First you have to empty all the elements of the current stack into the temporary stack, push the required element and empty the elements of the temporary stack into the original stack. Therfore taking 10+10+1+11+11= 43 seconds.

8. You have two jars, one jar which has 10 rings and the other has none. They are placed one above the other. You want to remove the last ring in the jar. And the second jar is weak and cannot be used to store rings for a long time.
a) Empty the first jar by removing it one by one from the first jar and placing it into the second jar
b) Empty the first jar by removing it one by one from the first jar and placing it into the second jar and empty the second jar by placing all the rings into the first jar one by one
c) There exists no possible way to do this
d) Break the jar and remove the last one
Answer: b
Clarification: This is similar to performing dequeue operation using push and pop only. Elements in the first jar are taken out and placed in the second jar. After removing the last element from the first jar, remove all the elements in the second jar and place them in the first jar.

9. Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?
a) Push
b) Pop
c) Enqueue
d) Returntop
Answer: c
Clarification: To perform Enqueue using just push and pop operations, there is a need of another array of same size. But as there is no extra available memeory, the given operation is not feasible.

10. Given an array of size n, let’s assume an element is ‘touched’ if and only if some operation is performed on it(for example, for performing a pop operation the top element is ‘touched’). Now you need to perform Dequeue operation. Each element in the array is touched atleast?
a) Once
b) Twice
c) Thrice
d) Four times
Answer: d
Clarification: First each element from the first stack is popped, then pushed into the second stack, dequeue operation is done on the top of the stack and later the each element of second stack is popped then pushed into the first stack. Therfore each element is touched four times.

Data Structure Multiple Choice Questions on “Sparse Array”.

1. 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
Answer: c
Clarification: They are set to a default value, usually 0 or null.

2. 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
Answer: b
Clarification: It need not necessarily be zero, it could be any default value, usually zero or null.

3. 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
Answer: b
Clarification: 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. 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
Clarification: 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. 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
Clarification: 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. 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
Clarification: A simple ‘for loop’ to count the non-null elements.

7. 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
Answer: b
Clarification: 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. 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
Answer: a
Clarification: Sparsity of a matrix is the fraction of number of zero elements over the total number of zero elements.

9. 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
Clarification: 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. 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
Answer: b
Clarification: 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. Which of the following is the disadvantage of sparse matrices over normal matrices?
a) Size
b) Speed
c) Easily compressible
d) Algorithm complexity
Answer: d
Clarification: 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.

Data Structures & Algorithms Multiple Choice Questions on “Tango Tree”.

1. Who developed the concept of tango tree?
a) Erik Demaine
b) Mihai Patrascu
c) John Lacono
d) All of the mentioned

Answer: d
Clarification: Erik Demaine is a well-known professor of Computer Science at MIT. John Lacono is an American computer scientist specialized in data structure and algorithm while Mihai Patrascu was a Romanian- American computer scientist. All of them together developed the concept of Tango tree.

2. Which type of tree is tango tree?
a) Ternary Tree
b) AVL Tree
c) Binary Search Tree
d) K-ary Tree

Answer: c
Clarification: Tango tree is an example of binary search tree which was developed by four famous scientists Erik Demaine, Mihai Patrascu, John Lacono and Harmon in the year 2004.

3. After which city is tango tree named?
a) Vatican City
b) Buenos Aires
c) New York
d) California

Answer: b
Clarification: Tango is a popular couple dance or partner dance that was originated in the 1880s somewhere between Argentina and Uruguay. Buenos Aires is a capital city off Argentina. Hence they named after Buenos Aires.

4. Which type of binary search tree or algorithm does tango tree use?
a) Online
b) Offline
c) Static
d) Dynamic

Answer: d
Clarification: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.

5. What is the time complexity of for achieving competitive ratio by tango tree?
a) O (log n)
b) O (n²)
c) O (n!)
d) O (log (log n))

Answer: d
Clarification: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.

6. Which type of binary search tree is imitated for construction of tango tree?
a) Complete Binary Search Tree
b) Perfect Binary Search Tree
c) Balanced Binary Search Tree
d) Degenerate Binary Search Tree

Answer: a
Clarification: Tango tree is constructed by simulating a complete binary search tree. This tree is also known as Reference tree, that contains all the elements of the tree. Also, the reference tree is never showed in actual implementation.

7. Which special balanced binary search tree is used to store the nodes of auxiliary tree?
a) Red – Black Tree
b) Red – Brown Tree
c) Red – Yellow Tree
d) Red – Tango Tree

Answer: a
Clarification: The path starting from the root and following the path of preferred child node till the end of leaf node is known as preferred path. Nodes are stored in Red – Black tree for the representation of the preferred path.

8. Is tango tree represented as a tree of trees.
a) True
b) False

Answer: a
Clarification: Partitioning method is used by tango tree which partitions a binary search tree into small sets of paths and then storing them to auxiliary trees. Hence tango tree is represented as a tree of trees.

9. Which operation is used to combine two auxiliary trees?
a) Join
b) Combinatorial
c) Add
d) Concatenation

Answer: a
Clarification: If the top node of one of the reference tree amongst the two, is the is the child of the bottom node of the other reference tree, then the join operation can be carried out to join the two auxiliary trees.

10. Is partitioning method used by Tango Tree.
a) True
b) False

Answer: a
Clarification: Partitioning method is used by tango tree which partitions a binary search tree into small sets of paths and then storing them to auxiliary trees. Hence tango tree is represented as a tree of trees.

11. Which operation is used to break a preferred path into two sets of parts at a particular node?
a) Differentiate
b) Cut
c) Integrate
d) Join

Answer: b
Clarification: A preferred path is broken into two parts. One of them is known as top part while other is known as bottom part. To break a preferred path into two sets, cut operation is used at a particular node.

12. What is the upper bound for a tango tree if k is a number of interleaves?
a) k+2 O (log (log n))
b) k O (log n)
c) K² O (log n)
d) k+1 O (log (log n))

Answer: d
Clarification: Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).

13. What is the time complexity for searching k+1 auxiliary trees?
a) k+2 O (log (log n))
b) k+1 O (log n)
c) K+2 O (log n)
d) k+1 O (log (log n))

Answer: d
Clarification: Since each search operation in the auxiliary tree takes O (log (log n)) time as auxiliary tree size is bounded by the height of the reference tree that is log n. So for k+1 auxiliary trees, total search time is k+1 O (log (log n)).

14. What is the time complexity for the update cost on auxiliary trees?
a) O (log (log n))
b) k-1 O (log n)
c) K² O (log n)
d) k+1 O (log (log n))

Answer: d
Clarification: The update cost also is bounded by the upper bound. We perform one cut as well as one join operation for the auxiliary tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).

15. Which of the following is the self-adjusting binary search tree?
a) AVL Tree
b) Splay Tree
c) Top Tree
d) Ternary Tree

Answer: b
Clarification: Splay tree is a self – adjusting binary search tree. It performs basic operations on the tree like insertion, deletion, loop up performing all these operations in O (log n) time.

Data Structure Multiple Choice Questions on “Weak Heap”.

1. Choose the correct properties of weak-heap.
a) Every node has value greater than the value of child node
b) Every right child of node has greater value than parent node
c) Every left child of node has greater value than parent node
d) Every left and right child of node has same value as parent node
Answer: b
Clarification: This is the property of a weak heap.

2. Left child of parent node has value lesser than the parent node.
a) True
b) False
Answer: b
Clarification: Weak heap has no left child.

3. What is the other name of weak heap?
a) Min-heap
b) Max-heap
c) Relaxed -heap
d) Leonardo heap
Answer: c
Clarification: Relaxed heap is just another name of weak heap.

4. What is the worst case time in searching minimum value in weak -heap?
a) O(log n)
b) O(n)
c) O(n logn)
d) O(1)
Answer: d
Clarification: Weak heap is an array based form that supports the operation of finding a minimum in O(1).

5. The total comparisons in finding both smallest and largest elements are
a) 2*n +2
b) n + ((n+1)/2) -2
c) n+logn
d) n²
Answer: b
Clarification: The total comparisons in finding smallest and largest elements is n + ((n+1)/2) – 2.

6. What is the complexity of given function of insertion.

	insert(int n)
	{
		if(buffer_size()< maxi_biffer_size())
		buffer_aar[ind]==n;
		else
		move_to_heap(buffer,buffer+maxi_buffer_size())
	}

a) O(logn)
b) amortized O(1)
c) O(n)
d) O (n*logn)
Answer: b
Clarification: Use a buffer array to store a fixed number of elements when the buffer is full the content of buffer is moved to heap.As a result the complexity
is amotized O(1).

7. Does there exist a heap with seven distinct elements so that the Inorder traversal gives the element in sorted order.
a) Yes
b) No
Answer: b
Clarification: No, The inorder traversal will not give elements in sorted order. As heap is implemented as either min-heap or max-heap, the root will be have highest or lowest value than remaining values of the nodes. So this traversal will not give a sorted list.

8. The leaf node for a heap of height h will be at which position.
a) h
b) h-1
c) h or h-1
d) h-2
Answer: c
Clarification: A complete binary tree is also a heap so by the property of binary tree the leaf nodes will be must at height h or h-1.