DSA Unit 3, 4, 5

Question 1

Define spanning tree

Answer 1

subset of graph G where vertices connected using minimum possible number of edges

Question 2

Justification of Array|Linked

Answer 2

Space efficiency (array could have many unused indices)
Dynamic size (adding or removing nodes frequently)
Traversal flexibility (without worrying about structure of array )

Question 3

Advantages and disadvantages of TBT

Answer 3

Efficient traversal
Space utilization
No stack Overhead
Faster Access

complex implementation
increased memory usage for every node

Question 4

Applications of MST

Answer 4

Image processing
Network design
Game development
Electric circuit

Question 5

Define Stack

Answer 5

Linear abstract data structure
LIFO principle

Question 6

Types of stack

Answer 6

Implicit - not implemented by user
Explicit - user implemented

Question 7

Stack Operations

Answer 7

Push
Pop
Peek
isFull
isEmpty
display

Question 8

Define Queue

Answer 8

Linear abstract data structure
FIFO principle

Question 9

Types of Queue

Answer 9

Simple
Circular
Priority Queue (Ascending and Descending)

Question 10

Define Graph

Answer 10

Non Linear Data structure using vertices (fundamental units) and edges (connections)

Question 11

Operations on Graph

Answer 11

Insert, Delete, Search, and Traverse

Question 12

Graph traversal methods

Answer 12

BFS (2 queues: Neighbour and Visited)
DFS (adjacent visits)

Question 13

Kruskal and Prim time complexity

Answer 13

O( |E|log|E| )

Question 14

Greedy Algorithm

Answer 14

paradigm that builds a solution by choosing pieces with greed (immediate benefit)

Question 15

Define Tree

Answer 15

Tree is a hierarchical data sturcture where data arranged in multiple levels

Question 16

Height and Depth

Answer 16

Depth - Root to node distance
Height - (Longest) Node to Lead distance

Question 17

Types of Binary Tree

Answer 17

Full (0 or 2 children)
Degenerate (1 child)
Skewed (only lefts or rights)
Complete (all levels filled except last)
Perfect (leaves at same level)

Question 18

Sequential Tree

Answer 18

Minimum information required to reconstruct a tree (no pointers)

Question 19

Tree traversal methods

Answer 19

Pre order - root - left - right
In order - left - root - right
Post order - left - right - root
BFS - level wise

Question 20

Huffmann Tree

Answer 20

according to frequency of nodes (highest - up, lowest - down)

Question 21

Threaded binary tree

Answer 21

Empty child nodes replaced with threads

Question 22

What is ADT

Answer 22

An ADT defines the interface or the contract of a data structure, specifying what operations can be performed on it, without specifying how those operations are implemented.

Question 23

Applications of Stack

Answer 23

Infix to Postfix/Prefix conversions
Reverse a string
Decimal to Binary conversions
Simulate recursion

Question 24

What is AVL and its time complexity?

Answer 24

AVL (Adelson Velsky and Landis)
self balancing binary tree which balances every time insertion or deletion occurs.
Time complexity : O(log n)

Question 25

Time complexity for heap sort

Answer 25

O(n log n)
Heap creation O(n)
Heapify O(nlogn)

Question 26

Time complexity for deleting a record from index sequential file

Answer 26

Best-case time complexity: O(log n) when the index is highly efficient and the record is located near the beginning of the file.
Average-case time complexity: O(n) due to the sequential search and shifting of records.
Worst-case time complexity: O(n) when the record is located at the end of the file and all records need to be shifted.