D C192039 Pages:2

Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER B.TECH DEGREE EXAMINATION(R&S), DECEMBER 2019

Course Code: ೮5205
Course Name: DATA STRUCTURES

Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
1 Calculate the run-time efficiency of the following program segment using (3)

frequency count analysis.
for (i= 1; i <=n; i++)
for (j = 1; ‏ز‎ <=n; j++)
printf ("%d %d \n", i, j);

2 Let F(n) = n’+ 11. Can you say F(n) is O(n*)? Justify your answer. (3)
3 Why a doubly linked list is known as two way list? Draw a doubly linked list (3)
with data values 25, 45, 15.
4 Let LIST be a singly linked list in memory. Write an algorithm to find the (3)
number of times a given data item X occurs in LIST.
PART B

Answer any two full questions, each carries 9 marks.
5 ച Write an algorithm/pseudo code to find the sum of two square matrices and find (6)
the time complexity of the algorithm using frequency count method.

b) Compare recursive and iterative algorithms. (3)
6 9) Explain stepwise refinement technique with the help of an example. (4.5)
b) Write an algorithm/pseudo code to add a new element in a particular position of (4.5)
an array.
7 2) Represent the polynomial 4x*y+5xy*+8 using a singly linked list. (1)

b) Write an algorithm/pseudo code to perform addition of two single variable (8)
polynomials using singly linked lists.
PART C
Answer all questions, each carries 3 marks.
8 Perform the following operations in the given order on an empty stack of size 5. (3)
Display the stack after each operation. Mention TOP of the stack.
POP(), PUSH(5), PUSH(8), POP(), PUSH(4), PUSH(2), POP()

What is a Binary tree? Give an example. Give its array representation. (3)
10 How is a circular queue represented using an array. Write down the QUEUE (3)
FULL condition for a circular queue.
11 What is a complete binary tree and full binary tree? Give example for each. (3)
PART D

Answer any two full questions, each carries 9 marks.
12 a) Trace the infix to postfix algorithm (clearly showing the status of stack) to find (5)
the equivalent postfix expression for the following infix expression.
^ + (B*C-(D/E%*F)*G)
0) Write a non recursive (iterative) algorithm/pseudo code to perform preorder (4)
traversal of a binary tree .
13 a) Write an algorithm/pseudo code to insert an element in a circular queue using (3)
array.

Page 1 of 2