CS/CT/CO-303 (GS) – Data Structures

B.Tech., III Semester
Examination, November 2022
Grading System (GS)
Max Marks: 70 | Time: 3 Hours

Note:
i) Attempt any five questions.
ii) All questions carry equal marks.

Previous Year Questions (November 2022)

Q.1

a) What are the different operations performed on data structures? Explain. (Unit 1)

b) How linked list is represented in memory? Explain. (Unit 1)
Q.2

a) Explain the operations performed on stack with a program. (Unit 2)

b) Convert the following infix to post fix expression.
$A + B - C * D * E \$ F \$ G$ (Unit 2)
Q.3

a) Explain briefly about the Circular Linked list and it operations. (Unit 1)

b) What are the different terminologies used in the trees? Explain with suitable diagrams. (Unit 3)
Q.4

Insert the following list of elements from the red black tree. Delete the elements 18, 2, 30 from the 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20 and 47. (Unit 3)
Q.5

a) Write a 'C' program, how to insert and delete elements in the Binary search tree? (Unit 3)

b) Discuss Kruskal's algorithm with an following graph. (Unit 4)

Undirected weighted graph with 9 vertices labeled 0 to 8. Vertex 0 connects to 1(4) and 7(8). Vertex 1 connects to 0(4), 2(8), 7(11). Vertex 2 connects to 1(8), 3(7), 5(4), 8(2). Vertex 3 connects to 2(7), 4(9), 5(14). Vertex 4 connects to 3(9), 5(10). Vertex 5 connects to 2(4), 3(14), 4(10), 6(2). Vertex 6 connects to 5(2), 7(1), 8(6). Vertex 7 connects to 0(8), 1(11), 6(1), 8(7). Vertex 8 connects to 2(2), 6(6), 7(7).
Q.6

a) Solve BFS and DFS traversal of following graph. (Unit 4)

Directed graph with 8 vertices labeled 1 through 8 arranged hierarchically. Vertex 1 points to 2, 3, and 4. Vertex 2 points to 5. Vertex 3 points to 5 and 6. Vertex 4 points to 6 and 7. Vertex 5 points to 8. Vertex 6 points to 8. Vertex 7 points to 8.

b) Discuss Prims algorithm with an following graph. (Unit 4)

Undirected weighted graph with 5 vertices labeled 0, 1, 2, 3, 4. Edges and weights are: (0-4) weight 4, (0-1) weight 8, (1-4) weight 6, (1-2) weight 3, (2-4) weight 5, (2-3) weight 9, (3-4) weight 7.
Q.7

a) Explain bubble sort algorithm and simulate it for the following data 35, 33, 42, 10, 14, 19, 27, 44. (Unit 5)

b) Explain Binary search and simulate it for the following data 4, 21, 36, 14, 62, 91, 8, 22, 81, 77, 10. (Unit 5)
Q.8

Write short notes on any two of the following:
i) Queue using linked list (Unit 2)
ii) Hashing (Unit 5)
iii) B+ tree (Unit 3)
iv) Post fix expression evaluation (Unit 2)