## Data Structures & Files - Dec 2015

### Information Technology Engineering (Semester 4)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.

### Solve any one question from Q1 and Q2

**1 (a)** Transform the following expression to prefix and postfix:

A+(((B-C)*(D-E)F)/G) $ (H-J) Here consider $ as a raised to operator.(6 marks)
**1 (b)** What is the priority queue? What is its use? Write a pseudo code for the function to add an element in the priority queue.(6 marks)
**2 (a)** What is Stack? Write a program for implementation of stack using linked organization and perform the following operation:

i) PUSH

ii) POP.(6 marks)
**2 (b)** Explain the concept of multi-queue and double ended queue with example.(6 marks)

### Solve any one question from Q3 and Q4

**3 (a)** Write a c function for inorder and preorder traversal of an inorder threaded binary tree.(6 marks)
**3 (b)** Consider the graph G given in figure below. Draw the adjacency list of G is also given. Assume that G represents the daily flights between different cities and we want to fly from city A to H with minimum stops. Find the minimum path p from A to H given that every edge has length of 1.
(6 marks)
**4 (a)** A binary tree is stored in the memory of a computer as shown below. Trace the structure of the binary tree and write the INORDER, PREORDER, POSTORDER traversal of the same:

Assume Root: 7

Node Number |
Lehild |
Data |
Rehild |

1 | 2 | 844 | 6 |

2 | 0 | 796 | 0 |

3 | 0 | 110 | 0 |

4 | 0 | 565 | 9 |

5 | 12 | 444 | 0 |

6 | 10 | 116 | 0 |

7 | 4 | 123 | 1 |

8 | 0 | 444 | 0 |

9 | 8 | 767 | 3 |

10 | 0 | 344 | 0 |

**4 (b)**Write a pseudo code for Prims algorithm.(6 marks)

### Solve any one question from Q5 and Q6

**5 (a)** Draw a Huffman's Tree for the given data set and find the corresponding Huffman Codes:

Character |
Weight |

A | 3 |

B | 15 |

C | 2 |

D | 4 |

E | 5 |

F | 12 |

G | 5 |

H | 10 |

I | 3 |

J | 4 |

K | 6 |

L | 8 |

M | 7 |

N | 2 |

**5 (b)**What are the characteristics of good hash function? List out different techniques to resolve collision in a hash table. Explain any one.(6 marks)

**6 (a)**Obtain an AVL tree by inserting all months in a calendar year. Label the rotations at appropriate place.(10 marks)

**6 (b)**Create a max heap with the following elements:

17 25 8 0 1 250 1008 65 48 101(4 marks)

### Solve any one question from Q7 and Q8

**7 (a)** Write a pseudo C code for all primitive operations of index sequential file.(8 marks)
**7 (b)** Distinguish between logical and physical deletion of records and illustrate it with an example.(4 marks)
**8 (a)** What is File? Explain different types of file organization.(6 marks)
**8 (b)** Write a pseudo code to perform the following operations on Direct Access File:

i) Insert

ii) Delete.(6 marks)