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)