Data Structures (AL-303) - Important Questions

What is Abstract data type? Explain with the help of example.

Explain how to measure / 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 the classification of data structures in detail.

Define Abstract Data Types (ADT). Explain the different operations performed on data structures and describe the criteria for cost estimation.

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 insertion operation in a linked list, including how to insert a node after a specified node.

Explain drawbacks of singly linked list and algorithm for search and modify operations in doubly linked list with example.

Differentiate between array and linked list.

Explain sparse matrices, their representation, upper and lower triangular matrices, and space-efficient representation with address determination formulas.

Write a note on Compaction, overflow, and Underflow in Array term.

Find dimensions length, total elements, and address of a given element in row-major multidimensional arrays with given base address and element size.

Explain the limitations of linear queue and the algorithms / C array implementation for various operations of circular queue, 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 \text{ ^ } - \ 6 \ 2 / +$ using a stack.

Write a program in 'C' to implementation of QUEUE.

Define Stack as an ADT. Explain the array and linked list implementation of stacks.

Explain the algorithm to convert an Infix expression to a Postfix notation using a stack.

Explain the concept of Queue simulation with a real-world example.

Define stack as an ADT and explain its implementation using arrays (and linked list).

Explain an algorithm to check whether the parentheses in an expression are balanced using a stack.

Construct an AVL tree by inserting a given sequence of keys starting from an empty tree, performing rotations to maintain balance.

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

Construct a Binary Search Tree from a given sequence and delete specified keys step by step, including insertion algorithm.

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

Define a Binary Search Tree (BST). Explain the algorithms for In-order, Pre-order, and Post-order traversal with an example.

What are AVL Trees? Explain the four types of rotations (LL, RR, LR, RL) used to balance an AVL tree.

Define the following tree terminologies: Height, Depth, Degree of a node, and Forest.

Construct an expression tree for a given expression and give inorder, preorder and postorder traversals.

Explain how to insert and delete an element in a binary search tree with algorithm/code for insertion.

Illustrate with examples the insertion and deletion operations in an AVL tree.

Construct binary tree from given inorder and postorder traversals and find preorder traversal.

How can a tree be stored in memory? Explain with an example, including advantages and disadvantages of array representation.

Draw the directed graph corresponding to the given adjacency matrix.

Explain the Adjacency Matrix and Adjacency List representations of a graph.

Describe the Depth First Search (DFS) and Breadth First Search (BFS) algorithms for graph traversal with examples.

What is a Minimum Spanning Tree (MST)? Explain Kruskal's or Prim's algorithm to find the MST of a weighted graph.

Compare and contrast spanning tree vs minimum spanning tree

Compare Prim's algorithm vs Kruskal's algorithm for finding minimum spanning trees

Explain Breadth First Search algorithm with example.

Explain the graph traversal techniques BFS and DFS with suitable examples.

Find the adjacency list representation and find the minimum cost spanning tree by Kruskal's algorithm for a given undirected graph.

Explain Dijkstra Algorithm with the help of example.

Compare and contrast spanning tree and minimum spanning tree.

Design an efficient algorithm for the longest directed path from $s$ to $t$ in an acyclic weighted digraph, including representation, data structures, and time complexity.

Write the heap sort algorithm (including heap creation) and use it to sort the given elements.

Explain the Quick Sort algorithm with suitable example.

Explain Binary Search with an example.

Write a short notes (any three)

Give real-world applications of hashing and explain two in detail.

Explain how to sort the elements by using selection sort and derive time complexity for the same.

What is a HashMap and how does it handle collisions, with explanation in C or Java?

Demonstrate LRU Algorithm. Which data structure uses LRU algorithm.

Differentiate internal sorting and external sorting. Also enlists the name of two sorting techniques of each.

Define hash function and discuss methods for resolving hash collisions.

Binary search is more efficient than Linear search. Justify your answer.

Write a short note on hashing and indexing.

Write short notes on any Two:

What do you mean by an algorithm? Write the criteria and characteristics of an algorithm.