DSA Unit 3, 4, 5 Flashcards

1
Q

Define spanning tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Justification of Array|Linked

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Advantages and disadvantages of TBT

A

Efficient traversal
Space utilization
No stack Overhead
Faster Access

complex implementation
increased memory usage for every node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Applications of MST

A

Image processing
Network design
Game development
Electric circuit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Define Stack

A

Linear abstract data structure
LIFO principle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Types of stack

A

Implicit - not implemented by user
Explicit - user implemented

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Stack Operations

A

Push
Pop
Peek
isFull
isEmpty
display

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define Queue

A

Linear abstract data structure
FIFO principle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Types of Queue

A

Simple
Circular
Priority Queue (Ascending and Descending)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Define Graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Operations on Graph

A

Insert, Delete, Search, and Traverse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Graph traversal methods

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Kruskal and Prim time complexity

A

O( |E|log|E| )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Greedy Algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define Tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Height and Depth

A

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

17
Q

Types of Binary Tree

A

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

18
Q

Sequential Tree

A

Minimum information required to reconstruct a tree (no pointers)

19
Q

Tree traversal methods

A

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

20
Q

Huffmann Tree

A

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

21
Q

Threaded binary tree

A

Empty child nodes replaced with threads

22
Q

What is ADT

A

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.

23
Q

Applications of Stack

A

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

24
Q

What is AVL and its time complexity?

A

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

25
Time complexity for heap sort
O(n log n) Heap creation O(n) Heapify O(nlogn)
26
Time complexity for deleting a record from index sequential file
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.
27
Time complexities of priority queue operations
LL Insertion/Deletion = O(1), O(n) Peek = O(1) Array Insertion/Deletion = O(n) Peek = O(1)
28
Applications of infix to postfix
Make it easier for the computer to understand Computer cannot easily differenciate between parethesis and operators
29
Applications of Queue
Print Line Documents Analysis of Traffic Telephone Operators Operating system task scheduling
30
Time complexity for insertion and deletion in BST
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)
31
Hash Function methods
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)
32
Collision resolution
Seperate chaining (Open Hashing) Open Addressing (Closed hashing) - Linear probing - Quadratic probing - Double Hashing
33
Applications of Topological Sort
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.
34
Applications of Heap
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.
35
Characteristics of a good Hash Function
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.