DATA STRUCTURES – COMPLETE EXAM NOTES

(DETAILED)
This document is written exactly in university exam style. Each topic includes: - Exam‑style Question -
Definition - Detailed explanation - Example - Diagram explanation (textual) - Algorithms / C programs
(where applicable) - Important exam focus ⭐

⭐ MOST REPEATED & IMPORTANT EXAM QUESTIONS

1. Stack operations and applications
2. Infix, Prefix, Postfix conversion and evaluation
3. Linked list types and comparisons
4. Circular queue and priority queue
5. Recursion vs Iteration
6. Binary Search Tree insertion, deletion, traversals
7. Comparison of searching and sorting techniques
8. Hashing methods and collision resolution

UNIT 1: ARRAYS

Q1. Define Array. Explain with example. (2–5 Marks)

Definition: An array is a linear data structure that stores elements of the same data type in contiguous
memory locations.

Explanation: All elements are stored sequentially in memory, and each element can be accessed
directly using its index.

Example: int a[5] = {10,20,30,40,50};

Diagram Explanation: Memory blocks are arranged continuously as: |10|20|30|40|50| Index starts
from 0.

⭐ Exam Focus: Definition + advantage/disadvantage

Q2. What is a Sparse Matrix? Explain its representation.

Definition: A sparse matrix is a matrix in which most of the elements are zero.

Explanation: Storing all zero values wastes memory. Hence, only non‑zero values are stored.

Example: Matrix: 0 0 5 0 8 0

1
Array Representation: (Row, Column, Value) (1,3,5) (2,2,8)

Linked Representation Diagram: Each node stores row, column, value, and link to next node.

⭐ Exam Focus: Definition + representation difference

UNIT 2: STACKS

Q3. Define Stack. Explain stack operations.

Definition: Stack is a linear data structure following LIFO principle.

Operations: - Push: Insert element at top - Pop: Remove top element - Peek: View top element

Diagram Explanation: Elements are stacked vertically like plates.

⭐ Exam Focus: Overflow & Underflow

Q4. Explain Infix, Prefix and Postfix expressions with examples.

Infix: A + B Prefix: +AB Postfix: AB+

Application: Used in expression evaluation using stack.

UNIT 3: LINKED LISTS

Q5. Define Linked List. Explain its types.

Definition: A linked list is a collection of nodes where each node contains data and address of next
node.

Types: - Singly Linked List - Doubly Linked List - Circular Linked List

Diagram Explanation: Nodes connected using pointers.

Q6. What is a Skip List?

A skip list is a multi‑level linked list that allows faster searching similar to binary search.

⭐ Exam Focus: Definition + advantage

2
UNIT 4: QUEUES

Q7. Define Queue. Explain Circular Queue.

Definition: Queue follows FIFO principle.

Circular Queue Explanation: Last position is connected to first to avoid memory wastage.

UNIT 5: RECURSION

Q8. What is Recursion? Explain advantages and limitations.

Definition: Recursion is a technique where a function calls itself.

Advantages: - Simple code

Limitations: - High memory usage

Internal Stack Explanation: Each recursive call is stored in system stack.

UNIT 6: TREES

Q9. Define Binary Search Tree. Explain insertion.

Definition: BST is a binary tree where left subtree < root < right subtree.

Insertion Explanation: Elements are inserted based on comparison.

Diagram Explanation: Root at top, left smaller, right larger.

Q10. Tree Traversals

• Inorder (LNR)
• Preorder (NLR)
• Postorder (LRN)

UNIT 7: SEARCHING & SORTING

Q11. Compare Linear Search and Binary Search.

Linear: Sequential search Binary: Divide and conquer

3
Q12. Explain Bubble Sort algorithm.

Explanation: Repeatedly swaps adjacent elements.

UNIT 8: HASHING

Q13. What is Hashing? Explain collision resolution techniques.

Definition: Hashing maps keys to values using hash function.

Collision Techniques: - Open Addressing - Separate Chaining - Rehashing

✍️ IMPORTANT ALGORITHMS & C PROGRAMS (UNIT-WISE, VIVA-

FRIENDLY)

UNIT 1: ARRAYS

Program 1: Matrix Multiplication (Dense Matrix)

Algorithm: 1. Read rows and columns of two matrices 2. Check compatibility 3. Multiply using triple
nested loops 4. Display result

#include <stdio.h>
int main(){
int a[10][10], b[10][10], c[10][10];
int r1,c1,r2,c2,i,j,k;
printf("Enter rows and columns of first matrix: ");
scanf("%d%d", &r1,&c1);
printf("Enter rows and columns of second matrix: ");
scanf("%d%d", &r2,&c2);
if(c1 != r2){
printf("Matrix multiplication not possible");
return 0;
}
printf("Enter elements of first matrix:
");
for(i=0;i<r1;i++)
for(j=0;j<c1;j++)
scanf("%d", &a[i][j]);
printf("Enter elements of second matrix:
");
for(i=0;i<r2;i++)
for(j=0;j<c2;j++)
scanf("%d", &b[i][j]);
for(i=0;i<r1;i++){

4
 for(j=0;j<c2;j++){
c[i][j]=0;
for(k=0;k<c1;k++)
c[i][j]+=a[i][k]*b[k][j];
}
}
printf("Resultant Matrix:
");
for(i=0;i<r1;i++){
for(j=0;j<c2;j++)
printf("%d ", c[i][j]);
printf("
");
}
return 0;
}

⭐ Viva Tip: Time complexity = O(n³)

UNIT 2: STACKS

Program 2: Stack Operations using Array

Algorithm: 1. Initialize top = -1 2. Push: increment top and insert 3. Pop: remove element and
decrement top

#include <stdio.h>
#define SIZE 5
int stack[SIZE], top = -1;
void push(){
int x;
if(top == SIZE-1)
printf("Stack Overflow
");
else{
printf("Enter element: ");
scanf("%d", &x);
stack[++top] = x;
}
}
void pop(){
if(top == -1)
printf("Stack Underflow
");
else
printf("Popped element = %d
", stack[top--]);
}

5
 int main(){
int ch;
do{
printf("[Link] [Link] [Link]
");
scanf("%d", &ch);
if(ch==1) push();
else if(ch==2) pop();
}while(ch!=3);
return 0;
}

⭐ Viva Tip: Stack follows LIFO

UNIT 3: LINKED LIST

Program 3: Singly Linked List – Insert at Beginning

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
int main(){
struct node *head=NULL, *new;
new = (struct node*)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &new->data);
new->next = head;
head = new;
printf("Node inserted successfully");
return 0;
}

⭐ Viva Tip: Dynamic memory using malloc

UNIT 4: QUEUE

Program 4: Queue using Array

#include <stdio.h>
#define SIZE 5
int q[SIZE], front=-1, rear=-1;
void enqueue(int x){
if(rear==SIZE-1)

6
 printf("Queue Full
");
else{
if(front==-1) front=0;
q[++rear]=x;
}
}
void dequeue(){
if(front==-1 || front>rear)
printf("Queue Empty
");
else
printf("Deleted = %d
", q[front++]);
}
int main(){
enqueue(10);
enqueue(20);
dequeue();
return 0;
}

⭐ Viva Tip: Queue follows FIFO

UNIT 5: RECURSION

Program 5: Factorial using Recursion

#include <stdio.h>
int fact(int n){
if(n==0)
return 1;
else
return n * fact(n-1);
}
int main(){
int n;
printf("Enter number: ");
scanf("%d", &n);
printf("Factorial = %d", fact(n));
return 0;
}

⭐ Viva Tip: Base condition stops recursion

7
UNIT 6: TREES

Program 6: Binary Search Tree – Inorder Traversal

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *left, *right;
};
struct node* newNode(int x){
struct node* n = (struct node*)malloc(sizeof(struct node));
n->data = x;
n->left = n->right = NULL;
return n;
}
void inorder(struct node* root){
if(root!=NULL){
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main(){
struct node* root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
inorder(root);
return 0;
}

⭐ Viva Tip: Inorder traversal gives sorted order in BST

🎯 LAST-MINUTE 1-DAY REVISION NOTES

Must Remember Definitions

• Stack → LIFO
• Queue → FIFO
• BST → Left < Root < Right
• Hashing → Key to address mapping

One-line Comparisons

• Array vs Linked List → Fixed vs Dynamic

• Linear vs Binary Search → Slow vs Fast
• Stack vs Queue → LIFO vs FIFO

8
Guaranteed Questions

• Stack operations
• Infix to Postfix
• Circular Queue
• BST traversal
• Hashing collision methods

✅ This section is fully viva-ready, lab-exam ready, and semester-exam safe.

➕ ADDITIONAL IMPORTANT PROGRAMS (OPTION C)

UNIT 2: STACK APPLICATION

Program 7: Infix to Postfix Conversion using Stack

Algorithm: 1. Scan infix expression from left to right 2. If operand, add to postfix 3. If operator, pop
higher precedence operators from stack 4. Push current operator 5. Pop remaining operators

#include <stdio.h>
#include <ctype.h>
char stack[20];
int top = -1;
void push(char x){ stack[++top] = x; }
char pop(){ return stack[top--]; }
int priority(char x){
if(x=='+'||x=='-') return 1;
if(x=='*'||x=='/') return 2;
return 0;
}
int main(){
char exp[20], x;
int i=0;
printf("Enter infix expression: ");
scanf("%s", exp);
while(exp[i] != ''){
if(isalnum(exp[i]))
printf("%c", exp[i]);
else{
while(priority(stack[top]) >= priority(exp[i]))
printf("%c", pop());
push(exp[i]);
}
i++;
}
while(top != -1)

9
 printf("%c", pop());
return 0;
}

⭐ Viva Tip: Stack handles operator precedence

UNIT 4: QUEUE USING STACK

Program 8: Queue using Two Stacks

#include <stdio.h>
int s1[10], s2[10];
int top1=-1, top2=-1;
void push1(int x){ s1[++top1]=x; }
int pop1(){ return s1[top1--]; }
void push2(int x){ s2[++top2]=x; }
int pop2(){ return s2[top2--]; }
void enqueue(int x){ push1(x); }
void dequeue(){
if(top2==-1)
while(top1!=-1)
push2(pop1());
printf("Deleted = %d", pop2());
}
int main(){
enqueue(10);
enqueue(20);
dequeue();
return 0;
}

⭐ Viva Tip: FIFO achieved using two LIFO stacks

UNIT 3: LINKED LIST OPERATIONS

Program 9: Traverse and Delete Node (Singly Linked List)

#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
int main(){
struct node *head=NULL,*temp,*prev;
int key;

10
 head = (struct node*)malloc(sizeof(struct node));
head->data=10;
head->next=(struct node*)malloc(sizeof(struct node));
head->next->data=20;
head->next->next=NULL;
printf("Linked List: ");
temp=head;
while(temp!=NULL){
printf("%d ", temp->data);
temp=temp->next;
}
printf("
Enter value to delete: ");
scanf("%d", &key);
temp=head;
while(temp!=NULL && temp->data!=key){
prev=temp;
temp=temp->next;
}
prev->next=temp->next;
free(temp);
printf("Node deleted successfully");
return 0;
}

⭐ Viva Tip: Traversal uses while loop and pointers

UNIT 8: HASHING

Program 10: Hashing using Linear Probing

#include <stdio.h>
#define SIZE 10
int hash[SIZE];
int main(){
int key, index, i;
for(i=0;i<SIZE;i++) hash[i]=-1;
printf("Enter keys (-1 to stop): ");
while(1){
scanf("%d", &key);
if(key==-1) break;
index = key % SIZE;
while(hash[index] != -1)
index = (index+1) % SIZE;
hash[index] = key;
}
printf("Hash Table:
");
for(i=0;i<SIZE;i++)

11
 printf("%d -> %d
", i, hash[i]);
return 0;
}

⭐ Viva Tip: Linear probing resolves collision

✅ Now your notes contain ALL major programs asked in exams and labs.

12