B.Tech-B.Tech Electrical Engineering 6th Sem 6EE5 Data Structures in C(Rajasthan Technical University-2011)

6E3113
B.Tech. VI Semester (MainlBack) Examination, May/June - 2011
Electrical Engineering (Common for EE and EX)
6EE5 Data Structures in C

Time: 3 Hours
Maximum Marks: 80
Min. Passing Marks : 24

 

 

Unit - I

 

Q.1. a) Solve the recurrence T(n) = 2.T (n/2) + c.n, where c is constant. Define theta ( B) notation and calculate C1,C2 & no to prove that the complexity ofan algorithm given by this recurrence is B (n.log2n). [4+2+4]

b) Define and compare static memory allocation and dynamic memory allocation. [6]

OR

Q.1. Write algorithms to insert a new node in

i) Beginning of a doubly linked list.

ii) Beginning of a circular linked list.

iii) End of doubly linked list.

iv) End of a circular linked list.

Assume that START and END are the pointers to the first and last node respectively. [4x4]

 

Unit - II

 

Q.2. a) What is a sparse matrix? How we can save memory space while storing a sparse mi\trix, suggest two methods. [2+3+3]

b) Formulate the address of element (R,C) in an array A[R1..R2] [C1..C2], whose base address is BASE and size of each element is S, when the array is represented in

i) Row major order

ii) Column major order [4+4]

OR

Q.2. Write algorithms to perform following operations on a sparse matrix, represented in 3-tuple format (using a 3 column array).

i) Read

ii) Transpose

iii) Display [5+6+5]

 

 

Unit - III

 

Q.3. a) What is tower of hanoi problem? Give the recursive solution for the problem. [2+4]

b) Write algorithm to insert and delete an item into a circular queue, assume that FRONT and REAR are pointers to first and last elements of the queue. [5+5]

OR

Q.3. a) Write algorithm to convert an infix expression to postfix expression. [10]

b) Write algorithm to evaluate a postfix expression. [6]

 

 

Unit - IV

 

Q.4. a) Define Binary Search Tree (EST). Write algorithm to inseli an element in BST. [2+6]

b) Discuss deletion of an element in BST. [8]

OR

Q.4. Explain following rotations in AVL tree with the help of neat diagrams,

i) RL rotation

ii) LR

iii) R-I

iv) LO                          [4x4]

 

 

Unit - V

 

Q.5. a) Define minimum spanning tree (MST). Explain prims algorithms for finding MST with the help of example. [2+6]

b) Define a graph. Write any graph traversing algorithm. [2+6]

OR

Q.5. Find the shortest path between every pair of vertices using warshall algorithm, in the graph defined by following adjacency matrix. R,S,T and U are the vertices of the graph.        [16]

 

 

 

 

 

 

 

Earning:  ₹ 6.50/-