Welcome to Data Structure Quiz, Intermediate Level !!

Question 1. The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
```typedef struct node
{
int value;
struct node *next;
}Node;

{
Node *p, *q;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________
}```

Choose the correct alternative to replace the blank line.

head = p; p->next = q; q->next = NULL;

Question 2. Consider the following C program segment where CellNode represents a node in a binary tree:
```struct CellNode
{
struct CellNOde *leftChild;
int element;
struct CellNode *rightChild;
};

int GetValue(struct CellNode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if ((ptr->leftChild == NULL) &&
(ptr->rightChild == NULL))
value = 1;
else
value = value +  GetValue(ptr->leftChild)
+  GetValue(ptr->rightChild);
}
return(value);
}```

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Question 3. Consider the following C code segment:
```int IsPrime(n)
{
int i,n;
for(i=2;i<=sqrt(n); i++  )
if(n%i == 0)
{
printf("Not Prime\n");
return 0;
}
return 1;
}```

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

T(n) = O(sqrt(n)) and T(n) = (sqrt(n))

T(n) = O(sqrt(n)) and T(n) = (1)

T(n) = O(n) and T(n) = (sqrt(n))

none of the above

Question 4. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

d e b f g c a

e d b g f c a

e d b f g c a

d e f g b c a

Question 5. Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1) Choose an i uniformly at random from 1..n;
2) If A[i] = x then Stop else Goto 1;
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

n

n - 1

2n

n/2

Question 6. What is the number of swaps required to sort n elements using selection sort, in the worst case?

O(n)

O(nlogn)

O(n^2)

O(n^2 log n)

Question 7. Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which of the following is true ?

T(n) = O(n^2)

T(n) = (n^2)

T(n) = (n^2)

T(n) = O(nLogn)

Question 8. What is the maximum height of any AVL tree with 7 nodes? Assume that the height of a tree with a single node is 0.

2

3

4

5

Question 9. To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Queue

Stack

Heap

B-Tree

Question 10. Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?

There is no polynomial time algorithm for X.

If X can be solved deterministically in polynomial time, then P = NP.

If X is NP-hard, then it is NP-complete.

X may be undecidable.