## Fundamentals of Data Structures - December 2013

### 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)**Differentiate between structure and union. 3 marks

**1 (b)** Explain logical operators in C.
3 marks

**1 (c)** Describe following declarations

i) int *A[10]; ii) charN[10][50]; iii) void *f(int a[], int n);
iv) float *p; v) double **p; vi) FILE *fp1;
3 marks

**2 (a)** Explain call by value and call by reference with suitable example.
3 marks

### Solve any one question from Q3 and Q4

**2 (b)**Write pseudo C algorithm to reverse a string. 3 marks

**2 (c)** Differentiate between binary and text file.
3 marks

**3 (a)** Give classification of data structures with one example of each type.
3 marks

**3 (b)** Sort the following list using selection sort. Show output of each pass and write time complexity. 10, 6, 13, 7, 5, 51, 27 ,2, 3, 15, -3, 4.
3 marks

### Solve any one question from Q5 and Q6

**4 (a)**Write Pseudo C code for binary search and analyze its time complexity. 3 marks

**4 (b)** What is frequency count? Write its importance in analysis of algorithm. Find time complexity of an algorithm to find union of two sets of length m and n.
3 marks

**5 (a)** Represent sparse matrix using suitable data structure and write simple/ slow transpose algorithm.
3 marks

**5 (b)** Explain use of stack in recursion. Write recursive function to find factorial of a positive number.
3 marks

### Solve any one question from Q7 and Q8

**5 (c)**Represent following polynomial using arrays. Write data structure declaration. 5x

^{2}y

^{3}+3x

^{2}+4xy+2. 3 marks

**6 (a)** Write a algorithm to add two sorted polynomials in single variable. Analyze its time complexity.
3 marks

**6 (b)** Give row major storage representation for two dimensional array. Write address calculation.
3 marks

**6 (c)** Write disadvantages og sequential memory organization.
3 marks

**7 (a)** Write a C function to reverse a linear singly linked list by changing link pointers. Write its time complexity.
3 marks

**7 (b)** Write node structure and represent following polynomial using generalized linked list. 5x^{2}y^{3}-3x^{2}y^{2}+2x+4.
3 marks

**7 (c)** Write advantages of linked memory organization.
3 marks

**8 (a)** What is doubly linked list? Write C code to

i) delete a node pointed by pointer temp in a circular DLL.

ii) insert a new node pointed by pointer newp after a node pointed by pointer temp in circular DLL.
3 marks

**8 (b)** What is generalized list? Represent following list using GLL. (a, ,b c, (e, f, g), h)
3 marks

**8 (c)** Write importance of header node in a linked list.
3 marks

**8 (d)** Compare linear and circular linked list.
3 marks