Data Structures - Unit 1, 2, 3 (Complete Answers)

Define the terms: data file, record with the help of example.
A data file is a stored collection of related records on secondary storage. A record is a single unit within
that file composed of fields. Example: Students.txt with records like {Roll:101, Name:Ramesh, Marks:85}. Thus,
a file = collection of records; record = collection of fields.
Define data structures. Give some examples.
A data structure is a way to organize and store data in memory for efficient access and modification. Examples
include arrays (contiguous memory), linked lists (nodes with pointers), stacks (LIFO), queues (FIFO), trees
(hierarchical), and graphs (networked relationships).
In how many ways can you categorize data structures? Explain each of them.
Data structures can be categorized as: 1) Primitive vs Non-primitive; 2) Linear vs Non-linear; 3) Static vs
Dynamic; 4) Homogeneous vs Heterogeneous. Each category highlights different properties (size, shape, memory
layout) and guides selection for problems.
Write a short note on different operations that can be performed on data structures.
Common operations: Creation, Insertion, Deletion, Traversal, Searching, Updating, and Sorting. These
operations form the backbone of algorithms that manipulate data structures in applications.
Explain the different types of data structures. Also discuss their merits and demerits.
Major types: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs, Hash Tables. Each has merits (fast access,
dynamic size, natural modeling of relationships) and demerits (memory overhead, complex implementation, slower
random access).
Discuss the best case, worst case, average case, and amortized time complexity of an algorithm.
Best case is the minimum time (e.g., search finds element first). Worst case is the maximum time (e.g.,
element absent). Average case is expected time over inputs. Amortized analyzes sequences of operations (e.g.,
dynamic array append — average O(1)).
Categorize algorithms based on their running time complexity.
Classification by growth: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!). Understanding these classes
helps estimate scalability and choose suitable algorithms.
Explain control structure used in Algorithm.
Control structures: Sequence (do steps in order), Selection (if-else decisions), Iteration (loops), and
Recursion (function calls itself). They determine the program flow and complexity of algorithms.
Write an algorithm
Answer: Write an algorithm
For swapping two values.
Answer: For swapping two values.
To find the largest of two numbers.
Algorithm to find largest of two numbers: 1. Read a,b 2. If a >= b then largest = a else largest = b 3. Print
largest Simple comparison gives the result in O(1).
To find a number is even or odd
Algorithm to check even/odd: 1. Read n 2. If n % 2 == 0 then 'Even' else 'Odd' This uses modulus operation and
runs in constant time.
To find the sum of first N natural numbers.
Two methods: 1) Loop: sum=0; for i=1..N sum+=i; O(N). 2) Formula: sum = N*(N+1)/2; O(1). The formula is
preferred for efficiency.
Explain different cases in which loops determine the efficiency of an algorithm.
Loop structure influences complexity: single loops → O(n); nested loops → O(n^2); exponential loops or divide-
and-conquer loops → O(n log n) or O(log n) depending on progression. Early exit reduces average time.
Define sorting. What are the different types of sorting techniques?
Sorting arranges elements in order (ascending/descending). Common methods: Bubble, Selection, Insertion,
Merge, Quick, Heap, Radix. Sorting improves searching and processing efficiency; different sorts balance ease
of implementation and performance.
Describe the following search algorithms to search the number 88 from the following array: 77, 33,
44, 11, 88, 22, 66, 55 i. Linear Search ii. Binary Search
Linear search checks elements one by one (O(n)). Example: finding 88 in [77,33,44,11,88,...] requires 5
comparisons. Binary search requires sorted data and repeatedly halves search space (O(log n)). Example: in
sorted list it finds 88 in ~4 comparisons.
i. List the different types of sorting techniques?
Answer: i. List the different types of sorting techniques?
ii. Explain any one sorting technique in detail with an Example.
Answer: ii. Explain any one sorting technique in detail with an Example.
Demonstrate quick sort for the following data: 88,11,22,44,66,99,32,67,54,10
Quick Sort picks a pivot, partitions array into elements less and greater than pivot, then recursively sorts
partitions. Average O(n log n), worst O(n^2) for bad pivots. Practical and in-place.
Sort the elements 77, 49, 25, 12, 9, 33, 56, 81 using
Answer: Sort the elements 77, 49, 25, 12, 9, 33, 56, 81 using
(a) insertion sort (b) selection sort
Answer: (a) insertion sort (b) selection sort
(c) bubble sort (d) merge sort
Merge Sort divides the array recursively until single elements, then merges sorted halves. Time complexity is
O(n log n) in all cases, stable, requires O(n) extra space. Useful for large data and external sorting.
(e) quick sort (f) radix sort
Quick Sort picks a pivot, partitions array into elements less and greater than pivot, then recursively sorts
partitions. Average O(n log n), worst O(n^2) for bad pivots. Practical and in-place.
If the following sequence of numbers is to be sorted using quick sort, then show the iterations of
the sorting process.
Quick Sort picks a pivot, partitions array into elements less and greater than pivot, then recursively sorts
partitions. Average O(n log n), worst O(n^2) for bad pivots. Practical and in-place.
42, 34, 75, 23, 21, 18, 90, 67, 78
Answer: 42, 34, 75, 23, 21, 18, 90, 67, 78
Sort the numbers given below using radix sort.
Answer: Sort the numbers given below using radix sort.
345, 654, 924, 123, 567, 472, 555, 808, 911
Answer: 345, 654, 924, 123, 567, 472, 555, 808, 911
Sort the elements given in the following array using quick sort algorithm
Quick Sort picks a pivot, partitions array into elements less and greater than pivot, then recursively sorts
partitions. Average O(n log n), worst O(n^2) for bad pivots. Practical and in-place.
27, 10, 36, 18, 25, 45
Answer: 27, 10, 36, 18, 25, 45
Sort the array given below using merge sort
Merge Sort divides the array recursively until single elements, then merges sorted halves. Time complexity is
O(n log n) in all cases, stable, requires O(n) extra space. Useful for large data and external sorting.
39, 9, 81, 45, 9, 27, 72, 18
Answer: 39, 9, 81, 45, 9, 27, 72, 18
Sort the array given below using selection sort.
Answer: Sort the array given below using selection sort.
39, 9, 81, 45, 90, 27, 72, 18
Answer: 39, 9, 81, 45, 90, 27, 72, 18
Sort the given array using Bubble sort
Answer: Sort the given array using Bubble sort
A[] = {30, 52, 29, 87, 63, 27, 19, 54}
Answer: A[] = {30, 52, 29, 87, 63, 27, 19, 54}
What do you understand by stack overflow and underflow? Explain with the help of example and
algorithm.
Stack overflow occurs when pushing into full stack; underflow when popping from empty stack. Use boundary
checks in PUSH and POP to avoid these errors. Example and pseudocode included previously.
What are the different applications of stack? Explain any one in detail.
Stacks are used in expression evaluation, function call management, undo features, DFS traversal, and checking
balanced parentheses. For example, compilers use stacks to evaluate arithmetic expressions and manage scopes.
Explain in detail following functions on stack.
Answer: Explain in detail following functions on stack.
PUSH()
Answer: PUSH()
POP()
Answer: POP()
PEEK()
Answer: PEEK()
Evaluate following postfix expression using stack
Answer: Evaluate following postfix expression using stack
9 3 4 * 8 + 4 / -
Answer: 9 3 4 * 8 + 4 / -
Evaluate following infix expression using stack
Answer: Evaluate following infix expression using stack
+ - 9 2 7 * / 4 12
Answer: + - 9 2 7 * / 4 12
Draw the stack structure in each case when the following operations are performed on an empty stack.
Sequence of pushes/pops: After pushing A-F → [A..F]; pop twice → [A..D]; push G,H → [A..D,G,H]; pop four →
[A,B]; push I → [A,B,I]. Final stack [A,B,I].
(a) Add A, B, C, D, E, F (b) Delete two letters
Answer: (a) Add A, B, C, D, E, F (b) Delete two letters
(c) Add G (d) Add H
Answer: (c) Add G (d) Add H
(e) Delete four letters (f) Add I
Answer: (e) Delete four letters (f) Add I
Explain the concept of a circular queue? How is it better than a linear queue?
Circular queue wraps around the array allowing reuse of freed slots; advantage over linear queue is efficient
memory usage and avoids shifting. Useful for buffers and scheduling.
Write algorithm to insert and delete an element in a circular queue with example.
Circular queue wraps around the array allowing reuse of freed slots; advantage over linear queue is efficient
memory usage and avoids shifting. Useful for buffers and scheduling.
Explain different types of Queue.
Types: Simple queue (FIFO), Circular queue (wrap-around), Deque (double-ended), Priority queue (served by
priority), Input/output restricted deques. Each suits different application needs.
Draw the queue structure in each case when the following operations are performed on an empty queue
For operations on empty queue: after enqueue A-F → [A,B,C,D,E,F]; delete two → [C,D,E,F]; add G,H →
[C..F,G,H]; delete four → [G,H]; add I → [G,H,I]. Final queue [G,H,I].
(a) Add A, B, C, D, E, F
Answer: (a) Add A, B, C, D, E, F
(b) Delete two letters
Answer: (b) Delete two letters
(c) Add G (d) Add H
Answer: (c) Add G (d) Add H
(e) Delete four letters (f) Add I
Answer: (e) Delete four letters (f) Add I
11. Consider the queue given below which has FRONT = 1 and REAR = 5.
Assuming elements at positions 1..5 are A..E: After add F → [A..F]; delete two → [C..F]; add G,H → [C..F,G,H];
delete four → [G,H]; add I → [G,H,I]. Final queue [G,H,I].
Now perform the following operations on the
Answer: Now perform the following operations on the
queue:
Answer: queue:
(a) Add F (b) Delete two letters
Answer: (a) Add F (b) Delete two letters
(c) Add G (d) Add H
Answer: (c) Add G (d) Add H
(e) Delete four letters (f) Add I
Answer: (e) Delete four letters (f) Add I