Data Structure (IT-303) - Important Questions

Define data structure and describe its classification with a diagram.

Define data structure, distinguish between linear and non-linear data structures and list operations on data structures.

Define algorithmic complexity and explain time complexity and space complexity.

Explain asymptotic analysis and Big-O notation and analyze the running time complexity of the given nested-loop function.

Discuss asymptotic notations (Big-O, Omega, Theta) with suitable examples.

Differentiate between primitive and non-primitive data structures.

List and explain non-linear data structures with examples.

Show the steps of sorting a given array using quick sort with a specified pivot.

Show the steps of inserting given keys one at a time into an initially empty binary heap / constructing a heap.

Consider an array $A[1:n]$ Given a position, write an algorithm to insert an element in the Array. If the position is empty, the element is inserted easily. If the position is already occupied the element should be inserted with the minimum number of shifts.

Compare the working of binary search and linear search with example.

Discuss common collision resolution strategies used in closed hashing.

Sort a given sequence using shell sort and radix sort showing required steps.

Write short notes on polynomial manipulation, red-black tree, and hashing.

How to implement binary search recursively?

How does input array size affect time complexity of linear search vs binary search?

Explain insertion sort in detail, give its algorithm and discuss its complexity.

What is a max heap? Give algorithm for heap sort with example.

Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. For the below array, algorithm should give $-80$ and $85$. Example: $1, 60, -10, 70, -80, 85$ Also discuss the complexity of the process and suggest and alternate way to optimize the complexity.

Write the algorithm for evaluating a postfix expression using a stack and apply it to evaluate a given postfix expression showing stack contents at each step.

Convert given infix expression(s) to postfix (and prefix) form

Classify the different types of queues and illustrate the difference between queues and linked lists with an example.

Describe about stack ADT in detail. Give an algorithm for push and pop operations on stack using a linked list.

Perform a sequence of enqueue and dequeue operations on a queue with given initial elements and state the resulting queue / dequeued elements.

Implement a queue using two stacks and discuss advantages and disadvantages.

Define the properties of circular queue and explain how to check full and empty conditions.

Define stack, list its operations, and explain why stack is a recursive data structure.

Explain the importance of queues and why using the head of a linked list as the rear of the queue is inefficient.

Explain the advantage of circular queue over ordinary queue and write a C program using array to implement insert, delete and display operations.

Design a data representation which sequentially map '$n$' data objects into an array $a[1, n]$, $n_1$ of these data objects are stacks and the remaining are queues. Write algorithms to add and delete elements from these objects.

Define stack and explain its basic operations (push, pop, etc.).

Explain and implement a singly linked list with an example.

What is a link list? Discuss the advantages of using link list; also write about the various operations which can be performed on link list with their time complexities.

Give an algorithm to find the merging point of two intersecting singly linked lists and state its running time complexity.

What is a linked list, its advantages, and the basic operations that can be performed on it with their time complexities?

List an algorithm to perform the insertion operations in a doubly linked list.

Write an algorithm to perform insertion operations in a circular linked list.

Simulate insertion of a given key sequence into an initially empty AVL tree, showing rotations to maintain balance.

Given a binary (search) tree, find its in-order, pre-order and post-order traversals; including building the BST from given keys first if required.

Define a binary tree with an example and explain its applications.

Construct the expression tree for the given arithmetic expression.

Explain the working of Dijkstra's algorithm with the help of an example graph.

Find the minimum spanning tree of a given graph using Prim's algorithm.

Write short notes on applications of queue, BFS and DFS, and doubly circular linked list (any two).

Insert the set of elements $\{30, 40, 24, 58, 48, 26, 11, 13\}$ to construct a binary search tree starting from a null tree taking one element at a time from left to right. Draw a tree for each steps?

Construct a binary tree from given preorder and postorder traversals.

What are L-L, L-R and R-R rotation? Write procedure for adding and deleting a node from the balanced tree and leave the resulting tree balanced.

Determine the preorder, postorder, and breadth-first traversal sequences for a given tree.

Define graph traversal, differentiate graph vs tree traversal, and verify given sequences as depth-first traversals using adjacency list and stack contents.