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