Data Structures Question Paper

[gview file=”http://educlash.com/wp-content/uploads/2016/10/DS.pdf”]




Data Structures

Subject CodeSubject NameCredits
MCA201Data Structures04
Subject

Code

Subject NameTeaching

Scheme

Credits

Assigned

TheoryPractTutTheoryTWTut.Total
MCA201Data Structures040404
Subject CodeSubject NameExamination Scheme
MCA 201Data StructuresTheory MarksTWPractOralTotal
Internal AssessmentEnd Semester Exam
Test1 (T1)Test2 (T2)Average of T1 & T2
20202080100

 

Pre-requisites:

Understanding of Algorithms

 

Course Educational Objectives (CEO):

 

CEO 1To teach efficient storage mechanisms of data for an easy access.
CEO 2To design and implement various basic and advanced data structures.
CEO 3To 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.1Analyze and compute efficiency of various algorithms.
MCA201.2Effectively choose the data structure that efficiently model the information in a problem
MCA201.3Describe how Linear data structures are represented in memory and used by algorithms and their applications
MCA201.4Identify the benefits of Non-linear Data Structures and their applications

 

 

 

 

 

 

Syllabus

 

SrModuleDetailed ContentsHours
1Introduction to Data Structures & AlgorithmsIntroduction    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
2Sorting         and searching algorithmsBubble sort, Insertion sort, Radix Sort, Quick sort, Merge sort,

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

6
3HashingDifferent     Hashing      Techniques,      Address     calculation

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

Rehashing, Double hashing, Link list addressing.

8
4Linear        Data StructuresStack 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
5Non-linear Data StructuresTree 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
6GraphsDefinition,   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.