1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER- II EXAMINATION WINTER 2018
Subject Code: 2620001 Date: 01-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

Do as directed.:
State different types of Data Structures.
Compare simple queue with Circular queue.
Define Storage structure.
Draw Threaded Storage Representation of Empty Tree.
State advantages of Doubly linked list over linear linked list.
Which traversal of Binary search tree gives the data elements in
ascending order?
What is the postfix form of the infix expression
07

Write a short note on following
KWIC Indexing
Storage representation of two dimensional array
07
Q.2

Convert following Infix expression to the corresponding Reverse Polish expression using Stack.
b↑ c↑ f
Give the trace of the steps including Stack Contents and Rank in tabular form.
07

Write algorithms for inserting and deleting an element from a Circular queue.
07
OR

Explain briefly Linked Linear List. State applications of Linked Linear List. Explain one of the application briefly.
07
Q.3

What is Doubly Linked List? Describe typical node structure used for it. Write an algorithm to Insert a node in Doubly Linked List.
07

Compare the algorithms of Selection sort with Bubble sort and discuss complexity of the best case ,worst case and average case
07
OR
Q.3

Define Graph. Show various representations for undirected, directed and weighted Graph with suitable example.
07

Sort the following data in ascending order using Quick sort.
42, 23, 74, 11, 65, 58, 94, 36, 99, 87
07
Q.4

Define the term searching? Write an algorithm for Sequential search. Compare performance of sequential search with binary search for small size of data.
07

Write short note on following
Height balance trees
Collision resolution techniques
07
OR
Q.4

Write short note on following
1. Trie Structres
2. AVL Tree
07

What is Hashing Explain three Hashing functions with example.
07
Q.5

Define binary tree. Write a note on storage representation of Binary tree.
07
2

Give difference between DFS and BFS using appropriate example.
07
OR
Q.5

Construct the expression tree for state the result with
preorder ,in-order and post order traversal of tree.
07

Write an algorithm for Two way merge sort. Show all passes of Two way merge sort for the following list:
42, 23, 74, 11, 65, 58, 94, 36, 99, 87
07