# Computer Science - Data Structures

### Exam Duration: 45 Mins Total Questions : 30

Stack can be represented by

- (a)
array

- (b)
linked list

- (c)
both a and b

- (d)
Neither a nor b

A postfix expression in merely the reverse of the prefix expression

- (a)
true

- (b)
false

- (c)
cannot say

- (d)
sometimes

If int s[s] is a one-dimensional array of integers, which of the following refers to the third element in the array?

- (a)
*(s+2)

- (b)
s+3

- (c)
*(s+3)+5

- (d)
*(s+3)+2

The postfix equivalent of the prefix *+ab-cd is

- (a)
ab+cd-*

- (b)
abcd+-*

- (c)
ab+cd*-

- (d)
ab+-cd*

is equivalent to The operation

i =POS(S)

push (S,I)

- (a)
i = stack to p(s)

- (b)
empty (s)

- (c)
remove (i)

- (d)
add (i)

The postfix expression for the infix expression

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

- (b)
ABCD+*F/DE*++

- (c)
A*B+CD/F*DE++

- (d)
A+*BCD/F*DE++

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)
None of the above

In heap property, function 'Right(i)' returns

- (a)
[1/2]

- (b)
2i

- (c)
2i+1

- (d)
None of these

Let p be a singly linked list. Let Q be the pointer to an intermediate node X in the list. What is the worst case time complexity of the best known algorithm to delete the node X from the list?

- (a)
O(n)

- (b)
O(log

^{2}n) - (c)
O(log n)

- (d)
O (1)

Which of the following is useful in implementing quick sort?

- (a)
Stack

- (b)
Set

- (c)
List

- (d)
Queue

Suppose each data structure is stored in a circular array with N memory cells, then find the number NUMB of elements in a deque in terms of LEFT and RIGHT.

- (a)
RIGHT-LEFT+1 (mod N)

- (b)
RIGHT+LEFT-1 (mod N)

- (c)
RIGHT+LEFT+1 (mod N)

- (d)
RIGHT-LEFT-1 (mod N)

If we want to make the above function as a last node then we want to have

- (a)
temp\(\rightarrow \)data = null

- (b)
temp \(\rightarrow \) link = null

- (c)
*q \(\rightarrow \) link = null

- (d)
None of these

Queue can be used to implement

- (a)
radix sort

- (b)
quick sort

- (c)
recursion

- (d)
depth first search

What is the minimum number of stacks of size n required to implement a queue of size n?

- (a)
One

- (b)
Two

- (c)
Three

- (d)
Four

Which of the following statements is true?

- (a)
1,2,4 are inorder sequence of three different BSTs

- (b)
1 is preorder sequence of some BST with 439 as the root

- (c)
2 is an inorder sequence of some BST where, 121 is the root and 52 is leaf

- (d)
4 is a postorder sequence of some BST with 149 as the root

The wrost case complexity for searching an element in binary search tree is

- (a)
(n)

- (b)
O(log n)

- (c)
(n log n)

- (d)
O(n

^{2})

Deque is called

- (a)
double ended queue

- (b)
single ended queue

- (c)
an operation

- (d)
None of these

If n numbers are inserted into a binary search tree then which of the following traversal outputs of numbers is sorted order?

- (a)
Preorder

- (b)
In order

- (c)
Postorder

- (d)
Breadth first

Let T be a binary search tree with 14 nodes and 60 as the external path length.Then the internal path length is

- (a)
28

- (b)
50

- (c)
32

- (d)
11

If a help has 7 nodes, the depth of the tree would

- (a)
5

- (b)
2

- (c)
3

- (d)
6

The running time of building max-heap is

- (a)
O(n log n)

- (b)
O(log n)

- (c)
O(n

^{2}) - (d)
O(n)

The implementation of priority queue is

- (a)
binary heap

- (b)
deque

- (c)
hashing

- (d)
None of theses

If there are n elements in a heap. What is the time complexity of inserting 0 new element in the heap in a wrost case?

- (a)
\(\theta \)(log n)

- (b)
\(\theta \)(n log n)

- (c)
\(\theta \)(n)

- (d)
\(\theta \)(n

^{2})

The right child of a node in position 10 will be in position

- (a)
9

- (b)
21

- (c)
11

- (d)
20

Which of the following statements is false?

- (a)
If a binary tree with n nodes contain \(\frac { n+1 }{ 2 } \) leaves then it is a strictly binary tree

- (b)
It an almost complete binary tree with (2n+1) nodes contains n leaves then it is strictly binary tree

- (c)
A complete binary tree is always strictly binary tree

- (d)
A strictly binary tree with n leaves contains (2n + 1) nodes

How many rotations are required during the construction of an AVL tree if the following elements are to be added in the order given?

35, 50, 40, 25, 30, 60, 78, 20, 28

- (a)
2 left rotations, 1 right rotations

- (b)
2 left rotations, 2 right rotations

- (c)
3 left rotations, 2 right rotations

- (d)
3 left rotations, 1 right rotations

Linked list are not suitable for

- (a)
Insertion sort

- (b)
binary search

- (c)
radix sort

- (d)
polynomial function

In linked list an element can be inserted

- (a)
Only at beginning

- (b)
Only at end

- (c)
Only at middle

- (d)
at any position in the list

In the above, the degree of A is

- (a)
1

- (b)
0

- (c)
3

- (d)
8

What is the maximum number of comparisons required to search an element in unsorted list of n elements using binary search?

- (a)
log

_{2}n - (b)
log

_{2}n + 1 - (c)
log

_{2}n - 1 - (d)
Cannot be determined