Unit 2: Linked Lists - Practice Quiz
1 What is a linked list?
2 What does a node in a singly linked list normally contain?
3 How are linked-list nodes usually arranged in memory?
4 What does the link field of a node store?
5 When is memory commonly allocated for a new linked-list node?
6 What should normally happen to the memory of a deleted node?
7 Where does traversal of a singly linked list normally begin?
8 When does traversal of a standard grounded singly linked list stop?
NULL
9 What must be updated when a new node is inserted at the beginning of a linked list?
10 To insert a node after a given node in a singly linked list, which information is essential?
11 What happens to the first-node pointer when the first node is deleted?
12 Before deleting a non-first node from a singly linked list, which node is commonly located?
13 What is a header node in a header linked list?
14 How is the end of a grounded header linked list usually represented?
NULL
NULL
15 Where does the last node point in a circular header linked list?
NULL reference
16 What distinguishes a circular header linked list from a grounded header linked list?
17 How many link fields does a typical node in a two-way linked list contain?
18 What is another common name for a two-way linked list?
19 Which traversal is directly supported by a two-way linked list?
20 When inserting a node between two nodes in a two-way linked list, which links may require updating?
21 A program frequently inserts records in the middle of a sequence, but it rarely accesses records by index. Why is a linked list generally more suitable than an array for this workload?
22 A singly linked list contains nodes, and only a pointer to the first node is available. What is the time complexity of accessing the node at position ?
23 Suppose a singly linked node occupies memory address 500, stores data 18, and has link value 740. What does the value 740 represent?
24 Each node in a singly linked list stores a 4-byte integer and an 8-byte pointer. Ignoring alignment and allocator overhead, how much memory is required for 25 nodes?
25 During insertion, memory allocation for a new linked-list node fails. What should the insertion operation do before modifying any existing links?
26 A deleted node is not returned to the memory allocator, and no list pointer refers to it afterward. Which problem has occurred?
27
The pointer current initially refers to the first node of a nonempty singly linked list. Which condition correctly allows every node to be processed exactly once in a standard linear traversal?
current != NULL
current->next != NULL
current == head
28
A singly linked list stores the values 4 -> 7 -> 3 -> 8 -> NULL. A traversal adds a value to a sum only when the value is even. What sum is produced?
29
A new node N must be inserted immediately after node P in a singly linked list. Which sequence preserves the remainder of the list?
N->next = P; P->next = NULL;
P->next = N; N->next = P->next;
P->next = NULL; N->next = P;
N->next = P->next; P->next = N;
30
A singly linked list maintains both head and tail. A valid new node is inserted at the end. What is the insertion time complexity?
31
In the list 10 -> 20 -> 30 -> 40 -> NULL, a pointer P refers to the node containing 20. Which update removes the node containing 30, assuming its memory is freed separately?
P->next->next = P;
head = P->next;
P->next = P->next->next;
P = P->next->next;
32
A singly linked list has exactly one node, and both head and tail point to it. After deleting that node, what should be true?
head should be NULL
head should refer to the released node until another insertion occurs
head and tail should be NULL
tail should be NULL
33
In a grounded header linked list, the header node is not counted as a data node. If header->next == NULL, what does this indicate?
34
A grounded header list is H -> 6 -> 11 -> NULL. To insert a new node containing 3 at the beginning of the data portion, which links should be assigned?
H->next->next = new; new->next = H;
new->next = H; H->next = NULL;
new->next = H->next; H->next = new;
H = new; new->next = NULL;
35
Which condition correctly terminates traversal of a nonempty circular header linked list when traversal starts at header->next?
current == NULL
current == header
current->next == NULL
36
A circular header list has one data node X. Which pair of links correctly represents this structure?
header->next = NULL and X->next = X
header->next = X and X->next = NULL
header->next = header and X->next = header
header->next = X and X->next = header
37
In the doubly linked sequence A <-> B <-> C, which relationships must hold for the adjacent nodes B and C?
B->next == C and C->next == B
B->prev == C and C->next == B
B->prev == A and every later node must store the address of A
B->next == C and C->prev == B
38 Compared with a singly linked list storing the same data, what is the principal memory cost of a two-way linked list?
39
A new node N is inserted between existing nodes P and Q in a doubly linked list, where P->next == Q. Which set of assignments correctly establishes all four local links?
N->prev=P; N->next=Q; P->next=N; Q->prev=N;
N->prev=P; N->next=Q; P->prev=N; Q->next=N;
N->prev=P; P->next=Q; Q->prev=N; N->next=P;
N->prev=Q; N->next=P; P->next=N; Q->prev=N;
40
Node X lies between nodes P and Q in a doubly linked list. Which updates remove X while preserving links between its neighbors, assuming X is freed afterward?
X->next = P; X->prev = Q;
P->next = Q; Q->prev = P;
P->next = NULL; Q->prev = NULL;
P->prev = Q; Q->next = P;
41 A singly linked list stores elements, and only a pointer to its first node is maintained. Which operation has worst-case time even when the target node is supplied as a direct pointer?
42 Nodes occupy unrelated heap addresses. A node begins at address 1200, its link field contains 7840, and the node at address 7840 has its link field set to 0. What conclusion follows independently of node sizes and allocation order?
43
To insert a node after p, a program first executes p->next = newNode and then attempts newNode->next = oldSuccessor. Which defect is fundamental if no separate copy of p->next was saved?
p
44
An insertion routine allocates q, initializes it, links it into a list, and then discovers that a required validation condition fails. Which rollback is sufficient when q has exactly one predecessor p and successor s?
q->next = p, then deallocate s
p->next = s, then deallocate q
p = s, then deallocate q
q, then evaluate q->next
45
Floyd's traversal starts slow and fast at the first node and repeatedly moves them by one and two links. In a list with a noncyclic prefix of length and a cycle of length , what is guaranteed if a cycle exists?
46 A list may be either null-terminated or circular, and no header-node convention or node count is supplied. Which traversal method safely terminates in both cases using auxiliary space?
NULL
NULL or a return to the first node
47
Let last point to the final node of a nonempty circular singly linked list, so last->next is the first node. Which updates insert q at the front while preserving last?
q->next = last; set last->next = q
last->next = q; set q->next = last
q->next = last->next; set last->next = q
last = q; set q->next = last->next
48
A sorted singly linked list permits duplicate keys and must remain stable by insertion time, with newer equal keys placed after older equal keys. While locating the insertion point for key , which condition should advance p?
p->next->key != k
p->next->key <= k
p->next->key >= k
p->next->key < k
49
A circular singly linked list is represented only by last. It contains one node, and that node is deleted. Which postcondition correctly represents the empty list without retaining a dangling pointer?
last = NULL after deallocating the node
last = last->next after deallocating the node
last unchanged and test its stored key
last->next = last after deallocating the node
50
In a singly linked list, p precedes the node q to be deleted. Which ordering avoids both losing the suffix and dereferencing freed storage?
p->next = q->next, then deallocate q
q, then set p->next = q->next
p = q->next, then deallocate q
q->next = p->next, then deallocate p
51
A grounded header list always contains a header node H; an empty list satisfies H->next == NULL. To concatenate list B onto nonempty list A in time, which additional maintained information is sufficient?
52
A grounded header list uses H as a permanent sentinel and stores no data in it. Which deletion loop correctly removes every data node without treating the header as an element?
H->next != NULL, remove the node referenced by H->next
H != NULL, remove the node referenced by H
H->next != H, remove the node referenced by H->next
H->next->next != NULL, remove the node referenced by H->next
53
In a circular header list with sentinel H, emptiness is represented by H->next == H. During a search, the target key is temporarily copied into H. What is the principal algorithmic benefit?
54
Two nonempty circular singly linked lists use headers H1 and H2, and pointers t1 and t2 identify their last data nodes. Which rewiring concatenates list 2 after list 1 while retaining H1 as the sole header?
t1->next = H2; set t2->next = H1->next
H1->next = H2; set t2->next = t1
t1->next = H2->next; set t2->next = H1
t2->next = H2->next; set t1->next = H1
55
For every adjacent pair of nodes and in a well-formed two-way list where x->next == y, which invariant must also hold?
y->prev == x
x->prev == y
x->next == x
y->next == x
56
A linear doubly linked list has both head and tail. Starting from the nearer end, what is the worst-case number of link traversals needed to reach the node at zero-based position among nodes?
57
In a noncircular doubly linked list, node q lies strictly between nodes p and r. Which pair of assignments removes q from the list before it is deallocated?
p->next = q and r->prev = q
p->prev = r and r->next = p
q->next = p and q->prev = r
p->next = r and r->prev = p
58
A nonempty linear doubly linked list maintains head and tail. After deleting its sole node, which state preserves all endpoint invariants?
head and tail are set to NULL
tail is set to NULL
head is set to NULL
59
A doubly linked list segment is a <-> b <-> c <-> d. The sublist from b through c must be detached while preserving it as an independent linear list. Which updates are required?
a->prev = d, d->next = a, b->next = NULL, and c->prev = NULL
a->next = c, c->prev = a, b->prev = NULL, and d->next = NULL
b->prev = d, c->next = a, a->next = NULL, and d->prev = NULL
a->next = d, d->prev = a, b->prev = NULL, and c->next = NULL
60
A circular doubly linked list has sentinel H. A new node q is inserted immediately before node x, where x may equal H. Which four assignments correctly perform the insertion?
q->prev = x->prev, q->next = H, H->prev = q, and x->next = q
q->prev = H, q->next = x, H->next = q, and x->prev = H
q->prev = x->prev, q->next = x, x->prev->next = q, and x->prev = q
q->prev = x, q->next = x->next, x->next->prev = q, and x->next = q
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill. The rest comes out of a student's own pocket: the domain, the storage, and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason. to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it. What it pays for →