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
Winter2016
BE  Semester
3
Winter  2016

01/02/2017
Total Marks
70
Q1
Explain the following terms in brief
14 Marks
(1)
Primitive data structure.
Marks
(2)
Nonprimitive data structure.
Marks
(3)
Linear data structure.
Marks
(4)
Nonlinear data structure.
Marks
(5)
Recursion.
Marks
(6)
Time complexity of an algorithm.
Marks
(7)
Doubleended queue.
Marks
(8)
Priority queue.
Marks
(9)
Circular linked list.
Marks
(10)
Complete binary tree.
Marks
(11)
23 tree.
Marks
(12)
Minimum spanning tree.
Marks
(13)
Degree of vertex.
Marks
(14)
Hash collision.
Marks
Q2
(a)
Write a pseudocode for PUSH and POP operations of stack.
3 Marks
(b)
What is prefix notation? Convert the following infix expression into prefix.
4 Marks
(c)
Write an algorithm to perform various operations (insert, delete and display) for simple queue.
7 Marks
OR
Q3
(a)
Convert the following infix expression into postfix.
3 Marks
(b)
Write algorithm(s) to perform INSERT_FIRST (to insert a node at the first position) and REVERSE_TRAVERSE (to display the data in nodes in reverse order) operations in doubly linked list.
4 Marks
(c)
Write a ‘C’ program to implement stack using linked list.
7 Marks
OR
Q3
(a)
3 Marks
(b)
Discuss various rehashing techniques.
4 Marks
(c)
Write ‘C’ functions to implement INSERT_FIRST (to insert a node at the first position), DELETE_FIRST (to delete a node from the first position), DELETE_LAST (delete a node from the last position) and TRAVERSE (to display the data in nodes) operations in circular linked list.
7 Marks
Q4
(a)
Write an algorithm for Binary search method.
3 Marks
(b)
4 Marks
(c)
Sort the following numbers using
7 Marks
OR
Q4
(a)
Write a ‘C’ function for Selection sort.
3 Marks
(b)
Write an algorithm for Quick sort.
4 Marks
(c)
Explain Depth First Search and Breadth First Search in graphs with an example.
7 Marks
Q5
(a)
Draw a binary expression tree for the following and perform preorder traversal for the same:
3 Marks
(b)
Construct a binary search tree for the following and perform inorder and postorder traversals:
4 Marks
(c)
Write ‘C’ functions for: inserting a node, postorder traversal and counting total number of nodes for binary search tree.
7 Marks
OR
Q5
(a)
Explain AVL trees.
3 Marks
(b)
Construct a binary search tree from the following traversals:
4 Marks
(c)
Write Kruskal’s algorithm for minimum spanning tree with an example.
7 Marks