Unit 3: Introduction to Linked Lists - Practice Quiz
1 What is a linked list?
2 What does a node in a singly linked list usually contain?
3 What does the head of a singly linked list refer to?
4 Where does traversal of a singly linked list normally begin?
5 Which value usually marks the end of a singly linked list?
6 When inserting a new node at the beginning of a singly linked list, what should the head reference afterward?
7 To insert a node after a given node, which link must be updated?
8 What happens to the head when the first node of a singly linked list is deleted?
9 When does linked list underflow occur?
10 When can linked list overflow occur?
11 Which description best matches a tree data structure?
12 What is the topmost node of a tree called?
13 What is a tree node with no children called?
14 What are two nodes with the same parent called?
15 What is an edge in a tree?
16 What is the maximum number of children that a node in a binary tree can have?
17 In a binary search tree, where are values smaller than a node usually placed?
18 Which order is used in preorder traversal?
19 Which order is used in inorder traversal?
20 Which order is used in postorder traversal?
21 A program frequently inserts records after a known record. Why may a linked list be more suitable than an array?
22 Which structure correctly represents a node in a singly linked list of integers?
23
For the list 8 → 3 → 6 → null, what is printed by a traversal that starts at head and prints each node before advancing to next?
8 3 6
6 3 8
8 6 3
3 6 8
24
In a nonempty singly linked list, the loop while (current.next != null) current = current.next; terminates with current pointing to which node?
25
Which sequence correctly inserts newNode at the beginning of a singly linked list?
head.next = newNode; newNode = head;
head = newNode.next; newNode.next = null;
newNode.next = head; head = newNode;
newNode.next = null; head.next = newNode;
26
Suppose p points to a node in a singly linked list. Which statements correctly insert newNode immediately after p without losing the remaining list?
newNode.next = p.next; p.next = newNode;
newNode.next = p; p.next = newNode;
p = newNode; newNode.next = p.next;
p.next = newNode; newNode.next = p.next;
27 Which operation correctly deletes the first node of a nonempty singly linked list while allowing its memory to be released?
temp = head.next; free(temp); head = temp;
head = null; free(head); temp = head.next;
free(head.next); head.next = null; temp = head;
temp = head; head = head.next; free(temp);
28
If q = p.next and q is not null, which statements delete q from the list?
p.next = q.next; free(q);
p = q.next; free(q);
q.next = null; free(p.next);
q.next = p; free(p);
29
A deletion is requested when head is null. Which condition has occurred?
30 When does linked list overflow normally occur in a dynamically allocated implementation?
31 A valid tree contains nodes. How many edges does it contain?
32
In a tree, root R has children A, B, and C; node A has children D and E. Which statement is correct?
D and E are siblings, and the degree of R is 3.
A and D are siblings, and the degree of R is 2.
B is a child of A, and the degree of A is 3.
D is the parent of A, and the degree of A is 1.
33 Using edges as the measure, a deepest leaf is reached from the root through three edges. What are the depth of that leaf and the height of the tree?
34
If node X and all nodes descended from X are considered together, what do they form?
X
X
X
X
35 If the root is at level , what is the maximum number of nodes at level of a binary tree?
36 Which statement must be true for every binary tree?
37
The keys 50, 30, 70, 20, 40, 60 are inserted into an empty binary search tree in that order. Where will key 65 be inserted?
70
70
60
60
38
A binary search tree has root 40; its right child is 60, whose left child is 50. Which comparison path is followed when searching for 50?
40 → 50 → 60
40 → 60 → null
60 → 40 → 50
40 → 60 → 50
39
A binary tree has root A; A has children B and C; B has children D and E; and C has right child F. What is its preorder traversal?
D, E, B, F, C, A
A, B, D, E, C, F
D, B, E, A, C, F
A, C, F, B, D, E
40
A binary tree has root A; A has children B and C; B has children D and E; and C has right child F. What is its inorder traversal?
D, B, E, A, C, F
A, B, D, E, C, F
D, E, B, F, C, A
D, B, A, E, C, F
41
A singly linked list is represented by head = 900, with nodes (900: A, 300), (300: B, 700), and (700: C, NULL), where each pair after the address stores (data, next). If the node at address 300 is relocated to address 500, which change preserves the same logical list?
head from address 900 to address 500
500 from 700 to 900
700 from NULL to 500
900 from 300 to 500
42
Assume n is a newly allocated node and head points to the first node of a possibly nonempty singly linked list. Which ordering correctly inserts n at the front without losing access to the original list?
head->next = n; n->next = head;
head = n; n->next = head;
n->next = head; head = n;
n->next = head->next; head = n;
43
A singly linked structure may end in NULL or may contain a cycle. Which traversal strategy guarantees that every reachable node is processed exactly once and that traversal terminates in both cases?
next until the current pointer becomes NULL
44
A sentinel-headed singly linked list is sorted in ascending order. A new value x must be inserted after all existing nodes equal to x. Starting with p at the sentinel, which loop finds the correct predecessor?
while (p->next != NULL && p->data <= x) p = p->next;
while (p->next != NULL && p->next->data >= x) p = p->next;
while (p->next != NULL && p->next->data < x) p = p->next;
while (p->next != NULL && p->next->data <= x) p = p->next;
45
A singly linked list maintains both head and tail. Which operation correctly appends a new node n and preserves head == tail for a one-node list?
tail->next = n; then set tail = n, and set head = n only when tail is NULL
n->next = tail; if empty set head = n, otherwise link head->next = n and set tail = n
n->next = NULL; if empty set head = tail = n, otherwise link tail->next = n and set tail = n
n->next = head; if empty set tail = n, otherwise set head = n and leave tail unchanged
46
Only a pointer p to a non-tail node of a singly linked list is available; neither head nor the predecessor is available. Assuming node identity need not be preserved, how can the logical element at p be deleted in time?
p's data into its successor, redirect p, and then free p
p to its successor, clear the old data, and leave all links unchanged
p onward, remove the final node, and reverse them again
p, bypass the successor, and free the successor
47
The following pointer-to-pointer algorithm deletes every node whose data equals x: Node **link = &head; while (*link != NULL) { if ((*link)->data == x) { Node *t = *link; *link = t->next; free(t); } else { /* missing */ } }. Which statement correctly replaces the missing part?
link = &(*link)->next;
*link = (*link)->next;
link = &head->next;
link = &link[1];
48 For a dynamically allocated linked-list stack with no imposed size limit, which pair most accurately describes underflow and overflow?
head->next is NULL; overflow occurs when the tail is reached
49 A connected undirected tree has vertices. One new edge is added between two distinct existing vertices. Which statement must then be true?
50
A rooted tree has edges R-A, R-B, R-C, A-D, A-E, B-F, E-G, F-H, and F-I. Levels begin at , and height is measured in edges. Which description is correct?
R has degree , E has depth , and the tree has height
R has degree , E has depth , and the tree has height
R has degree , E has depth , and the tree has height
R has degree , E has depth , and the tree has height
51 A rooted tree contains nodes and leaves. Every nonleaf node has either one child or three children. How many nodes have degree three?
52
A rooted tree has edges R-A, R-B, A-C, A-D, D-E, B-F, F-G, and F-H. Which tuple correctly gives (number of nodes in the subtree rooted at D, length of the path from E to G, lowest common ancestor of E and G)?
53 The height of a binary tree is measured as the number of edges on its longest root-to-leaf path. What is the minimum possible height of a binary tree containing nodes?
54 A complete binary tree contains nodes numbered from in level order. How many leaves and how many nodes with exactly one child does it contain?
55 Assume all keys are distinct. Which sequence can be the preorder traversal of a binary search tree?
40, 30, 20, 35, 60, 70, 50
40, 30, 20, 60, 35, 50, 70
40, 30, 20, 35, 60, 50, 70
40, 30, 35, 20, 60, 50, 70
56
Keys 50, 30, 70, 20, 40, 60, 80, 65 are inserted in that order into an empty binary search tree. Node 70 is then deleted using its inorder successor. What is the resulting preorder traversal?
50, 30, 20, 40, 60, 65, 80
50, 30, 40, 20, 80, 65, 60
50, 30, 20, 40, 80, 60, 65
50, 20, 30, 40, 80, 60, 65
57
A binary tree has preorder A, B, D, E, C, F, G and inorder D, B, E, A, F, G, C. What is the preorder traversal of its mirror tree, obtained by swapping the left and right children of every node?
A, C, F, G, B, E, D
A, C, G, F, B, E, D
A, B, E, D, C, F, G
A, C, F, G, B, D, E
58
A full binary tree with distinct labels has preorder A, B, D, E, C, F, G and postorder D, E, B, F, G, C, A. What is its inorder traversal?
E, B, D, A, F, C, G
D, B, E, A, G, C, F
D, E, B, A, F, G, C
D, B, E, A, F, C, G
59
A binary tree has preorder K, D, B, F, E, H, M, L, P and inorder B, D, E, F, H, K, L, M, P. What is its postorder traversal?
B, E, H, D, F, L, P, K, M
B, E, H, F, D, L, P, M, K
B, H, E, F, D, P, L, M, K
E, B, H, F, D, L, P, M, K
60
Keys 45, 25, 65, 15, 35, 55, 75, 30, 40, 70 are inserted into an empty binary search tree in that order. Which sequence is its postorder traversal?
15, 30, 40, 35, 25, 70, 55, 75, 65, 45
15, 30, 40, 35, 25, 55, 70, 75, 65, 45
15, 30, 40, 25, 35, 55, 75, 70, 65, 45
15, 40, 30, 35, 25, 55, 70, 75, 65, 45
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 →