Deck 17: Linked Lists

Question 1

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

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

Answer 1

D

Question 2

Linked lists of items are commonly implemented by

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

Answer 2

A

Question 3

The defining characteristic of a linked list is that

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

Answer 3

B

Question 4

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

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

Question 5

Variations of the linked list are

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

Question 6

Which of the following are linked list operations?

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

Question 7

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

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

Question 8

To build a linked list, we can

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

Question 9

To concatenate two linked lists, it is necessary to

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

Question 10

In many recursive operations on linked lists,

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

Question 11

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

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

Question 12

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

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

Question 13

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

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

Question 14

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

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

Question 15

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

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

Question 16

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

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

Question 17

One advantage a linked list has over a vector is that

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

Question 18

The STL implementation of a linked list is a class called

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

Question 19

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 previous node.
C)the head node.
D)the tail node.
E)None of the above

Question 20

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

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

Question 21

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 22

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

Question 23

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

Question 24

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

Question 25

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

Question 26

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

Question 27

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

Question 28

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 29

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

Question 30

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

Question 31

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 32

Nodes in a linked list are stored in contiguous memory.

Question 33

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 34

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 35

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

Question 36

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 37

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 38

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