Gujarat University 2009-2nd Year B.C.A Computer Application Data and File Structure - Question Paper

1

Answer the following.

14

(A)

Give differences (Any four)

8

1

Sequencial search and Binary search.

2

Linear data structure and Non-linear data structure.

3

Primitive and non-primitive data structure.

4

Base case and Worst case for searching methods.

5

Stack and Queue

(B)

Answer the following

4

Draw and explain memory representation of two-dimensional array using row-major order and column-major order.

(C)

Give the liked list representation of following polynomial:

2

4x³y²-9x²y²+10xy²+6xy-20 = 0

2

Answer the following

14

(A)

Write the algorithms (any two)

6

1

Sort an array with quick short.

2

Convert infix expression to suffix expression.

3

Peform Push, Changes and Delete on the stack.

(B)

Attempt (any two)

4

1

How many searches will be required to search element 79 from the follodwing data using binary search technique? Trace each search.

18  20  29  56  59  69  79  90  101

2

Trace the following data for selection sort:

10  54  23  98  76  33  29  80  6  45

3

Trace the following data for Insertion sort technique:

21  67  19  35  10  6  89  49

(C)

Write short notes on (any two)

4

1

Priority queue

2

Sparse Matrix and its sequencial and linked list representations.

2

Any one applicatoin of stack.

3

Answer the following (any seven).

14

(A)

Write algorithms (any three)

9

1

Insert an element at any position in singlly linked list

2

Perform insertion and deletion operation on circular queue.

3

Insert an element at end in dubly linked list.

(B)

Attempt (any two)

4

1

Write advantages and disadvantages of linked list.

2

Evalute following postfix expression using stack:

ABC^*+D-

Where A = 5 , B = 6 , C = 2 and D = 4.

3

Write advantages of singly linked-list over an array.

(C)

Answer the folowing

1

Draw the representation of empty doubly circular linked list.

4

Answer the following.

14

(A)

Attempt (any three).

6

1

Create binary tree using following traversal orders:

In-order: BACDF

Pre-order: ABDCF

2

Create an expression tree of -+x/yz*dg.

3

Convert following tree into a binary tree.

4

Following data are stored in an array , which represents binary tree. Draw two-way in-order threaded binary tree for this binary tree.

(B)

Attempt (any one)

4

1

Create max heap and min heap tree from the following data :

70  30  45  20  89  71  68  99  32  11

2

Explain any three properties of binary tree with example.

(C)

Write short note on following (any one)

4

1

B-tree

2

AVL tree

5

Answer the following.

14

(A)

Define following with respect to graph (any three).

3

1

Complete graph

2

Null graph

3

loop

4

Edge simple path

(B)

Attempt the following (any one)

5

1

Write a short note on PERT and CPM and find Critical Path for the following graph :

2

Write an algorithm for DFS traversal

(C)

Attempt the following (any two)

6

1

Define adjacency matrix and construct a graph from the following adjacency matrix. Draw adjacency list for the same graph.

2

Draw minimum cost spanning tree for following weighted graph using prim's algorithm and find cost of that spanning tree.

3

Give toopological sorting for following graph.