Category: Data Structure Objective Questions

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.

Data Structure Multiple Choice Questions on “Multigraph and Hypergraph”.

1. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}
ii) {{0,1}{1,0}}
iii) {{0,0,1}{0,1,0}{1,0,0}}
a) only i)
b) ii) and iii)
c) i) and iii)
d) i) ii) and iii)
Answer: c
Clarification: In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.

2. All undirected Multigraphs contain eulerian cycles.
a) True
b) False
Answer: a
Clarification: Only graphs with every vertex having even degree have eulerian circuits or cycles.

3. Determine the number of vertices for the given Graph or Multigraph?
G is a 4-regular Graph having 12 edges.
a) 3
b) 6
c) 4
d) Information given is insufficient
Answer: b
Clarification: Sum of degrees of all the edges equal to 2 times the number of edges. 2*12=4*n, n=>6.

4. Which of the following statement is true.
a) There exists a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
b) There exists a MultiGraph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
c) There exists a MultiGraph as well as a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
d) None of the mentioned
Answer: b
Clarification: If a vertex has a degree 9 that means it is connected to all the other vertices, in case of Multigraphs for an isolate vertex, and a multiple edge may compensate.

5. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}
ii) {{0,1}{1,0}}
iii) {{0,0,1}{0,1,0}{1,0,0}}
a) only i)
b) ii) and iii)
c) i) and iii)
d) i) ii) and iii)
Answer: c
Clarification: In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.

6. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?
a) 3, Infinite, 4
b) 4, 3, Infinite
c) 4, Infinite, infinite
d) 4, Infinite, Infinite
Answer: d
Clarification: MultiGraphs and PseudoGraphs may have infinite number of edges, while 4 possible simple graphs exist.

7. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?
a) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}
b) V = {v1, v2} E = {e1} = {{v1, v2}}
c) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}
d) All of the mentioned
Answer: d
Clarification: In a uniform Graph all the hyper-edges have the same cardinality.

8. What would be the Incidence Matrix of the given HyperGraph?
V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}
a) {{1,0,1,0},
{1,1,0,1},
{0,0,1,1}}
b) {{1,1,0,0},
{0,1,0,0},
{1,1,1,0}}
c) {{0,1,0,1},
{0,0,1,0},
{1,1,0,0}}
d) None of the Mentioned
Answer: a
Clarification: The columns represent edges while rows represent vertices.

9. What is the degree sequence of the given HyperGraph, in non-increasing order.
V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}
a) 3,2,1,1,1,1
b) 3,2,2,2,1,1
c) 3,2,2,2,2,1
d) 3,2,2,1,1,1
Answer: b
Clarification: The degree of v1,v2,v3,v4,v5,v6 is 3,2,1,2,2,1 respectively.

10. MultiGraphs having self-loops are called PseudoGraphs?
a) True
b) False
Answer: a
Clarification: All PsuedoGraphs are MultiGraphs, but all MultiGraphs are not PseudoGraphs as all PseudoGraphs have self loop, but all MultiGraphs do not have self loops.

Data Structure Interview Questions and Answers on “Stack Operations – 2”.

1. The postfix form of the expression (A+ B)*(C*D- E)*F / G is?
a) AB+ CD*E – FG /**
b) AB + CD* E – F **G /
c) AB + CD* E – *F *G /
d) AB + CDE * – * F *G /
Answer: c
Clarification: (((A+ B)*(C*D- E)*F) / G) is converted to postfix expression as
(AB+(*(C*D- E)*F )/ G)
(AB+CD*E-*F) / G
(AB+CD*E-*F * G/). Thus Postfix expression is AB+CD*E-*F*G/

2. The data structure required to check whether an expression contains a balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
Answer: a
Clarification: The stack is a simple data structure in which elements are added and removed based on the LIFO principle. Open parenthesis is pushed into the stack and a closed parenthesis pops out elements till the top element of the stack is its corresponding open parenthesis. If the stack is empty, parenthesis is balanced otherwise it is unbalanced.

3. What data structure would you mostly likely see in non recursive implementation of a recursive algorithm?
a) Linked List
b) Stack
c) Queue
d) Tree
Answer: b
Clarification: In recursive algorithms, the order in which the recursive process comes back is the reverse of the order in which it goes forward during execution. The compiler uses the stack data structure to implement recursion. In the forwarding phase, the values of local variables, parameters and the return address are pushed into the stack at each recursion level. In the backing-out phase, the stacked address is popped and used to execute the rest of the code.

4. The process of accessing data stored in a serial access memory is similar to manipulating data on a ________
a) Heap
b) Binary Tree
c) Array
d) Stack
Answer: d
Clarification: In serial access memory data records are stored one after the other in which they are created and are accessed sequentially. In stack data structure, elements are accessed sequentially. Stack data structure resembles the serial access memory.

5. The postfix form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
Answer: b
Clarification: Infix expression is (A*B)+(C/D)
AB*+(C/D)
AB*CD/+. Thus postfix expression is AB*CD/+.

6. Which data structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack
Answer: d
Clarification: The Stack data structure is used to convert infix expression to postfix expression. The purpose of stack is to reverse the order of the operators in the expression. It also serves as a storage structure, as no operator can be printed until both of its operands have appeared.

7. The prefix form of A-B/ (C * D ^ E) is?
a) -/*^ACBDE
b) -ABCD*^DE
c) -A/B*C^DE
d) -A/BC*^DE
Answer: c
Clarification: Infix Expression is (A-B)/(C*D^E)
(-A/B)(C*D^E)
-A/B*C^DE. Thus prefix expression is -A/B*C^DE.

8. What is the result of the following operation?
Top (Push (S, X))
a) X
b) X+S
c) S
d) XS
Answer: a
Clarification: The function Push(S,X) pushes the value X in the stack S. Top() function gives the value which entered last. X entered into stack S at last.

9. The prefix form of an infix expression (p + q) – (r * t) is?
a) + pq – *rt
b) – +pqr * t
c) – +pq * rt
d) – + * pqrt
Answer: c
Clarification: Given Infix Expression is ((p+q)-(r*t))
(+pq)-(r*t)
(-+pq)(r*t)
-+pq*rt. Thus prefix expression is -+pq*rt.

10. Which data structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List
Answer: b
Clarification: Stacks are used for the implementation of Recursion.

Data Structure for Interviews,