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

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