This Test will cover basic concepts of data Structure and related algorithm.

Q. What is the maximum height of stack required to process the given directed graph using
DFS (Depth first search) ?

Q. Which of the following BFS (Breadth First Search) sequence is valid for the given graph

Q. What is the maximum height of queue (To keep track of un-explored nodes) required to
process a connected Graph G1 which contains 'N' node using BFS algorithm?

Q. What will be the probability that the upcoming element will be hashed to 0th cell using linear probing:

Hash function : h(k) = k mod 10

Where K denotes the key to be inserted.

Hash function : h(k) = k mod 10

Where K denotes the key to be inserted.

Q. Which of the following permutations can be obtained in the output (In the same order) using a stack .Assuming the Input is the sequence A,B,C,D,E in that order.

Q. Consider a single linked list with start node pointed by 'head' pointer. Suppose there is a middle node 'X' which is pointed by a pointer 'ptr'. What is the time complexity of the best known algorithm to delete the node X .

Q. Suppose a new data type 'X' is created to hold integers. The maximum number of bits allocated to the this X is 5. Consider the number to be represented in 2's compliment form then what will be the range of the values which can be assigned to X.

Q. Consider a hash table with 50 slots .Collision is resolved using chaining. What is the probability that there will be No collision in any of the 50 slots

Q. Which of the following statements are true :

**(I)** When an integer array is initialized to number of elements less that the declared size then the uninitialized elements become 0.

**(II)** If a macro value is not defined then the pre-processor assigns 0 to it by default.

**(III)** In a queue when Front pointer = Rear +1 , this condition may denote Over flow.

**(IV)** 2 stacks are sufficient to implement queue.

Q. Which of the following statements are essentially true for NP problems.

**(I)** There doesn't exist any algorithm for NP problems which can solve it in O(polynomial) time.

**(II)** There always exist a polynomial time verification algorithm.

**(III)** Every P is NP but every NP is not P.

Q. Suppose there is problem X which satisfy the following properties:

1. X is NP.

2. X is NP hard.

3. X is P also.

Now which of the following conclusions can be drawn from the above properties.Q. What is the time complexity of the below 'C 'code snippet.

```
for (int j=0;j<n;j++)
{
for (int I =0 ;i<n;i=i*2)
printf("study tonight");
}
```

Q. What will be the recursive equation for the below code snippet.

```
Studytonight(n)
{
if(n>=1)
{
Studytonight(n/2);
int temp,a,b;
scanf("%d",&a);
scanf("%d",&b);
}
}
```

Q. What is the time complexity of the below recursive equation?
T(n) = 5 T(n/3) + n^{2}

Q. What is the maximum number of movements required in order to get the correct location of an element in insertion sort?