Data Structures Question Paper

Data Structures




Data Structures

Subject Code Subject Name Credits
MCA201 Data Structures 04
Subject

Code

Subject Name Teaching

Scheme

Credits

Assigned

Theory Pract Tut Theory TW Tut. Total
MCA201 Data Structures 04 04 04
Subject Code Subject Name Examination Scheme
MCA 201 Data Structures Theory Marks TW Pract Oral Total
Internal Assessment End Semester Exam
Test1 (T1) Test2 (T2) Average of T1 & T2
20 20 20 80 100

 

Pre-requisites:

Understanding of Algorithms

 

Course Educational Objectives (CEO):

 

CEO 1 To teach efficient storage mechanisms of data for an easy access.
CEO 2 To design and implement various basic and advanced data structures.
CEO 3 To introduce various techniques for representation of the data in the real world.

 

Course Outcomes: At the end of the course, the students will be able to :

 

MCA201.1 Analyze and compute efficiency of various algorithms.
MCA201.2 Effectively choose the data structure that efficiently model the information in a problem
MCA201.3 Describe how Linear data structures are represented in memory and used by algorithms and their applications
MCA201.4 Identify the benefits of Non-linear Data Structures and their applications

 

 

 

 

 

 

Syllabus

 

Sr Module Detailed Contents Hours
1 Introduction to Data Structures & Algorithms Introduction    of    Data    structures,    Abstract    Data Types,

Performance Analysis: Space Complexity, Time Complexity, Asymptotic Notations (Big O, Omega, Theta), Performance measurement, Divide and Conquer, Back Tracking Method, Dynamic programming

4
2 Sorting         and searching algorithms Bubble sort, Insertion sort, Radix Sort, Quick sort, Merge sort,

Heap sort, Selection sort, shell Sort, Linear Search, Sequential search, Binary search

6
3 Hashing Different     Hashing      Techniques,      Address     calculation

Techniques, Common hashing functions, Collision resolution techniques: Linear probe, Quadratic probe, Key offset.

Rehashing, Double hashing, Link list addressing.

8
4 Linear        Data Structures Stack Definition, Operations, Implementation of Stacks  (Array and Linked list) and applications-Evaluation of postfix expression, Balancing   of parenthesis

Queue: Definition, Operations, Implementation of simple queue (Array and Linked list) and applications of queue-BFS Types    of    queues:     Circular,     Double    ended,    Priority, Implementation using linked list

Types of Linked List: Singly, Doubly and Circular Linked list Definition, Operations (Insert, delete, traverse, count, search ) Applications of Linked List: Polynomial Addition and Subtraction

14
5 Non-linear Data Structures Tree Definition and concepts,

General Tree- Definition, Insertion and Deletion into general tree,

Binary Tree- Definition, Insertion and Deletion into binary tree,

Traversal of a binary tree, Reconstruction of a binary tree  from traversal, Conversion of general tree into binary tree, Huffman tree, Expression tree, Binary threaded three

Binary Search Tree- Definition, Operation, Implementation AVL tree- Definition, AVL tree rotation with examples, Heaps-Definition, Operations (insertion, delete, build)

M way Tree- Introduction, B tree-definition and examples and B*

14
6 Graphs Definition,   Types,   Operations,   Representation,  Networks,

Traversals of graph, Minimum spanning tree, Kruskal‟s Algorithm, Prim‟s Algorithm, Warshall‟s Algorithm,Shortest path algorithm-dijsktra‟s algorithm

6

 

Reference Books

  1. Richard F Gilberg Behrouz A Forouzan , “Data Structure A Pseudocode Approach with C“. Second edition

 

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein, “Introduction to ALGORITHMS”, PHI, India Second Edition.
  2. Shaum‟s Outlines Data Structure Seymour Lipschutz TMH
  3. Michael T.Goodrich “Data Structures and Algorithms in C++-“ Wiley Publications

 

Theory paper will be of 80 marks. Internal assessment will be of 20 marks, which will be the average of two tests (T1 and T2) of 20 marks each.