CS8391 Data Structures Anna University Questions Answers Nov Dec 2018

CS8391 Data structures exam questions and answers November December 2018, 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	November December 2018
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, NOVEMBER / DECEMBER 2018

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. State the advantage of ADT.

Answer:

Abstraction: the user of a type does not need to know or understand any implementation details of the type, which reduces the complexity of the programming task.

Implementations of ADTs can be changed (e.g., for efficiency) without requiring changes to the program that uses the ADTs.

Code is easier to understand (e.g., it is easier to see "high-level" steps being performed, not obscured by low-level code).

Reusability: ADTs can be reused in other programs.

 

2. What are the disadvantages of linked list over array?

Answer:

• Array implementation is simple whereas the linked list is little bit complex
• Wastage of memory space (data+pointer) in linked list. Space for pointer is not required in the case of array.
• Random access in not possible in linked list. In array we can access the required data using its storage index.
  

 

3. What are the applications of stacks?

Answer:

• Check for parenthesis mismatch
  
• Evaluation of expressions
• Conversion of expressions into the other form (infix to postfix, prefix)
• Memory management
• Backtracking problems
  

 

4. What are priority queues? What are the ways to implement priority queue?

5. For the tree in Figure 1.

(a) List the siblings for node E.

Answer: Siblings are nodes that are at the same level and have the same parent. Node D is the sibling of node E.

(b) Compute the height.

Answer: The height of a binary tree is equal to the largest number of the edges from the root to the most distant leaf node. Height of the given tree is 4 (the path A->B->E->J->L or A->B->E->J->M)

6. Show the result of in-order traversal of the binary search tree given in Figure 2.

Answer: Steps of In-order traversal

Visit the left sub-tree using in-order

Visit the root

Visit the right sub-tree using in-order

In-order traversal of the given binary tree: 1 2 3 4 5 6 7 9

7. What are the representations of the graphs?

Answer:

Two common ways to represent graphs on a computer are as an adjacency list or as an adjacency matrix. 

 

8. Define Euler circuits. 

Answer:

An Euler circuit is a circuit that uses every edge of a graph exactly once.

9. What are the advantage and disadvantage of separate chaining and linear probing?

Answer:

	Advantages	Disadvantages
Linear probing	Easy to implement; always finds a location if there is one; very good average-case performance when the table is not very full	“clusters” of keys form in adjacent slots in the table; when these clusters fill most of the array, performance deteriorates
Separate Chaining	Very Easy to implement	Memory Inefficient – requires a secondary data structure to store collisions Long Chains will produce Linear search times

 

10. State the complexity of binary search.

Answer:

Average case complexity : O(log n)

Worst case complexity : O(log n)

 

PART B — (5 x 138 = 65 marks)

 

11. (a) i) State the polynomial representation for 6x³+9x²+7x+1 using linked list. Write procedure to add and multiply two polynomials and explain with suitable example. (7)

ii) What are the ways to insert a node in linked list? Write an algorithm for inserting a node before a given node in a linked list. (6)

Or

(b) i) What are the various operations on array? Write a procedure to insert an element in the middle of the array. (7)

ii) Write a procedure to deleting the last node from a circular linked list. (6)

 

12. (a) Write the procedure to convert the infix expression to postfix expression and steps involved in evaluating the postfix expression. Convert the expression A-(B/C+ (D% E*F)/G*H to postfix form. Evaluate the given postfix expression 9 3 4 * 8 + 4 / -.

Or

(b) What are circular queues? Write the procedure to insert an element to circular queue and delete an element from a circular queue using array implementation.

 

13. (a) Write the following routines to implement the basic binary search tree operations.

i) Perform search operation in binary Search Tree.

ii) Find_min and Find_max.

Or

(b) Distinguish between B Tree and B+ tree. Create a B tree of order 5 by inserting the following elements: 3, 14, 7, 1, 8, 5, 11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, and 19.

 

14. (a) Distinguish between breadth first search and depth first search with example.

Or

(b) State and explain topological sort with suitable example.

 

15. (a) (i) State and explain the shell sort. State and explain the algorithm for shell sort. Sort the elements using shell sort. (7)

ii) Explain Open Addressing in detail. (6)

Or

(b) i) Distinguish between linear search and binary search. State and explain the algorithms for both the search with example. (7)

ii) Explain Rehashing and extendible hashing. (6)

 

PART C — (1 x 15 = 15 marks)

 

16. (a) What are expression Trees. Write the procedure for constructing an expression Tree.

Or

(b) Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x(mod10), show the resulting .

(i) open hash table

(ii) closed hash table using linear probing

(iii) closed hash table using quadratic probing

(iv) closed.

 

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