Data Structure and Algorithms - B.Tech. 3rd Semester Examination, 2023

What is the time complexity of the following code snippet?

for(i=0; i<n; i++) {
    for(j=0; j<i; j++) {
        int sum = i + j;
    }
}

1. \( O(n) \)
2. \( O(n^2) \)
3. \( O(log n) \)
4. \( O(1) \)

Which type of traversal of binary search tree outputs the value in sorted order?

1. Pre-order
2. In-order
3. Post-order
4. None of the above

Suppose a circular queue of capacity \( (n-1) \) elements is implemented with an array of n elements. Assume that the insertion and deletion operations 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

1. Full: FRONT = (REAR-1) mod n. Empty: REAR=FRONT
2. Full: FRONT = (REAR+1) mod n. Empty: REAR=(FRONT+1) mod n
3. Full: REAR = FRONT. Empty: FRONT = (REAR+1) mod n
4. Full: REAR = (FRONT+1) mod n. Empty: REAR=FRONT

Which of the following data structures can be used for parentheses matching?

1. Tree
2. Queue
3. Stack
4. Priority queue

What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

1. \( \Theta(n) \)
2. \( \Theta(n log n) \)
3. \( \Theta(n^2) \)
4. \( \Theta(1) \)

What will be the postfix expression for the given infix expression: \( (a+b)*c-d \)

1. *+abcd
2. ab+c*d-
3. ab+cd-*
4. abc*+d-

What is the outcome of the prefix expression + - * 3 2 / 8 4 1 ?

1. 12
2. 11
3. 5
4. 4

Where will the new element be inserted in the linked list implementation of the queue?

1. At the middle position of the linked list
2. At the head position of the linked list
3. At the tail position of the linked list
4. None of the above

Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and a hash table size of 10. What is the order of elements (from index 0 to size-1) in the hash table?

1. null, null, 77, 16, null, 34, 93, 2, 51, 80
2. 80, 51, 2, 93, 34, null, 16, 77, null, null
3. 77, 16, 34, 93, 2, 51, 80
4. 80, 51, 2, 93, 34, 16, 77

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

1. \( 2^h-1 \)
2. \( 2^{h-1}-1 \)
3. \( 2^{h+1}-1 \)
4. \( 2^{h+1} \)

Why do we need an asymptotic notation? Explain the different asymptotic notations with definitions and examples.

Write the worst-case run time complexity of the following algorithms: linear search, bubble sort, merge sort, and push operation in the stack.

Write push() and pop() functions of a stack.

Evaluate the following postfix expression using STACK. Show all the steps. 8, 2, /, 3, *, 4, -, 6, 2, /, +

Write the algorithm to count the total elements in a singly linked list.

How a doubly linked list is better than a singly linked list? Explain deletion on a doubly linked list using an example.

The following values are to be stored in a hash table: 25, 42, 96, 101, 102, 162, 197. Describe how the values are hashed by using the division method of hashing with a table size of 7. Use chaining as the method of collision resolution.

Apply the merge sort on the following numbers: 10, 15, 50, 17, 20, 25, 30, 16, 70, 6.

Differentiate between stack and queue. Explain different types of queues with examples.

Write the properties of a binary search tree. Create a binary search tree using the following elements: 45, 15, 79, 90, 10, 55, 12, 20, 50.

Consider the in-order and pre-order traversal of a binary search tree are (1, 2, 3, 4, 5, 6, 8, 10, 25) and (4, 3, 1, 2, 10, 8, 5, 6, 25) respectively. Construct a unique binary search tree for the given in-order and pre-order traversals.

Explain the insertion in the AVL tree using an example.

Explain the Heap sort algorithm. Create a heap for the following elements and then sort them: 13, 102, 405, 136, 15, 105, 390, 432, 28, 444.