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
Summer2018
BE  Semester
3
Summer  2018

05/21/2018
Total Marks
70
Q1
(a)
Differentiate between linear and non linear data structures.
3 Marks
(b)
Discuss the variations of a queue.
4 Marks
(c)
Write an algorithm to convert an infix expression to postfix expression.
7 Marks
Q2
(a)
Evaluate the following postfix expression using a stack. Show the steps.
3 Marks
(b)
Consider the stack S of characters, where S is allocated 8 memory cells.
4 Marks
(c)
Write a program to implement queue and check for boundary conditions.
7 Marks
OR
(c)
Write a program to implement a circularly linked list.
7 Marks
Q3
(a)
List the advantages of a doubly linked list over singly linked list.
3 Marks
(b)
Write an algorithm to swap two nodes, n and n+1, in a singly linked list.
4 Marks
(c)
Perform inorder, postorder and preorder traversals for the following binary tree.
7 Marks
OR
Q3
(a)
What is a header node? Explain its importance.
3 Marks
(b)
Write an algorithm to count the number of nodes in a singly circularly linked list.
4 Marks
(c)
What is a binary search tree? Create a binary search tree for the following data.
7 Marks
Q4
(a)
Explain the working of the Kruskal’s algorithm.
3 Marks
(b)
Write the algorithm for binary search and find its complexity.
4 Marks
(c)
Insert the following letters into an empty Btree of order 5:
7 Marks
OR
Q4
(a)
Define the following terms with respect to a graph: Node, Edge, Path
3 Marks
(b)
Discuss different representations of a graph.
4 Marks
(c)
Apply Djkstra’s algorithm for the following graph with Node S as the starting node.
7 Marks
Q5
(a)
What is the complexity of the quick sort algorithm on sorted data? Justify your answer.
3 Marks
(b)
What is hashing? Explain hash collision and any one collision resolution technique.
4 Marks
(c)
Explain the difference between insertion sort and selection sort with an example. What is the time complexity of these algorithms? How?
7 Marks
OR
Q5
(a)
List the qualities of a good hash function.
3 Marks
(b)
Explain two hash functions.
4 Marks
(c)
Apply merge sort algorithm for the following data and show the steps.
7 Marks