## Fundamentals of Data Structures - Dec 2016

### 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.

### Solve any one question.Q1(a,b,c) Q2(a,b,c)

**1(a)** Explain entry controlled loop structure in C.(4 marks)
**1(b)** What are advantages of using structure? Give difference between Union and Structure.(4 marks)
**1(c)** What is pointer varible? Explain declaration, intialization and accessing a pointer variable with an exmaple.(4 marks)
**2(a)** Write pseudo C algorithm for reverse of String using pointers.(4 marks)
**2(b)** Explain concept of arrays with suitable example.(4 marks)
**2(c)** Explain call by value and call by reference functions with suitable examples.(4 marks)

### Solve any one question.Q3(a,b) Q4(a,b)

**3(a)** Define the following terms with example:

i) Data object

ii) Data structure

iii) Abstract Data Type.(6 marks)
**3(b)(i)** Write Pseudo C algorithms for:

i) Linear Search(3 marks)
**3(b)(ii)** ii) Binary Search(4 marks)
**4(a)** Explain Big-oh,

omega and theta notation with example.(6 marks)
**4(b)** Explain selection sort with given example by showing all passes. Also analyze time complexity. Number are:

17,

35,

24,

13,

26,

14.(7 marks)

### Solve any one question.Q5(a,b) Q6(a,b)

**5(a)** Write a pseudo C algorithm for addition of two sparse matrices. Analyze its time complexity.(6 marks)
**5(b)** Explain the two-dimensional array in detail with column and row major representation and address calculation in both the cases.(6 marks)
**6(a)** Explain stack and write pseudo C algorithm PUSH and POP operations of stack.(6 marks)
**6(b)** Explain polynomial representation of an array and also write data structure declaration with suitable example.(6 marks)

### Solve any one question.Q7(a,b) Q8(a,b)

**7(a)** Explain concept Generalized Linked List and representation polynomial using GLL with given example:

4x^{3}+2x^{2}+6xy+7xy^{3}.(6 marks)
**7(b)** Write C function to insert a node and delete a node in DLL.(7 marks)
**8(a)** Explain with suitable example:

i) Circular Linked List

ii) Linked List as ADT.(6 marks)
**8(b)** Write a pseudo C algorithm to merge two Sorted Linked Lists into the third.(7 marks)