Data Structure Questions and Answers – Xor Linked List

Uncategorized

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

1. 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
A) i, ii, iii, iv
B) i, ii, iii
C) i, ii
D) i

Explanation: For certain operations, Xor lists take the same amount of time as arrays.

2. What’s wrong with this code which returns xor of two nodes address ?

//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

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

3. 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 above algorithm which datastructure 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 and so memory is saved
D) doubly linked list. because you can traverse back and forth

Explanation: XOR related lists are used to save memory by storing the XOR values of address in pointers rather than the actual address.

4. Consider the following pseudocode of insertion in XOR list and write the approximate code snippet of it.

void xor-linked-list insert(struct node **head_ref, int value)
{
    node *new_node  = new (struct node);
    new_node->value = value;
    new_node->nodepointerxored = xor (*head_ref, NULL);
    if (*head_pointer == NULL)
    {
        printf("invalid");
    }
    else
    {
        let b,c,d are nodes and a is to be inserted at beginning,
        a address field must contain NULL xor b and b 
        address filed must be a xor c.
    }
    *head_pointer = new_node;
}

A)

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref)->npx = XOR (new_node, next);

B)

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref) = XOR (new_node, next);

C)

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref)->npx->npx = XOR (new_node, next);

D)

node* next = XOR ((*head_ref),  NULL);
  (*head_ref)->npx = XOR (new_node, next);


Explanation: They code for the english is

node* next = XOR ((*head_ref)->npx,  NULL);
  (*head_ref)->npx = XOR (new_node, next);

.

5. In the above question would using arrays and swaping 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 same in efficiency
D) can’t say

Explanation: The locality of a normal array is faster in memory, and in the case of a xor linked list, one must traverse n-nodes to meet the target to reverse.

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

Explanation: The bitwise XOR operation is used to reduce the amount of storage needed for doubly linked lists.

7. What does a xor linked list have?
A) every node stores the XOR of addresses of previous and next nodes
B) actuall memory address of next node
C) every node stores the XOR of addresses of previous and next two nodes
D) every node stores xor 0 and the current node address

Explanation: Every node stores the XOR of addresses.

8. What does first and last nodes of a xor linked lists contain ? (let 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

Explanation: NULL xor A and B xor NULL.

9. Which of the following is an advantage of 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 doubly linked list

Explanation: XOR connected lists use XOR operations to store the addresses of previous and next nodes. It takes a single pointer to store both the next and previous node’s XOR addresses. As a result, it saves room. This is a benefit. However, debugging tools are unable to follow the XOR chain, previous node addresses must be remembered in order to access subsequent nodes, and pointers are not specified accurately.

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

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

In computer programming, an XOR linked list is a type of data structure. It uses the bitwise XOR operation to reduce the amount of storage needed for doubly linked lists. This type of list differs from a “traditional” XOR linked list in that the instruction sequences required to traverse the list forward are different from those required to traverse the list backward.

Leave a Reply

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