Lesson test: Linked structures

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Linked structures

1.[2p]
Why is indexing a singly linked list $Θ (n)$ rather than $Θ (1)$ ?

The address of node $i$ is stored inside node $i - 1$ , so it can only be found by following pointers

Correct

Pointers are slower to read than integers

The answer is: The address of node $i$ is stored inside node $i-1$, so it can only be found by following pointers

The nodes are stored in reverse order

The answer is: The address of node $i$ is stored inside node $i-1$, so it can only be found by following pointers

The list has to be counted before it can be indexed

The answer is: The address of node $i$ is stored inside node $i-1$, so it can only be found by following pointers

2.[2p]
A structure holds 10,000 elements. Inserting at position 100, how many elements does a dynamic array have to shift?

CorrectNot quite: 9900

3.[2p]
A singly linked list can delete a node in constant time given only a pointer to that node.

True

The answer is: False

False

Correct

4.[2p]
A ring buffer has capacity 8, head at slot 6, and holds 5 elements. Which slot will the next enqueue write to?

CorrectNot quite: 3

5.[2p]
Match each structure to the discipline it enforces.

Stack
Queue
Deque

last in, first out
insertion and removal at both ends
first in, first out

Show the answer

Stack: last in, first out Queue: first in, first out Deque: insertion and removal at both ends

6.[3p]
Which are genuine reasons to choose a doubly linked list over a dynamic array?

Select all that apply

Unlinking a node you already hold a reference to, in constant time

Correct

Splicing a whole sublist into another list in constant time

Correct

Needing a hard worst-case bound with no reallocation pause

Correct

Scanning all elements faster

The answer is: Unlinking a node you already hold a reference to, in constant time, Splicing a whole sublist into another list in constant time, Needing a hard worst-case bound with no reallocation pause

7.[3p]
Scanning a million 8-byte elements is roughly eight times faster in an array than in a linked list because

a 64-byte cache line delivers eight array elements per memory fetch, while scattered nodes need one fetch each

Correct

pointer arithmetic is eight times slower than index arithmetic

The answer is: a 64-byte cache line delivers eight array elements per memory fetch, while scattered nodes need one fetch each

the array scan is $Θ (n)$ and the list scan is $Θ (n \log n)$

The answer is: a 64-byte cache line delivers eight array elements per memory fetch, while scattered nodes need one fetch each

the array is stored in the processor's registers

The answer is: a 64-byte cache line delivers eight array elements per memory fetch, while scattered nodes need one fetch each

8.[2p]
An LRU cache uses a doubly linked list rather than an array because

a hash table hands it the node directly, and moving a held node to the front is then constant time

Correct

linked lists use less memory

The answer is: a hash table hands it the node directly, and moving a held node to the front is then constant time

arrays cannot store a million entries

The answer is: a hash table hands it the node directly, and moving a held node to the front is then constant time

the recency order does not need to be maintained

The answer is: a hash table hands it the node directly, and moving a held node to the front is then constant time

9.[2p]
To find an element whose position is unknown, both an array and a linked list cost $Θ (n)$ in the worst case.

True

Correct

False

The answer is: True

1.[2p] Why is indexing a singly linked list Θ(n) rather than Θ(1)?

2.[2p] A structure holds 10,000 elements. Inserting at position 100, how many elements does a dynamic array have to shift?

3.[2p] A singly linked list can delete a node in constant time given only a pointer to that node.

4.[2p] A ring buffer has capacity 8, head at slot 6, and holds 5 elements. Which slot will the next enqueue write to?

5.[2p] Match each structure to the discipline it enforces.

6.[3p] Which are genuine reasons to choose a doubly linked list over a dynamic array?

7.[3p] Scanning a million 8-byte elements is roughly eight times faster in an array than in a linked list because

8.[2p] An LRU cache uses a doubly linked list rather than an array because

9.[2p] To find an element whose position is unknown, both an array and a linked list cost Θ(n) in the worst case.

1.[2p]
Why is indexing a singly linked list $Θ (n)$ rather than $Θ (1)$ ?

2.[2p]
A structure holds 10,000 elements. Inserting at position 100, how many elements does a dynamic array have to shift?

3.[2p]
A singly linked list can delete a node in constant time given only a pointer to that node.

4.[2p]
A ring buffer has capacity 8, head at slot 6, and holds 5 elements. Which slot will the next enqueue write to?

5.[2p]
Match each structure to the discipline it enforces.

6.[3p]
Which are genuine reasons to choose a doubly linked list over a dynamic array?

7.[3p]
Scanning a million 8-byte elements is roughly eight times faster in an array than in a linked list because

8.[2p]
An LRU cache uses a doubly linked list rather than an array because

9.[2p]
To find an element whose position is unknown, both an array and a linked list cost $Θ (n)$ in the worst case.