Data structure- II CSBS

1.        What does the following function do for a given Linked List with first node as head?

 

void fun1(struct node* head)

{

  if(head == NULL)

    return;

 

  fun1(head->next);

  printf("%d  ", head->data);

}

•  a) Prints all nodes of linked lists

• b) Prints all nodes of linked list in reverse order

• c) Prints alternate nodes of Linked List

• d) Prints alternate nodes in reverse order

2.     Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next.

 

void fun(struct node **head_ref)

{

    struct node *temp = NULL;

    struct node current = head_ref;

 

    while (current !=  NULL)

    {

        temp = current->prev;

        current->prev = current->next;

        current->next = temp;

        current = current->prev;

    }

 

    if(temp != NULL )

        *head_ref = temp->prev;

}

Assume that reference of head of following doubly linked list is passed to above function 1 <--> 2 <--> 3 <--> 4 <--> 5 <-->6. What should be the modified linked list after the function call?

• a)  2 <--> 1 <--> 4 <--> 3 <--> 6 <-->5

• b) 5 <--> 4 <--> 3 <--> 2 <--> 1 <-->6

• c) 6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1

• d)  6 <--> 5 <--> 4 <--> 3 <--> 1 <--> 2

3.     Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

• a)     Insertion Sort

• b)     Quick Sort

• c)     Heap Sort

• d)     Merge Sort

4.     What is the output of following function in which start is pointing to the first node of the following linked list 1->2->3->4->5->6 ?

void fun(struct node* start)

{

  if(start == NULL)

    return;

  printf("%d  ", start->data);

  

  if(start->next != NULL )

    fun(start->next->next);

  printf("%d  ", start->data);

}

• a)     1 4 6 6 4 1

• b)     1 3 5 1 3 5

• c)     1 2 3 5

• d)     1 3 5 5 3 1

5.     In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

• a)     log(2*n)

• b)     n/2

• c)     log(2*n) -1

• d)     n

  6. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

• a) union

• b)  membership

• c)  cardinality

• d)  union, intersection

7.     What is the optimal time complexity to count the number of nodes in a linked list?

• a) O(n)

• b) O(1)

• c) O(log n)

• d) O(n log n)

8.     Which of the following algorithms is not feasible to implement in a linked list?

• a)            Insertion Sort

• b)            Quick Sort

• c)            Heap Sort

• d)            Binary Search

9.     What is the time complexity to insert an element to the front of a LinkedList(head pointer given)?

• a) O(n)

• b) O(1)

• c) O(log n)

• d) O(n log n)

10. 10. What is the time complexity of a program to reverse a linked list?

• a) O(n)

• b) O(1)

• c) O(log n)

• d) O(n log n)