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
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
Q1
(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
Q1
(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
Q2
(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
Q2
(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
Q2
OR
Q2
(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
Q3
(b)
How following hash functions work?
4 Marks
Q3
(c)
(i) In which case insertion and deletion cannot be performed in stack?
7 Marks
Q3
OR
Q3
(a)
How primitive data type floating point is stored in computer?
3 Marks
Q3
(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
Q3
(c)
(i) Convert a+b*cd/e*h to postfix.
7 Marks
Q4
(a)
How many null branches a binary tree possesses?
3 Marks
Q4
(b)
What is the difference between serial and sequential processing? How a record can be deleted in sequential file?
4 Marks
Q4
(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
Q4
OR
Q4
(a)
Explain indexing structure for index files.
3 Marks
Q4
(b)
Write recursive algorithm for computing factorial. Which data structure can be used to implement this algorithm?
4 Marks
Q4
(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
Q5
(b)
How binary search technique can be applied to search for a particular item with a certain key?
4 Marks
Q5
(c)
Apply quick sort on following data:
7 Marks
Q5
OR
Q5
(a)
Explain the structure of threaded binary tree.
3 Marks
Q5
(b)
How access of record is performed in multi key file organization?
4 Marks
Q5
(c)
Hash function map several keys into same address called collision. How collision resolution techniques work?
7 Marks