## Fundamentals of Data Structures - December 2015

### SPPU Information Technology (Semester 3)

Total marks: --

Total time: --
INSTRUCTIONS

(1) Assume appropriate data and state your reasons

(2) Marks are given to the right of every question

(3) Draw neat diagrams wherever necessary

### Solve any one question from Q1 and Q2

**1 (a)**What is the purpose of structure in 'C'? Can we define the structure into the structure? Give suitable example. 6 marks

**1 (b)** Write a pseudo code to find out length of string without using library function.
6 marks

**1 (c)** Explain pointer variable with example.
6 marks

**2 (a)** Given the following declarations:

int m=50, n=50;

int *p1 = & m, *p2= &n; What is the value of each of the following expression? (*p1)++;

ii) - - (

*p2);*

iii) *p1+ (p2)- -;

iii) *p1+ (

iv) ++(

*p2)-*p1; 6 marks

### Solve any one question from Q3 and Q4

**2 (b)**Explain how an array is passed to a function as a pointer with example. 6 marks

**2 (c)** Explain any four file operations.
6 marks

### Solve any one question from Q3 and Q4

**3 (a)**What is time complexity of an algorithm? Explain its importance with suitable example. 6 marks

**3 (b)** Explain linear and non-linear data structures with suitable examples.
6 marks

### Solve any one question from Q5 and Q6

**3 (c)**Show that output of each using insertion sort to arrange the following numbers in ascending order:

150, 350, 100, 250, 200, 50, 300. 6 marks

**4 (a)** Explain the importance of searching and sorting techniques in computer science field. What is sort stability?
6 marks

**4 (b)** With respect to algorithm analysis, explain the following terms:

i) Big Oh notation

ii) Omega notation

iii) Theta notation.
6 marks

**4 (c)** What is the importance of pivot element in the quick sort method.
6 marks

### Solve any one question from Q5 and Q6

**5 (a)**What is sparse matrix? What are its applications? 6 marks

**5 (b)** Explain row major and column major representation of arrays.
6 marks

**5 (c)** Represent the following polynomials using arrays:

i) 5x ∧2 - 10xy + y∧2-20

ii) x∧4+59x+10.
6 marks

**6 (a)** What is sequential memory organization? List the advantages and disadvantages of sequential memory organization.
6 marks

**6 (b)** Write a pseudo code for the following stack operations:

i) push operation

ii) pop operation
6 marks

**6 (c)** Explain the address calculation of element in arrays in row major and column major Representation.
6 marks

### Solve any one question from Q7 and Q8

**7 (a)**Compare linked list with arrays with reference to the following aspects:

i) Accessig any element randomly

ii) Insertion and deletion of an element

iii) Utilization of computer memory 6 marks

**7 (b)** Write a pseudo code to delete a node from singly linked list.
6 marks

**8 (a)** Explain GLL. Represent the following polynomial using GLL. (p, q, (r, s, (t, u, v), w), x, u).
6 marks

**8 (b)** Write a pseudo code to insert a node at start and at end in DLL.
6 marks