Data Structures- Computer Science Engineering-Dec2019

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]