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.

Question 27

Time complexities of priority queue operations

Answer 27

LL
Insertion/Deletion =
O(1), O(n)
Peek =
O(1)
Array
Insertion/Deletion =
O(n)
Peek =
O(1)

Question 28

Applications of infix to postfix

Answer 28

Make it easier for the computer to understand
Computer cannot easily differenciate between parethesis and operators

Question 29

Applications of Queue

Answer 29

Print Line Documents
Analysis of Traffic
Telephone Operators
Operating system task scheduling

Question 30

Time complexity for insertion and deletion in BST

Answer 30

Insertion:
Tree is empty O(1)
Tree is balanced O(logn)
Tree is skewed O(n)
O(logn)-O(n)
Deletion:
Node has no children O(1)
Tree is balanced O(logn)
Tree is skewed O(n)

Question 31

Hash Function methods

Answer 31

Dividing (divide by prime)
Mid Square (Square the key, mid digits)
Folding (divide into equal parts, sum, then modulo)
Perfect hashing (no two hash values are same)

Question 32

Collision resolution

Answer 32

Seperate chaining (Open Hashing)
Open Addressing (Closed hashing)
- Linear probing
- Quadratic probing
- Double Hashing

Question 33

Applications of Topological Sort

Answer 33

Job Scheduling: Topological sorting schedules jobs based on dependencies.
Shortest Paths: Topological sorting finds shortest paths. (Network Analysis)
Process Scheduling: Topological sorting schedules processes. (OS)
Risk Analysis: Topological sorting analyzes risks.

Question 34

Applications of Heap

Answer 34

Job Scheduling: Heaps are used to schedule jobs based on priority. (PQ)
Heap Sort: Heapsort is a comparison-based sorting algorithm using heaps
Dijkstra’s Algorithm: Heaps are used to find the shortest path in a graph.
Memory Allocation: Heaps manage memory allocation, ensuring efficient use.

Question 35

Characteristics of a good Hash Function

Answer 35

Deterministic - Given a specific input, the hash function always returns the same output.
Low Collision Rate - The hash function should minimize collisions
Non-Injective - Multiple input values can produce the same output hash value.
Fixed Output Size - The output of the hash function is always of a fixed size.