Capgemini Data Structures & Alogrithm MCQ

Questions 1: Consider an array A = { 2, 4, 61, 17, 8, 10, 13, 34, 67, 98 } and key element equals 88. How many comparison will it take to find the key element in the array using linear search algorithmn ?

  • Options
  • a : 11
  • b : 8
  • c : 9
  • d : 10

    • Answer: d

    Questions 2: Which of the following is the correct post-order traversal of the given rooted tree ?

  • Options
  • a : F-D-G-B-H-E-I-C-A
  • b : F-G-D-B-H-I-E-C-A
  • c : F-G-D-B-A-H-I-E-C
  • d : F-G-D-H-I-E-B-C-A

    • Answer: b

    Questions 3: Convert the following infix expression into prefix expression.

    ( A + B ) * ( C + D )

  • Options
  • a : A B + C D + *
  • b : + + A * B C D
  • c : * + A B + C D
  • d : A B C * + D +

    • Answer: c

    Questions 4: Evaluate the postfix expression 6 5 2 3 + 8 * + 3 + *

  • Options
  • a : 312
  • b : 288
  • c : 302
  • d : 308

    • Answer: b

    Questions 5: In an empty BST, insert the following elements in a similar sequence. Which element will be at the lowest level?

    105, 95, 122, 99, 97, 120

  • Options
  • a : 95
  • b : 97
  • c : 99
  • d : 120

    • Answer: b

    Questions 6: Consider a circular queue, which can hold maximum ( MAX ) of six elements. Initially, the queue is empty as shown in the image. Follow the steps provided and find out the correct option.

    1. Insert 11 to the circular queue
    2. Insert new elements 22, 33, 44, and 55 into the circular queue
    3. Delete an element
    4. Delete another element

  • Options
  • a :

  • b :

    • Answer: a

    c

    Questions 7: What does the following piece of code do?

    public void func(Tree root)
    {
    func(root.left());
    func(root.right());
    System.out.println(root.data());
    }

  • Options
  • a : Preorder traversal
  • b : Inorder traversal
  • c : Postorder traversal
  • d : Level order traversal

    • Answer: b

    Questions 8: A type of linked list, say X consists of nodes thatis divided into three parts:

  • The first part contains the address of the previous node.
  • The second part contains the data element.
  • The third part contains the address of the next node.
    • based on the above information, identify X.

  • Options
  • a : Circular linked list
  • b : Singly linked list
  • c : Doubly linked list
  • d : None

    • Answer: c

    Questions 9: Why open addressing provides better cache performance than chaining?

    1. In open addressing, everything is stored in the same table
    2.In chaining keys are stored using a linked list

  • Options
  • a : Only 1 is true
  • b : Only 2 is true
  • c : Both 1 and 2 are true
  • d : Both 1 and 2 are false

    • Answer: c

    Questions 10: Find out the correct inorder traversel sequence of a BST?

    1) 15, 19, 22, 26, 29, 35
    2) 15, 18, 20, 22, 28, 26, 32
    3) 14, 17, 19, 21, 26, 31, 33

  • Options
  • a : Only 1
  • b : Only 1 and 3
  • c : Only 2
  • d : Only 1 and 2

    • Answer: b