Data Structure Questions and Answers – Free List


This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Free List”.

1. How does implicit free lists(garbage collection) works in adding memory to free list ?
A) whichever comes last will be added to free list
B) whichever comes first will be added to free list
C) certain blocks cannot be used if there are no pointers to them and hence they can be freed
D) makes a probabilistic guess

Explanation: When no pointers pointing a block that means it is useless to be in memory.

2. What are the disadvantages in implementing buddy system algorithm for free lists?
A) internal fragmentation
B) it takes so much space
C)we no more have the hole lists in order of memory address, so it is difficult to detect if 2 holes remain adjacent in memory and shall be merged into one hole
D) both a and c are correct

Explanation: Internal fragmentation is an issue to be dealt and it takes so much space.

3. Assume there is a free list which contains nodes and is filled with a value if it is already assigned and the value will be the size of requested block else will be 0.

 z = startpoint;
 while ((z < end) &&    \\ didn't reach end
   (*z <= len))          \\ too small to satisfy request
   assign this block

The above code represents what?
A) code for first fit
B) code for best fit
C) code for worst fit
D) none of the mentioned

Explanation: As z is start point and now from beginning we are moving and checking if we reached end and then checking size naively assigning the first block which is bigger than required size hence it is first fit.

4. How are free blocks linked together mostly and in what addressing order?
A) circular linked list and increasing addressing order
B) linked list and decreasing addressing order
C) linked list and in no addressing order
D) none of the mentioned

Explanation: A common way is circular linked list and address are arranged in increasing order because merging would be easier which is actually a problem in buddy memory allocation.

5. Accessing free list very frequently for wide range of addresses can lead to
A) paging
B) segmentation fault
C) memory errors
D) cache problems

Explanation: Paging in/out of disk will be caused.

6. Free lists are used in
A) static memory allocation
B) dynamic memory allocation
C) contagious allocations
D) are used for speeding up linked list operations

Explanation: Their property is meant for dynamic allocations.

7. What are implicit and explicit implementations of freelists?
A) garbage collection and new or malloc operators respectively
B) new or malloc and garbage collection respectively
C) implicit implementation is not favored
D) explicit implementation is not favored

Explanation: Gc and new most widely known.

8. What datastructures can be used in implementing a free list?
A) only linked list
B) linked list or sort trees
C) arrays
D) trees

Explanation: Sort trees can also be used in impelementing free lists which remaincomplex.

9. What are different ways of implementing free lists and which is simple among them?
A) best fit, first fit, worst fit, simple-first fit
B) best fit, first fit, worst fit, simple-best fit
C) best fit, first fit, worst fit, simple-worst fit
D) best fit simple-best fit

Explanation: The‭ ‬simplest form of memory management system can be called as first-fit.‭ ‬a device or system maintains a single‭ ‬list of free memory locations.‭ ‬When request to memory is sent,‭ ‬the list is searched and the first block that is large enough is returned.

10. What is buddy memory management of free lists ?
A) modified version of first fit
B) buddy allocation keeps several‭ ‬free lists,‭ ‬each one holds blocks which are of one particular size
C) modified version of best fit
D) a tree representation of free lists

Explanation: When an allocation request is received,‭ ‬the list that holds blocks that are just large enough to satisfy the request are considered, and an open location is returned.‭ ‬If no‭ ‬free‭ ‬blocks that are smaller than two times the size that are requested are available,‭ ‬a larger block is split in two to satisfy the requirements.

A free list is a data structure that is used in a memory allocation system that is dynamic. It works by linking together unallocated memory regions in a linked list, with the first word of each unallocated region serving as a pointer to the next. It works best when allocating from a memory pool of items of the same size. Allocation and deallocation operations are made even easier with free lists. To make a region free, simply add it to the free list. To assign a region, simply take a single region from the end of the free list and use it. If the regions are variable in size, it might be necessary to look for a large enough area, which can be costly.

Leave a Reply

Your email address will not be published. Required fields are marked *