Data Structures (AD-303) - Important Questions

What is Abstract Data Type (ADT)? Explain with the help of an example.

Explain how to measure and demonstrate the efficiency and complexity of an algorithm, including asymptotic notations.

Describe all types of operations that can be performed on a linked list.

Explain representation of multidimensional arrays in row-major order. For an array with given base address, element size and dimensions, find total elements, length and address of a given element A[i][j].

Write the algorithm to convert an infix expression to postfix form using a stack and evaluate the postfix expression 2 3 9 * + 2 3 ^ - 6 2 / + using a stack.

What are the limitations of linear queue? Explain the algorithms for various operations of circular queue using array, including comparison of linear vs circular queue.

Create a Binary Search Tree starting from an empty tree for the numbers 45, 26, 10, 60, 70, 30, 40. Delete keys 10, 60 and 45 one after the other and show the trees at each step. Also write the insertion algorithm.

Construct an AVL tree by inserting the keys 10, 20, 30, 40, 50, 25 starting from an empty tree, performing LL, RR, LR, RL rotations to maintain balance. Show balance factor at each step.

What are the differences between i) Height and Depth ii) Order/Degree of a node? Define forest with example.

Prove that the maximum number of nodes in a binary tree of height h is 2^{h+1}-1.

Draw the directed graph that corresponds to the following adjacency matrix: V0: 0 1 1 0; V1: 0 0 1 1; V2: 0 0 0 1; V3: 1 0 0 0.

What is a Minimum Spanning Tree (MST)? Explain Kruskal's and Prim's algorithms to find the MST of a weighted graph with a suitable example.

Write the heap sort algorithm including heap creation procedure and use it to sort the elements 20, 12, 35, 15, 10, 80, 30.

What is hashing? Explain hash functions, collision handling techniques and indexing. Give two real-world applications where hashing is used.

Write short notes on any Two: a) Quick sort with example b) Binary search with example c) Comparison of various sorting techniques.