Data Structures - Dec 2015

Computer 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.

Short Questions

1(a) Define data structure(1 marks) 1(b) List operations performed on a stack(1 marks) 1(c) Mention variations of the queue data structure.(1 marks) 1(d) What is the worst case time complexity of searching an element in a list? How?(1 marks) 1(e) Mention one operation for which use of doubly linked list is preferred over the singly linked list.(1 marks) 1(f) Write an algorithm/steps to traverse a singly linked list.(1 marks) 1(g) Define: Height of a tree.(1 marks) 1(h) What is the height of a complete binary with n nodes?(1 marks) 1(i) Write two simple hash functions.(1 marks) 1(j) What is a header node and what is its use?(1 marks) 1(k) Is Queue a priority queue? Justify(1 marks) 1(l) What is the complexity of binary search algorithm?(1 marks) 1(m) Name two divide and conquer algorithms for sorting(1 marks) 1(n) Give two applications of graphs.(1 marks) 2(a) Write an algorithm to check if an expression has balanced parenthesis using stack.(3 marks) 2(b) What is postfix notation? What are its advantages? Convert the following infix expression to postfix. A$B-C*D+E$F/G(4 marks)

Solved any one question from 2(c) & 2(d)

2(c) Write a C program to implement a stack with all necessary overflow and underflow checks using array.(7 marks) 2(d) Write a C program to implement a circular queue using array with all necessary overflow and underflow checks(7 marks)

Solved any one question from Q.3 & Q.4

3(a) Evaluate the following postfix expression using a stack. Show the stack contents.
AB*CD$-EF/G/+ A=5, B=2, C=3, D=2, E=8, F=2, G=2(3 marks) 3(b) Perform following operations in a circular queue of length 4 and give the Front, Rear and Size of the queue after each operation
1) Insert A, B
2) Insert C
3) Delete
4) Insert D
5) Insert E
6) Insert F
7) Delete(4 marks) 3(c) Write a program to insert and delete an element after a given node in a singly linked list.(7 marks) 4(a) Explain various applications of queue.(3 marks) 4(b) Differentiate between arrays and linked list(4 marks) 4(c) Create a doubly circularly linked list and write a function to traverse it(7 marks)

Solved any one question from Q.5 & Q.6

5(a) Define complete binary tree and almost complete binary tree.(3 marks) 5(b) Explain deletion in an AVL tree with a suitable Example(4 marks) 5(c) What is binary tree traversal? What are the various traversal methods? Explain any two with suitable example.(7 marks) 6(a) Mention the properties of a B-Tree.(3 marks) 6(b) Construct a binary tree from the traversals given below:
Inorder: 1, 10, 11, 12, 13, 14, 15, 17, 18, 21
Postorder: 1, 11, 12, 10, 14, 18, 21, 17, 15, 13(4 marks) 6(c) What is a binary search tree? Create a binary search tree for inserting the following data.
50, 45, 100, 25, 49, 120, 105, 46, 90, 95
Explain deletion in the above tree.(7 marks)

Solved any one question from Q.7 & Q.8

7(a) Insert the following elements in a B-Tree. a, g, f, b, k, c, h, n, j(3 marks) 7(b) Apply quicksort algorithm to sort the following data. Justify the steps.
42, 29, 74, 11, 65, 58(4 marks) 7(c) What is hashing? What are the qualities of a good hash function? Explain any two hash functions in detail.(7 marks) 8(a) List advantages and disadvantages of Breadth First Search and Depth First Search.(3 marks) 8(b) What is a minimum spanning tree? Explain Kruskal's algorithm for finding a minimum spanning tree.(5 marks) 8(c) Discuss various methods to resolve hash collision with suitable examples.(7 marks)