Reg No.:

Max. Marks: 100

1

2

3

4

5 ஐ
b)

6 a)
b)

7 2)
b)

8

9

10

11

12 a)
b)

D3826 Pages: 2

Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER B.TECH DEGREE EXAMINATION, APRIL 2018

Course Code: CS205
Course Name: DATA STRUCTURES (CS, IT)

PART A
Answer all questions, each carries 3 marks

Write an algorithm to perform backward traversal of a doubly linked list.
Define the following terms, with examples:
i) Header linked list 1) Circular linked list
What is the purpose of calculating frequency count? Compute the frequency count
of the following code fragment.
for(i=0;i
for(j=0;jprintf(“%d”,a[i][j]);
What is stepwise refinement technique?

PART B
Answer any two full questions, each carries 9 marks

What is the difference between recursive and iterative algorithms?
Write recursive and iterative algorithm to traverse a singly linked list.
Write an algorithm to add two polynomials.
Write about top down and bottom up programming methodologies.
Write an algorithm to insert a node after a given node in a doubly linked list.
What is asymptotic notation? Describe about Big O notation.

PART C
Answer all questions, each carries 3 marks

Write an algorithm to perform substring searching.
Evaluate the following expressions written in reverse polish notation. Assume
single digit operands and ^ represents exponentiation operator

1) 123*+42/% ii) 63/45-*
Define the properties of circular queue. How will you check whether the circular
queue is

i) Full 11) Empty
Write a recursive algorithm to perform preorder traversal.

PART D
Answer any two full questions, each carries 9 marks

Write an algorithm to convert an infix expression to postfix.
Show the structure of the binary search tree after adding each of the following
values in that order: 10, 1, 3, 5, 15, 12, 16, What is the height of the created

Page 1 of 2

Duration: 3 Hours

Marks

(3)
(3)

(3)

(3)

(4.5)
(4.5)
(6)
(3)
(4.5)
(4.5)

(3)
(3)

(3)

(3)

(4.5)
(4.5)