Question Paper Code : 30116
B.E./B.Tech. DEGREE EXAMINATIONS, APRIL/MAY 2023.
Third Semester
Computer Science and Engineering
CS 3301 — DATA STRUCTURES
(Common to : )
(Regulations 2021)
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
- 1.
State the uses of Abstract Data Type (ADT).
- 2.
List the advantages of doubly linked list.
- 3.
Give the limitations of linear queue.
- 4.
Write the underflow and overflow conditions in stack?
- 5.
Mention the types of rotations performed on AVL tree.
- 6.
State the properties of binary search tree.
- 7.
Define critical path.
- 8.
State the uses of topological sort.
- 9.
Outline perfect minimal hashing function.
- 10.
Identify the principle behind the external sorting algorithms.
PART B — (5 × 13 = 65 marks)
- 11.(a)
Explain how list operations can be implemented using Arrays.
- Or
- (b)
Explain how polynomial expression can be represented using linked list.
- 12.(a)
Write an algorithm for Push and Pop operations on Stack using Linked list.
- Or
- (b)
Explain the addition and deletion operations performed on a circular queue with necessary algorithms.
- 13.(a)
Identify the types of Priority Queue. Explain about min heap insertion and deletion operations.
- Or
- (b)
Explain Heap tree ADT in detail.
- 14.(a)
Write and explain the prim's algorithm and depth first search algorithm.
- Or
- (b)
Explain about B+ trees with algorithms to insert a node into a B+ tree.
- 15.(a)
Write an algorithm to implement Bubble sort with suitable example.
- Or
- (b)
Discuss the common collision resolution strategies used in closed hashing system.
PART C — (1 × 15 = 15 marks)
- 16.(a)
The keys 12,18,13,2,3,23,5, and 15 are inserted into an initially empty hash table of length 10 using linear probing with hash function h (k) = k mod 10. What is the resultant hash table?
- Or
- (b)
Using Prim's Algorithm, find the cost of minimum spanning tree (MST) of the given graph. [Figure: undirected weighted graph; vertices a, b, c, d, f and two vertices both labelled e (one top right, one far right); edges a-b = 1, a-c = 5, b-c = 4, b-d = 8, b-e(top) = 7, c-d = 6, c-f = 2, d-e(top) = 11, d-f = 9, e(top)-f = 3, e(top)-e(right) = 10, f-e(right) = 12]