D R3946 Pages: 2

Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2018
Course Code: CS205
Course Name: DATA STRUCTURES (CS,IT)

Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
1 Write a recursive function to find the fibonacci series (3)
2 Draw a circular doubly linked list. Give an advantage of circular doubly (3)
linked list.
3 Check whether the following is true or not. (3)
2” is in O(2"). Give reason.
4 How will you represent a polynomial 3x? +2xy* ഒ +7yz using singly (3)

linked list?
PART 8
Answer any two full questions, each carries 9 marks.

5 a) Explain the Big O asymptotic notation used for specifying the growth rate (3)

of functions.
b) Given a doubly linked list, write an algorithm that removes a node witha (6)
particular value from the list and inserts it in the front.
6 a) What is an algorithm? How is its complexity analysed? (3)
b) What is thecomplexity of finding maximum and minimum value from an (6)
array of n values? Explain the steps of deriving complexity.
7 a) Give any three applications of linked list. (3)
b) Let 1.1 be asingly linked list in memory. Write an algorithm (6)

i) Finds the number of non zero elements in 1.1
ii) Adds a given value K to each element in 1
PART C
Answer all questions, each carries 3 marks.
8 Write an algorithm to find a substring in a given string. (3)

With the help of an example, explain how a binary tree can be represented (3)
using an array.

10 How can you reverse a string using stack? Give one example and show (3)
how you can reverse a given string using stack.
11 Write a recursive algorithm for pre-order traversal in a binary tree. (3)

Page 1 of 2