Questions Chapter 5

Question 1

Which of the following is NOT true? A reference to a class object:

a. can be used to access public methods in the object
b. has a size dependant on class.
c. has the data type of the class
d. does not hold the object itself.

Answer 1

b. has a size dependant on its class.

Question 2

Access to the links in a linked list is usually through the _______ link.

Answer 2

first

Question 3

When you create a reference to a link in a linked list, it:

a. must refer to the first link
b. must refer to the link pointed to by current
c. must refer to the link pointed to by next.
d. can refer to any link you want

Answer 3

d. can refer to any link you want.

Question 4

How many references must you change to insert a link in the middle of a singly linked list?

Answer 4

2.

Question 5

How many references must you change to insert a link at the end of a singly linked list?

Answer 5

1

Question 6

In the insertFirst( ) method in the LinkList.java program (Listing 5.1), the statement newLink.next = first; means that:

a. the next new link to be inserted will refer to first
b. first will refer to the new link
c. the “next” field fo the new link will refer to the old first link
d. newLink.next will refer to the new first link in the list

Answer 6

c. the “next” field of the new link will refer to the old first link.

Question 7

Assuming current points to the next-to-last link in a singly linked list, what statement will delete the last link from the list?

Answer 7

current.next = null;

Question 8

When all references to a link are changed to refer to something else, what happens to the link?

Answer 8

garbage collection

Question 9

A double-ended list:

a. can be accessed from either end
b. is a different name for a doubly linked list
c. has pointers running both forward and backward between links
d. has its first link connected to its last link

Answer 9

a. can be accessed from either end.

Question 10

A special case often occurs for insertion and deletion routines when a list is ________.

Answer 10

empty

Question 11

Assuming a copy takes longer than a comparison, is it faster to delete an item with a certain key from a linked list or from an unsorted array?

Answer 11

linked list

Question 12

How many times would you need to traverse a singly linked list to delete the item with the largest key?

Answer 12

1

Question 13

Of the lists: simple linked list, double-ended list, sorted list, doubly linked list, which one would be best for implementing a queue?

Answer 13

double-ended

Question 14

Which of the following is NOT true? Iterators would be useful if you wanted to:

a. do an insertion sort on a linked list
b. insert a new link at the beginning of a list
c. swap two links at arbitrary locations
d. delete all links with a certain key value

Answer 14

b. insert a new link at the beginning of a list

Question 15

Which do you think would be a better choice to implement a stack: a singly linked list or an array?

Answer 15

the list. The both do push( ) and pop ( ) in O(1) time, but the list uses memory more efficiently .

Question 16

Deleting an item at the beginning of a list involves setting first to point to ____________.

Answer 16

first.next

Question 17

To traverse a linked list, you start at _________ and then go from link to link, using each link’s ________ field.

Answer 17

start at first, use each link’s next field.

Question 18

A double-ended list maintains a reference to the ________ _________ in the list, as well as the _________ _________.

Answer 18

maintains reference to the last link and first link.

Question 19

A _________ list allows insertion at the end of the list.

Answer 19

double-ended list

Question 20

A(n) _________ is a data storage class considered without reference to its implementation.

Answer 20

ADT

Question 21

Insertion in a sorted list takes ________ time. Deletion of the smallest link takes _______ time.

Answer 21

Insertion: O(N). Deletion O(1).

Question 22

In a __________ list, each link contains a reference to the previous link as well as the next link.

Answer 22

doubly-linked list.

Question 23

A ________ list permits backward traversal and deletion from the end of the list

Answer 23

doubly-linked list.

Question 24

A(n) ________ is a reference, encapsulated in a class object, that refers to a link in an associated list.

Answer 24

iterator

Question 25

Iterator methods allow the user to move the iterator along the list and acces the _______ currently referred to.

Answer 25

link