Unit 2: Linked Lists - Practice Quiz

CSE205 — Data Structures And Algorithms 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is a linked list?

Introduction to linked lists Easy
A. A collection of nodes connected by links
B. A fixed group of adjacent variables
C. A sequence accessed only by indexes
D. A collection stored only in a matrix

2 What does a node in a singly linked list normally contain?

Introduction to linked lists Easy
A. Only data with no linking information
B. Only a link to the previous node
C. Data and links to every other node
D. Data and a link to the next node

3 How are linked-list nodes usually arranged in memory?

Memory representation Easy
A. In processor registers only
B. In consecutive memory locations only
C. In any available memory locations
D. In one fixed memory block

4 What does the link field of a node store?

Memory representation Easy
A. The size of the entire list
B. The value of the current node
C. The index of an array element
D. The address of another node

5 When is memory commonly allocated for a new linked-list node?

Memory allocation Easy
A. When the list is traversed
B. When the node is created
C. When the node is displayed
D. When the program is compiled

6 What should normally happen to the memory of a deleted node?

Memory allocation Easy
A. It should remain reserved
B. It should be released
C. It should store the list length
D. It should become the header

7 Where does traversal of a singly linked list normally begin?

Traversal Easy
A. At the middle node
B. At the final node
C. At a random node
D. At the first node

8 When does traversal of a standard grounded singly linked list stop?

Traversal Easy
A. When the first node is revisited
B. When the header stores zero
C. When the next link is NULL
D. When two nodes have equal data

9 What must be updated when a new node is inserted at the beginning of a linked list?

Insertion Easy
A. The address of the final node only
B. The pointer to the first node
C. The data in every existing node
D. The size of each existing node

10 To insert a node after a given node in a singly linked list, which information is essential?

Insertion Easy
A. The given node's link
B. The final node's memory size
C. The previous node's data value
D. The list's total memory size

11 What happens to the first-node pointer when the first node is deleted?

Deletion Easy
A. It points to the previous node
B. It points to the final node
C. It points to the second node
D. It remains on the deleted node

12 Before deleting a non-first node from a singly linked list, which node is commonly located?

Deletion Easy
A. The node immediately after it
B. The node with the largest value
C. The node immediately before it
D. The node at the list's midpoint

13 What is a header node in a header linked list?

Grounded header linked lists Easy
A. A temporary node used during sorting
B. A special node before the data nodes
C. The final node containing user data
D. A node that always stores maximum data

14 How is the end of a grounded header linked list usually represented?

Grounded header linked lists Easy
A. The first node links to NULL
B. The header links to itself
C. The last node links to NULL
D. The last node links to the header

15 Where does the last node point in a circular header linked list?

Circular header linked lists Easy
A. Back to the header node
B. To a newly allocated node
C. Back to the previous node
D. To a NULL reference

16 What distinguishes a circular header linked list from a grounded header linked list?

Circular header linked lists Easy
A. Its nodes occupy contiguous memory
B. Its last link returns to the header
C. Its nodes have no link fields
D. Its header always contains user data

17 How many link fields does a typical node in a two-way linked list contain?

Two-way lists Easy
A. Three link fields
B. Two link fields
C. One link field
D. No link fields

18 What is another common name for a two-way linked list?

Two-way lists Easy
A. Sequential search list
B. Static array list
C. Singly linked list
D. Doubly linked list

19 Which traversal is directly supported by a two-way linked list?

Operations on two-way linked lists Easy
A. Random traversal by index
B. Forward and backward traversal
C. Forward traversal only
D. Backward traversal only

20 When inserting a node between two nodes in a two-way linked list, which links may require updating?

Operations on two-way linked lists Easy
A. Only the header's data
B. All data fields in the list
C. Previous and next links
D. Only the new node's data

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?

Introduction to linked lists Medium
A. It avoids shifting later elements after the insertion point
B. It supports direct access to any indexed record in constant time
C. It automatically keeps the records sorted after each insertion
D. It stores all records in one contiguous memory block

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 ?

Introduction to linked lists Medium
A.
B.
C.
D.

23 Suppose a singly linked node occupies memory address 500, stores data 18, and has link value 740. What does the value 740 represent?

Memory representation Medium
A. The data stored in the next node
B. The size of the current node
C. The address of the next node
D. The number of nodes remaining in the list

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?

Memory representation Medium
A. 200 bytes
B. 300 bytes
C. 100 bytes
D. 400 bytes

25 During insertion, memory allocation for a new linked-list node fails. What should the insertion operation do before modifying any existing links?

Memory allocation Medium
A. Reuse the current first node without checking its stored data
B. Modify the predecessor link first and allocate the node afterward
C. Set the head pointer to null and report failure
D. Report failure and leave the list unchanged

26 A deleted node is not returned to the memory allocator, and no list pointer refers to it afterward. Which problem has occurred?

Memory allocation Medium
A. Memory leakage
B. Pointer aliasing
C. Index fragmentation
D. Stack overflow

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?

Traversal Medium
A. Continue while current != NULL
B. Continue while current->next != NULL
C. Continue while current == head
D. Continue until the list has been physically rearranged into contiguous memory

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?

Traversal Medium
A. 22
B. 15
C. 12
D. 11

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?

Insertion Medium
A. N->next = P; P->next = NULL;
B. P->next = N; N->next = P->next;
C. P->next = NULL; N->next = P;
D. 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?

Insertion Medium
A.
B.
C.
D.

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?

Deletion Medium
A. P->next->next = P;
B. head = P->next;
C. P->next = P->next->next;
D. 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?

Deletion Medium
A. Only head should be NULL
B. head should refer to the released node until another insertion occurs
C. Both head and tail should be NULL
D. Only 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?

Grounded header linked lists Medium
A. The list contains one data node
B. The header must be dynamically replaced before traversal
C. The list contains no data nodes
D. The final data node points to the header

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?

Grounded header linked lists Medium
A. H->next->next = new; new->next = H;
B. new->next = H; H->next = NULL;
C. new->next = H->next; H->next = new;
D. H = new; new->next = NULL;

35 Which condition correctly terminates traversal of a nonempty circular header linked list when traversal starts at header->next?

Circular header linked lists Medium
A. Stop when current == NULL
B. Stop when current == header
C. Stop when current->next == NULL
D. Stop after dynamically converting the circular list into a grounded list

36 A circular header list has one data node X. Which pair of links correctly represents this structure?

Circular header linked lists Medium
A. header->next = NULL and X->next = X
B. header->next = X and X->next = NULL
C. header->next = header and X->next = header
D. 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?

Two-way lists Medium
A. B->next == C and C->next == B
B. B->prev == C and C->next == B
C. B->prev == A and every later node must store the address of A
D. 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?

Two-way lists Medium
A. One additional data field per node
B. One additional link field per node
C. One complete array stored in each node
D. One extra copy of every node maintained by the list header

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?

Operations on two-way linked lists Medium
A. N->prev=P; N->next=Q; P->next=N; Q->prev=N;
B. N->prev=P; N->next=Q; P->prev=N; Q->next=N;
C. N->prev=P; P->next=Q; Q->prev=N; N->next=P;
D. 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?

Operations on two-way linked lists Medium
A. X->next = P; X->prev = Q;
B. P->next = Q; Q->prev = P;
C. P->next = NULL; Q->prev = NULL;
D. 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?

Introduction to linked lists Hard
A. Insert a new node immediately after the target
B. Replace the value stored in the target node
C. Delete the target while preserving list order
D. Read the value stored in the target node

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?

Memory representation Hard
A. The node at 1200 is followed logically by the node at 7840
B. The node at 1200 is stored contiguously before the node at 7840
C. The node at 7840 must contain the greatest key in the list
D. The node at 7840 was allocated immediately after the node at 1200

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?

Memory allocation Hard
A. The allocator must return memory adjacent to p
B. The successor address is lost before it can be assigned
C. The new node is necessarily leaked before it can be linked
D. The list becomes cyclic for every nonempty input

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?

Memory allocation Hard
A. Set q->next = p, then deallocate s
B. Set p->next = s, then deallocate q
C. Set p = s, then deallocate q
D. Deallocate 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?

Traversal Hard
A. They meet after at most slow-pointer moves
B. They meet after exactly slow-pointer moves
C. They meet after exactly slow-pointer moves
D. They meet after at most slow-pointer moves

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?

Traversal Hard
A. Stop when the next address is numerically smaller
B. Stop when the current key equals the first key
C. Stop only when the current node becomes NULL
D. Record the first node and stop on either 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?

Insertion Hard
A. Set q->next = last; set last->next = q
B. Set last->next = q; set q->next = last
C. Set q->next = last->next; set last->next = q
D. Set 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?

Insertion Hard
A. Advance while p->next->key != k
B. Advance while p->next->key <= k
C. Advance while p->next->key >= k
D. Advance while 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?

Deletion Hard
A. Set last = NULL after deallocating the node
B. Set last = last->next after deallocating the node
C. Leave last unchanged and test its stored key
D. Set 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?

Deletion Hard
A. Set p->next = q->next, then deallocate q
B. Deallocate q, then set p->next = q->next
C. Set p = q->next, then deallocate q
D. Set 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?

Grounded header linked lists Hard
A. A pointer to the first data node of list A
B. The key stored in the header of list B
C. The number of data nodes in list B
D. A pointer to the last data node of list A

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?

Grounded header linked lists Hard
A. While H->next != NULL, remove the node referenced by H->next
B. While H != NULL, remove the node referenced by H
C. While H->next != H, remove the node referenced by H->next
D. While 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?

Circular header linked lists Hard
A. The list remains sorted without insertion comparisons
B. The loop needs only a key-comparison termination test
C. The nodes become physically contiguous in memory
D. The search becomes asymptotically faster than

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?

Circular header linked lists Hard
A. Set t1->next = H2; set t2->next = H1->next
B. Set H1->next = H2; set t2->next = t1
C. Set t1->next = H2->next; set t2->next = H1
D. Set 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?

Two-way lists Hard
A. y->prev == x
B. x->prev == y
C. x->next == x
D. 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?

Two-way lists Hard
A.
B.
C.
D.

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?

Operations on two-way linked lists Hard
A. Set p->next = q and r->prev = q
B. Set p->prev = r and r->next = p
C. Set q->next = p and q->prev = r
D. Set 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?

Operations on two-way linked lists Hard
A. Both head and tail are set to NULL
B. Only tail is set to NULL
C. Both endpoints retain the freed address
D. Only 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?

Operations on two-way linked lists Hard
A. Set a->prev = d, d->next = a, b->next = NULL, and c->prev = NULL
B. Set a->next = c, c->prev = a, b->prev = NULL, and d->next = NULL
C. Set b->prev = d, c->next = a, a->next = NULL, and d->prev = NULL
D. Set 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?

Operations on two-way linked lists Hard
A. Set q->prev = x->prev, q->next = H, H->prev = q, and x->next = q
B. Set q->prev = H, q->next = x, H->next = q, and x->prev = H
C. Set q->prev = x->prev, q->next = x, x->prev->next = q, and x->prev = q
D. Set q->prev = x, q->next = x->next, x->next->prev = q, and x->next = q