CS8391 Data Structures Anna University Questions Answers April May 2019

CS8391 Data structures exam questions and answers April May 2019, Anna University CS8391 questions, Data structures university exam solved question paper, CS8391 Data Structures CSE/IT/CCE answers, CS8391 Data structures regulation 2017

 

Exam	B.E/B.Tech. (Full Time) DEGREE END SEMESTER EXAMINATIONS
Academic Year	April May 2019
Subject Code	CS8391
Subject Name	Data Structures
Branch	Computer Science and Engineering / Information Technology / Computer and Communication Engineering
Semester	Third Semester
Regulation	2017

 

B.E / B.Tech. (Full Time) DEGREE END SEMESTER EXAMINATIONS, APRIL / MAY 2019

CSE / IT / CCE

Third Semester

CS8391 – Data Structures

(Regulation 2017)

Time : 3 Hours                      Answer A L L Questions                Max. Marks 100

PART-A (10 x 2 = 20 Marks)

 

1. What are the advantages of Linked List over arrays?

Answer:

• Linked list is dynamic data structure whereas array is static. It means, linked list can grow during programs execution whereas array cannot. The array size is fixed
• Insertion and deletion can take place in any place of linked list easily. This cannot be the case for array where insertion in a particular place may need to move many other existing elements, and deletion is not possible.
  

2. Illustrate the differences between Linear linked list and Circular linked list.

Answer:

• In linear linked list, there is a last node and that will be pointing to NULL. In circular linked list, there is no last node. Actually the last node is connected to the first node hence form a chain.
• You can visit the previous nodes using the chain in circular linked list, whereas you cannot visit the previous nodes in linear linked list.
  

3. Convert the following infix expression to postfix expression using Stack a+b*c+(d re+f)/g.

4. A priority queue is implemented as a Max- Heap. Initially it has 5 elements. The level order traversal of the heap is : 10, 8, 5, 3, 2. Two new elements 11 and 7 are inserted into the heap in that order. Give the level order traversal of the heap after the insertion of elements.

5. How to resolve null links in a binary tree?

Answer:

The NULL links in a binary tree of N nodes will be N+1. 

Proof: The proof of the claim is by induction on N.

Basis step:  N=1.  The tree has one node and two NULL links as children.

Induction step: Suppose the claim is true for all 1 <= m <= N, N >= 1.  Then consider any (N+1)-node binary tree T.  It has q NULL links.  If we remove one leaf from T, then the resulting binary tree T' has two fewer NULL links (from the     removed leaf), but its parent now has a NULL link it did not have in T.  So, T has q-2+1 = q-1 NULL links as children.

 

T' has N nodes, so by the induction hypothesis, T' has N+1 NULL links as children.  Therefore, q-1 = N+1, and so q = (N+1)+1.  Thus, every (N+1)-node binary tree has N+2 NULL links as children.

 

6. The depth of complete binary tree is 8 and compute the number of nodes in leaf.

Answer:

A complete binary tree is a proper binary tree where all leaves have the same depth. In a complete binary tree, the number of nodes at depth d is 2^d. The number of leaf nodes in a complete binary tree of depth 8 is 2⁸ which is 256.

7. What is Bi-connectivity?

8. Given a weighted, undirected graph with |V| nodes, Assume all weights are non-negative. If each edge has weight <=w, What can you say about the cost of Minimum spanning tree?

9. Brief about Extendible hashing.

10. Compare linear search and Binary search.

 

PART B — (5 * 13 = 65 marks)

 

11. (a) i) Write a program to merge two sorted linked list (P & Q – assume that they are available) to get a single sorted list S.

Eg. P:1->2->45->56

Q: 3->24->56->63->66, (8)

ii) Write a non-recursive procedure to reverse a singly linked list. (5)

Or

(b) i) Write a function to add two polynomials represented by linked representation. Apply the function for the following input.

A= 3x¹⁴ + 2x¹⁸ +1, B= 8x¹²+ 3x¹⁰ + 3x⁸ +10x⁶ (9)

ii) Write a function to delete the node n from the given doubly linked list. (4)

p↔q↔r↔n↔s↔t↔z↔.

 

12. (a) Write algorithms to check if the given parenthesized arithmetic expression contains balanced parenthesis and to convert such expression to postfix form and evaluate it, Illustrate with example. (13)

Or

(b) i) State the advantage of Circular queue over linear queue, Write the functions for Insertion in a circular queue. (5)

ii) Build the max heap for the following 90, 150, 70, 40, 100, 20, 30, 10, 110. And show the result of delete max. (8)

 

13. (a) i) Write a routine for Post order traversal. Is it possible to find minimum and maximum value in the binary search tree using traversals? Discuss. (3)

ii) Display the given tree (Figure 13. a) using Inorder, Preorder and Postorder Traversals. (6)

 

ii) Delete 11 and 10 from the above binary search tree. And display the tree after each deletion. (4)

Or

(b) i) Write a routine for AVL tree insertion. Insert the following elements in the empty tree and how do you balance the tree after each element insertion?

Elements : 2, 5, 4, 6, 7,9, 8, 3,1, 10. (8)

ii) Brief about B+ Tree. And discuss the applications of heap. (5)

 

14. (a) Apply an appropriate algorithm to find the shortest path from ‘A’ to every other node of A. For the given graph Fig. 14(a) (13)

 

 Or

(b) i) Explain in detail about strongly connected components and illustrate with an example. (7)

ii) Find an Euler path or an Euler circuit using DFS for the following graph Fig. 14(b). (6)

Fig. 14(b)

 

15. (a) Consider a hash table with 9 slots. The hash function is h(k) =k mod 9. The following keys are inserted in the order 5, 28, 19, 15, 20, 33, 12, 17, 10. Draw the contents of the hash table when the collisions are resolved by

i) Chaining

ii) Linear probing

iii) Double hashing. The second hash function h2(x) = 7-(x mod 7) — (13)

Or

(b) i) Write a function to perform merge sort. Give example (6)

ii) Write a routine for Insertion sort. Sort the following sequence using Insertion sort. 3, 10, 4, 2, 8, 6,5, 1.                    (7)

 

PART C — (1 * 15 = 15 marks)

16. (a) i) Indicate whether you use an Array, Linked List or Hash Table to store data in each of the following cases. Justify your answer. (6)

(1) A list of employee records needs to be stored in a manner that it is easy to find max or min in the list.

(2) A library needs to maintain books by their ISBN number. Only thing important is finding them as soon as possible.

(3) A data set needs to be maintained in order to find the median of the set quickly.

ii) Define data abstraction. Write the ADT for the data structure in which the same condition can used appropriately, for checking over flow and underflow. Define all basic function of this ADT. (9)

Or

(b) i) When do you perform rehashing? [Illustrate with example. (8)

ii) From the Figure 16. (b), in what order are the vertices visited using DFS and BFS starting from vertex A? Where a choice exists, use alphabetical order. (7)

 

Figure 16. (b)

 

*************