# SRM University 2007 B.Tech Information Technology IT203 - Data Structures and Design of Algorithms - Question Paper

Wednesday, 30 January 2013 06:10Web

Page 1 of 2

UNIT I

**PART A**

1. Define Data Structure.

2. Define ADT

3. Write about Linked List.

4. What is the advantage of using Doubly Linked List?

5. Explain about Circular Linked List. Mention the advantage of this.

6. Describe about Stack model.

7. Mention the applications of Stack.

8. Briefly discuss about Queue ADT.

9. Define Big-O Notaion

10. Write about Running Time computations

**PART B**

1. Explain about the Array implementation of Stack.

2. Explain about the Pointer implementation of Stack.

3. Describe about the Array implementation of Queue

4.

**a.**Write about Circular Linked List with its advantages.

**b.**Write about Doubly Linked List with its advantages.

**5.**Write in detail about the operations of Singly Linked list

**6.**compute the Running time of the subsequent

(a).

void find_result()

{

int j,i=10,s=0;

for(j=0;j

*s = s + j;*

printf(“%d”,s);

}

(b)

void print_sum(int a[][])

{

int i,j;

float s=0;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

if(i==j)

s = s + a[i][j];

}

}

printf(“%f”,s); }

Expression’ using stack.

of stack while compiling the functions in a program.

UNIT II

1. What is a Tree ADT. describe ‘height’ of a tree with example.

2. What is a Binary tree? What is the avg. depth of a binary search tree? Draw Worst-case binary tree and specify its depth.

3. Write algorithm to insert a value into binary search tree.

4. What is an expression tree? Draw an expression tree for a*b*c+e/d.

5. What is lazy deletion?

6. What are self-adjusting data structures?

7. List the situations in which single rotations be performed in an AVL tree.

8. What is B-Tree? List the applications of B-Tree.

9. describe priority queu

10. Give a tree representation of the formula (a+b)*(c+d).

11. What is the worst case search time in a balanced binary tree.

12. Give prefix, infix, postfix expression corresponding to the subsequent tree.

1. Write algorithms to implement the basic binary search tree operations-search, delete.

2. Show the outcome of inserting 3,1,4,6,9,2,5,7 into an initially empty binary search tre

3. Show that the complexity of binary search algorithm for avg. and worst case is O(log2n).

4. Explain the concepts for performing single and double rotations of AVL Trees?

printf(“%d”,s);

}

(b)

void print_sum(int a[][])

{

int i,j;

float s=0;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

if(i==j)

s = s + a[i][j];

}

}

printf(“%f”,s); }

**7.**discuss about the concept of ‘Balancing the Symbols’ and ‘Evaluation of PostfixExpression’ using stack.

**8.**explain about the conversion of Infix into Postfix Notation using Stack and the usageof stack while compiling the functions in a program.

UNIT II

**Part A**1. What is a Tree ADT. describe ‘height’ of a tree with example.

2. What is a Binary tree? What is the avg. depth of a binary search tree? Draw Worst-case binary tree and specify its depth.

3. Write algorithm to insert a value into binary search tree.

4. What is an expression tree? Draw an expression tree for a*b*c+e/d.

5. What is lazy deletion?

6. What are self-adjusting data structures?

7. List the situations in which single rotations be performed in an AVL tree.

8. What is B-Tree? List the applications of B-Tree.

9. describe priority queu

**e.**Mention the properties of Binary Heap.10. Give a tree representation of the formula (a+b)*(c+d).

11. What is the worst case search time in a balanced binary tree.

12. Give prefix, infix, postfix expression corresponding to the subsequent tree.

**Part B**1. Write algorithms to implement the basic binary search tree operations-search, delete.

2. Show the outcome of inserting 3,1,4,6,9,2,5,7 into an initially empty binary search tre

**e.**Show the outcome of deleting the root.3. Show that the complexity of binary search algorithm for avg. and worst case is O(log2n).

4. Explain the concepts for performing single and double rotations of AVL Trees?

Earning: Approval pending. |