Category: Data Structure Objective Questions

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.

Data Structure Multiple Choice Questions on “Incidence Matrix and Graph Structured Stack”.

1. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?
a) True
b) False
Answer: b
Clarification: For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.

2. The column sum in an incidence matrix for a simple graph is __________
a) depends on number of edges
b) always greater than 2
c) equal to 2
d) equal to the number of edges
Answer: c
Clarification: For every edge only the vertices with which it is connected would have the value 1 in the matrix, as an edge connects two vertices sum will always be 2.

3. What are the dimensions of an incidence matrix?
a) Number of edges*number of edges
b) Number of edges*number of vertices
c) Number of vertices*number of vertices
d) Number of edges * (¹⁄₂ * number of vertices)
Answer: b
Clarification: Columns may represent edges and vertices may be represented by the rows.

4. The column sum in an incidence matrix for a directed graph having no self loop is __________
a) 0
b) 1
c) 2
d) equal to the number of edges
Answer: a
Clarification: Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.

5. Time complexity to check if an edge exists between two vertices would be ___________
a) O(V*V)
b) O(V+E)
c) O(1)
d) O(E)
Answer: d
Clarification: We have to check for all edges, in the worst case the vertices will have no common edge.

6. The graphs G1 and G2 with their incidences matrices given are Isomorphic.

		e1 	e2 	e3 	e4 	e5 	e6
	v1	1	0	0	0	0	0
	v2	1	1	0	0	0	1
	v3	0	1	1	0	1	0
	v4	0	0	1	1	0	0
	v5	0	0	0	1	1	1
 
 
 
		e1 	e2 	e3 	e4 	e5 	e6
	v1	0	0	1	0	0	0
	v2	1	0	1	0	1	0
	v3	1	1	0	1	0	0
	v4	0	1	0	0	0	1
	v5	0	0	0	1	1	1

a) True
b) False
Answer: a
Clarification: Two graphs are isomorphic if their Incidence Matrices differ only by permutation of columns and rows.

7. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?
a) n-1
b) values greater than n are possible
c) values less than n-1 are possible
d) insufficient Information is given
Answer: a
Clarification: Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.

8. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.

a) 1
b) 2
c) 3
d) 4
Answer: c
Clarification: Path ADE, BDE and BCE are possible.

9. A Graph Structured Stack is a _____________
a) Undirected Graph
b) Directed Graph
c) Directed Acyclic Graph
d) Regular Graph
Answer: c
Clarification: A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.

10. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?
a) Source – 1, 8 Sink – 7,4
b) Source – 1 Sink – 8,4
c) Source – 1, 8 Sink – 4
d) Source – 4, Sink – 1,8
Answer: c
Clarification: Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.

11. Graph Structured Stack finds its application in _____________
a) Bogo Sort
b) Tomita’s Algorithm
c) Todd–Coxeter algorithm
d) Heap Sort
Answer: b
Clarification: Tomita’s is a parsing algorithm which uses Graph Structured Stack in its implementation.

12. If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M.
a) True
b) False
Answer: b
Clarification: The answer would depend on the intermediate vertices also.

Data Structure Multiple Choice Questions on “Stack using Linked List”.

1. What is the best case time complexity of deleting a node in a Singly Linked list?
a) O (n)
b) O (n²)
c) O (nlogn)
d) O (1)
Answer: d
Clarification: Deletion of the head node in the linked list is taken as the best case. The successor of the head node is changed to head and deletes the predecessor of the newly assigned head node. This process completes in O(1) time.

2. Which of the following statements are not correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)?
a) Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
b) SLL uses lesser memory per node than DLL
c) DLL has more searching power than SLL
d) Number of node fields in SLL is more than DLL
Answer: d
Clarification: To insert and delete at known positions requires complete traversal of the list in worst case in SLL, SLL consists of an item and a node field, while DLL has an item and two node fields, hence SLL occupies lesser memory, DLL can be traversed both ways(left and right), while SLL can traverse in only one direction, hence more searching power of DLL. Node fields in SLL is 2 (data and address of next node) whereas in DLL is 3(data, address to next node, address to previous node).

3. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor.
Select from the options the appropriate pop() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.

class Node
{
	protected Node next;
	protected Object ele;
	Node()
	{
		this(null,null);
	}
	Node(Object e,Node n)
	{
		ele=e;
		next=n;
	}
	public void setNext(Node n)
	{
		next=n;
	}
	public void setEle(Object e)
	{
		ele=e;
	}
	public Node getNext()
	{
		return next;
	}
	public Object getEle()
	{
		return ele;
	}
}
 
class Stack
{
	Node first;
	int size=0;
	Stack()
	{
		first=null;
	}
}

a)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		Object o = first.getEle();
		first = first.getNext();
		size--;
		return o;
	}
}

b)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		Object o = first.getEle();
		first = first.getNext().getNext();
		size--;
		return o;
	}
}

c)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		first = first.getNext();
		Object o = first.getEle();
		size--;
		return o;
	}
}

d)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		first = first.getNext().getNext();
		Object o = first.getEle();
		size--;
		return o;
	}
}

View Answer

Answer: a
Clarification: pop() should return the Object pointed to by the node ‘first’. The sequence of operations is, first, get the element stored at node ‘first’ using getEle(), and second, make the node point to the next node using getNext().

4. What does the following function do?

public Object some_func()throws emptyStackException
{
	if(isEmpty())
		throw new emptyStackException("underflow");
	return first.getEle();
}

a) pop
b) delete the top-of-the-stack element
c) retrieve the top-of-the-stack element
d) push operation
Answer: c
Clarification: This code is only retrieving the top element, note that it is not equivalent to pop operation as you are not setting the ‘next’ pointer point to the next node in sequence.

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

public void display() 
{
	if(size == 0)
		System.out.println("underflow");
	else
	{
		Node current = first;
		while(current != null)
		{
			System.out.println(current.getEle());
			current = current.getNext();
		}
	}
}

a) reverse the list
b) display the list
c) display the list excluding top-of-the-stack-element
d) reverse the list excluding top-of-the-stack-element
Answer: b
Clarification: An alias of the node ‘first’ is created which traverses through the list and displays the elements.

6. What does ‘stack overflow’ 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: b
Clarification: Adding items to a full stack is termed as stack underflow.

7. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor. Select from the options the appropriate push() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.

class Node
{
	protected Node next;
	protected Object ele;
	Node()
	{
		this(null,null);
	}
	Node(Object e,Node n)
	{
		ele=e;
		next=n;
	}
	public void setNext(Node n)
	{
		next=n;
	}
	public void setEle(Object e)
	{
		ele=e;
	}
	public Node getNext()
	{
		return next;
	}
	public Object getEle()
	{
		return ele;
	}
}
 
class Stack
{
	Node first;
	int size=0;
	Stack()
	{
		first=null;
	}
}

a)

public void push(Object item)
{
	Node temp = new Node(item,first);
	first = temp;
	size++;
}

b)

public void push(Object item)
{
	Node temp = new Node(item,first);
	first = temp.getNext();
	size++;
}

c)

public void push(Object item)
{
	Node temp = new Node();
	first = temp.getNext();
	first.setItem(item);
	size++;
}

d)

public void push(Object item)
{
	Node temp = new Node();
	first = temp.getNext.getNext();
	first.setItem(item);
	size++;
}

View Answer

Answer: a
Clarification: To push an element into the stack, first create a new node with the next pointer point to the current top-of-the-stack node, then make this node as top-of-the-stack by assigning it to ‘first’.

8. Consider these functions:
push() : push an element into the stack
pop() : pop the top-of-the-stack element
top() : returns the item stored in top-of-the-stack-node
What will be the output after performing these sequence of operations

push(20);
push(4);
top();
pop();
pop();
pop();
push(5);
top();

a) 20
b) 4
c) stack underflow
d) 5
Answer: d
Clarification: 20 and 4 which were pushed are popped by the two pop() statements, the recent push() is 5, hence top() returns 5.

9. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack
Answer: d
Clarification: For every opening brace, push it into the stack, and for every closing brace, pop it off the stack. Do not take action for any other character. In the end, if the stack is empty, then the input has balanced parentheses.

10. Minimum number of queues to implement stack is ___________
a) 3
b) 4
c) 1
d) 2
Answer: c
Clarification: Use one queue and one counter to count the number of elements in the queue.

Data Structures & Algorithms Multiple Choice Questions on “Reverse a Word using Stack”.

1. Reversing a word using stack can be used to find if the given word is a palindrome or not.
a) True
b) False
Answer: a
Clarification: This application of stack can also be used to find if the given word is a palindrome because, if the reversed is same as that of the original word, the given word is a palindrome.

2. Which is the most appropriate data structure for reversing a word?
a) queue
b) stack
c) tree
d) graph
Answer: b
Clarification: Stack is the most appropriate data structure for reversing a word because stack follows LIFO principle.

3. Operations required for reversing a word or a string using stack are push() and pop().
a) True
b) False
Answer: a
Clarification: Push operation inserts a character into the stack and pop operation pops the top of the stack.

4. What is the time complexity of reversing a word using stack algorithm?
a) O (N log N)
b) O (N²)
c) O (N)
d) O (M log N)
Answer: c
Clarification: The time complexity of reversing a stack is mathematically found to be O (N) where N is the input.

5. What will be the word obtained if the word “abbcabb” is reversed using a stack?
a) bbabbca
b) abbcabb
c) bbacbba
d) bbacabb
Answer: c
Clarification: The string “abbcabb” is pushed on to the stack. If the characters are popped one by one, the word obtained will be bbacbba.

6. How many stacks are required for reversing a word algorithm?
a) one
b) two
c) three
d) four
Answer: a
Clarification: Only 1 stack is required for reversing a word using stack. In that stack, push and pop operations are carried out.

7. What will be result if the given stack is popped?

a) pat
b) tap
c) atp
d) apt
Answer: b
Clarification: The word ‘pat’ is pushed on to the stack. When the characters of the stack are popped one by one, the word ‘tap’ is obtained.

8. What will be output if the following sequence of operations are executed?

Push(a,s);
Push(b,s);
Pop(b);
Push(c,s);

a) abc
b) b
c) ac
d) acb
Answer: b
Clarification: The element ‘b’ is popped out of the stack. Hence the output of the following sequence of operations will be ‘b’.

9. What are the set of functions that are to be executed to get the following output?
cat
a) push(c, s); push(a, s); push(t, s);
pop(s); pop(s); pop(s);
b) push(c,s); pop(s); push(a,s); pop(s);push(t,s);pop(s);
c) pop(c ); pop(a); pop(t);
d) push(c,s); push(a,s); pop(t);
Answer: b
Clarification: During push operation, the characters ‘c’, ’a’, ’t’ are inserted into the stack and popped immediately after push.

10. How will your stack look like if the word ‘java’ is pushed?
a)
b)
c)
d)
Answer: a
Clarification: When a character is pushed, it stays on the top of the stack. While popping, the word occurs in reverse order since stack follows LIFO principle.

11. Find the error (if any) in the following code snippet for pop operation.

void pop() //removing an element from a stack
{
     printf(“%s”, stack[top++]);
}

a) run time error
b) compile time error
c) pop operation is performed, but top moved in wrong direction
d) pop operation is performed properly
Answer: c
Clarification: The statement printf(“%s”, stack[top++]) does a pop, but top gets incremented which is not correct. The statement stack[top++] should be replaced with stack[top–] in order to pop an operand and maintain stack properly.

12. What will be the output of the following program?

main()  
{  
   char str[]="san foundry";  
   int len = strlen(str);  
   int i;  
 
   for(i=0;i<len;i++)  
        push(str[i]);  // pushes an element into stack
 
   for(i=0;i<len;i++)  
      pop();  //pops an element from the stack
}

a)
b) san foundry
c) yrdnuof nas
d) foundry nas
Answer: c
Clarification: First, the string ‘san foundry’ is pushed one by one into the stack.
When it is popped, the output will be as ‘yrdnuof nas’.