[go: up one dir, main page]
Scribd
Upload
7 views15 pages

DSA M3&4 QB Answers

The document contains a question bank for data structures and algorithms, including tasks such as constructing a binary search tree and performing various tree traversals. It also includes implementations and time complexities for linear search, binary search, insertion sort, and selection sort. Additionally, it provides a task to construct an adjacency matrix for a given graph.

Uploaded by

udhay9203
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
7 views15 pages

DSA M3&4 QB Answers

The document contains a question bank for data structures and algorithms, including tasks such as constructing a binary search tree and performing various tree traversals. It also includes implementations and time complexities for linear search, binary search, insertion sort, and selection sort. Additionally, it provides a task to construct an adjacency matrix for a given graph.

Uploaded by

udhay9203
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/ 15

DATA STRUCTURES AND ALGORITHMS

QUESTION BANK

MODULE – 03
Construct the Binary search tree using the following elements
100,-1,-2,999,210,34,45,78,98,99,90,34,45,67,66
Perform In-order ,Pre-order and Post-order traversal on constructed tree
16. Construct the adjacency Matrix for the following graph.

A B C D

E F G
MODULE – 4
11. Linear Search

Time Complexity: O(n)

12. Binary Search


import java.util.Arrays;
public class BinarySearch {
public static int binarySearch(int[] arr, int key) {

int low = 0, high = arr.length - 1;


while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid; // Found
if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}

return -1; // Not found


}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
Arrays.sort(arr); // Ensure sorted
int key = 30;

System.out.println("Key found at index: " + binarySearch(arr, key));


}
}
Time Complexity: O(log n)

13. Insertion Sort


public class InsertionSort {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {40, 20, 50, 10, 30};
insertionSort(arr);
for (int num : arr) System.out.print(num + " ");
}
}

14. Selection Sort


public class SelectionSort {
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {

if (arr[j] < arr[minIdx]) minIdx = j;


}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {40, 20, 50, 10, 30};
selectionSort(arr);
for (int num : arr) System.out.print(num + " ");

} }

You might also like