Second Year B.Tech. (CSE) (Sem-III)
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.
Q.1 Solve any five questions.
i) What is circular linked list?
ii) Convert the following infix expression to equivalent postfix expression.
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]
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]