Scribd
Upload
6 views4 pages

Data Structures Revision Sheet

This document is a last-minute revision sheet for Data Structures in the B.Sc CS 1st Year curriculum, covering key concepts such as arrays, strings, linked lists, stacks, queues, trees, graphs, Dijkstra's algorithm, minimum cost spanning trees, and sorting algorithms. It includes definitions, operations, examples, and tips for exam writing, emphasizing the importance of clear diagrams and stepwise solutions. The content is structured to aid quick review and understanding of fundamental data structure principles and algorithms.

Uploaded by

Yuvraj Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views4 pages

Data Structures Revision Sheet

This document is a last-minute revision sheet for Data Structures in the B.Sc CS 1st Year curriculum, covering key concepts such as arrays, strings, linked lists, stacks, queues, trees, graphs, Dijkstra's algorithm, minimum cost spanning trees, and sorting algorithms. It includes definitions, operations, examples, and tips for exam writing, emphasizing the importance of clear diagrams and stepwise solutions. The content is structured to aid quick review and understanding of fundamental data structure principles and algorithms.

Uploaded by

Yuvraj Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

B.

Sc CS 1st Year Data Structures – Last


Minute Revision Sheet
1 Arrays
1️⃣
Definition:
Collection of elements of same type stored in contiguous memory.

Operations:
Traversal, Insertion, Deletion, Searching, Sorting

1D Example: [10, 20, 30] → Access A[1] = 20


2D Example:
123
456
789
Access A[2][0] = 7
Sum row/column → exam question style

2️⃣Strings
- Array of characters
- Ends with \0
- Operations: Length, Concatenate, Copy, Compare
Example: str1 = "HELLO", str2 = "WORLD"
Concatenate → "HELLOWORLD"

3️⃣Linked Lists
Types:
- Singly → next pointer only
- Doubly → prev + next
- Circular → last node points to first
- Circular Doubly → both directions + circular

Node Structure:
Singly: [Data | Next]
Doubly: [Prev | Data | Next]

Example (Doubly Insert 10,20,30):


NULL <- 10 <-> 20 <-> 30 -> NULL
Operations: Traversal, Insertion, Deletion, Search
Tip: Use head to start; Circular → no NULL pointers

4️⃣Stack & Queue (Basics)


Stack: LIFO
- Operations: Push, Pop, Peek
- Implementation: Array / Linked List

Queue: FIFO
- Operations: Enqueue, Dequeue, Front
- Types: Simple Queue, Circular Queue
Example Stack: [Top] 30 20 10 [Bottom]

5️⃣Trees
Binary Tree Traversals:
Inorder → Left → Root → Right
Preorder → Root → Left → Right
Postorder → Left → Right → Root
Level Order → Level by Level (BFS)

Example Tree:
5
/\
3 7
Inorder → 3,5,7
Preorder → 5,3,7
Postorder → 3,7,5
Level Order → 5,3,7

6️⃣Graphs
Definition: Set of vertices + edges (V,E)
Types: Directed, Undirected, Weighted, Unweighted, Cyclic, Acyclic
Representations: Adjacency Matrix / Adjacency List
Traversals: BFS (Queue), DFS (Stack/Recursion)

7️⃣Dijkstra’s Algorithm
Use: Shortest path from source to all vertices (weights ≥0)

Steps:
1. Initialize dist[source] = 0, others = ∞
2. Pick unvisited vertex with min distance
3. Update neighbors: dist[v] = min(dist[v], dist[u]+weight(u,v))
4. Mark visited, repeat

Example Table Style:


Vertex | dist[] | Visited
A | 0 | No
B | ∞ | No
…|…|…
Diagram: Nodes as circles, edges with weights

8️⃣Minimum Cost Spanning Tree (MCST)


Prim’s Algorithm (Grow Tree): Start from any vertex → add smallest edge connecting
visited→unvisited → repeat
Kruskal’s Algorithm (Edge-wise): Sort all edges ascending → pick edge if no cycle → repeat
until V-1 edges

Example Graph:
(A)
/
2/
/
(B)-------(C)
\
3
\
(E)
|
1
|
(D)

Prim’s MCST Edges: A—B, B—C, C—E, E—D → Total weight = 7


Kruskal’s MCST Edges: B—C, D—E, A—B, C—E → Total weight = 7
Tip: Always show stepwise selection table in exam for full marks

9️⃣Sorting Algorithms (Stepwise)


- Bubble Sort: Swap adjacent elements if wrong order
- Selection Sort: Select min element & swap
- Insertion Sort: Insert element at correct position
- Merge Sort: Divide → Sort → Merge
- Quick Sort: Pivot → Partition → Recur

Example Bubble Sort [5,2,9,1]:


Pass1 → [2,5,1,9]
Pass2 → [2,1,5,9]
Pass3 → [1,2,5,9] ✅ Sorted

1 Exam Writing Tips


0️⃣
1. Tables & Stepwise Solutions: Always show updates for Linked List, Dijkstra,
Prim/Kruskal, Sorting
2. Diagrams: Simple circles for nodes, edges labeled with weights; arrows for directed edges
3. Definitions: Write short, exact definitions first
4. Highlight MCST / Shortest Paths in diagrams for clarity
5. Start Linked List problems with head, mark prev/next properly

You might also like