Course Name
MCA (Master of Computer Application)
Subject Code MC0068 (Data Structures using C)
Get Questions
PART  A
PART  B
PART  C
Data Structures using C Syllabus.
Part 1: Arrays, Pointers and Structures
Introduction; Definition and concept of an Array: Array Used in „C‟
Language, Single – Dimensional Arrays (One Dimensional Array), Two Dimensional
Arrays. [Matrix]; Pointers; Declaring a pointer variable,: Pointer Operators;
Pointers and Arrays; Pointers used in function; Pointers used in an Array;
Structures: Declaration of structure, Initialization of structure, Processing of
Structure, Structure used with an Array.
Part 2 Overview of Data Structures
Introduction: What is a Data Structure?, Definition of data structure, The
Abstract Level, The Application Level, Implementation Level; Data Types and
Structured Data Type: Common Structures, Abstract Data Types, Properties of
Abstract Data Types, Generic Abstract Data Types, Programming with Abstract Data
Types; Pre and Post Conditions: Preconditions, Post conditions, Checking Pre &
Post Conditions, Implementation Checks Preconditions; Linear Data Structure: The
Array Data Structure, Using an Array and Lists as a Data Structure, Elementary
Data Structures; What the application needs ?;
Implementation methods; Non Linear Data Structures: Trees, Binary Tree, Hash
Tables.
Part 3: Overview of Stack
Introduction; Operations of Stack;Insert / Push operation; Delete/pop
operation; Display; Stack implementation using arrays; Applications of stack;
Stacks using structures; Sample C programs to represents the Stack
Implementation.
Part 4: Overview of Queues
Introduction; Queues and its Operations; Different types of queues: Ordinary
queue, Disadvantage of ordinary queue, Double ended queue (Deque), Circular
queue; Sample C programs to represents the Queue Implementation.
Part 5: Linked Lists
Introduction; Linear list; Linked list: Typical basic linkedlist
operations, SinglyLinked Lists; Circular singly linked list: Insert a node at
the front end, Insert a node at the rear end, Delete a node from the front end,
Delete a node from the rear end; Doubly linked lists: Insert a node at the front
end, Insert a node at the rear end, Delete a node from the front end.
Part 6 : Trees
Introduction; Overview of Tree Concept; Binary tree: Strictly binary tree,
Complete binary tree, Almost complete binary tree, Storage representation of a
binary tree; Various operations on binary trees using linked representation:
Insertion Operation, Traversals;
Binary search tree (BST): Insertion Operation, Searching, Other operations, To
find maximum value in a tree BST, To find minimum value in a BST, Height of
tree, Count nodes in a tree, Count leaves in a tree, Delete a node from the
tree.
Part 7: Graphs
Introduction; Overview of Graphs; Adjacency lists & Adjacency Matrix:
Adjacency lists, Adjacency Matrix; Depth – First Traversal; Breadth – First
Traversal; Spanning Trees.
Part 8: Searching Methods
Introduction; Basics Searching Techniques; Algorithmic Notation: Sequential
Search [Linear search], Binary Search; Illustration of C programmes.
Part 9: Sorting Methods
Introduction; Overview of Sorting Methods; How do you sort?; Evaluating a
Sorting Algorithms: Stability on Sorting algorithm; Internal Sorting: Insertion
Sort, Bubble Sort, Selection Sort, Shell Sort, Quick Sort, Tree Sort; External
Sorts: Merge Sort, 2Way Merge Sort.
Part 10: Advanced Topics in Trees and Their Applications
Introduction; Analyzing the BST Search Algorithm; Inserting Nodes into a BST;
The Order of Insertion Determines the BST's Topology; Deleting Nodes from a BST;
Traversing the Nodes of a BST: Preorder Traversal, Inorder Traversal, Postorder
Traversal; The Cost of Recursion; Binary Search Trees in the RealWorld; BigO
Notation: Application of BigO notation to algorithm analysis; Big and
Big:Properties of the sets O(f(n)) and (f(n)), Other useful mathematical
formulae; Height Balanced Trees: AVL Trees, RedBlack Trees, Lemma, Insertion
into a redblack tree, Deletions from a RedBlack tree; The AA tree; AVL Trees:
Definition, Worst case height of an AVL tree with n Nodes; The Binary Heap:
Definition, Insertions into a Binary Heap, Deletions from a Binary Heap,
Analysis of Insertion Algorithm, Build Heap  building a tree from a collection
of forests.
Part 11: Minimum Spanning Trees and Algorithms
Introduction; Spanning Trees: Minimum spanning trees, Why minimum spanning
trees; How to find minimum Spanning Tree?: Lemma; Kruskal's Algorithm; Prim's
algorithm; Finding Shortest Paths using BFS; Relaxation; Dijkstra Algorithm;
BellmanFord Algorithm; Singlesource shortest paths in Directed Acyclic Graph (DAG);
Floyd Warshall and Variants:Transitive Hull, MiniMax Distance, MaxiMin Distance,
Safest Path; Other Graphs: Graph Transpose Problem, Euler Cycle, Euler Path,
Topological Sort Problem, Strongly Connected Components problem.
Part 12: Graphs and their Applications – I
Introduction to Graphs; Representation; Examples of Graph Problems:
Telecommunication, Sample Problem: Riding The Fences, Knight moves, Overfencing;
Terminology; Directed Graph; Paths; Graph Representation: Edge List, Adjacency
Matrix, Adjacency List, Implicit Representation; Connectedness; Sub graphs;
Special Graphs: Rooted tree, Forest, Complete Graph, Bipartite Graph; Uninformed
Search: Breadthfirst search, Uniformcost search, Depthfirst search,
Depthlimited search , Iterative deepening search, Bidirectional search.
Part 13: Graphs and their Applications – II
Introduction; Depth First Search (DFS) Algorithm: Sample Problem: n Queens
[Traditional], Depth First Search (DFS) Implementation, Complexity; Breadth
First Search (BFS): Sample Problem: Knight Cover [Traditional], Breadth First
Search (BFS) Implementation, Complexity; Depth First with Iterative Deepening
(DFID): Complexity; Comparison of DFS, BFS & DFS+ID; Sample Problems:
Superprime Rib, Betsy's Tour , Udder Travel , Desert Crossing, Addition Chains;
Informed Search: Best First Search, A* Search; An Application of Graph;
Amortized Analysis: Aggregate Analysis, The potential method, Properties of the
Potential Function, The Dynamic Hash Table, A Dynamic Hash Table that both
expands and contracts.
Part 14: Splay Trees (Selfadjusting Search Trees)
Introduction; Splay Trees; Access lemma; Balance Theorem; Strong Access
Lemma; Static Optimality Theorem ; Static Finger Theorem; Other Theorems :
Working Set Theorem, Sequential Access Theorem, Dynamic Finger Theorem, Dynamic
Optimality Conjecture, Insertion, Join, Deletion.
Part 15: File Structures
Introduction; Logical or Physical Organization and Data Independence; A
language for describing file structures; Basic terminology; Sequential files;
Inverted files; Indexsequential files; Multilists; Cellular multilists; Ring
structures; Threaded lists; Trees; Scatter storage or hash addressing; Clustered
files; B  Tree File Organization; B Tree Index Files; Dynamic Hashing: How
does it work?.
