## 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++><>(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)