Learn Data Structure Types of Lists Multiple Choice Questions and Answers with explanations. Practice Data Structure Types of Lists MCQs Online Quiz Mock Test For Objective Interview.
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
Answer: Option B
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.
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
Answer: Option C
When no pointers pointing a block that means it is useless to be in memory.
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
Answer: Option D
Internal fragmentation is an issue to be dealt and it takes so much space.
What is the time complexity improvement of skip lists from linked lists in insertion and deletion?
- A. O(n) to O(logn) where n is number of elements
- B. O(n) to O(1) where n is number of elements
- C. no change
- D. O(n) to O(n2) where n is number of elements
Answer: Option A
To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?
- A. balanced binary search trees
- B. binary search trees
- C. binary trees
- D. linked lists
Answer: Option A
Skip lists are similar to any randomly built binary search tree. a BST is balanced because to avoid skew tree formations in case of sequential input and hence achieve O(logn) in all 3 cases. now skip lists can gurantee that O(logn) complexity for any input.