[go: up one dir, main page]
Scribd
Upload
3 views4 pages

Iat3 Answer Key

The document provides answers to various questions related to data structures and algorithms, including multiway search trees, tree traversal, B-trees, and AVL trees. It explains operations on heaps, depth-first search, and the properties of binary search trees, along with algorithms for searching and constructing minimum spanning trees. Additionally, it includes examples to illustrate concepts and operations discussed.

Uploaded by

rajalakshmi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views4 pages

Iat3 Answer Key

The document provides answers to various questions related to data structures and algorithms, including multiway search trees, tree traversal, B-trees, and AVL trees. It explains operations on heaps, depth-first search, and the properties of binary search trees, along with algorithms for searching and constructing minimum spanning trees. Additionally, it includes examples to illustrate concepts and operations discussed.

Uploaded by

rajalakshmi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

IAT-3 ANSWER KEY

1. What are the applications of multiway search tree?


Multiway search trees are used in databases and file systems for indexing, enabling efficient
searching, insertion, and deletion of large blocks of data.

2. Define tree traversal and what is the time complexity of level order traversal?
Tree traversal is the process of visiting all nodes in a tree systematically. The time complexity of
level order traversal is O(n), where n is the number of nodes.

3. Difference between B-tree and B+ tree?

 B-tree stores keys and data in all nodes.


 B+ tree stores data only in leaf nodes, with internal nodes containing keys only.
 B+ tree leaves are linked for fast sequential access; B-tree leaves are not linked.

4. Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights?
Yes, both Prim’s and Kruskal’s algorithms work correctly with negative edge weights, as they
only require non-cyclic graphs and do not depend on edge weights being positive.

5. Find the number of edges present in a complete graph having n vertices.


Number of edges = n(n - 1) / 2

6. What is topological ordering?


Topological ordering is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such
that for every directed edge u → v, vertex u appears before v.

7. Discuss about the AVL trees along with its properties and advantages with
suitable example

AVL Tree:

 It is a self-balancing binary search tree where the difference between heights of left and
right subtrees (balance factor) is at most 1 for every node.

o Balance factor (height of left subtree - height of right subtree) ∈ { -1, 0, +1 }


 Properties:
o Balancing is maintained by rotations (single or double) after insertions or
deletions.
 Advantages:
o Guarantees O(log n) time for search, insert, and delete.
o Avoids skewed trees ensuring faster operations.
 Example:
Insert nodes 10, 20, 30 in an empty AVL tree:
Insertion of 30 causes imbalance at node 10 (balance factor becomes -2), fixed by left
rotation at 10.
Resulting tree is balanced.

8a. Explain the insert and delete operations of heap with example

Heap Insert:

 Insert the new element at the end (bottom) of the heap.


 Compare it with its parent; if it violates the heap property, swap and bubble up until the
heap property is restored.

Example: Insert 15 into Max-Heap [20, 10, 5]:

 Insert 15 at the end → [20, 10, 5, 15]


 15 > 10, swap → [20, 15, 5, 10]

Heap Delete (usually root):

 Remove the root element.


 Replace root with the last element.
 Heapify down: compare with children and swap with the larger (max-heap) or smaller
(min-heap) child until heap property is restored.

Example: Delete root (20) from Max-Heap [20, 15, 5, 10]:

 Replace root with 10 → [10, 15, 5]


 10 < 15, swap → [15, 10, 5]

8b. Illustrate depth first search technique

Depth First Search (DFS):

 DFS explores as far as possible along each branch before backtracking.


 Uses a stack (explicit or recursion).
 Steps:
1. Start at a node, mark it visited.
2. Visit an adjacent unvisited node and repeat step 1.
3. Backtrack when no unvisited adjacent nodes.

Example: For graph with edges (A-B, B-C), DFS from A: A → B → C

9. State the BST property and outline an algorithm to search BST with example

BST Property:

 For each node, all keys in the left subtree are less, and all keys in the right subtree are
greater than the node’s key.

BST Search Algorithm:

1. Start at the root.


2. If root is null or key equals root’s key, return node.
3. If key < root’s key, search left subtree.
4. Else, search right subtree.

Example: Search 15 in BST:

 Root = 20 → 15 < 20, go left


 Left child = 10 → 15 > 10, go right
 Right child = 15 → found

10. The adjacency matrix of a four vertex graph is shown below. List the
sequence of nodes visited starting from vertex 4, in depth first search on the
graph.

ABCD
A 0 1 0 0
B 1 0 1 0
C 0 1 0 1
D 0 0 1 0

Starting from vertex D (4):

 Visit D → neighbors: C
 Visit C → neighbors: B, D (D visited)
 Visit B → neighbors: A, C (C visited)
 Visit A → neighbor: B (visited)

DFS order: D → C → B → A

11. Consider the given undirected graph and apply Prim’s Algorithm to find the
minimum spanning tree. Illustrate the steps.

Prim’s Algorithm Steps:

1. Start from any vertex (say vertex 1).


2. Select the edge with the minimum weight connecting the tree to a vertex not yet in the
tree.
3. Add the selected edge and vertex to the MST.
4. Repeat step 2 until all vertices are included.

Illustration: (You should provide the graph with weights and show each step adding edges with
minimum weights.)

You might also like