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

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