Data Structure (2130702)

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?

  (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?

  (c) The Preorder traversal of the tree is:

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.

  (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.

  (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.

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.

Q3 (a) How directed tree can be represented?

  (b) How following hash functions work?

  (c) (i) In which case insertion and deletion cannot be performed in stack?

OR

Q3 (a) How primitive data type floating point is stored in computer?

  (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.

  (c) (i) Convert a+b*c-d/e*h to postfix.

Q4 (a) How many null branches a binary tree possesses?

  (b) What is the difference between serial and sequential processing? How a record can be deleted in sequential file?

  (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 .

OR

Q4 (a) Explain indexing structure for index files.

  (b) Write recursive algorithm for computing factorial. Which data structure can be used to implement this algorithm?

  (c) “If no interchanges occurred, then the table must be sorted and no further passes are required.” Which sorting method works on this principal?

Q5 (a) How does priority queue work?

  (b) How binary search technique can be applied to search for a particular item with a certain key?

  (c) Apply quick sort on following data:

OR

Q5 (a) Explain the structure of threaded binary tree.

  (b) How access of record is performed in multi key file organization?

  (c) Hash function map several keys into same address called collision. How collision resolution techniques work?