DS - Unit-5 Previous Questions

Syllabus

Multi-way trees: Introduction, Definition, features. B-trees – Introduction, Definition and features, Construction of B-trees of order 3, order 4 and order 5, Implementation, Simplified B-Trees: 2-3 tree, 2-3-4 tree.

Graphs: Basic concepts, Terminologies: vertices, edge, cycle, loop, graph vs tree, operations: insert vertex delete vertex, insert edge, delete edge.

Graph traversals: Breadth-First- Search (BFS) Traversal, Depth-First- Search (DFS) Traversal, storage structures (Adjacency Matrix and Adjacency List), graph algorithms.

SEMESTER END EXAMINATIONS – JUNE 2024

Explain the characteristics of 2-3 trees. Formulate the procedure to design a 2-3 tree for the given input: 10, 6, 8, 5, 1, 4, 7.

Write the algorithm for depth first traversal of a graph. Explain the process of traversal with suitable graph data structure.

List the properties of B-tree. Explain the insertion operation in B-tree using essential data of your choice.

Discuss the steps to add and delete a vertex in the graph with suitable examples.

BACKLOG SUBJECT EXAMINATIONS – SEPTEMBER / OCTOBER 2023

Illustrate the properties of m-way tree with an example.

Explain Depth-first traversal of a graph with the help of an algorithm. Give the Depth-first traversal for the following graph starting from vertex 12.

5      12
	   |
	23
   |
25		3

5 connects 12 and 25
3 connects 12 and 25
23 connects 12 and 25

Define and give example for the following: i. B-tree, 2-3 tree, ii. 2-3-4 tree.

Draw the B-tree of order 4 created by inserting the following data arriving in sequence: Construct B-tree of order 4 from the following elements given as follows: 92, 24, 6, 7, 11, 8, 22, 4, 5, 16, 19, 20, 78.

Explain how Graph can be represented using a Adjacency Matrix and Adjacency List with suitable example.

SEMESTER END EXAMINATIONS – MAY / JUNE 2023

Calculate the maximum number of data entries in a: i) 3-way tree of height 3 ii) m-way tree of height h iii) B-Tree of order 5 with a height of h.

Write an algorithm for Breadth-first Traversal.

Draw the B-tree of order 3 created by inserting the following data arriving in sequence: 92, 24, 6, 7, 11, 8, 22, 4, 5, 16, 19, 20, 78

Construct B-tree of order 4 from the following elements given as follows: 1,6,8,2,9,12,15,7,18,3,4,20.

(Extra) Explain how Graph can be represented using an Adjacency Matrix and Adjacency List with suitable example.

Explain the two common structures used to store graphs with examples.

SUPPLEMENTARY SEMESTER EXAMINATIONS - NOVEMBER 2022

Define and give suitable example for the following trees: m-way search tree B-tree 2-3 tree 2-3-4 tree.

Describe the graph storage structures adjacency matrix and adjacency listwith example. Give the comparisons between them.

Construct a B-tree of order 4 created by inserting the following data arriving in sequence: 92 24 6 7 11 8 22 4 5 16 19 20 78

Explain Depth-first traversal of a graph with the help of an algorithm. Give the Depth-first traversal for the following graph starting from vertex A.

Graph of hexagonal and sqaure shape

SEMESTER END EXAMINATIONS – JUNE 2022

Discuss Breadth-first traversal of a graph with suitable example and algorithm

Draw a B-tree of order 5 for the following set of elements arriving in the sequence: 76, 21, 14, 11,97, 85, 74, 63, 45, 42, 57, 20, 16, 19, 52, 30, 21

Define the following with reference to Graph and an example for each: Path, Cycle, Loop, Degree, Weighted Graph.

Describe the two types of graph storage structures with suitable examples.

EXAMINATIONS SEPTEMBER /OCTOBER 2021

Explain different graph storage structure with example.

Create a 2-3 tree of order 3 for the following data arriving in sequence. 11,12,8,20,25,16,12,26,17,27,52,16,48,68,3,26,29,53,95,55.

Discuss Depth-first traversal of a Graph with an example.

Explain simplified B-tree with an example.

SEMESTER END EXAMINATIONS – JULY / AUGUST 2021

Define and explain with example for the following: i. m-way tree ii. B-tree iii. 2-3 tree iv. 2-3-4 tree

Explain how Graph can be represented using a Adjacency Matrix and Adjacency List with suitable example.

Draw the B-tree of order 4 created by inserting the following data arriving in sequence:92,24,6,7,11,8,22,4,5,16,19,20,78.

Discuss Breadth-first traversal of a graph with suitable example.

EXAMINATIONS SEPTEMBER /OCTOBER 2020

Construct a B-tree of order 4 created by inserting the following data arriving in sequence: 92 24 6 7 11 8 22 4 5 16 19 20 78

Describe the graph storage structures adjacency matrix and adjacency list with example. Give the comparisons between them.

Define the following with example: i) m-way search tree ii) B-tree iii) 2-3 tree iv) 2-3-4 tree

Explain Depth-first traversal of a graph with the help of an algorithm. Give the Depth-first traversal for the following graph starting from vertex A

Same circular graph

Draw a B-tree of order 5 for the following set of elements arriving in the sequence: 76, 21, 14, 11,97, 85, 74, 63, 45, 42, 57, 20, 16, 19, 52, 30, 21

Discuss Breadth-first traversal of a graph with suitable example.

Differentiate the following graph storage structures using suitable example. i) Adjacency Matrix ii) Adjacency List.

Draw complete 2-3 and 2-3-4 trees.

Define the following With reference to Graph and give one example each Path, Cycle, Loop, Degree, Out-Degree and In-Degree.