D D7144

Total Pages: 2
Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2017

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 Differentiate between abstract and concrete data structure. (3)

2 N’+ N= (N°) Justify your answer. (3)

3 What is frequency count? Explain with an example. (3)

4 How can we represent a linked list in memory using arrays? (3)

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

5 Describe Big റ notation used to represent asymptotic running time of algorithms. (9)
Give the asymptotic analysis of any one iterative algorithm.

6 9) Consider a singly linked list having n nodes. The data items 01, d2,....,dn are (5)
stored in the n 110005, Let X be a pointer to the jth node (1 stored. A new data item d stored in a node with address Y is to be inserted in the
list. Give an algorithm to insert d into the list after dj to obtain a list having items
‏سو ,02 و01‎ , dj, d, 011, .....dn in that order without using the header.

b) Explain about the use and representation of header node in linked list (4)

7 2) What are the application of vectors. (3)

b) Write an algorithm for deleting a node from a specified position in a circular (6)
queue
PART C
Answer all questions, each carries 3 marks.
8 How will you check the validity of an arithmetic expression using stack (3)
9 Let take initial memory as - (3)
ര || | |
0 150 200 300 410 500K
Do the following things with first fit approach and show the memory status:
1. Allocate process C of size 90K
2. Allocate process D of size 70K

10 Write a program in C to concatenate two strings using string function. (3)

11 If a full binary tree is of height 5, give the positions of left child and right child (3)
of the second node in level 2.

PART D
Answer any two full questions, each carries 9 marks.
12 Convert the following expression into its corresponding post fix form using the (9)

prescribed algorithm:
(300+23)*(43-21)/(84+7). Do the evaluation of resultant postfix expression.

Page 1 of 2