MCA-102
Data and File Structures
The structures everything else is stored in — arrays, lists, stacks, queues, trees, heaps and graphs — plus hashing and file organisation.
- Semester
- Semester 2
- Credits
- 3
- Scheme
- 3 lectures a week
- Contact hours
- 45 across four units
- Category
- Core
What the paper is
Data and File Structures is the paper the rest of your programming rests on, and the one whose material reappears in every interview you will ever sit. It is organised by shape: linear structures first, then trees, then graphs, then what happens when the data is too large to keep in memory at all.
That last part is what the “File Structures” in the title means, and it is the half students routinely forget is in the paper. Sequential, indexed sequential and relative file organisation, and the external merge algorithms, are examined alongside the in-memory structures and follow the same logic — the cost model has simply changed from comparisons to disk accesses.
Unit I carries fourteen contact hours, more than any other unit in the first year. The scheme is telling you something: sorting, searching and the linear structures are not preliminaries to get past, they are the bulk of the paper.
What to concentrate on
- Be able to derive, not recall, the complexity of every sort in Unit I. “Why is merge sort O(n log n) and insertion sort O(n²)” is the shape of question that recurs, and deriving it also prepares Unit I of Design and Analysis of Algorithms next semester.
- For trees, AVL rotations and B-tree insertion and deletion are the reliable numerical questions — traced on given input, marks awarded for the intermediate states. Practise them on paper rather than reading them.
- Graph algorithms here (BFS, DFS, Kruskal, Prim, Dijkstra, Floyd-Warshall, topological sort) are the same ones analysed formally in MCA-201. Learning to execute them now makes that paper considerably shorter.
Syllabus, unit by unit
Summarised from the approved scheme. Hours are the contact hours the scheme allots, which is a fair guide to where the marks sit.
Unit I · Linear data structures
14 hours- Classification of data structures and abstract data types
- Arrays: single and multi-dimensional, memory representation, address calculation, sparse matrices
- Linear and binary search; selection, bubble, insertion, radix, merge and shell sort
- Linked lists: dynamic versus static allocation, singly, doubly, header and circular lists, polynomial arithmetic
- Stacks and queues: implementation, types of queues, multi-stacks and multi-queues
- Applications of stacks: Polish and reverse Polish notation, quick sort, recursion
Unit II · Trees and heaps
12 hours- Trees: notation and terminology, binary trees, binary search trees and their operations
- Tree traversals, recursive and stack-based non-recursive; threaded binary trees, tree sort, tries
- AVL trees: properties, insertion and deletion
- M-way trees: B trees, B+ trees and B* trees
- Heaps: structural properties, heapify, heap sort, priority queue implementation
Unit III · Graphs
10 hours- Representation of graphs: adjacency matrix and linked representation
- Traversals: breadth first search, depth first search, connected components
- Spanning trees: Kruskal's and Prim's algorithms
- Shortest paths: Dijkstra's algorithm, Floyd-Warshall, topological sort
- Case studies: dynamic graphs, social network graphs and sparse graphs
Unit IV · Hashing and file structures
9 hours- Hashing: hash tables and functions, collision resolution by chaining and open addressing
- File organisation: sequential, index sequential and relative
- Creating, updating and retrieving from sequential files; handling files in C — seeking, positioning, reading and writing binary files
- External sorting: merging ordered and unordered files, natural merge, balanced merge, k-way and polyphase merge
How it is examined
- Question 1 is compulsory, covers the whole syllabus, and is made of objective or short-answer questions. It carries 12 marks.
- The rest of the paper is four units matching the four above. Each unit sets two questions and you attempt one, so there are four more answers at 12 marks each.
- Examiners are asked to map every question to a course outcome using Bloom's taxonomy, which is why questions are phrased as “apply”, “analyse” or “evaluate” rather than only “explain”.
The pass mark is 40 out of 100 in every paper.
Learning objectives
- Familiarisation with data and file structures and operations on them — insertion, deletion, searching and sorting
- Understanding and implementing arrays, linked lists, stacks, queues, trees, graphs and files
- Identifying a suitable data structure to model data in real-world applications
Assumed beforehand
- Discrete Structures
- Programming skills
Paired in the scheme with MCA-162 Data and File Structures Lab.
Books it is taught from
- TB1E. Horowitz and S. Sahni, “Fundamentals of Data Structures in C”, Universities Press, 2nd edition, 2008
- TB2Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, Pearson Education India, 4th edition, 2014
- TB3Mary E. S. Loomis, “Data Management and File Structure”, PHI, 2nd edition, 2009
Notes for MCA-102
Lecture notes, question papers and assignments filed against MCA-102 are in the library. Everything there has been checked by a moderator before it appears, and an account is free — new ones are approved by hand, which is what keeps the shelf clean.