1.. Theworsto aseoccurinlinearsearch algorithmwhen A. Item is somewhere in the m

ID: 3704110 • Letter: 1

Question

1.. Theworsto aseoccurinlinearsearch algorithmwhen A. Item is somewhere in the middle of the B. Item is not in the array at all C. Item is the last element in the array D, Item is the last element in the array or is not there at all -2. Afin tesetofstatementsthat?? guarantees an optimal solution in finite interval of time is A. Data structure B. Solution C. Plan D. Algorithm 3. Which of the following is not a limitation of binary4. The complexity of Binary search search algorithm? A. must use a sorted array B. requirement of sorted array is expensive when a lot of algorithm is A. O(n) B. O(log n) C. O(n2) D. O(n log n) IS insertion and deletions are needed C. there must be a mechanism to access middle element directly f D. binary search algorithm is not efficient when the data elements are more than 1000. 6. Traversing a doubly linked list can 5. Linked lists are best suited A. for relatively permanent collections of data B. for the size of the structure and the data in the structure be done are constantly changing for both of above situation for none of above situation A. At any point in the list. B. From the top of the list C. From either end of the list D. None of the above C. D. s. A variable P is called pointer if A. P contains the address of an element in form of access is used to add remove nodes from a stack. ?.LIFO B. FIFC C. Both A and B D. None of these DATA P points to the address of first element in DATA B. C. P can store only memory addresses D. P contain the DATA and the address of DATA 10. The complexity of merge sort 9. The complexity of Bubble sort algorithm is algorithm is A. O(n) B. O(log n) C. O(n) D. O(n log n) O(n) B. O(log n) C. O(n2) D. O(n log n)

Explanation / Answer

Section A

1. D => Worst case occur when item is at end of list, as we have to iterate(check) over all the elements

2. D => Algorithm are finite set of instruction to solve proble in finte time like linear search have time O(n)

3. D => Binary search is very effective as time complexity is 0(log n)

4. B => 0(log n)

5. B => if size of data constantly changes then we an insert any numbers of node(element) in linklist

6. C => Eithier end of the list as every node is pointing to next an previous

7. A => LIFO, like a stack of plate the last plate on stack will be removed firt (Last in First Out)

8. C => Pointer point to a memory(variable)

9. C => O(n*n)

10. D => 0(n log n)

Section B

1. =>

Basis for Comparison

Array

Linked list

Basic

It is a consistent set of a fixed number of data items.

It is an ordered set consisting of a variable number of data items.

Size

Specified during declaration.

No need to specify; grow and shrink during execution.

Storage Allocation

Element location is allocated during compile time.

Element position is assigned during run time.

Order of the elements

Stored consecutively

Stored randomly

Accessing the element

Direct or randomly accessed, i.e., Specify the array index or subscript.

Sequentially accessed, i.e., Traverse starting from the first node in the list by the pointer.

Insertion and deletion of element

Slow relatively as shifting is required.

Easier, fast and efficient.

Searching

Binary search and linear search

linear search

Memory required

less

Memory Utilization

Ineffective

Efficient

2 =>

   a=> as this program only check first element it will always take constant time irrespective of size of string
       so complexity is O(1)

   b=> this program check if a character is in string, so in worst case searching character can be a end of string
       in this case we have to travese till end so complexity is O(n)

3a =>
    Insertion at the front of list
   Insertion at the end of the list
    Insertion in the middle of the list (anywhere in the list)


3b =>

Insertion at the front of list

public void push(int new_data)
{
    /* 1 & 2: Allocate the Node & Put in the data*/
    Node new_node = new Node(new_data);

    /* 3. Make next of new Node as head */
    new_node.next = head;

    /* 4. Move the head to point to new Node */
    head = new_node;
}

Insertion at the end of the list

public void append(int new_data)
{
    /* 1. Allocate the Node &
       2. Put in the data
       3. Set next as null */
    Node new_node = new Node(new_data);

    /* 4. If the Linked List is empty, then make the
           new node as head */
    if (head == null)
    {
        head = new Node(new_data);
        return;
    }

    /* 4. This new node is going to be the last node, so
         make next of it as null */
    new_node.next = null;

    /* 5. Else traverse till the last node */
    Node last = head;
    while (last.next != null)
        last = last.next;

    /* 6. Change the next of last node */
    last.next = new_node;
    return;
}

-- This is not required as you need only algorithm but Node class look like this

// Linked List Class
class LinkedList
{
    Node head; // head of list

    /* Node Class */
    class Node
    {
        int data;
        Node next;

        // Constructor to create a new node
        Node(int d) {data = d; next = null; }
    }

   ---
   ---
   function in between
   ---
}