Scribd
Upload
13 views2 pages

DSA Questions Answers

The document provides a series of questions and answers related to data structures and algorithms, covering topics such as graph theory, binary trees, sorting algorithms, tree traversals, and hashing techniques. It includes definitions, examples, and explanations of various concepts like pendant vertices, undirected graphs, and the construction of binary search trees. Additionally, it discusses the characteristics of different sorting algorithms and traversal methods like BFS and DFS.

Uploaded by

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

DSA Questions Answers

The document provides a series of questions and answers related to data structures and algorithms, covering topics such as graph theory, binary trees, sorting algorithms, tree traversals, and hashing techniques. It includes definitions, examples, and explanations of various concepts like pendant vertices, undirected graphs, and the construction of binary search trees. Additionally, it discusses the characteristics of different sorting algorithms and traversal methods like BFS and DFS.

Uploaded by

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

DSA Questions & Answers

Very Short Questions (1 mark each)


1) Pendant Vertex
A pendant vertex is a vertex of a graph that has degree one, i.e., it is connected to exactly one other
vertex.
2) Application of Graph
Graphs are widely used in real life, for example in social networks where people are represented as
vertices and friendships as edges.
3) Undirected Graph
An undirected graph is a graph in which edges have no direction. If there is an edge between vertex
u and v, it can be traversed both ways.
4) Children in Binary Tree
In a binary tree, each node can have a maximum of two children. Thus, a node may have 0, 1, or 2
children.
5) Worst Case Time Complexity of Selection Sort
The worst-case time complexity of selection sort is O(n²), because for every element the algorithm
searches through the remaining array.
6) Space Complexity
Space complexity is the total amount of memory space required by an algorithm to run, including
input data, temporary variables, and auxiliary storage.
7) Sorting Algorithm not Stable
Selection sort is an example of a sorting algorithm that is not stable, as it may change the relative
order of equal elements.

Short Questions (5 marks each)


1) Tree Traversals
Traversal of a binary search tree (BST) means visiting all its nodes in a specific order.
- In-order (L–Root–R): Visits left subtree, root, then right.
- Pre-order (Root–L–R): Visits root first, then left, then right.
- Post-order (L–R–Root): Visits left, then right, then root.

Example BST:
10
/\
5 15
In-order: 5, 10, 15
Pre-order: 10, 5, 15
Post-order: 5, 15, 10

2) Sorting Concepts
Sorting is the process of arranging data in ascending or descending order.
A sorting algorithm is said to be stable if it preserves the relative order of equal elements (e.g.,
Merge Sort, Bubble Sort).
An algorithm is in-place if it requires only a constant amount of extra memory (e.g., Quick Sort,
Insertion Sort).

3) Constructing a BST
Given data: 45, 15, 79, 90, 10, 55, 12, 20, 50
Steps:
45 → root
15 → left of 45
79 → right of 45
90 → right of 79
10 → left of 15
55 → left of 79
12 → right of 10
20 → right of 15
50 → left of 55

Final BST:
45
/\
15 79
/\/\
10 20 55 90
\/
12 50

4) BFS, DFS and MST


- BFS (Breadth First Search): Traverses graph level by level using a queue.
- DFS (Depth First Search): Traverses graph depth-wise using a stack or recursion.

Example graph (A connected to B and C):


BFS: A → B → C
DFS: A → B → C

Minimum Spanning Tree (MST): A spanning tree that connects all vertices with the minimum
possible total edge weight. Algorithms: Prim’s and Kruskal’s.

5) Hashing and Hash Functions


Hashing is a technique to map data (keys) into a fixed-size table (hash table) using a hash function,
for quick searching and retrieval.

Types of Hash Functions:


1. Division Method: h(k) = k mod m
2. Multiplication Method: Uses multiplication and fractional part
3. Mid-Square Method: Square the key and take middle digits
4. Folding Method: Break key into parts and add them

You might also like