Data Structures (CY-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.

Differentiate between array and linked list.

Write the algorithm to convert an infix expression to postfix form using a stack. Also 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 C array implementation, including comparison of linear vs circular queue.

Construct an AVL tree by inserting the keys 45, 27, 10, 60, 70, 30, 40, 25 starting from an empty tree, performing LL, RR, LR and RL rotations to maintain balance. Show the tree after each insertion.

Define and distinguish tree terminologies: height vs depth, degree/order of a node, and forest.

Create a Binary Search Tree 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, including insertion algorithm.

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 45, 26, 10, 60, 70, 30, 40.

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

Explain the classification of data structures in detail.

Write short notes on any Two: a) Doubly linked list and circular linked list b) BFS and DFS graph traversal c) Quick sort and Binary search d) B-tree and Red-Black tree