Question Paper: Data Structures & Algorithms : Question Paper Jun 2015 - Electronics & Telecom Engineering (Semester 3) | Pune University (PU)
0

## Data Structures & Algorithms - Jun 2015

### Electronics & Telecom Engineering (Semester 3)

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.

### Answer any one question from Q1 and Q2

1 (a) What do you mean by recursive function? Explain with example.(6 marks) 1 (b) Write a C function for insertion sort to sort integer numbers.(6 marks) 2 (a) Explain parameter passing by value and passing parameter by reference with suitable example.(6 marks) 2 (b) What is pointer ? What are the advantages of using pointer? Explain pointer declaration and its initialization with an example.(6 marks)

### Answer any one question from Q3 and Q4

3 (a) What is singly linked list ? Write C function for inserting a node at a given location into a Singly Linked List.(6 marks) 3 (b) Evaluate the following postfix expression using stack
623+ -382/+*2∧.
Note: ∧ stands for power and all operands are single digit.
(7 marks)
4 (a) Write short notes on:
(6 marks)
4 (b) What is priority queue? Explain its implementation using any one method.(7 marks)

### Answer any one question from Q5 and Q6

5 (a) What is Binary Search Tree (BST)? Write C functions for:
(i) Finding the smallest number in BST
(ii) Recursive inorder traversal of BST.
(7 marks)
5 (b) What is AVL Tree ? Define balance factor. Explain RR rotation with an example.(5 marks) 6 (a) What is Binary Search Tree (BST)? Construct a BST for the following numbers:
27, 42, 43, 17, 39, 31, 10, 9, 19, 54, 33, 48.
Show all the steps. Write its preorder traversal
(8 marks)
6 (b) Explain threaded binary tree with an example. What is its advantage?(4 marks)

### Answer any one question from Q7 and Q8

7 (a) Write C function to implement Depth First Search traversal of a graph implemented using adjacency matrix.(6 marks) 7 (b) What do you mean by indegree and outdegree of a vertex in a graph ? Write a C function to find indegree and outdegree of vertex in a graph implemented using adjacency matrix.(7 marks) 8 (a) Define the term Graph. With the help of suitable example give adjacency matrix representation and adjacency list representation of a graph.(7 marks) 8 (b) What do you mean by spanning tree of a graph ? Find the minimal spanning tree of the following graph using Kruskal's algorithm. (Refer Fig. 1). (6 marks)