Deck 5: Linked Lists

Question 1

Every node in a linked list has two components: one to store the relevant information and one to store the address.

Answer 1

True

Question 2

The order of the nodes in a linked list is determined by the data value stored in each node.

Answer 2

False

Question 3

The address of the first node in a linked list is stored in a separate location, called the head.

Answer 3

True

Question 4

In computer memory, the memory addresses are in binary.

Question 5

Each node of a linked list has at least four components.

Question 6

The link component of each node is a pointer.

Question 7

Operations such as search, insert, and delete require a linked list to be sorted.

Question 8

Building a linked list forward places the new item to be added at the beginning of the linked list.

Question 9

Building a linked list backwards places the new item to be added at the end of the linked list.

Question 10

In general, there are three types of linked lists-sorted, unsorted and mixed.

Question 11

The algorithms to implement the operations search, insert, and remove are the same for sorted and unsorted lists.

Question 12

To simplify operations such as insert and delete, you can define the class to implement the node of a linked list as a struct.

Question 13

To delete a given item from an ordered linked list, there is no need to search the list to see whether the item to be deleted is in the list.

Question 14

In a doubly linked list, every node contains the address of the next node (except the last node), and every node contains the address of the previous node (except the first node).

Question 15

A doubly linked list is a linked list in which every node has a next pointer and a null pointer.

Question 16

A linked list is a random access data structure such as an array.

Question 17

Every element in an STL list points to its immediate predecessor and to its immediate successor.

Question 18

To access the fifth element in a list, we must first traverse the first four elements.

Question 19

In the STL container list, the function push_front adds an element at the beginning of the list.

Question 20

In an ordered list, the header node at the beginning of the list typically contains a value smaller than the smallest value in the data set.

Question 21

In an ordered list, the trailer node at the end of the list contains a value larger than the largest value in the data set.

Question 22

Header and trailer nodes are considered part of a linked list.

Question 23

The usual operations on lists with header and trailer nodes are to initialize the list, destroy the list, print the list, find the length of the list, search the list for a given item, insert an item in the list, delete an item from the list,and copy the list.

Question 24

The data type of each ____ depends on the specific application.

A) pointer
B) node
C) address
D) link

Question 25

Searching through a linked list or inserting an item in a linked list requires a ____ of the list.

A) review
B) deletion
C) copying
D) traversal

Question 26

In a linked list, we always want head to point to the ____ node.

A) key
B) main
C) first
D) last

Question 27

Building a linked list forward places the item to be added at the ____ of the linked list.

A) beginning
B) end
C) middle
D) key point

Question 28

Building a linked list backward places the item to be added at the ____ of the linked list.

A) beginning
B) end
C) middle
D) key point

Question 29

We need ____ pointers to build a linked list.

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

Question 30

Because initially the list is empty, the pointer first must be initialized to ____.

A) NULL
B) EMPTY
C) NIL
D) NOP

Question 31

____ is a basic operation of the linked list ADT.

A) Initializing the list
B) Comparing two lists
C) Sorting the list
D) Dividing the list

Question 32

____ lists have elements that are arranged according to some criteria.

A) Structured
B) Unstructured
C) Random
D) Sorted

Question 33

____ lists have elements that are in no particular order.

A) Search
B) Structured
C) Unsorted
D) Randomized

Question 34

An ____ is an object that produces each element of a container, such as a linked list, one element at a time.

A) initiator
B) iterator
C) interpreter
D) accessor

Question 35

In an ordered linked list, the search algorithm is somewhat improved because the list is ____.

A) larger
B) smaller
C) referenced
D) sorted

Question 36

A doubly linked list is a linked list in which every node has a next pointer and a ____ pointer.

A) back
B) center
C) null
D) binary

Question 37

In a doubly linked list, every node contains the address of the next node except for the ____ node.

A) middle
B) last
C) first
D) second to last

Question 38

A doubly linked list can be traversed in ____ direction.

A) only the forward
B) only the backward
C) a circular
D) either the forward or backward

Question 39

In a doubly linked list, some of the operations require modification from how they were implemented for a regular linked list, because of the ____ pointer(s) in each node.

A) binary
B) two
C) three
D) null

Question 40

A linked list is not a random access data structure such as a(n) ____.

A) stack
B) deque
C) structure
D) array

Question 41

In the STL container list, the function pop_front ____.

A) inserts element at the beginning of the list
B) inserts element at the end of the list
C) returns the first element
D) removes the first element from the list

Question 42

The header node is placed at the ____ of a list.

A) middle
B) end
C) beginning
D) key location

Question 43

Trailer nodes at the end of the list should contain a value ____.

A) smaller than the largest value in the data set
B) larger than the largest value in the data set
C) smaller than the smallest value in the data set
D) the same size as the smallest value in the data set

Question 44

A linked list in which the last node points to the first node is called a ____ linked list.

A) circular
B) recursive
C) standard
D) doubly