## Data Structures and Problem Solving - May 2014

### 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)** Find the frequency count for the following code.

for(i=1;i<=n;i++)

{

for(i=1;i<=n;i++)

{

for(i=1;i<=n;i++)

{

sum=sum+I;

}

}

}(3 marks)
**1 (b)** Write a function for selection sort using templates.(3 marks)
**1 (c)** What is ADT? Write an ADT for Deques.(6 marks)
**2 (a)** Explain different Asymptotic notations.(3 marks)
**2 (b)** Convert the following tree into Binary tree.

(6 marks)
**2 (c)** Consider the following tree given in the problem. Show a Postorder, Preorder and In order Traversal of the tree.

(3 marks)

### Answer any one question from Q3 and Q4

**3 (a)** Sort the digraph for topological sort refer figure 1 below.

(3 marks)
**3 (b)** Convert given graph into MST refer figure 2 below.
(3 marks)
**3 (c)** What is collision? What Are different collision resolution techniques?(3 marks)
**3 (d)** Draw a binary search tree for the following data 10, 08, 15, 12, 13, 07, 09, 17, 20, 18, 04, 05.(3 marks)
**4 (a)** Explain with suitable example the various storage structures for the graph.(6 marks)
**4 (b)** Construct the AVL tree for the following data by inserting each data item one at a time. 15, 20, 24, 10, 13, 7, 30, 36, 25.(6 marks)

### Answer any one question from Q5 and Q6

**5 (a)** Sort the following data in ascending order using heap sort.15, 19, 10, 7, 17, 16.(6 marks)
**5 (b)** Write an algorithm to search an element in a B Tree.(4 marks)
**5 (c)** Define sequential file organization and state its advantages and disadvantages.(3 marks)
**6 (a)** What is ISMA in file organization? Explain Advantages & Disadvantages of sequential file organization.(6 marks)
**6 (b)** What is a B+ tree? Give structure of its internal node. What are the order of B+ tree & Characteristics of B+ tree.(7 marks)

### Answer any one question from Q7 and Q8

**7 (a)** Explain in detail the models used for parallel computation.(6 marks)
**7 (b)** Write a parallel algorithm to perform the addition of the given numbers using complete binary tree method.(7 marks)
**8 (a)** Write a parallel algorithm for pointer doubling. Explain with suitable example.(7 marks)
**8 (b)** Write a parallel algorithm for odd-even merge sort.(6 marks)