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
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?
| Earning: Approval pending. |
