Free List Test - Sanfoundry

1. Which of the following represents the space complexity for an unrolled linked list?

O(n²)

O(n)

O(n³)

O(1)

2. Insertion and deletion are much faster in an unrolled linked list than in a singly linked list.

True

False

3. What happens if a node cannot fit an element in an unrolled linked list?

The elements are moved to the next node

The node is discarded

The element is discarded

Error message is shown

4. Which among the following is a typical declaration of an unrolled linked list in C?

#define SIZE N                                                             
struct node 
{                                                                           
    int node_count;                                                     
    int arr[SIZE];                                              
    struct node *next;                              
};

#define SIZE N                                                          
struct node 
{                                                                           
    int node_count;                                                                                           
    struct node *next;                              
};

#define SIZE N                                                            
struct node 
{                                                                                                                              
    int arr[SIZE];                                              
    struct node *prev;      
    struct node *top;                        
};

#define SIZE N                                                         
struct node 
{                                                                           
    int node_count;                                                     
    int arr[SIZE];                                                                           
};

5. Unrolled linked-list requires more storage space for pointers compared to a singly linked list.

True

False

6. Which among the following is the time complexity for inserting an element in an unrolled linked list?

O(1)

O(log n)

O(n²)

O(n)

7. An unrolled linked list consists of which of the following data structures?

Linked-list and array

Array and queue

Linked-list and stack

Stack and array

8. Which of the following is a drawback of an unrolled linked list?

Slow insertion and deletion

Small memory overhead

High overhead per node

Cache management

9. The algorithm given is for deleting an element in an unrolled linked list. What should be the correct statement for the blank given below?

Find an element in node a
    a.data.delete(element)
    a.elementNum--
    while a.elementNum < a.data.size / 2
        put element from a.next.data in a.data
        a.next.elementNum--
        a.elementNum++
    if a.next.elementNum < a.next.data.size / 2
         _______________________
         _______________________

delete node a
    merge nodes a.prev and a.next

a.elementNum--
    a.elementNum++

a.next.elementNum--
    a.next.elementNum++

merge nodes a and a.next
    delete node a.next