0
Data Structures and Problem Solving : Question Paper Dec 2013 - Computer Engineering (Semester 3) | Pune University (PU)

Data Structures and Problem Solving - Dec 2013

Computer Engineering (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.


Answer any one question from Q1 and Q2

1 (a) Draw the IPO chart for obtaining the solution for 'Calculating the area of Triangle'.(3 marks) 1 (b) Define the terms with respect to sorting: internal sort, external sort and sorting stability.(3 marks) 1 (c) Convert the following generalized tree into a binary tree. (3 marks) 1 (d) What is the necessity of threaded binary tree? Define the terms inorder successor and inorder predecessor with respect to inorder threaded binary tree.(3 marks) 2 (a) Find the frequency count of the following code:
for(i=0;i<n;i++ )="" <br=""> {
for(j=0;j<n;j++ )="" <br=""> {
c[i][j] = 0;
for(k=0;k<n;k++ )="" <br=""> c[i][j] = a[i][k] × b[k][j];
}
}</n;k++&gt;<>(3 marks)
2 (c) Represent the following binary tree using array.

(3 marks) 2 (d) Write a pseudo C/C++ code for any of the recursive depth first traversal of the binary tree.(3 marks) 2(b) Sort the following data in ascending order using Radix Sort: 25, 06, 45, 60, 140, 50.(3 marks)


Answer any one question from Q3 and Q4

3 (a) Explain any three applications of graphs in the area of Computer Engineering.(3 marks) 3 (b) Differentiate between Prim's and Kruskal's algorithm for generating the spanning tree of the graph.(3 marks) 3 (c) Create an AVL tree for the following data by inserting it in an order one at a time:
10, 20, 15, 12, 25, 30.
(4 marks)
3 (d) Enlist the names of static tree tables with suitable example.(2 marks) 4 (a) Explain the situation in which linked representation of a graph is more beneficial than array representation.(2 marks) 4 (b) Write a pseudo C/C++ code for finding depth first traversal of the graph.(4 marks) 4 (c) What is the use of hash tables? Enlist the characteristics of good hash function.(3 marks) 4 (d) Assume the size of hash table as 8. The hash function to be used to calculate the hash value of the data X is: X%8. Insert the following values in hash table: 10, 12, 20, 18, 15. Use linear probing without replacement for handling collision.(3 marks)


Answer any one question from Q5 and Q6

5 (a) Write a pseudo C/C++ code to sort the data in ascending order using heap sort.(6 marks) 5 (b) Create a B tree of order 3 for the following data : 20, 10, 30, 15, 12, 40, 50.(4 marks) 5 (c) Explain the various modes of opening the file in C or C++.(3 marks) 6 (a) Sort the following data in ascending order using heap sort: 15, 10, 40, 25.(4 marks) 6 (b) Write a pseudo C/C++ code to search the data stored in a B tree.(6 marks) 6 (c) Explain any three operations carried out on sequential files.(3 marks)


Answer any one question from Q7 and Q8

7 (a) Write a parallel algorithm to calculate the addition of numbers stored in an array using prefix computation method.(6 marks) 7 (b) Explain the various models used for parallel computation.(4 marks) 7 (c) Explain pointer doubling problem in brief.(3 marks) 8 (a) Write a parallel algorithm for odd - even merge sort. Explain the algorithm with suitable Example.(7 marks) 8 (b) Write a parallel algorithm to perform the addition of the given numbers using complete binary tree method.(6 marks)

0  upvotes

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More