TISL Placement Paper -: DATA STRUCTURES Questions And Answers

TISL Previous Years Solved Sample Placement Papers

1. What would be the Prefix notation for the given equation? A^B^C^D
   (a) ^^^ABCD
   (b) ^A^B^CD
   (c) ABCD^^^
   (d) AB^C^D
   Answer: (a)
   Explanation: Reverse the equation or scan from right to left. The exponentiation operator has right-to-left associativity, so all operators are pushed onto the stack, resulting in ^^^ABCD.

2. If the tree is not a complete binary tree, then what changes can be made for easy access of children of a node in the array?

   A) Every node stores data saying which of its children exist in the array (Ans)

   B) No need of any changes, continue with 2w and 2w+1 if the node is at i

   C) Keep a separate table telling children of a node

   D) Use another array parallel to the array with the tree

3. Why is the heap implemented using array representations rather than tree (linked list) representations though both have the same complexities?

   A) Arrays can store trees that are complete and heaps are not complete

   B) List representation takes more memory, hence memory efficiency is less. Go with arrays because arrays have better caching (Ans)

   C) Lists have better caching

   D) In lists, insertion and deletion are difficult

4. Can a tree stored in an array using either one of inorder, postorder, or preorder traversals be reformed?

   A) Yes, just traverse through the array and form the tree

   B) No, we need one more traversal to form a tree (Ans)

   C) No, in case of sparse trees

   D) Yes, by using both inorder and array elements

5. What data structure is used when converting an infix notation to prefix notation?
   (a) Stack
   (b) Queue
   (c) B-Trees
   (d) Linked-list
   Answer: (a)
   Explanation: To convert infix to prefix, reverse the equation and use the infix-to-postfix algorithm. This process utilizes stacks for operator precedence and association.

6. What would be the Prefix notation for the given equation? a+b-c/d&e|f
   (a) |&-+ab/cdef
   (b) &|-+ab/cdef
   (c) |&-ab+/cdef
   (d) |&-+/abcdef
   Answer: (a)
   Explanation: Reverse the equation or scan from right to left. The precedence order is | & + /. Operators are pushed and popped based on precedence, resulting in |&-+ab/cdef.

7. What would be the Prefix notation for the given equation? (a+(b/c)*(d^e)-f)
   (a) -+a*/^bcdef
   (b) -+a*/bc^def
   (c) -+a*b/c^def
   (d) -a+*/bc^def
   Answer: (b)
   Explanation: Reverse the equation or scan from right to left. Solve equations within brackets first. The precedence order is +*/^, resulting in -+a*/bc^def.

8. What would be the Prefix notation and Postfix notation for the given equation? A+B+C
   (a) ++ABC and AB+C+
   (b) AB+C+ and ++ABC
   (c) ABC++ and AB+C+
   (d) ABC+ and ABC+
   Answer: (a)
   Explanation: Prefix notation places operators before their operands, resulting in ++ABC. Postfix notation places operators after their operands, resulting in AB+C+.

9. Which of the following is an infix expression?

   a) (a+b)*(c+d)

   b) ab+c*

   c) +ab

   d) abc+*

   Answer: a

   Explanation: (a+b)*(c+d) is an infix expression. +ab is a prefix expression and ab+c* is a postfix expression.

10. What is the time complexity of an infix to postfix conversion algorithm?

    a) O(N log N)

    b) O(N)

    c) O(N²)

    d) O(M log N)

    Answer: b

    Explanation: The time complexity of an infix to postfix expression conversion algorithm is mathematically found to be O(N).

11. What is the postfix expression for the corresponding infix expression?

    a+b*c+(d*e)

    a) abc*+de*+

    b) abc+*de*+

    c) a+bc*de+*

    d) abc*+(de)*+

    Answer: a

    Explanation: Using the infix to postfix expression conversion algorithm, the corresponding postfix expression is found to be abc*+de*+.

12. Parentheses are simply ignored in the conversion of infix to postfix expression.

    a) True

    b) False

    Answer: b

    Explanation: When a parenthesis is encountered, it is placed on the operator stack. When the corresponding parenthesis is encountered, the stack is popped until the other parenthesis is reached and they are discarded.

13. It is easier for a computer to process a postfix expression than an infix expression.

    a) True

    b) False

    Answer: a

    Explanation: Computers can easily process a postfix expression because a postfix expression keeps track of precedence of operators.

14. What is the postfix expression for the infix expression?

    a-b-c

    a) -ab-c

    b) ab – c –

    c) – -abc

    d) -ab-c

    Answer: b

    Explanation: The corresponding postfix expression for the given infix expression is found to be ab-c- and not abc- -.

15. Which of the following is false?

    A) A B+ -tree grows downwards

    B) A B+ -tree is balanced

    C) In a B+ -tree, the sibling pointers allow sequential searching

    D) B+ -tree is shallower than B-tree

    (Ans) A) A B+ -tree grows downwards.

16. When a node is split during insertion, the middle key is promoted to the parent as well as retained in the right half-node. When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.

    A) Statement 1 is true but statement 2 is false (Ans)

    B) Statement 2 is true but statement 1 is false

    C) Both the statements are true

    D) Both the statements are false

    Explanation: During the split, the middle key is retained in the right half node and also promoted to the parent node. When a key is deleted from the leaf, it is retained in non-leaves because it can still be a valid separator between keys in nodes below.

17. Efficiency of finding the next record in a B+ tree is ____.

    A) O(n)

    B) O(log n)

    C) O(n log n)

    D) O(1) (Ans)

    Explanation: In a B+ -tree, finding the next record (successor) involves accessing an additional leaf at most. So, the efficiency of finding the next record is O(1).

18. What is the maximum number of keys that a B+ -tree of order 3 and of height 3 can have?

    A) 3

    B) 80

    C) 27

    D) 26 (Ans)

    Explanation: A B+ tree of order n and height h can have at most n^h – 1 keys. Therefore, the maximum number of keys = 3³ - 1 = 27 - 1 = 26.

19. Which of the following is false?

    A) Compared to B-tree, B+ -tree has larger fanout

    B) Deletion in B-tree is more complicated than in B+ -tree

    C) B+ -tree has greater depth than the corresponding B-tree

    D) Both B-tree and B+ -tree have the same search and insertion efficiencies

    (Ans) C) B+ -tree has greater depth than the corresponding B-tree.

    Explanation: A B+ -tree has a larger fanout and therefore has a depth smaller than that of the corresponding B-tree.