D 08000CS205122001 Pages: 3

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
Third Semester B.Tech Degree (S,FE) Examination December 2020 (2015 Scheme)

Course Code: CS205
Course Name: DATA STUCTURES

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries 3 marks. Marks
1 Give two methods through which the performance of an algorithm can be (3)

analysed. Use an example each to illustrate.

2 What are the properties that an algorithm should have? (3)
What is an Abstract Data Type? What is its use? (3)
4 Illustrate how the polynomial 4x*+11 can be represented using an array anda (3)
linked list.
PART ‏تا‎

Answer any two full questions, each carries 9 marks.

5 9) Calculate the total computation time for the following code and represent it (4.5)
using Big O notation

c=0
for (k=1;k<=n;k*=2)
for (j=1;j<=n;j++)
C++

b) Given a pointer HEAD that points to the first element of a singly linked list, a (4.5)
value ITEM to be stored in the linked list and a value A after which ITEM is to
be inserted, write an algorithm to insert ITEM to the list.

6 2) [पव how step-wise refinement is used to arrive at a solution/algorithm toa (5)
problem, given a problem definition.

b) A programmer needs to store the details of all students of a class of 60 students (4)
for an application he/she is developing. What data structure would be most
appropriate? Provide appropriate justifications.

7 8) What is the characteristic of a recursive algorithm? Write non-recursive version (4)
of binary search algorithm.

b) Write an algorithm for multiplying two polynomials using linked lists (5)

1/3