Deck 16: Linked Lists

Question 1

A linked list is a collection of components called ____.

A) elements
B) nodes
C) members
D) pointers

Answer 1

B

Question 2

The link field of the last node of a linked list is ____.

A) NULL
B) 1
C) n-1
D) n

Answer 2

A

Question 3

You deallocate the memory for a linked list by calling the operator clear.

Answer 3

False

Question 4

Data can be organized and processed sequentially using an array called a(n)____ list.

A) linked
B) ordered
C) sequential
D) ascending

Question 5

Each node of a singly linked list has two components: ____ and ____.

A) info, head
B) link, back
C) back, head
D) info, link

Question 6

Linked lists allow you to overcome the size limitations of an array data type.

Question 7

The length of a linked list is the number of nodes in the list.

Question 8

In a linked list,the address of the first node in the list is stored in a separate location,called the ____ or first.

A) head
B) pointer
C) front
D) top

Question 9

Suppose that the pointer head points to the first node in the list,and the link of the last node is NULL.The first node of the linked list contains the address of the ____ node.

A) head
B) first
C) second
D) tail

Question 10

What is the purpose of the following code? current = head;
While (current != NULL)
{
//Process current
Current = current->link;
}

A) Insertion of a node
B) Selection of a node
C) Traversal of a linked list
D) Creation of a new list

Question 11

When you build a linked list in the backward manner,a new node is always inserted at the end of the linked list.

Question 12

In a linked list,the order of the nodes is determined by the address,called the ____,stored in each node.

A) head
B) tail
C) link
D) first

Question 13

A linked list is a random access data structure.

Question 14

Every node (except of the last node)in a singly linked list contains ____.

A) the next node
B) no address information
C) the address of the next node
D) the address of the previous node

Question 15

It is not possible to create an ordered linked list.

Question 16

A doubly linked list can be traversed in either direction.

Question 17

In a linked list,if a new item is always inserted at the beginning or at the end of the list and the data read is unsorted,the linked list will be unsorted.

Question 18

Because each node of a linked list has two components,we need to declare each node as a(n)____.

A) reference and string
B) int and object
C) index and element
D) class or struct

Question 19

You can use the pointer head of a linked list to traverse the list.

Question 20

Memory for the components of an array does not need to be contiguous.

Question 21

Which of the following correctly initializes a doubly linked list in the default constructor?

A) head = NULL;
Back = NULL;
B) head = 0;
Back = 0;
Count = 0;
C) first = 0;
Last = 0;
D) first = NULL;
Last = NULL;
Count = 0;

Question 22

When building a linked list in the ____ manner,a new node is always inserted at the end of the linked list.

A) backward
B) forward
C) traversal
D) random

Question 23

template
____ doublyLinkedList::isEmptyList() const
{
return (first == NULL);
}
Consider the following code,which deletes all the nodes in a linked list. void doublyLinkedList::destroy()
{
NodeType *temp; //pointer to delete the node
While (first != NULL)
{
Temp = first;
First = first->next;
____
}
Last = NULL;
Count = 0;
}
Which of the following is the missing statement?

A) delete first;
B) delete temp;
C) destroy temp;
D) clear temp;

Question 24

template
____ doublyLinkedList::isEmptyList() const
{
return (first == NULL);
}
Consider the accompanying statements.The list is empty if the pointer first is ____.

A) NULL
B) 0
C) last
D) next

Question 25

What is the output of the following program segment? (The class unorderedLinkedList is as defined in the book.) unorderedLinkedList list;
List.insertFirst(6);
List.insertLast(5);
List.insertFirst(4);
List.insertFirst(8);
List.insertLast(10);
List.deleteNode(4);
List.insertFirst(1);
List.print();

A) 1 6 5 8 10
B) 1 6 8 10 5
C) 1 8 6 5 10
D) 1 8 10 6 5

Question 26

In C++,the dereferencing operator is represented by the ____________________ symbol.

Question 27

In a linked list,the link component of each node is a(n)____________________.

Question 28

Each node of a linked list must store the data as well as the ____________________ for the next node in the list.

Question 29

How many pointers are needed to build a linked list in a backward manner?

A) One
B) Two
C) Three
D) Four

Question 30

The ____ deallocates the memory occupied by the nodes of a list when the class object goes out of scope.

A) constructor
B) destructor
C) head pointer
D) tail pointer

Question 31

Every node in a doubly linked list has two pointers: ____ and ____.

A) previous; next
B) back; next
C) current; next
D) previous; current

Question 32

template
____ doublyLinkedList::isEmptyList() const
{
return (first == NULL);
}
Consider the accompanying statements.The operation returns true if the list is empty; otherwise,it returns false.The missing code is ____.

A) protected
B) int
C) void
D) bool

Question 33

The deleteNode operation (if the item to be deleted is in a doubly linked list)requires the adjustment of ____ pointer(s)in certain nodes.

A) one
B) two
C) three
D) four

Question 34

struct nodeType
{
int info;
nodeType *link;
};
nodeType *head, *p, *q, *newNode;
newNode = new nodeType;
Consider the accompanying code.What is the effect of the following statement? newNode->info = 50;

A) Stores 50 in the info field of the newNode
B) Creates a new node
C) Places the node at location 50
D) Cannot be determined from this code

Question 35

Which of the following is a basic operation on singly linked lists?

A) Retrieve the data of an arbitrary node.
B) Swap the head and the last nodes.
C) Determine whether the list is full.
D) Make a copy of the linked list.

Question 36

The steps involved in inserting a new item at the beginning of an unordered linked list are ____.

A) 1. Create a new node. 2. Insert the node before first.
3) Increment the counter by 1.
B) 1. Create a new node. 2. Store the new item in the new node.
3) Insert the node before first.
4) Increment the counter by 1.
C) 1. Create a new node. 2. Store the new item in the new node.
3) Insert the node before first.
D) 1. Create a new node. 2. Store the new item in the new node.
3) Insert the node before first.
4) Decrement the counter by 1.

Question 37

template
____ doublyLinkedList::isEmptyList() const
{
return (first == NULL);
}
Which of the following statements appears in the insert function of a doubly linked list?

A) current++;
B) trailCurrent++;
C) newNode++;
D) count++;

Question 38

template
____ doublyLinkedList::isEmptyList() const
{
return (first == NULL);
}
Consider the following code: template
Int doublyLinkedList::length()const
{
____
}
The statement that provides the length of the linked list is ____.

A) cout <<< count;
B) destroy();
C) return count;
D) return next;

Question 39

A(n)____________________ is an object that produces each element of a container,such as a linked list,one element at a time.

Question 40

The ____________________ operator advances the iterator to the next node in the linked list.

Question 41

In a circular linked list with more than one node,it is convenient to make the pointer first point to the ____________________ node of the list.

Question 42

The nodes of a standard ordered list (as constructed in the text)are in ____________________ order.

Question 43

In a linked list,the ____________________ operator returns the info of the current node.

Question 44

If a formal parameter is a value parameter,the ____________________ constructor provides the formal parameter with its own copy of the data.

Question 45

For classes that include pointer data members,the assignment operator must be explicitly ____________________.

Question 46

The ____________________ constructor executes when an object is declared and initialized using another object.

Question 47

A(n)____________________ linked list is a linked list in which every node has a next pointer and a back pointer.

Question 48

The ____________________ constructor can make an identical copy of a linked list.

Question 49

A linked list must be searched ____________________,starting from the first node.

Question 50

A linked list in which the last node points to the first node is called a(n)____________________ linked list.