Data Structure (CS-303) - Important Questions

Write an algorithm for insert and delete operations in a circular linked list

Write short notes on any Two:

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.

Define data structure and explain the classification / various types of data structures in detail with examples.

Describe asymptotic notation in detail.

Write an algorithm for traversing nodes in a single linked list? Explain with an example.

Compare and contrast arrays and linked lists as abstract data types.

Describe the concept of a dynamic array and how it differs from a static array in memory management and flexibility.

Explain what an abstract data type is, with example, and describe the different abstract data types.

Determine worst-case complexity of sequential loops and nested loop followed by non-nested loop.

Differentiate between stack and queue.

Write a C program to convert an infix expression to postfix expression.

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.

What is recursion? Explain the concept of recursion in detail with example.

Explain the stack-based algorithm to convert an infix expression to postfix notation with example.

Write an algorithm to reverse the order of elements on a stack using one additional stack and additional variables

Explain insertion and deletion operations in a circular queue with algorithm/diagram.

Write an algorithm for Push and Pop operations on stack using linked list

What is a DeQueue? Explain its operations with example.

Explain the Tower of Hanoi problem, its rules and steps with example/diagram.

Explain in-order, pre-order and post-order traversal of a binary (search) tree with an example.

Write a C program to insert and delete elements in a binary search tree.

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.

Write recursive functions/programs for preorder, inorder and postorder traversals of a binary tree.

Explain single and double rotations (LL, RR, LR, RL) used to balance an AVL tree

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

Create a binary search tree from given keys and delete given keys showing trees at each stage.

Insert given keys in order to construct AVL tree

Construct/draw a binary tree from given inorder and preorder/postorder traversal sequences.

Insert given elements into AVL tree and delete specified elements

Explain / discuss Kruskal's algorithm with the help of an example / following graph.

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.

Differentiate between Depth First Search (DFS) and Breadth First Search (BFS).

Define what is a minimum spanning tree and write / explain Prim's or Kruskal's algorithm to find it.

Describe / write the DFS and BFS algorithms for graph traversal with examples.

Write / explain Prim's algorithm to find the minimum spanning tree of a graph, with an example.

For a given graph, find its adjacency list, adjacency matrix, and adjacency multilist representations.

Compare and contrast BFS and DFS graph traversals.

Find the BFS and DFS traversal of a given graph.

Apply / discuss Prim's algorithm on a given following graph to find the minimum spanning tree.

Explain shell sort algorithm and simulate it for the following data 35, 33, 42, 10, 14, 19, 27, 44.

Explain sequential search and simulate it on a given list of data.

Explain the Quick Sort algorithm with suitable example.

Explain Binary Search with an example.

Sort the given list of numbers in ascending order using Quick Sort showing partition steps.

Explain multiway merge sort with an example.

What is meant by sorting and why is sorting needed?

Apply binary search to search for a value in a given unsorted list.

Write short notes on Hashing and Indexing, Heap Sort and Red Black Tree.

Apply binary search to find a target value in a given sorted array, showing the steps.

Insert given keys into hash table of size 7 using separate chaining, linear probing and double hashing.

Sort given data using Quick Sort and prove worst-case $O(n \log n)$ time for Heap sort, Merge sort, Quick sort.

Write short notes on any two of the following:

Describe the performance of the algorithms used to multiply two $N \times N$ matrices using suitable measures of complexity. You should make clear what operations you are counting, what is the worst-case that you are considering, (and, perhaps, average-case, and best-case, where appropriate). Also consider space complexity?