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

05/31/2017
Total Marks
70
Q1
Short Questions
14 Marks
Q1
(1)
Arithmetic expression evaluation is an explanation of which data structure?
1 Marks
Q1
(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
Q1
(3)
A graph containing only isolated nodes is called a ___.
1 Marks
Q1
(4)
What is the 2’s complement representation for integer 5 in modulo 16?
1 Marks
Q1
(5)
What is the result of 7+7 using 2’s complement representation and modulo 16 arithmetic.
1 Marks
Q1
(6)
In which type of tree, each leaf node is kept at the same distance from root?
1 Marks
Q1
(7)
What is the reverse polish notation for infix expression a / b *c ?
1 Marks
Q1
(8)
What does the following function do for a given Linked List with first node as head?
1 Marks
Q1
(9)
Which of the traversal technique outputs the data in sorted order in a Binary Search Tree?
1 Marks
Q1
(10)
What is common in inorder, preorder and postorder traversal?
1 Marks
Q1
(11)
For sorting 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?
1 Marks
Q1
(12)
In 23 trees, what do leaves contain and what do nonleaf nodes indicate?
1 Marks
Q1
(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
Q1
(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
Q2
(b)
Given Inorder and Preorder traversal, find Postorder traversal.
4 Marks
Q2
(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
Q2
OR
Q2
(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
Q3
(b)
Write an algorithm for inserting an element in a stack, removing an element from stack .
4 Marks
Q3
(c)
Write algorithm for inserting and deleting an element in circular queue.
7 Marks
Q3
OR
Q3
(a)
Consider the expression v1*v2(v3+v4^v5). Show the tree corresponding to the expression.
3 Marks
Q3
(b)
What is an ordered tree? What is forest?
4 Marks
Q3
(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
Q4
(b)
How open addressing can be used for collision resolution?
4 Marks
Q4
(c)
Explain structure of sequential file. Explain processing in sequential file.
7 Marks
Q4
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
Q4
(b)
Give definitions
4 Marks
Q4
(c)
What is priority queue? Explain the array representation of priority queue.
7 Marks
Q5
(a)
Explain outdegree and indegree.
3 Marks
Q5
(b)
Explain Depth First Search operation.
4 Marks
Q5
(c)
Explain the trace of selection sort on following data.
7 Marks
Q5
OR
Q5
(a)
Write and explain application of queue.
3 Marks
Q5
(b)
Explain Breadth First Search operation.
4 Marks
Q5
(c)
Explain the trace of bubble sort on following data.
7 Marks