DSA 2019 Makeup

4th semester

Group A

  1. Big Theta notation (Θ) :
    The equation simply means there exist positive constants C 1 and C 2 such that f(n) is sandwich between C 2 g(n) and C 1 g(n
  2. FIFO stands for First In – First Out, which simply means the request which has come first will be dealt first. As this is the case with a QUEUE data structure, we simply call an ordinary queue as a FIFO queue.
  3. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
  4. The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. So if it is tail recursion, then storing addresses into stack is not needed. We can use factorial using recursion, but the function is not tail recursive.
  5. Splaying an element, is the process of bringing it to the root position by performing suitable rotation operations. In a splay tree, splaying an element rearranges all the elements in the tree so that splayed element is placed at the root of the tree.
  6. A heap is a tree-based data structure in which all the nodes of the tree are in a specific order. specific order with respect to the value of and the same order will be followed across the tree.
  7. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
  8. A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices. … We use the names 0 through V-1 for the vertices in a V-vertex graph.
  9. Data sorting is any process that involves arranging the data into some meaningful order to make it easier to understand, analyze or visualize. When working with research data, sorting is a common method used for visualizing data in a form that makes it easier to comprehend the story the data is telling.
  10. Different collision resolution techniques in Hashing
  • Open Hashing (Separate chaining)
  • Closed Hashing (Open Addressing) Liner Probing. Quadratic probing. Double hashing.


Group B

Q.No 11.

package folder2019;
import java.util.Scanner;
class Stack {
    private java.util.LinkedList list = new java.util.LinkedList();
    public Stack() {
    public void clear() {
    public boolean isEmpty() {
        return list.isEmpty();
    public void push(Object el) {
    public Object pop() {
        if (isEmpty()) {
            System.out.println("stack is empty");
        return list.removeLast();
    public String toString() {
        return list.toString();
public class makeup2019no11 {
    public static void main(String[] args) {
        Stack ob = new Stack();
        int data;
        Scanner sc = new Scanner(System.in);
        System.out.println("the stack is empty:" + ob.isEmpty());
        System.out.println("enter a number to push in any stack");
        for (int i = 0; i < 3; i++) {
            data = sc.nextInt();



Q.no 12

package folder2019;
import java.util.Scanner;
class Node
public int info;
 public Node next;
 public Node()
 next = null;
 public Node(int el)
 info = el;
 next = null;
 public Node(int el, Node ptr)
 info =el;
 next = ptr;
class List{
    Node head,tail;
public void deleteAtAny(int n)
Node previous = head;
int count=1, position=n;
while(count < position - 1)
previous = previous.next;
Node current = previous.next;
previous.next = current.next;
current.next = null;
public class makeup2019no12{
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        System.out.println("Singly linked list created");
        List mylist = new List();
        System.out.println("Enter the position");
        int pos=sc.nextInt();

Q.n0 13

Q.no 14

Q.no 15

import java.util.Scanner;
public class SelectionSorting {
    public static void selectionSort(int[] data){
       int i,j,least,temp;
           for(j=i+1,least=i; j<data.length;j++){
    static void result(int[] data){
         System.out.println("The array after selection sorting is: ");
        for(int i=0;i<data.length;i++)
            System.out.print(data[i]+ " ");
    public static void main(String args[]){
        SelectionSorting obj1 =new SelectionSorting ();
        Scanner sc=new Scanner(System.in);
        System.out.println("enter the size of array for sorting");
        int size=sc.nextInt();
        System.out.println("Enter the element for array");
         int data[]=new int[size];
        for(int i=0;i<size;i++){

Leave a Reply

Your email address will not be published.