Category: Data Structure Objective Questions

Data Structure Multiple Choice Questions on “Stack using Array”.

1. Which of the following real world scenarios would you associate with a stack data structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) tatkal Ticket Booking in IRCTC
Answer: a
Clarification: Stack follows Last In First Out (LIFO) policy. Piling up of chairs one above the other is based on LIFO, people standing in a line is a queue and if the service is based on priority, then it can be associated with a priority queue. Tatkal Ticket Booking Follows First in First Out Policy. People who click the book now first will enter the booking page first.

2. What does the following function check for? (all necessary headers to be included and function is called from main)

#define MAX 10
 
typedef struct stack
{
    int top;
    int item[MAX];
}stack;
 
int function(stack *s)
{
    if(s->top == -1)
        return 1;
    else return 0;
}

a) full stack
b) invalid index
c) empty stack
d) infinite stack
Answer: c
Clarification: An empty stack is represented with the top-of-the-stack(‘top’ in this case) to be equal to -1.

3. What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
Answer: c
Clarification: Removing items from an empty stack is termed as stack underflow.

4. What is the output of the following program?

public class Stack
{
	protected static final int CAPACITY = 100;
	protected int size,top = -1;
	protected Object stk[];
 
	public Stack()
	{
		stk = new Object[CAPACITY];
	}
 
	public void push(Object item)
	{
		if(size_of_stack==size)
		{
			System.out.println("Stack overflow");
				return;
		}
		else
		{
			top++;
			stk[top]=item;
		}
	}
	public Object pop()
	{
		if(top<0)
		{
			return -999;
		}
		else
		{
			Object ele=stk[top];
			top--;
			size_of_stack--;
			return ele;
		}
	}
}
 
public class StackDemo
{
	public static void main(String args[])
	{
		Stack myStack = new Stack();
		myStack.push(10);
		Object element1 = myStack.pop();
		Object element2 = myStack.pop();
		System.out.println(element2);
	}
}

a) stack is full
b) 20
c) 0
d) -999
Answer: d
Clarification: The first call to pop() returns 10, whereas the second call to pop() would result in stack underflow and the program returns -999.

5. What is the time complexity of pop() operation when the stack is implemented using an array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: a
Clarification: pop() accesses only one end of the structure, and hence constant time.

6. Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack > N)?
a) S[N-1]
b) S[N]
c) S[1]
d) S[0]
Answer: b
Clarification: Elements are pushed at the end, hence N.

7. What happens when you pop from an empty stack while implementing using the Stack ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown
Answer: c
Clarification: The Stack ADT throws an EmptyStackException if the stack is empty and a pop() operation is tried on it.

8. What is the functionality of the following piece of Java code?
Assume: ‘a’ is a non empty array of integers, the Stack class creates an array of specified size and provides a top pointer indicating TOS(top of stack), push and pop have normal meaning.

public void some_function(int[] a)
{
	Stack S=new Stack(a.length);
	int[] b=new int[a.length];
	for(int i=0;i<a.length;i++)
	{
		S.push(a[i]);
	}
	for(int i=0;i<a.length;i++)
	{
		b[i]=(int)(S.pop());
	}
	System.out.println("output :");
	for(int i=0;i<b.length;i++)
	{
		System.out.println(b[i]);
	}
}

a) print alternate elements of array
b) duplicate the given array
c) parentheses matching
d) reverse the array
Answer: d
Clarification: Every element from the given array ‘a’ is pushed into the stack, and then the elements are popped out into the array ‘b’. Stack is a LIFO structure, this results in reversing the given array.

9. Array implementation of Stack is not dynamic, which of the following statements supports this argument?
a) space allocation for array is fixed and cannot be changed during run-time
b) user unable to give the input for stack operations
c) a runtime exception halts execution
d) improper program compilation
Answer: a
Clarification: You cannot modify the size of an array once the memory has been allocated, adding fewer elements than the array size would cause wastage of space, and adding more elements than the array size at run time would cause Stack Overflow.

10. Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N)?
a) S[N-1]
b) S[N]
c) S[N-2]
d) S[N+1]
Answer: a
Clarification: Array indexing start from 0, hence N-1 is the last index.

Data Structure Multiple Choice Questions on “Towers of Hanoi”.

1. The optimal data structure used to solve Tower of Hanoi is _________
a) Tree
b) Heap
c) Priority queue
d) Stack
Answer: d
Clarification: The Tower of Hanoi involves moving of disks ‘stacked’ at one peg to another peg with respect to the size constraint. It is conveniently done using stacks and priority queues. Stack approach is widely used to solve Tower of Hanoi.

2. Select the appropriate code for the recursive Tower of Hanoi problem.(n is the number of disks)
a)

public void solve(int n, String start, String auxiliary, String end)
{
       if (n == 1) 
       {
           System.out.println(start + " -> " + end);
       } 
       else
       {
           solve(n - 1, start, end, auxiliary);
           System.out.println(start + " -> " + end);
           solve(n - 1, auxiliary, start, end);
       }
}

b)

public void solve(int n, String start, String auxiliary, String end) 
{
       if (n == 1) 
       {
           System.out.println(start + " -> " + end);
       } 
       else 
       {
           solve(n - 1, auxiliary, start, end);
           System.out.println(start + " -> " + end);
       }
}

c)

public void solve(int n, String start, String auxiliary, String end) 
{
       if (n == 1) 
       {
           System.out.println(start + " -> " + end);
       } 
       else 
       {
           System.out.println(start + " -> " + end);
	   solve(n - 1, auxiliary, start, end);
       }
}

d)

public void solve(int n, String start, String auxiliary, String end)
{
       if (n == 1) 
       {
           System.out.println(start + " -> " + end);
       } 
       else
       {
           solve(n - 1, start, end, auxiliary);
           System.out.println(start + " -> " + end);
       }
}

View Answer

Answer: a
Clarification: First transfer all the diska to the auxiliary and then to the end peg, this is achieved by making auxiliary peg as the end peg in the first recursive call, in the second recursive call, the auxiliary becomes the start peg from where the disks are transferred to the end peg.

3. Which among the following is not a palindrome?
a) Madam
b) Dad
c) Malayalam
d) Maadam
Answer: d
Clarification: A palindrome is a string that reads the same forward and backward, Madam, Dad and Malayalam are palindromes where as Maadam is not a palindrome.

4. Which data structure can be used to test a palindrome?
a) Tree
b) Heap
c) Stack
d) Priority queue
Answer: c
Clarification: Stack is a convenient option as it involves pushing and popping of characters.

5. Select the appropriate code which tests for a palindrome.
a)

public static void main(String[] args) 
{
	System.out.print("Enter any string:");
        Scanner in=new Scanner(System.in);
        String input = in.nextLine();
        Stack<Character> stk = new Stack<Character>();
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String reverse = "";
	while (!stk.isEmpty())
	{
            reverse = reverse + stk.pop();
        }
	if (input.equals(reverse))
        System.out.println("palindrome");
        else
        System.out.println("not a palindrome");
}

b)

public static void main(String[] args) 
{
	System.out.print("Enter any string:");
        Scanner in=new Scanner(System.in);
        String input = in.nextLine();
        Stack<Character> stk = new Stack<Character>();
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String reverse = "";
	while (!stk.isEmpty())
	{
            reverse = reverse + stk.peek();
        }
	if (input.equals(reverse))
        System.out.println("palindrome");
        else
            System.out.println("not a palindrome");
}

c)

public static void main(String[] args) 
{
	System.out.print("Enter any string:");
        Scanner in=new Scanner(System.in);
        String input = in.nextLine();
        Stack<Character> stk = new Stack<Character>();
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String reverse = "";
	while (!stk.isEmpty())
	{
            reverse = reverse + stk.pop();
			stk.pop();
        }
	if (input.equals(reverse))
        System.out.println("palindrome");
        else
            System.out.println("not a palindrome");
}

d)

public static void main(String[] args) 
{
	System.out.print("Enter any string:");
        Scanner in=new Scanner(System.in);
        String input = in.nextLine();
        Stack<Character> stk = new Stack<Character>();
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String reverse = "";
	while (!stk.isEmpty())
	{
            reverse = reverse + stk.pop();
			stk.pop();
        }
	if (!input.equals(reverse))
        System.out.println("palindrome");
        else
            System.out.println("not a palindrome");
}

View Answer

Answer: a
Clarification: Push all the characters in the input string to a stack, now pop them and append to a new string which is checked for equality with the original string.

6. What is the number of moves required to solve Tower of Hanoi problem for k disks?
a) 2k – 1
b) 2k + 1
c) 2^k + 1
d) 2^k – 1
Answer: d
Clarification: Tracing of the moves in the above ToH problem will prove this result, instead you can simply add a count for each recursive call to check the number of moves.

7. Select the appropriate code which reverses a word.
a)

public String reverse(String input)
{
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String rev = "";
	while (!stk.isEmpty())
	{
            rev = rev + stk.peek();
        }
	return rev;
}

b)

public String reverse(String input)
{
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String rev = "";
	while (!stk.isEmpty())
	{
            rev = rev + stk.pop();
        }
	return rev;
}

c)

public String reverse(String input)
{
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String rev = "";
	while (!stk.isEmpty())
	{
            rev = rev + stk.pop();
        }
}

d)

public String reverse(String input)
{
	for (int i = 0; i < input.length(); i++) 
	{
            stk.push(input.charAt(i));
        }
	String rev = "";
	while (!stk.isEmpty())
	{
            rev = rev + stk.pop();
	    stk.pop();
        }
	return rev;
}

View Answer

Answer: b
Clarification: Although, it is possible to reverse the string without using stack, it is done by looping through the string from the end character by character.
In Java, it is also possible to use the StringBuilder and StringBuffer classes which have a built-in method ‘reverse’.
Note its similarity to PalindromeTest.

Data Structure Multiple Choice Questions on “Xor Linked List”.

1. What is xor linked list?
a) uses of bitwise XOR operation to decrease storage requirements for doubly linked lists
b) uses of bitwise XOR operation to decrease storage requirements for linked lists
c) uses of bitwise operations to decrease storage requirements for doubly linked lists
d) just another form of linked list
Answer: a
Clarification: Why we use bitwise XOR operation is to decrease storage requirements for doubly linked lists.

2. What does a xor linked list have?
a) every node stores the XOR of addresses of previous and next nodes
b) actuall memory address of next node
c) every node stores the XOR of addresses of previous and next two nodes
d) every node stores xor 0 and the current node address
Answer: a
Clarification: Every node stores the XOR of addresses.

3. What does first and last nodes of a xor linked lists contain ? (let address of first and last be A and B)
a) NULL xor A and B xor NULL
b) NULL and NULL
c) A and B
d) NULL xor A and B
Answer: a
Clarification: NULL xor A and B xor NULL.

4. Which of the following is an advantage of XOR list?
a) Almost of debugging tools cannot follow the XOR chain, making debugging difficult
b) You need to remember the address of the previously accessed node in order to calculate the next node’s address
c) In some contexts XOR of pointers is not defined
d) XOR list decreases the space requirement in doubly linked list
Answer: d
Clarification: XOR linked list stores the address of previous and next nodes by performing XOR operations. It requires single pointer to store both XOR address of next and previous nodes. Thus it reduces space. It is an advantage. But the main disadvantages are debugging tools cannot follow XOR chain, previous node address must be remembered to get next nodes and pointers are not defined accurately.

5. Which of the following is not the properties of XOR lists?
a) X⊕X = 0
b) X⊕0 = X
c) (X⊕Y)⊕Z = X⊕(Y⊕Z)
d) X⊕0 = 1
Answer: d
Clarification: The important properties of XOR lists are X⊕X=0, X⊕0=X and (X⊕Y)⊕Z = X⊕(Y⊕Z).

6. Which of the following statements are true?
i) practical application of XOR linked lists are in environments with limited space requirements, such as embedded devices.
ii)xor lists are not suitable because most garbage collectors will fail to work properly with classes or structures that don’t contain literal pointers
iii)in order to calculate the address of the next node you need to remember the address of the previous node
iv)xor lists are much efficient than single, doubly linked lists and arrays
a) i, ii, iii, iv
b) i, ii, iii
c) i, ii
d) i
Answer: b
Clarification: Xor lists requires same time for most of the operations as arrays would require.

7. What’s wrong with this code which returns xor of two nodes address ?

//struct is common userdefined datatype in c/c++ and class is it's alternative
 
struct node* XOR (struct node *a, struct node *b) 
{
    //this logic is used to fill the nodes with address of a xor linked list
    return  ((int) (a) ^ (int) (b));   
}

a) nothing wrong. everything is fine
b) type casting at return is missing
c) parameters are wrong
d) total logic is wrong
Answer: b
Clarification: It must be typecasted– return (struct node*)((int) (a) (int) (b));

8. Given 10,8,6,7,9
swap the above numbers such that finally you got 6,7,8,9,10
so now reverse 10
9,7,6,8,10
now reverse 9
8,6,7,9,10
7,6,8,9,10
6,7,8,9,10
at this point 6 is ahead so no more reversing can be done so stop.
To implement above algorithm which datastructure is better and why ?
a) linked list. because we can swap elements easily
b) arrays. because we can swap elements easily
c) xor linked list. because there is no overhead of pointers and so memory is saved
d) doubly linked list. because you can traverse back and forth
Answer: c
Clarification: XOR linked lists are used to reduce the memory by storing the XOR values of address instead of actual address in pointers.

9. Consider the following pseudocode of insertion in XOR list and write the approximate code snippet of it.

void xor-linked-list insert(struct node **head_ref, int value)
{
    node *new_node  = new (struct node);
    new_node->value = value;
    new_node->nodepointerxored = xor (*head_ref, NULL);
    if (*head_pointer == NULL)
    {
        printf("invalid");
    }
    else
    {
        let b,c,d are nodes and a is to be inserted at beginning,
        a address field must contain NULL xor b and b 
        address filed must be a xor c.
    }
    *head_pointer = new_node;
}

a)

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref)->npx = XOR (new_node, next);

b)

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref) = XOR (new_node, next);

c)

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref)->npx->npx = XOR (new_node, next);

d)

node* next = XOR ((*head_ref),  NULL);
  (*head_ref)->npx = XOR (new_node, next);

View Answer

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref)->npx = XOR (new_node, next);

10. In the above question would using arrays and swaping of elements in place of xor linked list would have been more efficient?
a) no not all
b) yes arrays would have been better than xor lists
c) both would be same in efficiency
d) can’t say
Answer: b
Clarification: The locality of a normal array is faster in memory and moreover one has to traverse n-nodes to reach the target to reverse in case of xor linked list.

Data Structure Multiple Choice Questions on “Weight Balanced Tree”.

1. What is a weight balanced tree?
a) A binary tree that stores the sizes of subtrees in nodes
b) A binary tree with an additional attribute of weight
c) A height balanced binary tree
d) A normal binary tree
Answer: a
Clarification: Unlike AVL and redblack trees which uses height and color as book keeping information, weight balanced trees use the size of subtrees.

2. What are the applications of weight balanced tree?
a) dynamic sets, dictionaries, sequences, maps
b) heaps
c) sorting
d) storing strings
Answer: a
Clarification: They are a type of self balancing trees which are mostly used in storing key-value pairs, which is mostly used in functional programming languages. they are very useful to maintain big set of ordered objects.

3. A node of the weight balanced tree has
a) key, left and right pointers, size
b) key, value
c) key, size
d) key
Answer: a
Clarification: As a weight balanced tree stores height of the subtrees, we need to use size as an additional attribute to every node. also value(for mappings) may be an optional attribute.

4. The size value of various nodes in a weight balanced tree are
leaf – zero
internal node – size of it’s two children
is this true?
a) true
b) false
Answer: a
Clarification: Size of a node k is size[k] = size[k.left] + 1 + size[k.right] and based on this the weight will be given as weight[k] = size[k] + 1.

5. What is the condition for a tree to be weight balanced. where a is factor and n is a node?
a) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].
b) weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n].
c) weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n].
d) weight[n] is a non zero
Answer: a
Clarification: The tree is said to be a-balanced if the condition is satisfied. and ‘a’ value will be determined during tree formation. large value of ‘a’ is more effective.

6. What are the operations that can be performed on weight balanced tree?
a) all basic operations and set intersection, set union and subset test
b) all basic operations
c) set intersection, set union and subset test
d) only insertion and deletion
Answer: a
Clarification: The speciality of a weight balanced tree is a part from basic operations we can perform collective operations like set intersection, which helps in rapid prototyping in functional programming languages.

7. Consider a weight balanced tree such that, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on k nodes can be described as
a) log2 n
b) log4/3 n
c) log3 n
d) log3/2 n
Answer: d
Clarification: Total number of nodes can be described by the recurrence T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1 T(1) = 1. height of the tree will be H(n) = H(2/3(n-1)) + 1, H(1). drawing a recurrence tree and the cost at each level is 1 and the height will be log(3/2)n.

8. Why the below pseudo code where x is a value, wt is weight factor and t is root node can’t insert?

WeightBalanceTreeNode insert(int x, int wt, WeightBalanceTreeNode k) :
 
           if (k == null)
                k = new WeightBalanceTreeNode(x, wt, null, null)
           else if (x < t.element) :
 
                k.left = insert (x, wt, k.left)
                if (k.left.weight < k.weight)
                    k = rotateWithRightChild (k)
 
            else if (x > t.element) :
 
                k.right = insert (x, wt, k.right)
                if (k.right.weight < k.weight)
                    k = rotateWithLeftChild (k)

a) when x>t. element Rotate-with-left-child should take place and vice versa
b) the logic is incorrect
c) the condition for rotating children is wrong
d) insertion cannot be performed in weight balanced trees
Answer: a
Clarification: The rotations of children must be interchanged in the code.

9. What does the below definations convey?
i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.
a) weight balanced and height balanced tree definations
b) height balanced and weight balanced tree definations
c) definations of weight balanced tree
d) definations of height balanced tree
Answer: a
Clarification: They are the definations of weight and height balanceness. height balanced trees wont convey weight balanceness but opposite can be true.

10. Elements in a tree can be indexed by its position under the ordering of the keys and the ordinal position of an element can be determined, both with good efficiency.
a) true
b) false
Answer: a
Clarification: In a weight balanced tree we can even store the key information so as to use as a key value pair.

Data Structures & Algorithms Multiple Choice Questions on “Disjoint-Set Data Structure”.

1. How many properties will an equivalent relationship satisfy?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: An equivalent relationship will satisfy three properties – reflexive, symmetric and transitive.

2. A relation R on a set S, defined as x R y if and only if y R x. This is an example of?
a) reflexive relation
b) symmetric relation
c) transitive relation
d) invalid relation

Answer: b
Clarification: A symmetric property in an equivalence relation is defined as x R y if and only y R x.

3. Electrical connectivity is an example of equivalence relation.
a) true
b) false

Answer: a
Clarification: Electrical connectivity is reflexive, symmetric and also transitive. Hence, electrical connectivity is an equivalence relation.

4. What is the worst case efficiency for a path compression algorithm?
a) O(N)
b) O(log N)
c) O(N log N)
d) O(M log N)

Answer: d
Clarification: The worst case efficiency for a path compression algorithm is mathematically found to be O(M log N).

5. Path Compression algorithm performs in which of the following operations?
a) Create operation
b) Insert operation
c) Find operation
d) Delete operation

Answer: c
Clarification: Path compression algorithm is performed during find operation and is independent of the strategy used to perform unions.

6. What is the definition for Ackermann’s function?
a) A(1,i) = i+1 for i>=1
b) A(i,j) = i+j for i>=j
c) A(i,j) = i+j for i = j
d) A(1,i) = i+1 for i<1

Answer: a
Clarification: The Ackermann’s function is defined as A(1,i) = i+1 for i>=1. This form in text grows faster and the inverse is slower.

7. ___________ is one of the earliest forms of a self-adjustment strategy used in splay trees, skew heaps.
a) Union by rank
b) Equivalence function
c) Dynamic function
d) Path compression

Answer: d
Clarification: Path compression is one of the earliest forms of self-adjustment used in extremely important strategies using theoretical explanations.

8. What is the depth of any tree if the union operation is performed by height?
a) O(N)
b) O(log N)
c) O(N log N)
d) O(M log N)

Answer: b
Clarification: If the Unions are performed by height, the depth of any tree is calculated to be O(log N).

9. When executing a sequence of Unions, a node of rank r must have at least 2^r descendants.
a) true
b) false

Answer: a
Clarification: By the induction hypothesis, each tree has at least 2^{r – 1} descendants, giving a total of 2^r and establishing the lemma.

10. What is the value for the number of nodes of rank r?
a) N
b) N/2
c) N/2^r
d) N^r

Answer: c
Clarification: Each node of a rank r is the root of a subtree of at least 2^r. Therefore, there are at most N/2^r disjoint subtrees.

11. What is the worst-case running time of unions done by size and path compression?
a) O(N)
b) O(logN)
c) O(N logN)
d) O(M logN)

Answer: d
Clarification: The worst case running time of a union operation done by size and path compression is mathematically found to be O(M logN).

12. In the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from?
a) leaf to root
b) root to node
c) root to leaf
d) left subtree to right subtree

Answer: a
Clarification: One of the lemmas state that, in the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from leaf to root.

13. How many strategies are followed to solve a dynamic equivalence problem?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: There are two strategies involved to solve a dynamic equivalence problem- executing find instruction in worst-case time and executing union instruction in worst-case time.

14. What is the total time spent for N-1 merges in a dynamic equivalence problem?
a) O(N)
b) O(log N)
c) O(N log N)
d) O(M log N)

Answer: c
Clarification: The total time spent for N-1 merges in a dynamic equivalence problem is mathematically found to be O(N log N).

15. What is the condition for an equivalence relation if two cities are related within a country?
a) the two cities should have a one-way connection
b) the two cities should have a two-way connection
c) the two cities should be in different countries
d) no equivalence relation will exist between two cities

Answer: b
Clarification: If the two towns are in the same country and have a two-way road connection between them, it satisfies equivalence property.