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
Winter2017
BE  Semester
3
Winter  2017

11/14/2017
Total Marks
70
Q1
(a)
A two dimensional array is stored row by row, then what is the address of matrix element A[i,j] for n row and m column matrix? How array representation of polynomial 2x2+5xy+y2 can be done?
3 Marks
(b)
Which data structure is used in a time sharing single central processing unit and one main memory computer system where many users share the system simultaneously? How users are added for use of the system?
4 Marks
(c)
The Preorder traversal of the tree is:
7 Marks
Q2
(a)
What is the problem with sign and magnitude representation if addition of +7 with 6 is performed? Evaluate 7+7 using 2’s complement representation and modulo 16 arithmetic.
3 Marks
(b)
Write an algorithm for calculating square of the number for all the prime numbers ranging between 1 to n. Perform time and space analysis.
4 Marks
(c)
Given a linked list whose typical node consists of an INFO and LINK field. Formulate an algorithm which will count the number of nodes in the list.
7 Marks
OR
(c)
What is the need of doubly linked list? Consider a problem of inserting a node into a doubly linked linear list to the left of a specified node whose address is given by variable M. Give details of algorithm.
7 Marks
Q3
(a)
How directed tree can be represented?
3 Marks
(b)
How following hash functions work?
4 Marks
(c)
(i) In which case insertion and deletion cannot be performed in stack?
7 Marks
OR
Q3
(a)
How primitive data type floating point is stored in computer?
3 Marks
(b)
A communications network is represented by graph. Each node represents a communication line and each edge indicate the presence of interconnection between the lines. Which traversal technique can be used to find breakdown in line? Explain.
4 Marks
(c)
(i) Convert a+b*cd/e*h to postfix.
7 Marks
Q4
(a)
How many null branches a binary tree possesses?
3 Marks
(b)
What is the difference between serial and sequential processing? How a record can be deleted in sequential file?
4 Marks
(c)
What is the advantage of circular queue? Write an algorithm for inserting ‘A’,’B’,’C’,delete ‘A’ and ‘B’and insert ‘D’ and ‘E’ in circular queue .
7 Marks
OR
Q4
(a)
Explain indexing structure for index files.
3 Marks
(b)
Write recursive algorithm for computing factorial. Which data structure can be used to implement this algorithm?
4 Marks
(c)
“If no interchanges occurred, then the table must be sorted and no further passes are required.” Which sorting method works on this principal?
7 Marks
Q5
(a)
How does priority queue work?
3 Marks
(b)
How binary search technique can be applied to search for a particular item with a certain key?
4 Marks
(c)
Apply quick sort on following data:
7 Marks
OR
Q5
(a)
Explain the structure of threaded binary tree.
3 Marks
(b)
How access of record is performed in multi key file organization?
4 Marks
(c)
Hash function map several keys into same address called collision. How collision resolution techniques work?
7 Marks