Subject
DS - 2130702
DBMS - 2130703
SE - 2160701
About
About Us
Contact Us
Paper Solution of
DS
(2130702)
for
Summer
- 2016
Data-Structure-2130702
Summer-2016
Modal title
Widget settings form goes here
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - Semester - ____ EXAMINATION -
Summer-2016
Date:
06/09/2016
Total Marks :
70
NOTE:
Click on the Question to View Answer!
Q.1
Short Question
(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 B-Tree.
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
Q.2
(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
Q.3
(a)
Evaluate the following postfix expression using stack:
(a) 9 3 4 * 8 + 4 / -
(b) 5 6 2 + * 1 2 4 / - +
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
Q.3
(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
Q.4
(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
Q.4
(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
Q.5
(a)
Explain Breadth First Search in graphs with an example.
3 marks
(b)
Construct a binary tree from the traversals given below:
Inorder: 1 3 4 6 7 8 10 13 14
Preorder: 8 3 1 6 4 7 10 14 13
4 marks
(c)
Explain various Hash collision resolution techniques with examples.
7 marks
OR
Q.5
(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:
(A $ B $ C) + (D – E * F)
4 marks
(c)
Write Prim’s algorithm for minimum spanning tree with an example.
7 marks