## Fundamentals of Data Structures - May 2014

### Information Technology 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)** Explain entry controlled loop structures in C.(4 marks)
**1 (b)** Write pseudo C/C++ algorithm to concatenate two strings using pointers without using library functions.(4 marks)
**1 (c)** Explain any four bitwise operators in C with example.(4 marks)
**2 (a)** Explain use of pointer to array of structure with suitable example.(4 marks)
**2 (b)** Explain different storage classes in C.(6 marks)
**2 (c)** Write use of void data type.(2 marks)

### Answer any one question from Q3 and Q4

**3 (a)** Explain Big-oh, omega and theta notation with example.(6 marks)
**3 (b)** Sort the following list in ascending order using bubble sort. Show all passes. Analyze time complexity.

9, 7, -2, 4, 5, 3, -6, 2, 1, 8.(6 marks)
**4 (a)** Write different types of data structures. Give one example of each type.(6 marks)
**4 (b)** Sort the following list using merge sort

38, 27, 43, 3, 9, 82, 11, 10(4 marks)
**4 (c)** Compare linear and binary search.(2 marks)

### Answer any one question from Q5 and Q6

**5 (a)** What is recursion ? Explain role of stack in recursion. Write recursive function to add digits of a given positive integer.(6 marks)
**5 (b)** Write a C/C++ function to add two sparse matrices. Analyse its time complexity.(6 marks)
**5 (c)** Write address calculation for elements of one dimensional array.(2 marks)
**6 (a)** Write pseudo C/C++ algorithm to find transpose of sparse matrix using fast transpose algorithm.(6 marks)
**6 (b)** Explain row and column major storage representation of two dimensional array.(6 marks)
**6 (c)** Write a non-recursive algorithm to find factorial of a positive number.(2 marks)

### Answer any one question from Q7 and Q8

**7 (a)** Write a C/C++ program to create singly inked list of integers and display it forward.(6 marks)
**7 (b)** Write node structure and represent following list using generalized linked list.

(A, B, (C, D, E), F, (G, H, (I, J), K), L)(4 marks)
**7 (c)** Write advantages of linked memory organization.(2 marks)
**8 (a)** Write pseudo C/C++ algorithm to add two sorted polynomials represented by SLL.(6 marks)
**8 (b)** What is generalized list ? Give node structure to represent multi variable polynomial using GLL.(4 marks)
**8 (c)** Write advantages of circular singly linked list over a linear linked list.(2 marks)