Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER- 2 EXAMINATION WINTER 2018
Subject Code: 3620002 Date: 03-01-2019
Subject Name: Data Structures
Time: 02.30 pm to 5.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(a)
Do as Directed.
07
Define Data Structures
Define :Primitive data structure
Give two example of Stack application.
Define sparse matrix.
What is dequeue?
Write application of tree.
Trie structure.

Write a short note on KWIC indexing.
03
What is string? Explain any three string handling functions. Write the applications of
string.
04
Q.2(a)
Explain the storage structure in Array.
07

What is stack? Write an algorithm to insert ,pop and peep from a stack.
07
OR

Write the algorithm to convert infix to postfix and convert the following expression
into postfix. A B C D E F G
07
Q.3(a)
What is queue? Write algorithm to insert and pop element
From double ended queue.
07

Define recursion. What care should be taken in writing recursive functions? Give a
recursive solution for the problem of Towers of Hanoi.
07
OR

What is a linked list? Write the algorithm to insert an element in a doubly linked list.
07

Write an algorithm for Binary Search. Discuss time analysis for Binary Search
algorithm and trace it for following sample table to search the value 275.
75 151 203 275 318 489 524 591 647 727
07
Q.4(a)
What is graph? Explain all the type representation of graphs with suitable example.
07

Write Kruskal's algorithm for minimum spanning tree with an example.
07
OR

What is hashing? Explain hash collision and any one collision resolution technique.
Explain two hash functions.
07

What is sorting? Write an algorithm to perform Selection sort.
Trace the algorithm for following input values (to arrange them in ascending order).
10 50 0 20 30 10
07
Q.5(a)
Explain sparse matrix with multi linked structure with example.
Difference between DFS and BFS.
04
03

Define heap tree. Explain types of heap tree. Demonstrate creation of min heap tree for
the following set of data: 80, 45, 70, 95]
07
OR

What is Merge sort? Write its algorithm and state its complexity.
07

Explain AVL trees.
Construct a binary search tree from the following traversals:
Inorder: 3 4 5 6 7 9 17 20 22
Preorder: 9 4 3 6 5 7 17 22 20
03
04