1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER II- EXAMINATION WINTER 2017
Subject Code: 2620001 Date: 29-12-2017
Subject Name: Data Structure
Time: 02:30 pm to 05:00 pm Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1

Write any seven out of the following:
Define Big Oh notation.
ii) List out the areas where Data Structure is used extensively.
iii) What are the primitive string handlings functions?
iv) Write at least three operations normally performed on Tree.
What is the role of HEAD node in doubly linked list?
vi) What is storage structure and file structure?
vii) Define Null Graph
viii) What is Garbage Collection
ix) Define Multiway Tree
What is Trie Structure
07

What is KWIC Indexing?
ii) Represent 2x2+5xy+y2 in two dimensional array of size 5×5.
04
03
Q.2

In which situation linked list data structure is used? What are the disadvantages of linked list data structure? Compare Array with Linked List.
07

Write an algorithm for Depth First Traversal. Give the DFT traversal from vertex H for following graph and show the content of stack.
07
OR

Describe briefly Circular Linked List and a typical Node Structure used for it. Write the pseudo code of an Algorithm to Delete a Node from Circular Linked List whose address is specified.
07
2
Q.3

1. What is hashing function? Explain the following hashing methods
a. The Folding Method
b. The Division Method
c. The Midsquare Method
07

Write an algorithm for Binary Search.
07
OR
Q.3

Define Graph. State its different storage representations. Explain the Matrix representation of a Graph. If A is the matrix representation of a graph, What A2, A3… An indicate?
07

Explain the Dijkstra's algorithm by giving suitable example.
07
Q.4

Differentiate between Stack and Queue.
ii) Discuss the various applications of stack.
03
04

Write algorithm of factorial using recursion and iteration. Discuss which is better and why.
07
OR
Q.4

Convert the following Infix expression to the corresponding Reverse Polish expression: b↑ c↑ f d). Give the trace of the steps including Stack Contents and Rank in tabular form.
04
03

Write the algorithm for insertion and deletion of node in linked representation of Queue and explain the benefits of linked representation against array representation of Queue. Specify two applications of queue.
07
Q.5

What is the significance of Threaded Binary Tree? Give the node structure of it. Also explain advantages of threaded binary tree. Construct threaded binary tree for given data: 67, 34, 12, 11, 56, 89, 54, 33, 98, 17.
07

What is sorting? Explain Bubble sort algorithm and trace it with sample data.
07
OR
Q.5

Show all passes of Heap Sort for the list:
04
03

Define the characteristic of a B-Tree. Construct a B-tree of order 5 by inserting following elements: 23,12,20,26,4,16,18,24,25 and 19.
07