HTML/JavaScript

Data Structures Interview Questions with Answers

 

1.             The term "push" and "pop" is related to the___.

(a)      stacks           (b)  lists                    (c)  array                     (d) all of above

Answer: a

2.     A data structure where elements can be added or removed at either end but not in the middle is called           .

(a)      linked lists   (b)  dequeue             (c)  queues                  (d) Stacks

Answer: b

3.     The Infix equivalent of the prefix  * + ab −cd is         .

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

Answer: c

4.     The postfix equivalent of the prefix  * + ab −cdis         .

(a)      ab + − cd*    (b)   abcd +−*           (c)   ab + cd*−            (d) ab + cd− *

Answer: d

5.     The postfix equivalent of the infix expression a+b+c+dis          .

(a)   abcd+++       (b)  ab+c+d+            (c)  ab+cd++               (d)(a−b)*(c+d)

Answer: b

6.     The prefix equivalent of the infix expression a+b+c+dis         .

(a)   +ab+c+d       (b)  +++abcd            (c)  ++ab+cd+             (d)abcd++++

Answer: b

7.     The postfix equivalent of the infix expression a+b/c*d−e/fis        .

(a)      ab+cd*/ef−/(b)  abcd*+/ef−/         (c)  ab+cd*/ef/−         (d)abc/d*+ef/−

Answer: d

8.     The prefix equivalent of the infix expression a+b/c*d−e/fis        .

(a)   +abc−*/ef     (b)  +/*−/abcdef       (c)  −+a*/bcd/ef         (d)+a*/bcd−/ef

Answer: c

9.     The postfix equivalent of the infix expression a+b/c−d*e−fis        .

(a)      abc/+de*−f−(b)  abcd*+/ef−/        (c)  ab+cd*/ef/−         (d)abc/d*+ef/−

Answer: a

10.     The prefix equivalent of the infix expression a+b/c−d*e−fis        .

(a)   +abc−*/ef     (b)  −−+a/bc*def      (c)  −+a*/bcd/ef         (d)+a*/bcd−/ef

Answer: b

11.     The infix equivalent of the postfix ab+cd+ef*−/ is       .

(a)   ((a+b)/((c+d))−(e*f))                    (b)   (a+b) −(c+d)/(e*f)

(c)   (a+b)*(c+d)−(e/f)                         (d)  ((a+b)/(c+d))−(e*f)

Answer: a

12.     The infix equivalent of the postfix ab*cd/+e− is         .

(a)   a+b*c/d−e    (b)  a*b+c/d−e          (c)  (a*b)−(c/d)+e      (d)a*b−c/d+e

Answer: b

13.     The prefix equivalent of the postfix ab*cd/+e− is         .

(a)   +−/abc*de    (b)  −+*abc/de          (c)  −+*ab/cde            (d)*ab/+cd−e

Answer: c

14.     Pick the correct prefix form to the given infix expression:{a*[b/(c−d)*f]/g}/[e+h]

(a)      //*a/b*−cdfg+ch                           (b)  abcd−f*/g/*eh+/

(c)   //*a*/b−cdfg+eh                           (d)  //*ab*/−cdfg+eh

Answer: c

15.       Suppose a circular queue of capacity (n – 1) elements is implemented with an array  of n elements. Assume that the insertion and deletion operation are carried out  using REAR and FRONT as array index variables, respectively. Initially, REAR =FRONT

= 0. The conditions to detect queue full and queue empty are

(a)      Full: (REAR+1) mod n == FRONT, empty: REAR ==FRONT

(b)      Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n ==REAR

(c)      Full: REAR == FRONT, empty: (REAR+1) mod n ==FRONT

(d)      Full: (FRONT+1) mod n == REAR, empty: REAR ==FRONT

Answer: a

16.     Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes :(()(())(()))

(a)  4                    (b) 3                          (c) 2                            (d)6

Answer: b

17.     Suppose we have an array implementation of the stack class, with ten items in the stack stored at data [0] through data [9]. The SIZE is 42. Where does the push function place the new entry in the array?

(a)      data[0]          (b)  data[1]               (c)  data[9]                 (d)data[10]

Answer: c

18.     If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

(a)      ABCD          (b)  ABDC                (c)  DCAB                  (d)DCBA

Answer: d

19.     What data structure is used to perform recursion?

(a)      Stack            (b)  Queue                (c)  Linked List          (d)Arrays

Answer: a

20.     For the expression ((A + B) * C – (D – E)/(F + G)), the equivalent Postfix notations

(a)      AB + C * DE − − /FG+                 (b) AB + C * DE − FG +/−

(c)   AB + C * DE − − FG +/                (d) AB + C − DE − * FG +/

Answer: b

21.     Which data structure allows deleting data elements from front and inserting arrear?

(a)      Stacks                                            (b)Queues

(c)   Deques                                          (d) Binary search tree

Answer: b

22.     Identify the data structure which allows deletions at one end of the list but insertion anywhere

(a)      Input restricted dequeue               (b) Output restricted dequeue

(c)   Priority queues                             (d) none of above

Answer: c

23.     One difference between a queue and a stack is           .

(a)      Queue can be implemented using linked lists, but stack cannot

(b)      Stack can be implemented using linked lists, but queues cannot

(c)      Queues use two ends of the structure; stacks use only one

(d)      Stacks use two ends of the structure, queues use only one

Answer: d

24.     Suppose we have a circular array implementation of the queue, with ten items in the queue stored at data[2] through data[11], the current capacity is 12. Where does the insert method place the new entry in the array?

(a)      data[1]          (b)  data[0]               (c)  data[11]               (d)data[12]

Answer: b

25.     If we have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?

(a)      Neither changes                            (b) Only front changes

(c)   Only rear changes                         (d) An exception is caused

Answer: c

26.     If we have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during deletion into the NONEMPTY queue?

(a)      Neither changes                            (b) Only front changes

(c)   Only rear changes.                        (d) An exception is caused

Answer: b

27.     If we have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue?

(a)      Neither changes                            (b) Only front changes

(c)   Only rear changes                         (d) Both front and rear change

Answer: d

28.     Queues and Stacks can be implemented using either arrays or linked lists.

(a)      True              (b)False

Answer: a

29.     In order to input a list of values and output them in order, you could use a queue.

(a)      True              (b)False

Answer: a

30.     In order to input a list of values and output them in the opposite order, you could use a Stack.

(a)      True              (b)False

Answer: a

31.     Which of the following is not the type of queue?

(a)      Ordinary queue                             (b) Single ended queue

(c)   Circular queue                              (d) Priority queue

Answer: a

32.     Which is/are the application(s) of the stack?

(a)      Function calls                               (b) Parentheses check

(c)   Evaluation of arithmetic expressions     (d) All of the above

Answer: d

33.     Stack is also called as           .

(a)      Last in first out                             (b)   First in last out

(c)   Last in last out                              (d)   First in first out

Answer: a

34.     Queue is also called as           .

(a)      Last in first out                             (b)   First in last out

(c)   Last in last out                              (d)   First in first out

Answer: d

35.          is very useful in a situation when data have to stored and then retrieved in reverse order.

(a)      Stack            (b)  Queue                (c)  List                       (d) Link list

Answer: a

36.     Consider the following pseudo-code; 

                 declare a stack of characters

                   while (there are more characters in the word to read)

                        {

                    read a character

                    push the character on the stack

                        }

                    while ( the stack is not empty )

                        {

                    pop a character off the stack

                    write the character to the screen 

                        }

What is written to the screen for the input "carpets"?

(a)      serc               (b)  carpets               (c)  steprac                 (d)ccaarrppeettss

Answer: a

37.     In the linked list implementation of the stack, where does the push method place the new entry on the linked list?

(a)      Before the first node

(b)      At the end of the last node

(c)      After all other entries that is greater than the new entry.

(d)      After all other entries that are smaller than the new entry.

Answer: a

38.     What is the value of the postfix expression 6 3 2 4 + − *                                                                                                                                          (a)  18                                          (b)−18

(c)        15                                             (d) Invalid expression

Answer: b

39.     What is the value of the postfix expression 23456*+−/      (a)   16                                                        (b)−18

(c)  −15                                                 (d) Invalid expression

Answer: c

40.     What is the value of the postfix expression 23456*+−                                                                                                                                                                                                               (a)   16                                         (b) -18 

(c)  15                                          (d) Invalid expression

Answer: d

41.       Here is an infix expression: 4+3*(6*3−12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

(a)  5                    (b) 2                          (c) 3                            (d) 4

Answer: d

42.     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: a

43.                                                                                                                                                                                                   A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a                                              .

(a)      Queue           (b)  Stack                  (c)  Tree                      (d) Linked List

Answer: a

44.     The data structure required to evaluate a postfix expression is        .

(a)      Queue           (b)  Stack                  (c)  Array                    (d)Linked−list

Answer: b

45.     What data structure would you most likely see in a non-recursive implementation of a recursive algorithm?

(a)      Queue           (b)  Stack                  (c)  Array                    (d)Linked−list

Answer: b

46.     The postfix form of A*B+C/Dis         .

(a)      *AB/CD+     (b)  AB*CD/+          (c)  A*BC+/D             (d)ABCD+/*

Answer: b

47.     What is the postfix form of the following prefix *+ab–cd

(a)      ab+cd–*       (b)  abc+*–               (c)  ab+*cd–               (d)ab+*cd–

Answer: a


48.     Which data structure is needed to convert infix notation to postfix notation?

(a)      Branch          (b)  Queue                (c)  Tree                      (d)Stack

Answer: d

49.     What is the result of the following operation done on stack S which is not full? push (&S, 10); x = pop (&S); where S is a structure containing array and top

(a)      x=−1             (b)   x= 10                (c)   x=Null                 (d)Error

Answer: b

50.     The prefix form of an infix expression p + q − r *tis          .

(a)   + pq − *rt     (b)   − +pqr*t            (c)   − +pq*rt              (d)   − + * pqrt

Answer: c

51.     The equivalent prefix expression for the following infix                  expression (A+B)−(C+D*E)/F*G is

(a)      −+AB*/+C*DEFG                               (b) /−+AB*+C*DEFG

(c)   −/+AB*+CDE*FG                               (d) −+AB*/+CDE*FG

Answer: a

52.                         The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +,*is            .

                     (a)600          (b)  350                     (c)  650                       (d) 588

          Answer: b

53.     The meaning of FIFO is            and it stands for        .

(a)      First In FastOut,Stack                   (b) First In First Out,Stack

(c)   First In FirstOut, Queue               (d) First In Fast Out, Queue

Answer: c

54.     The meaning of LIFO is            and it stands for        .

 

(a)   Last In First Out, Queue

(b)

Last In First Out, Stack

(c)   Last In Fast Out, Stack

(d)

Last In First Out, Priority Queue

Answer: b

 

 

55.   Adding data to stack is called                                                             .

 

 

(a)   Push              (b)Pop

(c)

Insert                    (d)Delete

Answer: a

 

 

56.     Items can be removed from both ends of       .

(a)      queue            (b)  stack                  (c)  tree                       (d)dequeue

               Answer: d

57.     In the linked list each node consists of    

(a)      data and link to next node                      (b) data only

(c)   link only                                        (d) address of the first node

Answer: a

58.     In linked lists there are no NULL links in  .

(a)      Circular linked list                       (b) singly linked list

(c)   doubly linked list                          (d) empty linked list

Answer: a

59.     In stack, the command to access the element at top is      .

(a)      x = pop();     (b)  pop(x);               (c)  pop(top);              (d) top=pop();

Answer: a

60.     The result of evaluating prefix expressions *+++abcdc where, a = 1, b = 2, c = 3 and d =4is   .

(a)   10                 (b)  12                       (c)  30                         (d)18

Answer: c

61.     The dummy header in the linked list contains      .

(a)      First record                                   (b) last record

(c)   link to the first record                        (d) link to the last record

Answer: c

62.     If the sequence of operations (push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2),pop),areperformedonastack,thesequenceofpoppedoutvaluesare

       .

(a)   2, 2, 1,1, 2    (b)   2, 2, 1,2, 2         (c)   2, 1, 2,2, 1           (d) 2, 1, 2, 2,2

Answer: a

63.     In evaluating the arithmetic expression 2 * 3 − (4 + 5), using stacks to evaluate its equivalent postfix form, which of the following stack configurations are not possible?

 

 

 

4

6

 

 

5

4

6

 

 

 

9

6

 

 

9

3

2

(a                                (b                                 (c                                   (d)


Answer : d

64.     The postfix expression for the infix expression

A + B* (C + D) / F +D*E is      .

(a)      AB + CD + *F / D+ E*                 (b) ABCD + *F / + DE*+

(c)   A*B + CD /F*DE++                     (d) A + *BCD / F*DE++

Answer: b

65.     Which of the following is essential for converting an infix expression to the postfix form efficiently?

(a)      An operator stack

(b)      An operand stack

(c)      An operator stack and an operand stack

(d)      A parse tree

Answer: a

66.     Identify the data structure which allows deletions at one end of the list but insertion at both ends.

(a)      Input−restricted deque                  (b) Output−restricted deque

(c)   Priority Queues                             (d) None of the above

Answer: b

67.     Identify the data structure which allows deletions at both ends of the list but insertion at one end.

(a)      Input−restricted deque                  (b) Output−restricted deque

(c)   Priority queues                             (d) None of the above

Answer: a

68.     Identify the data structure which allows deletions as per the priority.

(a)      Input−restricted deque                  (b) Output−restricted deque

(c)   Priority queues                             (d)dequeue

Answer: c

69.     In array implementation of stack full condition is   .

(a)      top equal to one less then the size of a stack

(b)      top is equal to 0

(c)      the top is equal to NULL

(d)      top is equal to −1

 

Answer: c

70.     Which out of these is a non-linear data-structure      .

(a)      arrays           (b)  linked-lists        (c)  queues                  (d)tree

Answer: d

71.     A stack is a data structure in which elements are stored and retrieved by   .

(a)      FIFO method                                 (b) LIFO method

(c)   FCFS method                                (d) None of the above

Answer: b

72.     The different types of arrays are     .

(a)      One and Multi-dimensional         (b) int and float

(c)   int, char, float                                (d) One and Two dimensional

Answer: c

73.     An array is passed into a function     .

(a)      By value                                        (b) by reference

(c)   element by element                       (d) Any of the above

Answer: b

74.     A queue is a data structure in which elements are stored and retrieved by     .

(a)      FIFO method                                 (b) LIFO method

(c)   FCFS method                                (d) None of the above

Answer: a

75.     If an array with the name, A exists which of the following statements is incorrect                           (a)                A++            (b)printf(“%d”,*(A+1))

(c)   printf(“%u”,A+1)                         (d) All are correct

Answer: a

76.     An uninitialized pointer is known as    .

(a)      Dangling pointer                           (b) NULL pointer

(b)      generic pointer                              (d) None of the above

Answer: a

77.     The unary operator used with pointer variable to indirectly access the contents of memory location pointed to by the pointer is called     .

(a)      Address-of operator                      (b) dot operator

(c)   Indirection operator                      (d) asterisk operator

Answer: c

 

78.   What will be the postfix expression for the following infix expression? b * c + d / e

(a)           bc*de/+           (b) bcd*e/+     (c) b*cde/+    (d) bc*de+/

Answer: a

79.    Evaluate Postfix expression from given infix expression. A + B * (C + D) / F + D * E

(a)   AB+CD*F/+D*E           (b) ABCD+*F/+DE*+            (c) ABCD+*/F+DE*   (d) AB+CD*F/+DE*

Answer:  b

80.     Assume that the operators +, -, × are left-associative and ^ is right-associative. The order of precedence (from highest to lowest) is ^, x, +, -. The postfix expression corresponding to the infix expression a + b × c – d ^ e ^ f is

 

(a)          abc × + de ^ f ^ –                    (b) ab + c × d – e ^ f ^       

(c)      abc × + def ^ ^ –                     (d) – + a × bc ^ ^ def

 

Answer: c

 

81.  Two main measures for the efficiency of an algorithm are

a.        Processor and memory

b.       Complexity and capacity

c.        Time and space

d.       Data and space

Answer: c

 

82.  The time factor when determining the efficiency of the algorithm is measured by

a.      Counting microseconds

b.      Counting the number of key operations

c.      Counting the number of statements

d.      Counting the kilobytes of algorithm

Answer: b

 

83.  Which of the following case does not exist in complexity theory

a.      Best case

b.      Worst case

c.      Average case

d.      Null case

Answer: d

 

84.  The upper bound on the time complexity of the nondeterministic sorting algorithm is

a.     O(n)

b.    O(n log n)

c.     O(1)

d.    O( log n)

Answer: a

 

85.  The concept of order Big O is important because of

a.     It can be used to decide the best algorithm that solves a given problem

b.    It determines the maximum size of a problem that can be solved in a given amount of time

c.     It is the lower bound of the growth rate of algorithm

d.    Both A and B

Answer: d

 

 

86.  Graphical representation of algorithm is      

a.        Pseudo-code

b.       Graph Coloring

c.        Flow Chart

d.       Dynamic programming

Answer: c

 

87.  O(1) means computing time is          

a.        Constant

b.       Quadratic

c.        Linear

d.       Cubic

 

Answer: a

 

88.  O(n) means computing time is          

a.        Constant

b.       Quadratic

c.        Linear

d.       Cubic

 

Answer: c

 

89.  O(n2) means computing time is         

a.        Constant

b.       Quadratic

c.        Linear

d.       Cubic

 

Answer: b

 

90.  O(n3) means computing time is         

a.      Exponential

b.      Quadratic

c.      Linear

d.      Cubic

 

Answer: d

 

91.  O(2n) means computing time is         

a.      Constant

b.      Quadratic

c.      Linear

d.      Exponential

 

Answer: d

 

92.  Tight bound is denoted as     

a.      Ω

b.      Θ

c.      Ω

d.      O

 

Answer: b

 

93.  Upper bound is denoted as    

a.      Ω

b.      Θ

c.      ω

d.      O

Answer: d

 

94.  Lower bound is denoted as    

a.      Ω

b.      Θ

c.      ω

d.      O

Answer: a

95.  If each node in a tree has a value greater than every value in its left subtree and value less than every value in its right subtree, the tree is known as

a.      Complete Tree

b.      Full Binary Tree

c.      Binary Search Tree

d.      Threaded Tree

    

Answer: c

96.  Which of the following properties are necessary for an Algorithm?

a.      Definiteness

b.      Correctness

c.      Effectiveness

d.      A and C

       Answer: d

 

97. int a = 0, b = 0;

for (i = 0; i < N; i++) {

    a = a + rand();

}

for (j = 0; j < M; j++) {

    b = b + rand();

}

 

a)     O(N * M) time, O(1) space

b)     O(N + M) time, O(N + M) space

c)     O(N + M) time, O(1) space

d)     O(N * M) time, O(N + M) space

 

Answer: c

 

98.  What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

    for (j = N; j > i; j--) {

        a = a + i + j;

    }

}

 

a)     O(N)

b)     O(N*log(N))

c)     O(N * Sqrt(N))

d)     O(N*N)

Answer: d

 

99. What is the time complexity of following code:

 

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

    for (j = 2; j <= n; j = j * 2) {

        k = k + n / 2;

    }

}

 

a)     O(n)

b)     O(nLogn)

c)     O(n^2)

d)     O(n^2Logn)

Answer: b

 

100. What is the time complexity of following code:

 

int a = 0, i = N;

while (i > 0) {

    a += i;

    i /= 2;

}

a)     O(N)

b)     O(Sqrt(N))

c)     O(N / 2)

d)     O(log N)

Answer: d

Post a Comment

0 Comments