How To Exam?

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

Wednesday, 30 January 2013 06:10Web

UNIT I
PART A
1. Define Data Structure.
7. Mention the applications of Stack.
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
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); }

7. discuss about the concept of ‘Balancing the Symbols’ and ‘Evaluation of Postfix
Expression’ using stack.
8. explain about the conversion of Infix into Postfix Notation using Stack and the usage
of 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 queue. 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 tree. 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?