Data Structure & Algorithms - End Semester Examination - 2022

In a stack, if a user tries to remove an element from empty stack it is called:

1. underflow
2. empty collection
3. garbage collection
4. overflow

Consider the binary max-heap implemented using an array. Which one of the following array represents the heap:

1. 25, 12, 16, 13, 10, 8, 14
2. 25, 12, 16, 13, 10, 8, 14
3. 25, 14, 16, 13, 10, 8, 12
4. 25, 14, 12, 13, 10, 8, 16

A hash function is defined as h(key) = key mod 7, with linear probing used to insert keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

1. 3
2. 4
3. 5
4. 6

If the number of values to be sorted is already partially sorted, then ______ sorting can be efficient.

1. merge
2. insertion
3. bubble
4. selection

The time complexity of merge sort is:

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

State true or false: A: Binary search is used for searching in a sorted array. B: The time complexity of binary search is \( O(\log n) \).

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

In a circular linked list organization, insertion of a record involves modification of:

1. One pointer
2. Two pointers
3. More than two pointers
4. No pointer

Level order traversal of a rooted tree can be done by starting from the root and performing:

1. pre-order traversal
2. in-order traversal
3. depth first search
4. breadth first search

An Abstract Data Type (ADT) is:

1. same as an abstract class
2. a data type that cannot be instantiated
3. a data type for which only the operations defined on it can be used, but none else
4. all of the above

How many distinct BSTs can be constructed with 3 distinct keys?

1. 4
2. 5
3. 6
4. 7

Explain different asymptotic notations (Big-O, \( \Omega \), \( \Theta \)) used for comparing the time complexity of an algorithm with neat figures.

The run time of an algorithm is represented by the recurrence relation \( T(n) = 2T(n/2) + n \); \( n \ge 2 \) and with boundary condition \( T(1) = 0 \). What is the time complexity (in terms of \( \Theta \) notation).

Discuss pre-order, in-order and post-order traversal techniques of binary tree. Write a C function for non-recursive pre-order traversal.

The pre-order traversal sequence of a Binary Search Tree (BST) is 30, 20, 10, 15, 25, 23, 39, 35, 42. Write step by step process to derive the BST and find post-order traversal also.

Consider a circular queue of capacity n-elements implemented with an array. Write C functions for insertion and deletion operations.

Convert the given infix expression into postfix using stack: \( A + B / C * (D + E) - F \). For each input symbol clearly mention the action taken and status of the stack during conversion.

Write a C function to delete last node from a singly linked list.

Create a max-heap by inserting following keys in the given order. Show each insertion step with clear illustration: 25, 35, 18, 9, 46, 70, 48.

Write an algorithm for merge sort and discuss space and time complexity.

Define collision in hashing. Explain briefly different methodologies to resolve collision.

Write algorithm to count leaf nodes in binary tree. What is the complexity of your algorithm?

Compare BFS and DFS traversal techniques for graph. Write an algorithm to perform BFS using queue.

Differentiate between system defined data types and abstract data types with suitable examples.

What is doubly linked list? What are its applications? Explain how a node can be added as last node using appropriate pseudo code.

AVL Rotations

Open Addressing & Chaining

B-Tree

Priority Queue