Unit 1: Searching, sorting, trees and graphs
Data Structures-II Laboratory notes · PTU syllabus (UGCC2511)
On this page
Unit summary
This lab implements searching, sorting, tree traversals, graph traversals, shortest paths and hashing in C. These are the classic programs asked in practical exams and coding interviews.
After this unit you can
- Implement linear and binary search and four sorting algorithms
- Build a binary tree and traverse it in preorder, inorder and postorder
- Implement DFS, BFS and a shortest path algorithm
- Implement a hash table with collision handling
PTU syllabus topics
- Linear and binary search
- bubble/selection/insertion/quick sort
- binary tree preorder/inorder/postorder traversal
- depth-first and breadth-first search in graphs
- shortest path algorithm
- hashing implementation
Data required
Any order
Must be sorted
Time
O(n)
O(log n)
Method
Check each element in turn
Halve the search range each step
Best for
Small or unsorted lists
Large sorted lists
Topic 1
Sorting programs
cvoid bubble(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
}
void insertion(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
}
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; }
int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
return i + 1;
}
void quick(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quick(a, lo, p - 1); quick(a, p + 1, hi); }
}Topic 2
Binary tree traversals
Create nodes with malloc, link them, then call recursive preorder, inorder and postorder functions. For a BST, insert recursively: go left if the value is smaller, right if larger.
Topic 3
Graph traversals and shortest path
- Store the graph as an adjacency matrix
int adj[MAX][MAX]and keep avisited[]array. - DFS: recursive — mark the vertex visited, print it and call DFS on each unvisited neighbour.
- BFS: use a queue — enqueue the start vertex; repeatedly dequeue, print and enqueue unvisited neighbours.
- Dijkstra: keep
dist[], pick the unvisited vertex with minimum distance each round and relax its neighbours.
Topic 4
Hashing
- 1Compute index
h = key % SIZE
- 2Slot empty?
Store the key
- 3Slot taken?
Try (h + 1) % SIZE, then the next
- 4Table full?
Report overflow
- 5Search
Probe the same way until found or an empty slot
Exam tip
Count comparisons in your search and sort programs and report them — it shows the complexity practically and impresses examiners.
Key terms
- visited array
- Tracks which vertices have been processed
- Partition
- Rearranging around a pivot in quick sort
- Linear probing
- Trying the next slot after a collision
- Adjacency matrix
- A 2-D array storing graph edges
Quick revision
- Binary search only on sorted arrays.
- Quick sort: partition, then recurse on both sides.
- DFS recursion/stack; BFS queue; both need visited[].
- Linear probing: (h + i) % SIZE.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What is the role of the visited array in graph traversal?
- Q2.Why must data be sorted for binary search?
- Q3.What does the partition function return in quick sort?
- Q4.How does linear probing resolve collisions?
Long-answer questions
- Q1.Write a program to sort an array using quick sort and explain the partition step.
- Q2.Write a program to create a binary search tree and display its three traversals.
- Q3.Implement BFS and DFS for a graph represented by an adjacency matrix.
- Q4.Implement a hash table using linear probing with insertion and search.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures-II Laboratory, or to ask about studying BCA at Synetic.