Data Structures & Files : Question Paper Dec 2015 - Information Technology Engineering (Semester 4)

6views

written 6.8 years ago by

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

(6 marks) 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

(8 marks) 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)

ADD COMMENT EDIT