THAKRAL COLLEGE OF TECHNOLOGY, BHOPAL
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
|Course No. |Course Name |L (Hrs) |T (Hrs) |
|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
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.
REFERECNE BOOKS
1. Deshpande U.A. & Other: Data Structure and Algorithms
2. M. RadhaKrishnan: Data Structure using C
3. Rajni Jindal: Data Structure Using C
4. Michael Main: Data Structure & Other Object Using C++
5. Schaum’s Series: Data Structure and it’s Algorithm
6. Cormen,Thomas H.,Charles E. Introduction to Algorithms, 2nd ed. MH, New York.
|Tactical Instruction Plan |
|Course Code MCA-203 |Session Jan-Jun 2008 |
|Course Title Data Structure | |
|Course Faculty NAME | |
|U NO |Topic / Sub Topic |Frequency Of asking |Remarks |Relative Weight age in terms |
| | |Question | |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
1. What is Top –Down and Bottom –up programming.
2. Drive an expression for calculating the address of A[ij] element of the
a two dimensional matrix.
3. Explain the concept of Dynamic memory management.
4. What is the value of following postfix expression
5 4 6 + * 4 9 3 / + *
5. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
6. What are the advantages circular queue over linear queue?
7. Write an algorithm to count the number of items in a queue?
8. What is a Deque ?
9. Discuss the application of queue ?
10. Write the linked implementation of stack ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2008)
Data Structure
Tutorial – 2
1. Write an algorithm for inserting a node in a Link list.
2. Write an algorithm for deleting a node from a Link list.
3. Write an algorithm for push and pop operations on a stack.
4. Write an algorithm for Insertion and Deletion operation in a Que.
5. What are advantages and disadvantages of link list?
6. How a link list can be implemented using array?
7. Write an algorithm for
8. How will you declare doubly linked list in C language?
9. How a polynomial can be represented as link list ?
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
1. Describe Insertion sort with example.
2. Explain Quick sort and Merge sort with example.
3. Explain Heap sort with example.
4. Calculate the complexity of all the sorting algorithms.
5. What are the advantages and disadvantage of sequential search ?
6. Explain interpolation search?
7. Explain the working of binary search ?
8. Explain various techniques used to build hash function ?
9. What are the different techniques of collision resolution?
10. What are the shell sort ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
DEPARTMENT OF MCA
MCA II Semester (2006)
Data Structure
Tutorial – 5
1. What is graph terminology?
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
1. What is Top –Down and Bottom –up programming.
2. Drive an expression for calculating the address of A[ij] element of the
a two dimensional matrix.
3. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
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
1. Write an algorithm for inserting a node in a Link list.
2. Write an algorithm for deleting a node from a Link list.
3. Write an algorithm for push and pop operations on a stack.
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
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?
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
Unit Test –V
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MID SEMESTER EXAMINATION (Jan - Jun 2006)
MCA II SEMSTER
Subject: Data Structure Max marks: 40
Subject Code : MCA 203 Time: 2 hrs
Note: 1. All question are compulsory
2. All questions carry equal marks.
1. What are the advantages circular queue over linear queue?
2. Write an algorithm for push and pop operations on a stack
3. What are advantages and disadvantages of link list?
4. Write an algorithm for Insertion and Deletion operation in a Que.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MID SEMESTER EXAMINATION II (Jan - Jun 2006)
MCA II SEMSTER
Subject: Data Structure Max marks: 40 Time: 2 hrs
Note: All question are compulsory, each question carry equal marks.
1. Write an algorithm for push and pop operations on a stack.
2. What are the advantages circular queue over linear queue?
3. Write an algorithm for deleting a node from a Link list.
4. Discuss various implementation of a Binary Tree?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2007)
Data Structure
Tutorial – 1
1. What are the advantages circular queue over linear queue?
2. What is Top –Down and Bottom –up programming.
3. Write the linked implementation of stack ?
4. Drive an expression for calculating the address of A[ij] element of the
a two dimensional matrix.
5. Explain the concept of Dynamic memory management.
6. What is the value of following postfix expression
3 2 5 + / 8 7 3 - + *
7. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
8. Write an algorithm to count the number of items in a queue?
9. What is a Deque ?
10. Discuss the application of queue ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2007)
Data Structure
Tutorial – 2
1. Write an algorithm for deleting a node from a Link list.
2. Write an algorithm for push and pop operations on a stack.
3. Write an algorithm for Insertion and Deletion operation in a Que.
4. What are advantages and disadvantages of link list?
5. How a link list can be implemented using array?
6. Write an algorithm for insertion a node in Queue ?
7. How will you declare doubly linked list in C language?
8. How a polynomial can be represented as link list ?
9. How does a circular header link list differs then a linear link list ?
10. Write an algorithm for inserting a node in a Link list.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2006)
Data Structure
Tutorial – 3
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2006)
Data Structure
Tutorial – 4
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2006)
Data Structure
Tutorial – 5
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2007)
Data Structure
MCA – 404
Unit Test –1
1. What is a Deque ?
2. Discuss the application of queue ?
3. Explain the concept of Dynamic memory management
4. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2007)
Data Structure
MCA - 404
Unit Test –2
1. Write an algorithm for deleting a node from a Link list.
2. Write an algorithm for push and pop operations on a stack.
3. How will you declare doubly linked list in C language?
4. How does a circular header link list differs then a linear link list ?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2007)
Data Structure
MCA - 404
Unit Test –3
1. What do you mean by Binary Search Tree?
2. Describe threaded Binary Tree?
3. How do you convert forest in to Tree?
4. What is Tree traversal?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2006)
Data Structure
MCA - 404
Unit Test –4
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2006)
Data Structure
MCA - 404
Unit Test – 5
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2006)
Data Structure
MCA – 404
Unit Test –1
1. What is a Deque ?
2. Discuss the application of queue ?
3. Explain the concept of Dynamic memory management
4. Convert the following infix expression to postfix expression
((a+b)-((c+d)*e)/f)*g
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2006)
Data Structure
MCA - 404
Unit Test –2
1. Write an algorithm for deleting a node from a Link list.
2. Write an algorithm for push and pop operations on a stack.
3. How will you declare doubly linked list in C language?
4. 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
MCA - 404
Unit Test –3
1. What are advantages and disadvantages of link list?
2. How a polynomial can be represented as link list ?
3. How do you convert forest in to Tree?
4. What is Tree traversal?
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2005)
Data Structure
Tutorial – 1
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2005)
Data Structure
Tutorial – 2
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2005)
Data Structure
Tutorial – 3
1. Write a shell script to redirect the output of date command without time in it to a file.
2. Describe in brief any one technique of process synchronization used in unix.
3. Write short note on device driver.
4. Define mounting of a file system.
5. Explain IPC.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2005)
Data Structure
Tutorial – 4
1. What are the advantages of delayed write mechanism.
2. Define user file description.
3. Write limitation of multiprocessor.
4. Give the layout of unix system memory.
5. How ‘write’ system call works. What are its input parameter and return information.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
MCA II Semester (2005)
Data Structure
Tutorial – 5
1. Describe the architecture of unix operating system.
2. Write down the strength of unix operating system.
3. Explain in brief structure of regular file.
4. Describe any five system calls for the file system.
5. Describe PCB.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2005)
Data Structure
MCA - 404
Unit Test – 1
1. Explain Buffer cache in Detail?
2. Discuss silent feature of Unix OS?
3. Explain Process State Diagram.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2005)
Data Structure
MCA - 404
Unit Test – 2
1. What are the similarities and differences between buffer header and inode.
2. Define : chrot, chdir, chown, chmod.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2005)
Data Structure
MCA - 404
Unit Test – 3
1. What are the contents of process table.
2. Discuss sleeping state of a process.
3. Describe the manipulation of address space.
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2005)
Data Structure
MCA - 404
Unit Test – 4
NAME COLLEGE OF TECHNOLOGY, BHOPAL
Department of MCA
MCA II Semester (2005)
Data Structure
MCA - 404
Unit Test – 5
Mid Semester Test, September 2005
MCA II Semester
Data Structure
Time :2 Hrs.
Max Marks :40
Note: Attempt any 5. All question carry equal marks.
-----------------------
Approved By:
)
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- disadvantages of technology in education
- use of technology in schools
- importance of technology in business
- benefits of technology in education
- the use of technology in education
- benefits of technology in business
- importance of technology in workplace
- ethics of technology of philosophy
- use of technology in education
- the philosophy of technology pdf
- effects of technology in education
- impacts of technology on education