1. What is a skip list?

a) a linkedlist with size value in nodes
b) a linkedlist that allows faster search within an ordered sequence
c) a linkedlist that allows slower search within an ordered sequence
d) a tree that is in the form of a linked list

MCQ on Virus - Examsegg Biology

It is a data structure, which can make a search in a sorted linked list faster in the same way as a binary search tree and sorted array (using binary search) are faster.

2. Consider the 2-level skip list

How to access 38?

a) travel 20-30-35-38
b) travel 20-30-40-38
c) travel 20-38
d) travel 20-40-38

Let us call the nodes 20, 30, and 40 top lines and the nodes between them normal lines. the advantage of skip lists is we can skip all the elements between the top-line elements as required.

3. Skip lists are similar to which of the following data structure?

a) stack
b) heap
c) binary search tree
d) balanced binary search tree

• Skip lists have the same asymptotic time complexity as a balanced binary search tree.
• For a Balanced Binary Search Tree, we skip almost half of the nodes after one comparison with the root element.
• The same thing was done in the skip lists. Hence skip lists are similar to balanced Binary search trees.

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

a) O(n) to O(log N) where n is the number of elements
b) O(n) to O(1) where n is the number of elements
c) no change
d) O(n) to O(n2) where n is the number of elements

In the Skip list, we skip some of the elements by adding more layers. In this, the skip list resembles balanced binary search trees. Thus we can change the time complexity from O (n) to O (long).

5. To which data structure is skipped lists similar in terms of time complexities in worst and best cases?

a) balanced binary search trees
b) binary search trees
c) binary trees

Skip lists are similar to any randomly built binary search tree. a BST is balanced to avoid skew tree formations in case of sequential input and hence achieve O(logn) in all 3 cases. now skip lists can guarantee that O(log N) complexity for any input.

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

a) probabilistically
b) randomly
c) sequentially
d) orthogonally

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

7. Are the below statements true about skip lists?
In a sorted set of elements skip lists can implement the below operations
i.given an element find the closest element to the given value in the sorted set in O(logn)
ii. find the number of elements in the set whose values fall a given range in O(logn)

a) true
b) false

To achieve the above operations augment with a few additional stuff like partial counts.

8. How to maintain multi-level skip list properties when insertions and deletions are done?

a) design each level of a multi-level skip list with varied probabilities
b) that cannot be maintained
c) rebalancing of lists
d) reconstruction

By designing each level of a multi-level skip list with varied probabilities we can maintain multi-level skip list properties when insertions and deletions are done

For example, consider a 2-level skip list. the level-2 skip list can skip one node on average and some places may skip 2 nodes, depending on probabilities. this ensures O(long).

9. Is a skip list like a balanced tree?

a) true
b) false

Skip list behaves as a balanced tree with high probability and can be commented as such because nodes with different heights are mixed up evenly.

10. What is an indexed skip list?

a) it stores the width of the link in place of the element
b) it stores index values
d) indexed tree

The width is defined as a number of bottom layer links that are being traversed by each of the higher layer elements. e.g: for a level-2 skip list, all level-1 nodes have 1 as width, for level-2 width will be 2.

1. What is xor linked list?

a) uses of bitwise XOR operation to decrease storage requirements for doubly-linked lists
b) uses of bitwise XOR operation to decrease storage requirements for linked lists
c) uses of bitwise operations to decrease storage requirements for doubly-linked lists
d) just another form of linked list

We use bitwise XOR operation to decrease storage requirements for doubly-linked lists.

2. What does a xor linked list have?

a) every node stores the XOR of addresses of previous and next nodes
b) actual memory address of the next node
c) every node stores the XOR of addresses of the previous and next two nodes
d) every node stores xor 0 and the current node address

A xor linked list has every node store the XOR of addresses of previous and next nodes.

Every node stores the XOR of addresses.

3. What do the first and last nodes of a xor link list contain? (let the address of first and last be A and B)

a) NULL xor A and B xor NULL
b) NULL and NULL
c) A and B
d) NULL xor A and B

The first and last nodes of a xor link list contain NULL xor A and B xor NULL.

4. Which of the following is an advantage of the XOR list?

a) Almost of debugging tools cannot follow the XOR chain, making debugging difficult
b) You need to remember the address of the previously accessed node in order to calculate the next node’s address
c) In some contexts XOR of pointers is not defined
d) XOR list decreases the space requirement in a doubly-linked list

XOR linked list stores the address of previous and next nodes by performing XOR operations. It requires a single pointer to store both the XOR address of the next and previous nodes. Thus it reduces space. It is an advantage. But the main disadvantages are debugging tools cannot follow the XOR chain, the previous node address must be remembered to get the next nodes, and pointers are not defined accurately.

5. Which of the following is not the properties of XOR lists?

a) X⊕X = 0
b) X⊕0 = X
c) (X⊕Y)⊕Z = X⊕(Y⊕Z)
d) X⊕0 = 1

The important properties of XOR lists are X⊕X=0, X⊕0=X, and (X⊕Y)⊕Z = X⊕(Y⊕Z).

6. 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 more efficient than single, doubly linked lists and arrays

a) i, ii, iii, iv
b) i, ii, iii
c) i, ii
d) i

Xor lists require the same time for most of the operations as arrays would require.

7. What’s wrong with this code which returns xor of two nodes’ addresses?

//struct is common userdefined datatype in c/c++ and class is it's alternative

struct node* XOR (struct node *a, struct node *b)
{
//this logic is used to fill the nodes with address of a xor linked list
return ((int) (a) ^ (int) (b));
}

a) nothing wrong. everything is fine
b) type casting at return is missing
c) parameters are wrong
d) total logic is wrong

It must be typecasted– return (struct node*)((int) (a) (int) (b));

8. Given 10,8,6,7,9
swap the above numbers such that finally, you got 6,7,8,9,10
so now reverse 10
9,7,6,8,10
now reverse 9
8,6,7,9,10
7,6,8,9,10
6,7,8,9,10
at this point 6 is ahead so no more reversing can be done so stop.
To implement the above algorithm which data structure is better and why?

a) linked list. because we can swap elements easily
b) arrays. because we can swap elements easily
c) xor linked list. because there is no overhead of pointers, memory is saved
d) doubly linked list because you can traverse back and forth

XOR linked lists are used to reduce the memory by storing the XOR values of address instead of the actual address in pointers.

10. In the above question would using arrays and swapping of elements in place of xor linked list would have been more efficient?

a) no not all
b) yes arrays would have been better than xor lists
c) both would be the same in efficiency
d) can’t say

The locality of a normal array is faster in memory and moreover one has to traverse n-nodes to reach the target to reverse in case of xor linked list.

1. 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

Free lists are used in dynamic memory allocation. Their property is meant for dynamic allocations.

2. What are implicit and explicit implementations of free lists?

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

The implicit and explicit implementations of free lists are garbage collection and new or malloc operators respectively. Gc and new most widely known.

3. What data structures can be used in implementing a free list?

b) linked list or sort trees
c) arrays
d) trees

linked list or sort trees data structures can be used in implementing a free list. Sort trees can also be used in implementing free lists which remain complex.

4. 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

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

5. What is buddy memory management of free lists?

a) modified version of the 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

When an allocation request is received,‭ ‬the list that holds blocks that are just large enough to satisfy the request is 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.

6. How do implicit free lists(garbage collection) works in adding memory to the free list?

a) whichever comes last will be added to the free list
b) whichever comes first will be added to the 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

Certain blocks cannot be used if there are no pointers to them and hence they can be freed to implicit free lists(garbage collection) works in adding memory to the free list.

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

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

The disadvantage of implementing a buddy system algorithm for free lists is Internal fragmentation issue to be dealt and it takes so much space.

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

8. Assume there is a free list that contains nodes and is filled with a value if it is already assigned and the value will be the size of the 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 the first fit
b) code for best fit
c) code for worst fit
d) none of the mentioned

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

9. How are free blocks linked together mostly and in what addressing order?

d) none of the mentioned

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

10. Accessing a free list very frequently for a wide range of addresses can lead to

a) paging
b) segmentation fault
c) memory errors
d) cache problems