Questions and answers for exam Preparation

MCQs

Total Questions : 10

Question 1. What is buddy memory management of free lists ?

modified version of first fit
buddy allocation keeps several free lists, each one holds blocks which are of one particular size
modified version of best fit
a tree representation of free lists

Discuss Question

Answer: Option B. -> buddy allocation keeps several free lists, each one holds blocks which are of one particular size

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.

Question 2. What are the disadvantages in implementing buddy system algorithm for free lists ?

internal fragmentation
it takes so much space
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
both a and c are correct

Discuss Question

Answer: Option D. -> both a and c are correct

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

Question 3. To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?

balanced binary search trees
binary search trees
binary trees
linked lists

Discuss Question

Answer: Option A. -> balanced binary search trees

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.

Question 4. What is the time complexity improvement of skip lists from linked lists in insertion and deletion?

O(n) to O(logn) where n is number of elements
O(n) to O(1) where n is number of elements
no change
O(n) to O(n2) where n is number of elements

Discuss Question

Answer: Option A. -> O(n) to O(logn) where n is number of elements

Question 5. How does implicit free lists(garbage collection) works in adding memory to free list ?

whichever comes last will be added to free list
whichever comes first will be added to free list
certain blocks cannot be used if there are no pointers to them and hence they can be freed.
makes a probabilistic guess

Discuss Question

Answer: Option C. -> certain blocks cannot be used if there are no pointers to them and hence they can be freed.

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

Question 6. Disadvantages of xor lists

Almost of debugging tools cannot follow the XOR chain, making debugging difficult
You need to remember the address of the previously accessed node in order to calculate the next node's address
In some contexts XOR of pointers is not defined
All of the mentioned

Discuss Question

Answer: Option D. -> All of the mentioned

All the listed options are right.

Question 7. The nodes in a skip list may have many forward references. their number is determined

probabilistically
randomly
sequentially
orthogonally

Discuss Question

Answer: Option A. -> probabilistically

The number of forward references are determined probabilistically, that is why skip list is a probabilistic algorithm.

Question 8. Which of the following statements are true ?
i) practical application of XOR linked lists are in environments with limited space requirements, such as embedded devices.
ii)xor lists are not suitable because most garbage collectors will fail to work properly with classes or structures that don't contain literal pointers
iii)in order to calculate the address of the next node you need to remember the address of the previous node
iv)xor lists are much efficient than single, doubly linked lists and arrays