Data Structure (2130702)

BE | Semester 3 
  Summer - 2017|05/31/2017
Total Marks 70

Q1
Short Questions

  (1) Arithmetic expression evaluation is an explanation of which data structure?

  (2) How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available.

  (3) A graph containing only isolated nodes is called a ___.

  (4) What is the 2’s complement representation for integer 5 in modulo 16?

  (5) What is the result of 7+7 using 2’s complement representation and modulo 16 arithmetic.

  (6) In which type of tree, each leaf node is kept at the same distance from root?

  (7) What is the reverse polish notation for infix expression a / b *c ?

  (8) What does the following function do for a given Linked List with first node as head?

  (9) Which of the traversal technique outputs the data in sorted order in a Binary Search Tree?

  (10) What is common in inorder, preorder and postorder traversal?

  (11) For sorting 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

  (12) In 2-3 trees, what do leaves contain and what do nonleaf nodes indicate?

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

  (14) Draw tree whose postorder traversal is C B F E G D A

Q2 (a) Write an algorithm for finding average of given numbers. Calculate time complexity.

  (b) Given Inorder and Preorder traversal, find Postorder traversal.

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

OR

  (c) Insertion sequence of names is Norma, Roger,John,Bill,Leo,Paul, Ken and Maurice

Q3 (a) Write an algorithm to return the value of ith element from top of the stack.

  (b) Write an algorithm for inserting an element in a stack, removing an element from stack .

  (c) Write algorithm for inserting and deleting an element in circular queue.

OR

Q3 (a) Consider the expression v1*v2-(v3+v4^v5). Show the tree corresponding to the expression.

  (b) What is an ordered tree? What is forest?

  (c) Explain the structure of indexed sequential file.

Q4 (a) Consider singly linked storage structures,Write an algorithm which inserts a node into a linked linear list in a stack like manner.

  (b) How open addressing can be used for collision resolution?

  (c) Explain structure of sequential file. Explain processing in sequential file.

OR

Q4 (a) Consider singly linked storage structures,Write an algorithm which performs an insertion at the end of a linked linear list.

  (b) Give definitions

  (c) What is priority queue? Explain the array representation of priority queue.

Q5 (a) Explain outdegree and indegree.

  (b) Explain Depth First Search operation.

  (c) Explain the trace of selection sort on following data.

OR

Q5 (a) Write and explain application of queue.

  (b) Explain Breadth First Search operation.

  (c) Explain the trace of bubble sort on following data.