Unit 1 of 1 · BCA Sem 3

Unit 1: Searching, sorting, trees and graphs

Data Structures-II Laboratory notes · PTU syllabus (UGCC2511)

3 min read4 topics8 exam questions
On this page
  1. Unit summary
  2. Sorting programs
  3. Binary tree traversals
  4. Graph traversals and shortest path
  5. Hashing
  6. Key terms
  7. Quick revision
  8. Important questions

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
1

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); }
}
2

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.

Example

Traversals of one tree: root 50, left child 30 (children 20 and 40), right child 70 (children 60 and 80). Inorder: 20 30 40 50 60 70 80. Preorder: 50 30 20 40 70 60 80. Postorder: 20 40 30 60 80 70 50.

Exam tip

Inorder traversal of a binary search tree always gives the keys in ascending order.

3

Topic 3

Graph traversals and shortest path

  • Store the graph as an adjacency matrix int adj[MAX][MAX] and keep a visited[] 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.

Example

BFS and DFS from A: edges are A–B, A–C, B–D, C–D, D–E. BFS (queue) visits A, B, C, D, E level by level. DFS (stack or recursion) visits A, B, D, C, E, going deep first.

Exam tip

BFS uses a queue; DFS uses a stack. BFS finds the shortest path in an unweighted graph.

4

Topic 4

Hashing

ProcessHash table with linear probing
  1. 1Compute index

    h = key % SIZE

  2. 2Slot empty?

    Store the key

  3. 3Slot taken?

    Try (h + 1) % SIZE, then the next

  4. 4Table full?

    Report overflow

  5. 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.

Example

Linear probing: table size 10 and h(k) = k mod 10. Insert 23 → index 3. Insert 43 → index 3 is full, so index 4. Insert 13 → 3 and 4 are full, so index 5. Insert 27 → index 7.

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

  1. Q1.What is the role of the visited array in graph traversal?
  2. Q2.Why must data be sorted for binary search?
  3. Q3.What does the partition function return in quick sort?
  4. Q4.How does linear probing resolve collisions?

Long-answer questions

  1. Q1.Write a program to sort an array using quick sort and explain the partition step.
  2. Q2.Write a program to create a binary search tree and display its three traversals.
  3. Q3.Implement BFS and DFS for a graph represented by an adjacency matrix.
  4. 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.

WhatsApp us