Subjects
Advanced Java  2160707
Basic Electrical Engineering  3110005
Basic Mechanical Engineering  3110006
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Data Structure  2130702
Database Management Systems  2130703
Engineering Graphics & Design  3110013
English  3110002
Environmental Science  3110007
Information And Network Security  2170709
MathematicsI  3110014
Mobile Computing And Wireless Communication  2170710
Operating System  2140702
Physics Group  I  3110011
Physics Group  II  3110018
Programming for Problem Solving  3110003
Software Engineering  2160701
Theory Of Computation  2160704
Workshop  3110012
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