1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA INTEGRATED SEMESTER-III • EXAMINATION SUMMER 2017
Subject Code: 4430602 Date:08/05/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

Do as Directed
1. What is the advantage of doubly linked list over singly linked list?
2. What is circular queue?
3. Draw node structure of 3 variable polynomial.
4. Give difference between full binary tree and complete binary tree.
5. Define best case and worst case of time complexity.
01
01
01
02
02

Do as directed
1. Define multiplicity and weighted graph
2. Define parallel edges and multigraph
3. Define biconnected graph and cutvertex
4. If there are 20 nodes in binary tree, then it is having null branches.
02
02
02
01
Q.2

1. Draw expression tree of the following expression
A B C D E F H
2. Write algorithm to insert an element in circular queue.
3. If depth of the binary tree is then total no. of nodes are .
03
03
01

Find preorder:
Inorder 1 3 5 6 4 2 7
Postorder 6 5 4 3 7 2 1
07
OR

Convert following infix expression into postfix using stack table.
A B C D E F H
07
Q.3

1. Give difference between BFS and DFS.
2. Explain topological sorting in detail with e.g.
03
04

What is asymptotic notation? List and explain asymptotic notations in detail.
07
OR
Q.3

Draw AVL tree using following elements
21,22,23,24,25,26
07

1. Give difference between linear search and binary search.
2. Explain KWIC indexing in detail with e.g.
03
04
Q.4

Write algorithm to add two 3 variable polynomials.
07

Write algorithm of quick sort and arrange following elements in sorted order using quick sort.
50,15,62,5,20,58,91,3
07
OR
Q.4

Write algorithm to insert and delete node from circular singly linked list.
07

Arrange following elements in sorted order using heap sort.
50,15,62,5,20,58,91,3
07
Q.5

What is hashing? Explain collision resolution techniques in detail.
07
2

What is MST? Explain Kruskal's algorithm by taking e.g.
07
OR
Q.5

Explain Dijkstra's algorithm by taking e.g.
07

1. Write a short note on trie structure.
2. Write a short note on garbage collection.
03
04