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++></n;j++></n;i++></span>(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)