Data Structures and Algorithms - B.Tech 3rd Semester Exam., 2020 (New Course)

Which of the following is time complexity of the given code?
\( int\ a=0; \)
\( for(i=0; i< N; i++) \{ \)
\( \quad for(j=N; j>i; j--) \{ \)
\( \quad \quad a = a + i + j; \)
\( \quad \} \)
\( \} \)

1. \( O(N) \)
2. \( O(N * \log(N)) \)
3. \( O(N * \sqrt{N}) \)
4. \( O(N * N) \)

Which of the following is time complexity of the given code?
\( int\ i,\ j,\ k=0; \)
\( for(i=n/2; i<=n; i++) \{ \)
\( \quad for(j=2; j<=n; j=j*2) \{ \)
\( \quad \quad k = k + n/2; \)
\( \quad \} \)
\( \} \)

1. \( O(N) \)
2. \( O(N * \log(N)) \)
3. \( O(N * \sqrt{N}) \)
4. \( O(N * N) \)

Which of the following cases does not exist in complexity theory?

1. Best case
2. Worst case
3. Average case
4. Null case

The operation of processing each element in the list is known as

1. sorting
2. merging
3. inserting
4. traversal

Arrays are best data structures

1. for relatively permanent collections of data
2. for the size of the structure and the data in the structure are constantly changing
3. Both (i) and (ii)
4. None of the above

Each array declaration needs not give, implicitly or explicitly the information about

1. the name of array
2. the data type of array
3. the first data from the set to be stored
4. the index set of the array

In general, the binary search method needs not more than

1. \( [\log_2 n] - 1 \)
2. \( [\log n] + 1 \)
3. \( [\log_2 n] \)
4. \( [\log_2 n] + 1 \) comparisons.

State True or False:
A. Binary search is used for searching in a sorted array.
B. The time complexity of binary search is O(logn).

1. True, False
2. False, True
3. False, False
4. True, True

Which of the following is non-linear data structure?

1. Stack
2. Linked list
3. String
4. Tree

Which is the correct output for the following sequence of operations? push(5), push(8), pop, push(2), push(5), pop, pop, pop, push(1), pop

1. 85251
2. 85521
3. 82551
4. 81255

Analyse the time complexity of the given function and also write the recurrence relation of the function:
\( int\ DoSomething(int\ n) \{ \)
\( \quad if(n<=2)\ return\ 1; \)
\( \quad else\ return\ (DoSomething(floor(sqrt(n))) + n); \)
\( \} \)

Consider the following postfix expression : 873-/6254+*+-
The above expression is evaluated using stack. Show the content of stack after each step.

What are the different notations for comparing the time complexity of an algorithm? Explain each of them with neat figures.

Explain the queue and circular queue with examples. Also, write the differences between the two.

Let a and b be positive integers. Suppose a function F is defined recursively as follows:
\( F(a,b) = \begin{cases} 0 & \text{if } a < b \\ F(a-b,b) + 1 & \text{if } b \le a \end{cases} \)
Find the values of the following: (a) \( F(2,3) \) (b) \( F(14,3) \)

Write the algorithm of prefix evaluation with example.

Write prefix notation of the following infix notation: \( A+B*C+D \)

What do you mean by ADT? Explain the ADT stack with test cases for both pop and push.

Hashing

Circular linked list

Adjacency list

AVL tree