Deck 17: Linked Lists

Question 1

To concatenate two linked lists, it is necessary to

A) traverse one of the lists to get to its end.
B) traverse both lists to get to their ends.
C) first reverse one of the lists.
D) first reverse both lists.
E) None of the above

Answer 1

A

Question 2

Deleting an entire list requires traversing the list to delete the nodes.

Answer 2

True

Question 3

The STL implementation of a linked list is a class called

A) LinkedList.
B) DynamicList.
C) dequeue.
D) list.
E) None of the above

Answer 3

D

Question 4

In a doubly-linked list, each node contains a pointer to the next node in the list, as well as a pointer to

A) itself.
B) the head node.
C) the tail node.
D) the previous node.
E) None of the above

Question 5

The ________ of a linked list points to the first node in the list.

A) starter
B) head
C) tail
D) declaration
E) None of the above

Question 6

The list container provided by the Standard Template Library is a template version of a

A) singly-linked list.
B) doubly-linked list.
C) circular-linked list.
D) backward-linked list.
E) None of the above

Question 7

Moving through a linked list is referred to as ________ the list.

A) cruising
B) traversing
C) node-hopping
D) alternating
E) None of the above

Question 8

The defining characteristic of a linked list is that

A) data are stored in consecutive locations in the memory of the computer.
B) lists are very efficient at storing data.
C) the locations that store list data do not have to be consecutive in memory.
D) the maximum size of a list is fixed when the list is created.
E) None of the above

Question 9

Inserting an item into a linked list requires that all the items past the point of the insertion be shifted to make room for the new item.

Question 10

A linked list can grow and shrink as a program runs.

Question 11

In a non-empty list, there must be exactly one list item with no successor.

Question 12

In many recursive operations on linked lists,

A) the head of the list is chopped off and thrown away.
B) the base case considers the last element of the list.
C) the base case is when the list is empty or has a single element.
D) All of the above
E) None of the above

Question 13

When you create a linked list, you must know in advance how many nodes the list will contain.

Question 14

If a node is not the first node in a linked list, deleting it may require setting the successor pointer in its predecessor.

Question 15

When an item stored in a linked list is removed, all list items stored after it have to be moved down to plug up the hole.

Question 16

A new node cannot become the first node in the list.

Question 17

A non-empty linked list of items can be reversed by removing the head, reversing what is left, and then adding the (original) head at the end of the reversed tail.

Question 18

A new node must always be made the last node in the list.

Question 19

The values stored in the value portion of a node of a linked list can be simple data types, structures, objects of classes, or any other data type.

Question 20

If the head pointer points to NULL, it is an indication that

A) the list has been destroyed.
B) the list needs to be destroyed.
C) there are no nodes in the list.
D) the list is full and cannot accept any new nodes.
E) None of the above

Question 21

Each node in a ________ list contains pointers to the nodes before and after it.

A) singly-linked
B) doubly-linked
C) circular-linked
D) both B and C
E) None of the above

Question 22

A linked list class using dynamically allocated memory should free its memory when the list is destroyed. This can be done by

A) the system's memory deallocator.
B) the class destructor.
C) overriding the class removal function.
D) overloading the class removal function.
E) None of the above

Question 23

When you delete a node from a linked list, you must ensure that the links in the surrounding nodes are set to bypass the node being deleted.

Question 24

A ________ is used to step through a linked list and search for data.

A) node
B) pointer
C) NULL value
D) traversal operator
E) None of the above

Question 25

Adding a new node in the middle or at the end of a singly-linked list requires a pointer to the node after which the new node will be added.

Question 26

Variations of the linked list are

A) doubly-linked list.
B) circular linked list.
C) triply linked list.
D) A and B
E) None of the above

Question 27

One advantage a linked list has over a vector is that

A) a linked list can dynamically shrink or grow, and a vector cannot.
B) a linked list is smaller than a vector.
C) insertion and removal of items is faster with lists than with vectors.
D) All of the above
E) None of the above

Question 28

A list that contains pointers to the previous node, the next node, and a node in the third dimension is known as a triple-linked list.

Question 29

Linked lists are less complex to code and manage than arrays.

Question 30

Nodes in a linked list are stored in contiguous memory.

Question 31

Deleting an entire linked list requires a call to the delete operator for each node in the list.

Question 32

To build a linked list, we can

A) start with an empty list, and then form an array of nodes.
B) start with an empty list, and then perform a series of add item operations.
C) use the constructor to create an array of nodes.
D) call the list init function.
E) None of the above

Question 33

If new information needs to be added to a linked list, the program simply ________ and inserts it into the list.

A) allocates another node
B) removes a node
C) borrows a node from the compiler
D) either B or C
E) None of the above

Question 34

The Standard Template Library (STL) provides a linked list container.
L) provides a linked list container.

Question 35

Linked lists of items are commonly implemented by

A) using an array to hold list items.
B) using a function to compute the link to the next item.
C) using a class template to represent list items.
D) using a structure containing an item and a pointer to the structure type.
E) None of the above

Question 36

Which of the following are linked list operations?

A) adding an item
B) traversing the list
C) removing an item
D) All of the above
E) None of the above

Question 37

The successor pointer in the last node of a linked list should have its value set to

A) NULL .
B) the address of the previous node.
C) the address of the first node in the list.
D) nothing: the last node has no successor pointer.
E) None of the above

Question 38

When using a node pointer to traverse a linked list, we know we have reached the end of a list when

A) we encounter the new line character '\n'.
B) we encounter a successor pointer value of NULL in the current node.
C) we arrive back at the beginning of the list.
D) we encounter a sentinel, usually 9999.
E) None of the above