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
Summer2017
BE  Semester
3
Summer  2017

05/31/2017
Total Marks
70
Q1
Short Questions
14 Marks
(1)
Arithmetic expression evaluation is an explanation of which data structure?
1 Marks
(2)
How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available.
1 Marks
(3)
A graph containing only isolated nodes is called a ___.
1 Marks
(4)
What is the 2’s complement representation for integer 5 in modulo 16?
1 Marks
(5)
What is the result of 7+7 using 2’s complement representation and modulo 16 arithmetic.
1 Marks
(6)
In which type of tree, each leaf node is kept at the same distance from root?
1 Marks
(7)
What is the reverse polish notation for infix expression a / b *c ?
1 Marks
(8)
What does the following function do for a given Linked List with first node as head?
1 Marks
(9)
Which of the traversal technique outputs the data in sorted order in a Binary Search Tree?
1 Marks
(10)
What is common in inorder, preorder and postorder traversal?
1 Marks
(11)
For sorting 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?
1 Marks
(12)
In 23 trees, what do leaves contain and what do nonleaf nodes indicate?
1 Marks
(13)
Consider a situation where swap operation is very costly. Which of the sorting algorithms should be preferred so that the number of swap operations are minimized in general?
1 Marks
(14)
Draw tree whose postorder traversal is C B F E G D A
1 Marks
Q2
(a)
Write an algorithm for finding average of given numbers. Calculate time complexity.
3 Marks
(b)
Given Inorder and Preorder traversal, find Postorder traversal.
4 Marks
(c)
Consider an example where the size of the queue is four elements. Initially the queue is empty. It is required to insert symbols ‘A’,’B’ and ‘C’. delete ‘A’ and ‘B’ and insert ‘D’ and ‘E’. Show the trace of the contents of the queue.
7 Marks
OR
(c)
Insertion sequence of names is Norma, Roger,John,Bill,Leo,Paul, Ken and Maurice
7 Marks
Q3
(a)
Write an algorithm to return the value of ith element from top of the stack.
3 Marks
(b)
Write an algorithm for inserting an element in a stack, removing an element from stack .
4 Marks
(c)
Write algorithm for inserting and deleting an element in circular queue.
7 Marks
OR
Q3
(a)
Consider the expression v1*v2(v3+v4^v5). Show the tree corresponding to the expression.
3 Marks
(b)
What is an ordered tree? What is forest?
4 Marks
(c)
Explain the structure of indexed sequential file.
7 Marks
Q4
(a)
Consider singly linked storage structures,Write an algorithm which inserts a node into a linked linear list in a stack like manner.
3 Marks
(b)
How open addressing can be used for collision resolution?
4 Marks
(c)
Explain structure of sequential file. Explain processing in sequential file.
7 Marks
OR
Q4
(a)
Consider singly linked storage structures,Write an algorithm which performs an insertion at the end of a linked linear list.
3 Marks
(b)
Give definitions
4 Marks
(c)
What is priority queue? Explain the array representation of priority queue.
7 Marks
Q5
(a)
Explain outdegree and indegree.
3 Marks
(b)
Explain Depth First Search operation.
4 Marks
(c)
Explain the trace of selection sort on following data.
7 Marks
OR
Q5
(a)
Write and explain application of queue.
3 Marks
(b)
Explain Breadth First Search operation.
4 Marks
(c)
Explain the trace of bubble sort on following data.
7 Marks