Question Paper Code : 20863
B.E./B.Tech. DEGREE EXAMINATIONS, NOVEMBER/DECEMBER 2023.
Third Semester
Computer Science and Engineering
CS 3301 — DATA STRUCTURES
(Common to : )
(Regulations 2021)
Time : Three hoursMaximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
- 1.
Define abstract data type.
- 2.
Infer the usage of multilists.
- 3.
Recall when an overflow and underflow condition occur during stack operations.
- 4.
List some applications of queues.
- 5.
Indicate the properties of binary tree.
- 6.
Distinguish binary search tree and AVL tree.
- 7.
Define B+ Tree with an example.
- 8.
Express how a graph differs from a spanning tree with an example.
- 9.
Distinguish internal and external sorting.
- 10.
State hashing function.
PART B — (5 × 13 = 65 marks)
- 11.(a)
- (i)Infer how lists and linked list are stored in memory with an example and write a function to check current position is last in a linked list.(7)
- (ii)Distinguish circular linked list and doubly linked list during insertion and deletion operation.(6)
- Or
- (b)
- (i)Express an algorithm to add two polynomials having m and n terms respectively using linked list with an example.(7)
- (ii)Explain how linked list are used for sorting the following set of numbers using radix sort. A = [432, 8, 530, 90, 88, 231, 11, 45, 677, 199](6)
- 12.(a)
- (i)Outline the pseudo-code for performing the following operations in stacks using array implementation. (1) Create (2) Push (3) Pop (4) Stack Top(8)
- (ii)Identify how stacks are used for checking whether an expression is balanced or not for every right and left brace, bracket and parenthesis.(5)
- Or
- (b)
- (i)State the procedure for performing enqueue, dequeue, Isempty, and Isfull operations in a queue data structure with example data.(8)
- (ii)Recognize the differences between circular queue and dequeue.(5)
- 13.(a)
- (i)Classify the three types of binary tree traversal and write the pseudo-code for in-order traversal with an example.(7)
- (ii)Explain how a postfix expression is converted into an expression tree with an example.(6)
- Or
- (b)
- (i)Write the insertion algorithm for binary search tree and analyze its complexity.(7)
- (ii)Summarize how rebalancing occurs in AVL trees during double rotation with an example.(6)
- 14.(a)
- (i)List the principles of B-trees and explain how a node can be inserted into a B-Tree with an example.(7)
- (ii)Outline an algorithm for traversing a graph using breadth -first method with an example.(6)
- Or
- (b)
- (i)State dijkstra's algorithm and identify the minimum cost and shortest path for the following graph. [Figure: directed weighted graph with vertices 1 to 6 and edges 1->2 = 50, 1->3 = 45, 1->4 = 10, 4->1 = 20, 2->3 = 10, 2->4 = 15, 4->5 = 15, 5->2 = 20, 5->3 = 35, 3->5 = 30, 6->5 = 3](7)
- (ii)Describe topological sorting with a pseudo-code.(6)
- 15.(a)
- (i)Defend how binary search logic is better than linear search with an algorithm and an example.(7)
- (ii)Indicate the function for insertion sort with an example.(6)
- Or
- (b)
- (i)Write the merge sort algorithm and show how it arranges the following array of ten elements in sorted order. Analyze the complexity of the algorithm. A[1:10] = (31, 28, 17, 65, 35, 42, 86, 25, 45, 52).(7)
- (ii)Discuss about linear probing collision resolution technique with an example.(6)
PART C — (1 × 15 = 15 marks)
- 16.(a)
- (i)Demonstrate how minimum cost spanning tree can be obtained by Prim's method with an algorithm.(10)
- (ii)Trace the above algorithm for the following graph and analyze the time and space complexity. [Figure: undirected weighted graph with vertices 1 to 6 and edges 1-2 = 10, 1-4 = 30, 1-5 = 45, 2-3 = 50, 2-5 = 40, 2-6 = 25, 3-5 = 35, 3-6 = 15, 4-6 = 20, 5-6 = 55](5)
- Or
- (b)
- (i)Convert the following infix expression to postfix expression with a neat sketch using stacks. ((A - (B + C) * D)$(E + F)). (A/(B - C + D)) * (E - A) * C(5)
- (ii)Devise an algorithm for evaluating the above postfix expression using stacks and analyze the complexity.(10)