NAME COLLEGE OF TECHNOLOGY, BHOPAL
DEPARTMENT OF MCA
COURSE FILE
Program : Master of Computer Application
Semester : II
Course Code : MCA 203
Subject Name : Data Structure
Prepared By:
CONTENTS
1. SYLLABUS
2. LIST OF BOOKS
3. TIME TABLE
4. LECTURE PLAN
5. TUTORIAL SHEET
6. UNIT TEST PAPER
7. MID SEM PAPER
8. INSTRUCTIONAL PLAN
9. TACTICAL PLAN
10. QUESTION PAPER
11. ATTENDANCE SHEET
12. CLASS NOTES
SYLLABUS
Max / Min / Max / Min / Max / Min
MCA-203 / Data Structure / 3 / 1 / 4 / 100 / 40 / 50 / 30 / 50 / 25 / 200
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 children 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; kruskal & dijkstra 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
- Kruse R.L. Data Structures and Program Design in C; PHI
- Aho “Data Structure & Algorithms”.
- Trembly “Introduction to Data Structure with Applications”.
- TennenBaum A.M. & others: Data Structures using C & C++; PHI
- Horowitz & Sawhaney: Fundamentals of Data Structures, Galgotia Publishers.
- Yashwant Kanetkar, Understanding Pointers in C, BPB.
Note : Paper is to be set unit wise with internal choice.
List of 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.
Lecture Plan
Subject Code / MCA-203 / Semester / II
Department / Master of Computer application / Branch / MCA
Lect. / Topics to be covered / Date of Completion / Remark
1. / Prerequisites: Array, Structure, Pointers / R2:28-55
R4:36- 58
2. / Prerequisites: Pointer to Structure, Functions / R4:62-68
3. / Prerequisites: Parameter Passing, Recursion / R1-88
R4:68-133,150
Unit-I
4. / Stack: Contiguous Implementations of Stack, Various Operations on Stack / R1:74-77- 79
R2-67 R4:93-96
5. / Various Polish Notations-Infix, Prefix, Postfix, / R2:94-95
R4:111-114
6. / Conversion From One to Another-Using Stack; / R1:550- 551
R4-118
7. / Evaluation of Post & Prefix Expressions / R1:535-545
R4:114-115
8. / Queue: Contiguous Implementation of Queue: Various Operations on Queue / R2:70-74
R4:190-192-196
9. / Linear Queue, Its Drawback; Circular Queue / R2:70-74
R4:219-229-245
10. / Linked Implementation Of Stack & Queue- Operations / R4:207- 210
11. / Linked Implementation Of Stack & Queue- Operations / R4:207- 210
Unit-II
12. / General List: List & It’s Contiguous Implementation, It’s Drawback / R2:54-56
R4:202-203
13. / Singly Linked List-Operations on it; / R4:211-214-219
14. / Doubly Linked List-Operations on it; / R2:64-65
R4-253
15. / Circular Linked List / R4:245-246
16. / Linked List Using Arrays / R2:55- 56
R4:219- 222
Unit-III
17. / Trees: Definitions-Height, Depth, Order, Degree, Parent And Child Relationship Etc; / R2:89-91
R4:265-21,401
18. / Binary Trees- Various Theorems / R4:265-321,270
19. / Complete Binary Tree, Almost Complete Binary Tree / R2:89-120 R4:267- 496
20. / Tree Traversals-Preorder, Inorder & Postorder Traversals / R4:272-290,294
21. / Their Recursive & Non Recursive Implementations / R4:162-169
22. / Expression Tree- Evaluation / R2-94
23. / Linked Representation of Binary Tree-Operations / R4:278-286-292
24. / Threaded Binary Trees; / R4: 289-290
25. / Heap-Definition. / R2:393-406
Unit-IV
26. / Searching: Requirements of A Search Algorithm; Sequential Search, Binary Search, / R4:138- 148,345
27. / Indexed Sequential Search, Interpolation Search / R4:408- 413
28. / Hashing: Hashing-Basics, Methods / R2:126-152,176 R4:386- 484
29. / Collision, Resolution of Collision, Chaining / R2:139- 145 R4:486-522
30. / Sorting: Internal Sorting- Bubble Sort, Selection Sort / R2:267-306
R4:345- 355-367
31. / Insertion Sort, Quick Sort / R4:381- 393,358
32. / Merge Sort on Linked and Contiguous List / R4:156-388-392
33. / Shell Sort, Heap Sort, Tree Sort. / R2:267-306 R2:363-375
34. / Shell Sort, Heap Sort, Tree Sort. / R4:367-375,382
Unit-V
35. / Graphs: Related Definitions: Graph Representations / R4:531 R2:17-26
36. / Adjacency Matrix, Adjacency Lists, Adjacency Multi-list / R2:161- 213-246 R4:536- 557-563
37. / Traversal Schemes- Depth First Search, Breadth First Search; / R2:253-256
R4:585-589
38. / Minimum Spanning Tree; Shortest Path Algorithm; / / R2:225- 247 R4:542- 590
39. / Kruskals & Dijkstras Algorithm / R2:218- 224-250 R4:544- 590
40. / Miscellaneous Features Basic Idea of AVL Tree Definition, / R2:210
R4-429
41. / Insertion & Deletion Operations; / R4: 430-436
42. / Basic Idea of B-Tree- Definition, Order, Degree, / R4-451
43. / Insertion & Deletion Operations / R2:211- 383
R4-453
44. / B+-Tree- Definitions, Comparison With B-Tree / R4:443-447,476
45. / Basic Idea Of String Processing. / R1:210-213
LIST OF BOOKS
TEXT BOOKS
R1. Kruse R.L. Data Structures and Program Design in C; PHI
R2. Aho “Data Structure & Algorithms”.
R3. Trembly “Introduction to Data Structure with Applications”.
R4. TennenBaum A.M. & others: Data Structures using C & C++; PHI
R5. Horowitz & Sawhaney: Fundamentals of Data Structures, Galgotia Publishers.
R6. Yashwant Kanetkar, Understanding Pointers in C, BPB.
REFERECNE BOOKS
R1. Deshpande U.A. & Other: Data Structure and Algorithms
R2. M. RadhaKrishnan: Data Structure using C
R3. Rajni Jindal: Data Structure Using C
R4. Michael Main: Data Structure & Other Object Using C++
R5. Schaum’s Series: Data Structure and it’s Algorithm
R6. Cormen,Thomas H.,Charles E. Introduction to Algorithms, 2nd ed. MH, New York.
Tactical Instruction PlanCourse Code MCA-203 / Session Jan-Jun 2008
Course Title Data Structure
Course Faculty NAME
U NO / Topic / Sub Topic / Frequency Of asking Question / Remarks / Relative Weight age in terms of marks out of 100
Topic / Unit
1 / Prerequisites: Array, Structure, pointers, pointer to structure, functions, parameter passing, recursion.
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.
2 / 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.
3 / Trees: definitions-height, depth, order, degree, parent and children 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.
4 / 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.
5 / 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; kruskal & dijkstra 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.
Counter signature of the HOD Signature of the concerned faculty member
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2008)
Data Structure
Tutorial – 1
Q 1. What is Top –Down and Bottom –up programming.
Q 2. Drive an expression for calculating the address of A[ij] element of the
a two dimensional matrix.
Q 3. Explain the concept of Dynamic memory management.
Q 4. What is the value of following postfix expression
5 4 6 + * 4 9 3 / + *
Q 5. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
Q 6. What are the advantages circular queue over linear queue?
Q 7. Write an algorithm to count the number of items in a queue?
Q 8. What is a Deque ?
Q 9. Discuss the application of queue ?
Q 10. Write the linked implementation of stack ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2008)
Data Structure
Tutorial – 2
Q 1. Write an algorithm for inserting a node in a Link list.
Q 2. Write an algorithm for deleting a node from a Link list.
Q 3. Write an algorithm for push and pop operations on a stack.
Q 4. Write an algorithm for Insertion and Deletion operation in a Que.
Q 5. What are advantages and disadvantages of link list?
Q 6. How a link list can be implemented using array?
Q 7. Write an algorithm for
Q 8. How will you declare doubly linked list in C language?
Q 9. How a polynomial can be represented as link list ?
Q 10. How does a circular header link list differs then a linear link list ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
DEPARTMENT OF MCA
MCA II Semester (2006)
Data Structure
Tutorial – 3
1. What is Binary Tree?
2. Describe almost complete Binary tree?
3. What is Tree traversal?
4. Write recursive algorithm for various type of tree traversal?
5. Discuss various implementation of a Binary Tree?
6. Describe the evaluation of Binary Expression?
7. Define height, depth order and degree of Tree?
8. What do you mean by Binary Search Tree?
9. Describe threaded Binary Tree?
10. How do you convert forest in to Tree?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
DEPARTMENT OF MCA
MCA II Semester (2006)
Data Structure
Tutorial – 4
Q 1. Describe Insertion sort with example.
Q 2. Explain Quick sort and Merge sort with example.
Q 3. Explain Heap sort with example.
Q 4. Calculate the complexity of all the sorting algorithms.
Q 5. What are the advantages and disadvantage of sequential search ?
Q 6. Explain interpolation search?
Q 7. Explain the working of binary search ?
Q 8. Explain various techniques used to build hash function ?
Q 9. What are the different techniques of collision resolution?
Q 10. What are the shell sort ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
DEPARTMENT OF MCA
MCA II Semester (2006)
Data Structure
Tutorial – 5
Q 1. What is graph terminology?
Q 2. Consider a graph of at least 4 vertexes and 7 edges.
I. Find a simple path between any two vertex.
II. Are there any source and sinks
III. Find edge and out degree.
IV. Find the adjancey matrix A of the graph G.
Q 3. Define DFS and BFS graph traversing Technique.
Q 4. What is height balanced binary tree ?
Q 5. Describe the method of constructing a B-Tree?
Q 6. Describe Kruskal Minimum Cost Spanning tree algorithm?
Q 7. Explain Dijkstra Algorithm?
Q 8. How a Graph can be represented using array?
Q 9. What do you mean by Multi way Search Tree?
Q 10. What is Weight balanced binary tree?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2008)
Data Structure
MCA – 404
Unit Test -I
Q 1. What is Top –Down and Bottom –up programming.
Q 2. Drive an expression for calculating the address of A[ij] element of the
a two dimensional matrix.
Q 3. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
Q 4. What are the advantages circular queue over linear queue?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2008)
Data Structure
MCA – 404
Unit Test –II
Q 1. Write an algorithm for inserting a node in a Link list.
Q 2. Write an algorithm for deleting a node from a Link list.
Q 3. Write an algorithm for push and pop operations on a stack.
Q 4. Write an algorithm for Insertion and Deletion operation in a Que.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2008)
Data Structure
MCA – 404
Unit Test –III
Q 1. What is Binary Tree?
Q 2. Describe almost complete Binary tree?
Q 3. What is Tree traversal?
Q 4. Write recursive algorithm for various type of tree traversal?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2008)
MID SEMESTER I
Data Structure
MCA – 404
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2008)
Data Structure
MCA – 404