**Second Year B.Tech. (CSE) (Sem-III)****Data Structures****[Revised]**

**Time :3 Hours Max. Marks : 80**

Instructions to the candidates:

1) AQ.No.1 and 6 are compulsory.

2) Solve any two questions from the remaining in each section.

**Section A**

Q.1 Solve any five questions.

i) What is circular linked list?

ii) Convert the following infix expression to equivalent postfix expression.

A-(B+C)*D/E

iii) What is a recursive function?

iv) What is an ADT? How it is useful?

v) What is a circular Queue?

vi) What are primitive and non-primitive data structures?

vii) Write any four applications of stack. **[10M]**

Q.2 a) What are the advantages and limitations of linked lists over arrays? **[5M]**

b) What are the basic operations that can be performed on the Queue? Explain the

implementation of Queue using linked list. **[10M]**

Q.3 a) Explain the ADT specification of a rational number. **[5M]**

b) Describe an algorithm for the conversion of an infix expression to postfix expression using

stack with an example. **[10M]**

Q.4 a) Write an algorithm for the following operations on a doubly linked list.

i) Append a node ii) Delete a node **[5M]**

b) Explain the algorithm for adding two polynomials using a linked list with an example. **[10M]**

Q.5 a) Explain the dynamic memory allocation functions in detail. **[5M]**

b) Write brief notes on circular Queue, double ended queue and priority queue. **[10M]**

**Section B**

Q.6 Attempt any five questions:-

i) What is a 2-3 tree?

ii) What are the properties of a BST?

iii) What are the techniques of representing a graph in memory?

iv) What is B+ tree? What are the applications?

v) Sort the following list using insertion sort :

8, 2, 4, 6, 9, 7, 10, 1, 5, 3.

vi) What is hashing? Give the characteristics of hash function.

vii) What are spanning trees and minimum cost spanning trees? **[10M]**

Q.7 a) Differentiate between tree traversal and graph traversal. **[5M]**

b) Explain Bell-man ford algorithm with an example. **[10M]**

Q.8 a) What are the Collision resolution techniques in hashing? Explain. **[10M]**

b) Show the steps of sorting the following elements in ascending order using quick sort. Show

the snapshots after every interchange:

25, 57, 48, 37, 12, 92, 86 **[5M]**

Q.9 a) Write a recursive ‘C’ function to perform binary search of ‘n’ data elements for a given

key, k. **[5M]**

b) Compare insertion and deletion in B- tree and B+ tree. **[10M]**

Q.10 a) Explain the following terms:-

i) Height balanced tree ii) Threaded binary tree **[5M]**

b) What do you mean by traversing a binary tree? Explain the tree traversal techniques with

the help of an example. **[10M]**

Login

Accessing this course requires a login. Please enter your credentials below!