Subjects
Applied Mathematics for Electrical Engineering  3130908
Complex Variables and Partial Differential Equations  3130005
Engineering Graphics and Design  3110013
Basic Electronics  3110016
MathematicsII  3110015
Basic Civil Engineering  3110004
Physics Group  II  3110018
Basic Electrical Engineering  3110005
Basic Mechanical Engineering  3110006
Programming for Problem Solving  3110003
Physics Group  I  3110011
MathematicsI  3110014
English  3110002
Environmental Science  3110007
Software Engineering  2160701
Data Structure  2130702
Database Management Systems  2130703
Operating System  2140702
Advanced Java  2160707
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Information And Network Security  2170709
Mobile Computing And Wireless Communication  2170710
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