Post Graduate Diploma- Post Graduate Diploma In Computer Applications (PGDCA) 4th Sem 401 : DATA STRUCTURES AND ALGORITHMS(University of Pune, Pune-2013)
P.G.D.C.A. (Semester – IV) Examination, 2013
401 : DATA STRUCTURES AND ALGORITHMS
(2008 Pattern)
Time : 3 Hours Max. Marks : 70
Note :
i) Solve any 5 questions.
ii) Write structure definitions.
iii) Answer all sub questions of a question at one place.
1. A) Convert the following infix form to its prefix form :
A* (B + C) / D – E
Show the contents of both the stacks at each step in a tabular form. (7)
B) Evaluate the following postfix form : AB + CDE / + *
where A = 7, B = 5, C = 4, D = 3, E = 2.
Show the contents of the stack at each step in a tabular form. (7)
2. A) Write a function that returns total count of nodes in a Doubly linked list. (7)
B) Write a function to delete an element in a linear queue of characters implemented as a linked list. (7)
3. A) Write functions for pre-order and post-order traversal of Binary Search Tree. (7)
B) Compute row major and column major address of the member nos [6][8] of a 2-d array nos [10][10] where base address of the array is 200 and each member occupies 2 bytes of memory. (7)
4. A) Write a function that prints data of nodes of a single linear linked list in reverse order. (7)
B) Write a program for stack implementation using arrays (7)
P.T.O.
[4386] – 401
5. Consider the following graph. (14)
a) Write adjacency matrix
b) Write adjacency list
c) Generate the output of Breadth First Search (BFS) when starting vertex is 1.
d) Generate the output of Depth First Search (DFS) when starting vertex is 1.
e) Write in degree of each vertex.
6. A) Design Huffman’s tree for the following message : “Competition”. What kind of tree is a Huffman’s tree ? (7)
B) Give the steps for sorting following numbers using Bubble sort :
3 9 5 2 4 8 . 7
—
| Earning: ₹ 7.05/- |
