Qualcomm Linked Lists Quiz-1

Question 1

Time: 00:00:00

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Insertion Sort

Quick Sort

Heap Sort

Merge Sort

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 2

Time: 00:00:00

The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function.

/* Link list node */
struct node
{
int data;
struct node* next;
};

/* head_ref is a double pointer which points to head (or start) pointer
of linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
/*ADD A STATEMENT HERE*/
}

What should be added in place of "/*ADD A STATEMENT HERE*/", so that the function correctly reverses a linked list.

*head_ref = prev;

*head_ref = current;

*head_ref = next;

*head_ref = NULL;

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 3

Time: 00:00:00

The following C function takes a simply-linked list as an input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. Choose the correct alternative to replace the blank line.

typedef struct node
{
int value;
struct node *next;
}Node;

Node *move_to_front(Node *head)
{
Node *p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________
return head;
}

q = NULL; p->next = head; head = p;

q->next = NULL; head = p; p->next = head;

head = p; p->next = q; q->next = NULL;

q->next = NULL; p->next = head; head = p;

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 4

Time: 00:00:00

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

union only

intersection, membership

membership, cardinality

union, intersection

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 5

Time: 00:00:00

What are the time complexities of finding the 8th element from the beginning and 8th element from the end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8

O(1) and O(n)

O(1) and O(1)

O(n) and O(1)

O(n) and O(n)

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 6

Time: 00:00:00

Is it possible to create a doubly linked list using only one pointer with every node?

Not Possible

Yes, possible by storing XOR of addresses of previous and next nodes.

Yes, possible by storing XOR of the current node and next node.

Yes, possible by storing XOR of current node and previous node

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 7

Time: 00:00:00

Given pointer to a node X in a singly linked list. Only one pointer is given, the pointer to head node is not given, can we delete the node X from given linked list?

Possible if X is not the last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next to X.

Possible if the size of the linked list is even.

Possible if size of linked list is odd

Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 8

Time: 00:00:00

Consider the following function to traverse a linked list.

void traverse(struct Node *head)
{
while (head->next != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
Which of the following is FALSE about above function?

The function may crash when the linked list is empty

The function doesn\'t print the last node when the linked list is not empty

The function is implemented incorrectly because it changes head

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 9

Time: 00:00:00

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together

O(Log2N)

O(N)

O(N2)

Θ(N2 Log N)

Good Job!

Oops!