MCA-203 Data Structure:

Prerequisites: Array, Structure, pointers, pointer to structure, functions, parameter passing, recursion.

UNIT-I

Stack and Queue: contiguous implementations of stack, various operations on stack, various polish notations-infix, prefix, postfix, conversion from one to another-using stack; evaluation of post and prefix expressions. Contiguous implementation of queue: Linear queue, its drawback; circular queue; various operations on queue; linked implementation of stack and queue- operations.

UNIT-II

General List: list and it’s contiguous implementation, it’s drawback; singly linked list-operations on it;doubly linked list-operations on it; circular linked list; linked list using arrays.

UNIT-III

Trees: definitions-height, depth, order, degree, parent and child relationship etc;

Binary Trees- various theorems, complete binary tree, almost complete binary tree;

Tree traversals-preorder, in order and post order traversals, their recursive and non recursive implementations; expression tree- evaluation; linked representation of binary tree-operations. Threaded binary trees; forests, conversion of forest into tree. Heap-definition.

UNIT-IV

Searching, Hashing and Sorting: requirements of a search algorithm; sequential search, binary search,indexed sequential search, interpolation search; hashing-basics, methods, collision, resolution of collision,chaining; Internal sorting- Bubble sort, selection sort, insertion sort, quick sort, merge sort on linked and contiguous list, shell sort, heap sort, tree sort.

UNIT-V

Graphs: related definitions: graph representations- adjacency matrix, adjacency lists, adjacency multilist;traversal schemes- depth first search, breadth first search; Minimum spanning tree; shortest path algorithm; kruskals & dijkstras algorithm.

Miscellaneous features Basic idea of AVL tree- definition, insertion & deletion operations; basic idea of B-tree- definition, order, degree, insertion & deletion operations;

B+-Tree- definitions, comparison with B-tree; basic idea of string processing.

BOOKS:

1. Kruse R.L. Data Structures and Program Design in C; PHI

2. Aho “Data Structure & Algorithms”.

3. Trembly “Introduction to Data Structure with Applications”.

4. TennenBaum A.M. & others: Data Structures using C & C++; PHI

5. Horowitz & Sawhaney: Fundamentals of Data Structures, Galgotia Publishers.

6. Yashwant Kanetkar, Understanding Pointers in C, BPB.

---------------------------------------------------------------------------------------------

click here for MCA FULL SYLLABUS SEMESTER WISE WITH NOTES

---------------------------------------------------------------------------------------------