DS SET 1
1. What data structure would you mostly likely see in a non recursive implementation of a recursive
algorithm?
A. Linked List
B. Stack
C. Queue
D. Tree
ANSWER: B
2. Consider the problem of computing min-max in an unsorted array where min and max are
minimum and maximum elements of array. Algorithm A1 can compute min-max in a1 comparisons
without divide and conquer. Algorithm A2 can compute min-max in a2 comparisons by scanning the
array linearly. What could be the relation between a1 and a2 considering the worst case scenarios?
A. a1 < a2
B. a1 > a2
C. a1 = a2
D. Depends on the input
ANSWER: B
3. Which of the following is true about linked list implementation of queue?
A. In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation,
nodes must be removed from end.
B. In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be
removed from the beginning.
C. Both of the above
D. None of the above
ANSWER: C
4. How many stacks are needed to implement a queue. Consider the situation where no other data
structure like arrays, linked list is available to you.
A. 1
B. 2
C. 3
D. 4
ANSWER: B
5. In linked list implementation of a queue, where does a new element be inserted?
A. At the head of link list
B. At the tail of the link list
C. At the centre position in the link list
D. None
ANSWER: B
6. A data structure in which elements can be inserted or deleted at/from both the ends but not in
the middle is?
A. Queue
B. Circular queue
C. Deque
D. Priority queue
ANSWER: C
7. Which of the memory management algorithm searches the entire list and takes the smallest hole
that is adequate?
A. First fit
B. Next fit
C. Best fit
D. Worst fit
ANSWER: C
8. Which of the following statement(s) is false? 1)Stack implemented using arrays works only for fixed
no.of data values. 2)Stack implemented using arrays is suitable even if we don’t know the size of the
data. 3)Stack implemented using linked list works for variable size of data.
A. 1&2
B. 2
C. 2&3
D. none
ANSWER: B
9. Which of the following is not an application of a stack?
A. implementation of recursion
B. job scheduling
C. reversing a string
D. infix to postfix conversion
ANSWER: B
10. The type of expression in which operator succeeds its operand is
A. infix
B. prefix
C. postfix
D. none
ANSWER: C
11. 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
12. Pushing an element into a stack already having 5 elements and stack size of 5 results in
A. overflow
B. underflow
C. crash
D. none
ANSWER: A
13.In an input restricted double ended queue which of the statements are true 1)insertion is
performed at both ends 2)insertion is performed at one end 3)deletion is performed at both ends
4)deletion is performed at one end
A. 1
B. 2&3
C. 3&4
D. none
ANSWER: B
14. What is the average case complexity of bubble sort
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n^2)
ANSWER: D
15. What is the output of following function for start pointing to first node of following linked list?
1->2->3->4->5->6
void fun(struct node* start)
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
A. 1 4 6 6 4 1
B. 1 3 5 1 3 5
C. 1 2 3 5
D. 1 3 5 5 3 1
ANSWER: B
16. Consider the following function implemented in C:
void printxy(int x, int y)
int *ptr;
x = 0;
ptr = &x;
y = *ptr;
*ptr = 1;
printf("%d,%d", x, y);
The output of the printxy(1,1) is
A. 0,0
B. 0,1
C. 1,0
D. 1,1
ANSWER: C
17. Consider the following sequence of operations on an empty stack.
push(22); push(43); pop(); push(55); push(12); s=pop();
Consider the following sequence of operations on an empty queue.
enqueue(32);enqueue(27); dequeue(); enqueue(38); enqueue(12); q=dequeue();
The value of s+q is
(A) 44 (B) 54 (C) 39 (D) 70
ANSWER: C
18. The following postfix expression with single digit operands is evaluated using a stack:
822^/43*+51*-
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is
evaluated are:
(A) 12,2 (B) 12,5 (C) 2,12 (D) 2,5
ANSWER: A
19.Consider the following C function:
int f(int n)
{
static int r = 0;
If (n < = 0) return 1;
If (n > 3)
{ r = n;
return f (n – 2) + 2;
}
return f(n – 1) + r;
What is the value of f(5)?
A) 3
B) 7
C) 9
D) 18
Answer: D
20. Suppose you are given an implementation of a queue of integers. The operations that can be
performed on the
queue are:
isEmpty(Q) – returns true if the queue is empty, false otherwise.
delete(Q) – deletes the element at the front of the queue and returns its value.
insert(Q, i) – inserts the integer i at the rear of the queue.
Consider the following function:
void f(queue Q)
{
int i;
if(!isEmpty (Q)) {
i = delete(Q);
f(Q)
insert(Q, i);
}
}
What operation is performed by the above function f?
A) Leaves the queue Q unchanged
B) Reverse the order of elements in the queue Q
C) Deletes the element at the front of the queue Q and inserts it at the rear keeping the other
elements in the same order
D) Empties the queue Q.
Answer: B
21. Which of the following is true about linked list implementation of stack?
A) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation,
nodes must be removed from enD)
B) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be
removed from the beginning.
C) Both of the above
D) None of the above
Answer: D
22) Which of the following is not the type of queue?
A) Priority queue
B) Circular queue
C) Single ended queue
D) Ordinary queue
Answer: C
23) 8. Inserting an item into the stack when stack is not full is called …………. Operation and
deletion of item form the stack, when stack is not empty is called ………..operation.
A) push, pop
B) pop, push
C) insert, delete
D) delete, insert
Answer:A
24) 10. ………… is very useful in situation when data have to stored and then retrieved in reverse
order.
A) Stack
B) Queue
C) List
D) Link list
Answer:A
25) The efficient data structure to insert/delete a number in a stored set of numbers is
A) Queue
B) Linked list
C) Doubly linked list
D) Binary tree
Answer C
26.The following postfix expression with single digit operands is evaluated using a stack:
823^/23*+51*-
Note that ^ is the exponentiation operator. The top two elements of the stack after the first
*is evaluated are:
A) 6, 1
B) 5, 7
C) 3, 2
D) 1, 5
Answer: A
27. Minimum number of queues needed to implement the priority queue is ...........
a) 1 b) 2 c) 3 d) 4
ANS: b
28. Which of the following is not the application of stack?
a) A parenthesis balancing program b) Tracking of local variables at runtime
c) Compiler Syntax Analyzer d) Data Transfer between two asynchronous processes
Ans: d
29. In the worst case, the number of comparisons needed to search a singly linked list of length n for
a given element is?
a) log 2 n b) n/2 c) log 2 n – 1 d) n
ANSWER: D
30. To implement a stack using queue (with only enqueue and dequeue operations), how many
queues will you need?
a) 1 b) 2 c) 3 d) 4
Ans: b
31. The optimal data structure used to solve Tower of Hanoi is _________
a) Tree b) Heap c) Priority queue d) Stack
Ans: d
32. Assume that the operators +, -, X are left associative and ^ is right associative. The order of
precedence (from highest to lowest) is ^, X, +, -.
The postfix expression for the infix expression
a + b X c – d ^ e ^ f is?
a) abc X+ def ^^ – b) abc X+ de^f^ – c) ab+c Xd – e ^f^ d ) ) -+aXbc^ ^def
Ans:a
33. Which one of the following is an application of Queue Data Structure?
a) When a resource is shared among multiple consumers.
b) When data is transferred asynchronously(data not necessarily received at same rate as sent)
between two processes
c) Load Balancing
d) All of the above
ANSWER: d
34. 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
35. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are
performed efficiently.
Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
a) Both operations can be performed in O(1) time.
b) Atmost one operation can be performed in O(1).
c) The worst case time complexity for both operations is O(n).
d) The worst case time complexity for both operations is O(log n).
ANSWER: a
36.The best data structure to check whether an arithmetic expression has balanced parentheses is a
a) Queue
b) Stack
c) Tree
d) List
ANSWER: b
37. 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 opeartor and an operand stack
d) A parse tree
ANSWER: a
38. Consider the following statements:
(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for
almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a
linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.
a) (ii) and (iii) are true
b) (i) and (ii) are true
c) (iii) and(iv) are true
d) (ii) and (iv) are true
ANSWER: a
