Data Structures (AL-303) - Important Questions

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

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

Describe the memory representation of a Singly Linked List. Write an algorithm to insert a node at a specific position in a linked list.

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

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.

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

Construct an AVL tree by inserting the keys 10, 20, 30, 40, 50, 25 starting from an empty tree, showing rotations to maintain balance at each step.

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

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 or Prim's algorithm to find the MST of a weighted graph with an example.

Write the heap sort algorithm including heap creation and use it to sort the elements 20, 35, 15, 10, 40, 5, 30.

What is hashing and indexing? Explain collision handling techniques and give real-world applications where hashing is used.

What are the drawbacks of singly linked list? Explain the representation of doubly linked list and operations of search and modify with example.

Explain the Quick Sort algorithm with suitable example and its time complexity.

Write short notes on any Two: a) DFS and BFS graph traversal b) Binary search c) Circular queue vs linear queue d) AVL rotations.