Fundamentals of Data Structures - Dec 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) Differentiate between pass by reference and pass by value.(4 marks) 1 (b) Explain the different modes of opening a file in C using fopen( ) function.(6 marks) 1 (c) What will be the output of the following code snippets?
(1) #define M(x) x * x
main( )
{
printf("%d", M(2+3))
}

(2) Main( )
{
int x;
x=4+2%-8;
printf("%d", x);
}(2 marks) 2 (a) What is macro? What are its advantages and disadvantages?(4 marks) 2 (b) Explain the use of break and continue keywords in C with suitable example.(4 marks) 2 (c) Write a C function to compare two strings.(4 marks)

Answer any one question from Q3 and Q4

3 (a) Show the output of each pass using bubble sort to arrange the following numbers in ascending order.
90, 87, 76, 65, 43, 32, 19, 7, 0, ?17.(6 marks) 3 (b) Explain the following terms:
(i) Data Object
(ii) Data Type.(3 marks) 3 (c) What is space complexity of an algorithm? Explain its importance with example.(3 marks) 4 (a) Explain the following terms:
(i) Internal sorting
(ii) External sorting
(iii) Sort stability.(6 marks) 4 (b) Explain the different asymptotic notations.(3 marks) 4 (c) Explain with example the linear data structure.(3 marks)

Answer any one question from Q5 and Q6

5 (a) Represent the sparse matrix using suitable data structure and write a pseudo C code to find transpose of a spare matrix using slow transpose.(7 marks) 5 (b) Explain the concept of column major address calculation for multidimensional array with suitable example.(4 marks) 5 (c) Represent the following polynomials using arrays:
i) x³+2xy+y³-y+x
ii) 5x²+10xy+y²-20.(2 marks) 6 (a) Write a pseudo C algorithm for addition of two sparse matrices. Analyze its time complexity.(7 marks) 6 (b) Explain sequential memory organization with example.(4 marks) 6 (c) What is sparse matrix ? Explain how it is represented.(2 marks)

Answer any one question from Q7 and Q8

7 (a) Suppose a Linked List consists of numerical values. Write a function for finding the maximum element of the List and the product of all the numbers in the List.(7 marks) 7 (b) Write a C code for reversing the Singly Linked List without using additional data structure.(6 marks) 8 (a) Write a pseudo code to merge two Sorted Linked Lists into the third.(7 marks) 8 (b) Explain GLL. Represent following polynomial using GLL
(L, (M, (N, (O, P)), Q), R, (S, T), (A, (B, C))).(6 marks)