Subjects
Advanced Java  2160707
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Data Structure  2130702
Database Management Systems  2130703
Information And Network Security  2170709
MathematicsI  3110014
Mobile Computing And Wireless Communication  2170710
Operating System  2140702
Software Engineering  2160701
Theory Of Computation  2160704
Semester
Semester  1
Semester  2
Semester  3
Semester  4
Semester  5
Semester  6
Semester  7
Semester  8
Data Structure
(2130702)
DS2130702
Summer2016
BE  Semester
3
Summer  2016

06/09/2016
Total Marks
70
Q1
Short Question
14 Marks
(1)
Define primitive data structure.
Marks
(2)
Explain space and time complexity.
Marks
(3)
What is the time complexity of Quicksort algorithm in the worst case?
Marks
(4)
List the applications of Stack.
Marks
(5)
Define graph.
Marks
(6)
Explain degree of a vertex in a graph.
Marks
(7)
List the applications of Graphs.
Marks
(8)
List the applications of Binary trees.
Marks
(9)
Define BTree.
Marks
(10)
Describe the time complexity of Binary search algorithm.
Marks
(11)
What is hash collision?
Marks
(12)
Write ‘C’ structure of Binary tree.
Marks
(13)
Write ‘C’ structure of Singly linked list.
Marks
(14)
Define priority queue.
Marks
Q2
(a)
Write an algorithm for simple queue with ENQUEUE operations.
3 Marks
(b)
Write an algorithm to reverse a string using stack.
4 Marks
(c)
Write a program to implement stack using linked list.
7 Marks
OR
(c)
Write a program to implement circular queue using array.
7 Marks
Q3
(a)
Evaluate the following postfix expression using stack:
3 Marks
(b)
Explain the concept of circular queue. Compare circular queue with simple queue.
4 Marks
(c)
Explain insert and delete operations in AVL trees with suitable examples.
7 Marks
OR
Q3
(a)
Explain double ended queue.
3 Marks
(b)
Write ‘C’ functions to implement DELETE_FIRST_NODE and TRAVERSE operations in doubly linked list.
4 Marks
(c)
With a suitable example, explain steps for conversion of a general tree into a binary tree.
7 Marks
Q4
(a)
Explain Sequential search method.
3 Marks
(b)
Explain Threaded binary trees with suitable examples.
4 Marks
(c)
Write an algorithm for Selection sort method. Explain each step with an example.
7 Marks
OR
Q4
(a)
Explain Depth First Search in graphs with an example.
3 Marks
(b)
Explain Binary search method.
4 Marks
(c)
Write an algorithm for Insertion sort method. Explain each step with an example.
7 Marks
Q5
(a)
Explain Breadth First Search in graphs with an example.
3 Marks
(b)
Construct a binary tree from the traversals given below:
4 Marks
(c)
Explain various Hash collision resolution techniques with examples.
7 Marks
OR
Q5
(a)
Explain Sequential file organizations and list its advantages and disadvantages.
3 Marks
(b)
Draw a Binary expression tree for the following and perform preorder traversal:
4 Marks
(c)
Write Prim’s algorithm for minimum spanning tree with an example.
7 Marks