Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the near node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.

A

I only

B

II only

C

Both I and II

D

Neither I and II

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

A

Possible if X is not last node

B

Possible if size of linked list is even

C

Possible if size of linked list is odd

D

Possible if X is not first node

Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list ?

A

Delete the first element of the list

B

Interchange the first two elements of the list

C

Delete the last element of the list

D

Add an element at the end of the list

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

A

Delete the first element

B

Insert a new element as a first element

C

Delete the last element of the list

D

Add a new element at the end of the list

Consider the problem of reversing a singly linked list. To take an example, given the linked list below, the reversed linked list should look like Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

A

The best algorithm for the problem takes θ(n) time in the worst case.

B

The best algorithm for the problem takes θ(n log n) time in the worst case

C

The best algorithm for the problem takes θ(n²) time in the worst case.

D

It is not possible to reverse a singly linked list in O(1) space

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

A

θ(1), θ(1)

B

θ(1), θ(n)

C

θ(n), θ(1)

D

θ(n), θ(n)

In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

A

Θ(n²)

B

Θ(n + m)

C

Θ(m²)

D

Θ(n⁴)

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?

A

O(log²N)

B

O(N)

C

O(N²)

D

Θ (N²log N)

The correct statement for a function that takes pointer to a float, a pointer to a pointer to a char and returns a pointer to a pointer to a integer is ____________

A

int **fun(float**, char**)

B

int *fun(float*, char*)

C

int **fun(float*, char**)

D

int ***fun(*float, **char)

The correct statement for a function that takes pointer to a float, a pointer to a pointer to a char and returns a pointer to a pointer to a integer is

A

int **fun(float**, char**)

B

int *fun(float*, char*)

C

int ***fun(float*, char**)

D

int ***fun(*float, **char)

Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?

Related Questions