DSA Model Questions and Solutions(2)

Group- “A”

Brief Answer Questions:

1. Define Asymptotic notations.

Ans: Asymptotic notations are mathematical tools used in computer science and mathematics to describe the behavior of functions as their input values approach infinity. They are primarily used to analyze the efficiency and performance of algorithms, providing a way to express how the runtime or space requirements of an algorithm grow as the size of the input grows.

2. Draw a doubly linked list.

null <-- [prev] Node 1 [next] --> [prev] Node 2 [next] --> [prev] Node 3 [next] --> ... --> [prev] Last Node [next] --> null

In a doubly linked list, each node contains two pointers, one pointing to the previous node (prev) and one pointing to the next node (next). The list starts with a head node and ends with a tail node, both of which have null pointers for prev and next.

3. Define stack.

Ans: A stack is an abstract data type (ADT) that follows the Last In, First Out (LIFO) principle. It is a collection of elements where the addition or removal of items occurs only at one end, traditionally called the “top” of the stack. The end opposite to the top is known as the “base.”

4. What is priority queue.

Ans: A priority queue is an abstract data structure similar to a regular queue or stack, but with an added priority associated with each element. In a priority queue, elements are removed in order of priority, rather than in the order they were added. Elements with higher priority are removed before elements with lower priority.

5. what do you mean by tail recursion.

Ans: Tail recursion is a specific form of recursion in computer science where the recursive call is the last operation performed by the function before it returns its result. In other words, in a tail-recursive function, the recursive call is at the “tail” end of the function, with no further computation to be done after the recursive call returns.

6. Define a balanced tree.

Ans: A balanced tree is a hierarchical data structure in computer science where the heights of the subtrees of any node do not differ by more than one. In other words, for every node in the tree, the heights of its left and right subtrees differ by at most one level.

7. Define Hashing.

Ans: Hashing is a process used in computer science and cryptography to convert input data of arbitrary size into a fixed-size string of characters, typically a sequence of numbers and letters. This fixed-size string is called a hash value or simply a hash.

8. what do you mean by degree of a vertex?

Ans: The degree of a vertex is a measure of how many edges are incident to that vertex. In other words, it’s the number of edges connected to a particular vertex.

9. List any two sorting algorithms.

Ans: Two commonly used sorting algorithms are:

1. Quick Sort
2. Merge Sort

10. Why is Huffman algorithms needed?

Ans: The Huffman algorithm is a method used for lossless data compression, which is the process of reducing the size of data without losing any information. It is particularly useful in scenarios where storage space or bandwidth is limited, such as in file compression for storage or transmission over networks.

Group- “B”

Short Answer Questions ( Attempt any five Questions).

11. Explain abstract Data Type.

Ans: An abstract data type (ADT) is a theoretical concept in computer science that defines a data structure in terms of its behavior and operations, without specifying its implementation details. It provides a logical description of how data can be manipulated, stored, and accessed, without prescribing the specific algorithms or data structures used internally.

Here are the key characteristics and components of an abstract data type:

‣Data Structure:

An ADT defines a collection of data and operations that can be performed on that data. This data could be simple types like integers or characters, or complex types like lists, stacks, queues, trees, graphs, etc.

‣Operations:

ADTs define a set of operations or functions that can be performed on the data they encapsulate. These operations typically include functionalities like insertion, deletion, searching, sorting, accessing elements, etc.

‣Encapsulation:

ADTs encapsulate both data and operations into a single unit. This encapsulation hides the internal details of how the data is stored and manipulated, providing abstraction to the users of the ADT. Users only interact with the ADT through its defined interface, without needing to know the underlying implementation.

‣Information Hiding:

ADTs enforce information hiding by separating the interface from the implementation. Users of an ADT only need to know what operations are available and how to use them, without needing to understand how those operations are implemented internally. This allows for easier maintenance, modification, and extension of the codebase.

‣Consistency:

ADTs guarantee a consistent behavior for the operations they define, regardless of the underlying implementation. As long as the interface remains unchanged, users can rely on the ADT to behave consistently, even if the implementation changes.

‣Flexibility:

ADTs provide flexibility in choosing the appropriate implementation based on the specific requirements of an application. For example, a list ADT could be implemented using arrays, linked lists, or other data structures, depending on factors like performance, memory usage, and ease of implementation.

‣Reusability:

ADTs promote code reusability by allowing the same abstract data structure to be used across multiple applications. Once an ADT is defined, it can be reused in different contexts without modification, as long as the interface remains compatible.

12. Explain Worse – Case time complexity.

Ans: “Worst-case time complexity” refers to the maximum amount of time an algorithm can take to complete its task under the least favorable circumstances, assuming the maximum possible input size. It provides an upper bound on the runtime of an algorithm for any input of a given size.

In analyzing algorithms, worst-case time complexity is particularly important because it guarantees that the algorithm will always perform within a certain time limit, regardless of the specific input. This is crucial for ensuring predictable performance, especially in critical systems or applications where performance guarantees are necessary.

When evaluating worst-case time complexity, we typically focus on the operation that dominates the runtime as the input size grows. This allows us to express the time complexity using Big O notation, which provides an upper bound on the growth rate of the algorithm’s runtime relative to the size of the input.

For example, if an algorithm’s worst-case time complexity is O(n^2), it means that the algorithm’s runtime grows quadratically with the size of the input (n). This implies that as the input size increases, the time taken by the algorithm increases at most quadratically.

It’s worth noting that worst-case time complexity doesn’t necessarily represent the typical or average performance of an algorithm. In some cases, an algorithm may have a high worst-case time complexity but perform significantly better on average or for typical inputs. Conversely, an algorithm with a low worst-case time complexity may perform poorly for specific inputs that trigger the worst-case behavior. Therefore, when analyzing algorithms, it’s essential to consider other factors such as average-case time complexity, best-case time complexity, and practical performance characteristics in addition to worst-case time complexity

13. Write a function to traverse a binary tree in preorder.

Ans: A function to traverse a binary tree in preorder (root, left, right) is as follow:

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreePreorderTraversal {

    public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        // Print the root node
        System.out.print(root.val + " ");

        // Traverse left subtree
        preorderTraversal(root.left);

        // Traverse right subtree
        preorderTraversal(root.right);
    }

    public static void main(String[] args) {
        // Creating a binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Creating an instance of BinaryTreePreorderTraversal
        BinaryTreePreorderTraversal traversal = new BinaryTreePreorderTraversal();

        // Traversing the binary tree in preorder and printing the elements
        System.out.println("Preorder traversal:");
        traversal.preorderTraversal(root);
    }
}

Output:

Preorder traversal:
1 2 4 5 3 

14. Explain different application of queue.

Ans: Queues are a fundamental data structure in computer science that follow the First-In-First-Out (FIFO) principle. They are commonly used in various applications across different domains due to their efficient and organized manner of handling data. Here are several different applications of queues:

1. Operating Systems:
   • Process Scheduling: In operating systems, queues are used to manage processes waiting to be executed by the CPU. Different queues may represent different priority levels, such as ready queue, waiting queue, etc.
   • I/O Buffers: Queues are used to manage input/output requests from various devices. For example, when data is sent to a printer, it’s typically queued up until the printer is ready to process it.
2. Networking:
   • Network Queues: In networking, queues are used to manage packets of data waiting to be transmitted or processed. Routers and switches often use queues to handle incoming data packets, prioritizing and forwarding them based on certain criteria.
3. Web Servers:
   • Request Queues: Web servers often use queues to manage incoming requests from clients. This ensures that requests are processed in the order they are received, preventing overload or bottlenecks.
4. Job Scheduling:
   • Task Queues: Queues are used in job scheduling systems to manage tasks or jobs waiting to be executed. This can include tasks in a distributed computing environment, where jobs are queued up for execution by available resources.
5. Print Spooling:
   • Print Queues: Queues are used in print spooling systems to manage print jobs. When multiple users send print jobs to a printer, they are queued up and processed in the order they were received.
6. Breadth-First Search (BFS) Algorithm:
   • Graph Traversal: Queues are used in algorithms like BFS for traversing graphs level by level. Nodes are visited in the order they were added to the queue, ensuring that nodes at the same level are visited before moving to the next level.

15. .How binary search differs from linear search?

Ans: Here is the difference between binary and linear search:

16. Explain Breadth First Traversal of a graph.

Ans: Breadth First Traversal (BFS) is a fundamental algorithm for traversing or searching tree or graph data structures. It explores all the vertices of a graph or nodes of a tree level by level, visiting all the vertices adjacent to a vertex before moving to the next level. BFS starts at a specified node (often called the ‘root’ in trees) and explores all of its neighbors at the present depth before moving on to the nodes at the next depth level.

Here’s how the BFS algorithm works:

1. Choose a starting node (or vertex) in the graph.
2. Visit all the neighboring nodes of the starting node.
3. For each neighboring node that hasn’t been visited, mark it as visited and enqueue it into a queue data structure.
4. Dequeue a node from the queue and repeat steps 2 and 3 for its neighboring nodes.
5. Continue this process until the queue is empty.

BFS can be implemented using a queue data structure to keep track of the nodes that need to be explored. By utilizing the queue, BFS ensures that nodes are visited in the order of their distance from the starting node, which means closer nodes are visited before farther ones.

BFS is commonly used for tasks such as finding the shortest path in an unweighted graph, checking for connectivity, and solving puzzles like the shortest transformation sequence in word ladders.

Group- “C”

Long Answer Questions ( Attempt any three Questions).

17. Write an algorithm to find the factorial of n number using recursion.

Ans: Here’s a Java algorithm to find the factorial of a number using recursion:

public class Factorial {
    public static void main(String[] args) {
        int n = 5; // Change the value of n as needed
        long result = factorial(n);
        System.out.println("Factorial of " + n + " is: " + result);
    }
    
    // Recursive function to calculate factorial
    public static long factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

Output:

Factorial of 5 is: 120 

18. Define an AVL tree. Construct an AVL tree from the given data: 14, 16, 22, 19, 15, 12, 21.

Ans: An AVL tree, named after its inventors Adelson-Velsky and Landis, is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If, after an insertion or deletion operation, this property is violated, rotations are performed to rebalance the tree.

Here’s how you can construct an AVL tree from the given data: 14, 16, 22, 19, 15, 12, 21.

1. Start with an empty AVL tree.
2. Insert each element one by one into the tree, maintaining the AVL property by performing rotations as necessary.

Let’s construct the AVL tree step by step:

Initial tree (empty):

       _
      | |

Insert 14:

       14
      /  \
     _    _
    | |  | |

Insert 16:

       14
      /  \
     _    16
    | |  | |

Insert 22:

       14
      /  \
     _    16
    | |  | |
         \
         22

Insert 19:

       16
      /  \
     14   22
          / \
         19  _
            | |

Insert 15:

       16
      /  \
     14   22
        / \
       15  _
          | |

Insert 12:

       16
      /  \
     14   22
    /  \
   12  15

Insert 21:

       16
      /  \
     14   21
    /  \    \
   12  15   22

Now, the tree satisfies the AVL property, as the heights of the subtrees at each node differ by at most one. Thus, it is a valid AVL tree.

19. Sort the given data using quick sort algorithms: 17, 8, 91, 10, 111.

Ans: Quick Sort is a popular sorting algorithm that follows the divide-and-conquer strategy. Here’s how you can sort the given data (17, 8, 91, 10, 111) using the Quick Sort algorithm:

1. Choose a pivot element from the array. (For simplicity, we’ll choose the last element of the array as the pivot.)
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than or equal to the pivot.
3. Recursively apply the above steps to the sub-arrays.

Let’s walk through the steps:

Given array: [17, 8, 91, 10, 111]

1. Choose pivot: We’ll choose 111 as the pivot.
2. Partition the array around the pivot:
   • Lesser elements: [17, 8, 10]
   • Pivot: 111
   • Greater or equal elements: [91]
3. Recursively apply Quick Sort to the sub-arrays:
   • Lesser elements: [8, 10, 17]
   • Greater or equal elements: [91]

So, the sorted array is [8, 10, 17, 91, 111].

20. Draw a minimum spanning tree of the below graph using Kruskal`s algorithms:

Group- “D”

Comprehensive Answer/ Case / Situation Analysis Questions:

21. Write an algorithms to perform insertion and deletion operation in a binary search tree.

Ans: An algorithms to perform insertion and deletion operation in a binary search tree is as follow:

// Node class to represent a node in BST
class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

// BinarySearchTree class
class BinarySearchTree {
    Node root;

    BinarySearchTree() {
        root = null;
    }

    // Insertion operation
    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        return root;
    }

    // Deletion operation
    void deleteKey(int key) {
        root = deleteRec(root, key);
    }

    Node deleteRec(Node root, int key) {
        if (root == null)
            return root;

        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
        else {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            root.key = minValue(root.right);
            root.right = deleteRec(root.right, root.key);
        }

        return root;
    }

    int minValue(Node root) {
        int minv = root.key;
        while (root.left != null) {
            minv = root.left.key;
            root = root.left;
        }
        return minv;
    }

    // Inorder traversal to print the BST
    void inorder() {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }
}

// Main class to test the implementation
public class Main {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        // Insertion
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // Output after insertion
        System.out.println("Inorder traversal of the BST:");
        tree.inorder(); // Should output: 20 30 40 50 60 70 80
        System.out.println();

        // Deletion
        System.out.println("Delete key 20:");
        tree.deleteKey(20);
        System.out.println("Inorder traversal after deletion:");
        tree.inorder(); // Should output: 30 40 50 60 70 80
    }
}

Output:

Inorder traversal of the BST:
20 30 40 50 60 70 80 
Delete key 20:
Inorder traversal after deletion:
30 40 50 60 70 80 

22. Illustrate push and pop operation in stack using linked lists.

Ans: Illustrating the push and pop operation in stack using linked lists is as follow:

// Node class represents each node in the linked list
class Node {
    int data; // Data to be stored
    Node next; // Reference to the next node

    // Constructor to initialize a node with data
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Stack class to implement stack operations using linked list
class Stack {
    private Node top; // Reference to the top node

    // Constructor to initialize an empty stack
    public Stack() {
        this.top = null;
    }

    // Method to check if the stack is empty
    public boolean isEmpty() {
        return top == null;
    }

    // Method to push an element onto the stack
    public void push(int data) {
        Node newNode = new Node(data); // Create a new node with the given data
        newNode.next = top; // Set the next of the new node to the current top
        top = newNode; // Update top to point to the new node
        System.out.println("Pushed: " + data);
    }

    // Method to pop an element from the stack
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
            return -1; // Return -1 indicating stack underflow
        }
        int popped = top.data; // Store the data of the top node
        top = top.next; // Move top to the next node
        System.out.println("Popped: " + popped);
        return popped; // Return the popped element
    }

    // Method to display the elements in the stack
    public void display() {
        Node current = top; // Start from the top
        System.out.print("Stack: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next; // Move to the next node
        }
        System.out.println();
    }
}

// Main class to demonstrate stack operations
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();

        // Pushing elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.display();

        // Popping elements from the stack
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop(); // Trying to pop from an empty stack
        stack.display();
    }
}

Output:

Pushed: 10
Pushed: 20
Pushed: 30
Stack: 30 20 10 
Popped: 30
Popped: 20
Popped: 10
Stack is empty!
Stack: