# RTU Previous Question Papers BE CS 3rd Semester

# Data Structures and Algorithms Feb 2011

**Unit-I**

1.a) How to Define complexity? Explain time and space complexity with simple

algorithm and also explain various characteristics of algorithm.

b) For the following array B compute

i) The dimension of B

ii) The space occupied by B in memory

iii) The address of B [7, 2]

Array : B column index 0 : 5

Base address : 1003 Size of memory location: 4 byte Row index 0:15

**OR**

2. a) What do you understand by Asympotatic Notation? Explain the notation Big ‘O’ Thetha, Omega with suitable example. (2+6) b) Each element of an array a [-20——–20, 10——-35] Required 1 byte of storage. If the array is coloumn major implemented and the beginning of the array is at location 500. Determine the address of element a [0,30].

**Unit – II**

3. a) How to define Queue? What are the application of Queue? And also explain algorithm for insertion and deletion in circular Queue.

b) Write an algorithm to evaluate the prefix expression.

**OR**

4. a) How to define priority Queue? Explain one way and array representation of priority Queue.

b) Transform following prefix expression to infix

a)++ A – * $ BCD/+EF * GHI

b) + – $ ABC * D ** EFG

**Unit-****III**

5. a) Explain insertion and deletion in Doubly linked list with algorithm.

b) Write an algorithm to implement stack operation using linked list.

**OR**

6. a) Explain comparision of arrays and linked list as data structure.

b) What do you mean by searching? Differentiate between sequential search and binary search with suitable example.

**Unit-IV**

7. a) How to define Non-linear Data structure? Explain algorithm for post order traversing in binary tree.

b) What is the importance of threads in Binary tree? How they are represented in memory? Explain with example.

**OR**

8. a) How to define the AVL search tree? Explain insertion and deletion in AVL search tree with example.

b) Suppose the following sequence list the nodes of Binary Tree T in preorder and inorder respectively. Preorder : G, B, Q, A, C, K, F, P, D, E, R, H Inorder : Q, B, K, C, F, A, G, P, E, D, H, R Draw diagram of tree.

**Unit-V**

9. a) How to define graph? Explain representation of graph using adj acency matrix and list.

b) Explain quick sort algorithm in detail with example.

**OR**

10. a) Define the graph traversal and which graph traversal is better? Explain breadth first traversal of graph.

b) How to define sorting? Explain internal and external sorting. Also write algorithm for bubble sorting.