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.

Google Online Preview   Download