Deck 9: Lists

Question 1

The items in a list are logically contiguous, but need not be physically contiguous in memory.

Answer 1

True

Question 2

Items in a list must be sorted to make sense.

Answer 2

False

Question 3

For a linked implementation of a list, a singly linked structure allows movement to the next node or the previous node.

Answer 3

False

Question 4

There are two broad categories of list operations discussed in most textbooks on data structures: index-based and content-based.

Question 5

A traversal with a list iterator begins by moving the cursor to the first position or to the last position.

Question 6

The object heap is an area of the disk drive from which the Python virtual machine allocates segments of various sizes for all new data objects.

Question 7

In the array implementation of a list, the index-based operation __getitem__ uses the subscript operator on the array variable.

Question 8

List positions are usually counted from 0 to the length of the list plus 1.

Question 9

Unlike a simple iterator, a list iterator supports movement to previous positions, directly to the first position, and directly to the last position.

Question 10

A disk's surface is divided into concentric tracks, and each track is further subdivided into sectors.

Question 11

The sentinel node points to the first data node and the last data node.

Question 12

The __init__ method of a doubly linked list creates a node with no data.

Question 13

Linked implementations of lists use physical positions in an array to represent logical order.

Question 14

A list is a concrete data structure with a specific and unvarying implementation based on a single block of physical memory.

Question 15

Because a list is ordered linearly, you can refer unambiguously to an item in a list via its relative position from the head of the list.

Question 16

The list method remove(item) is an example of a content-based operation.

Question 17

The head of a list is at index 1 and the tail is at index n which is the length of the list.

Question 18

Initially, when a list iterator is opened on a non-empty list, the cursor's position is immediately after the first item in the list.

Question 19

The basic building block of a doubly linked structure is a node with two pointers: head, which points left; and tail, which points right.

Question 20

A list supports manipulation of items at only the head and tail within a linear collection.

Question 21

A Lisp list is a recursive data structure.

Question 22

How does position-based operations allow the programmer to navigate through a list?

A) by incrementing the head pointer
B) by decrementing the tail pointer
C) by moving the cursor
D) by changing the backing store

Question 23

What is the typical argument to a content-based list operation?

A) an index
B) an item
C) a list instance
D) an array

Question 24

What is each numeric position in a list called?

A) index
B) pointer
C) tail
D) vector

Question 25

What are the values of a list index at the head and tail of the list, respectively?

A) 0, n-1
B) 1, n
C) 0, n
D) n-1, 1

Question 26

Recursive list processing became one of the building blocks of a movement in software development called abstract programming.

Question 27

Where is the cursor positioned when a list iterator is opened on a non-empty list?

A) at the position of the length of the list minus 1
B) immediately after the first item
C) it is undefined
D) immediately before the first item

Question 28

Which of the following is NOT an example of a list?

A) a recipe
B) a jar of marbles
C) words on a document
D) a file on a disk

Question 29

The index-based function get returns the i th element of a given list.

Question 30

If a list contains the items x y z and the cursor is currently undefined, what happens when hasNext() is executed?

A) a value of True is returned
B) a value of False is returned
C) a value of False is returned and the cursor is positioned before the first item
D) a value of True is returned and the cursor is positioned after the last item

Question 31

Why can you refer to an item in a list via its relative position from the head of the list using an index?

A) because it has a circular structure
B) because it uses round-robin
C) because it is ordered linearly
D) because it's arranged in a hierarchy

Question 32

How do a list iterator and a for loop differ?

A) a list iterator allows movement directly to the last position
B) a for loop allows movement directly to the first position
C) a for loop allows movement to previous positions
D) a list iterator only allows sequential movement through the list

Question 33

Which of the following list operations is a mutator that works at the currently established position in the list iterator?

A) previous
B) first
C) remove
D) hasPrevious

Question 34

With respect to memory, what happens when an object is no longer needed?

A) the garbage collector returns the object's space to the free list
B) the disk block is marked as unused
C) the size of the array holding the object is reduced by 1
D) the data block is marked as deleted and is unavailable to other objects

Question 35

A list iterator is an object attached to a list that provides positional operations on that list.

Question 36

Which of the following is an area of memory from which the Python virtual machine allocates segments of various sizes for all new data objects.

A) call stack
B) virtual memory
C) object heap
D) memory partition

Question 37

Which of the following is NOT one of the three broad categories of list operations discussed in Chapter 9?

A) index-based
B) content-based
C) position-based
D) hash-based

Question 38

What is true about how lists are indexed?

A) indices increase in both movement directions
B) indices decrease to the left and increase to the right
C) indices decrease in both movement directions
D) indices decrease to the right and increase to the left

Question 39

Which of the following is true about lists?

A) items must be sorted
B) items must be physically contiguous
C) the order of items is unimportant
D) items are logically contiguous

Question 40

In the implementation of the lister iterator on a doubly linked list, the method hasNext returns False if the cursor is less than the backing store's length.

Question 41

Which of the following is NOT a type of precondition when implementing a list iterator?

A) the next operation cannot be run if hasNext returns False
B) consecutive mutator methods are required
C) a next operation must be run before each mutation
D) mutations cannot be run on the list itself

Question 42

Which of the following is NOT true about a file system's directory?

A) it occupies the first few tracks on the disk
B) it contains an entry for each file
C) each file entry holds the address of the sector containing file data
D) the directory is organized as a linear structure

Question 43

When the first method is run on the list iterator, what happens?

A) the cursor is reset to 0
B) the list is cleared
C) the cursor is set to -1
D) the list is instantiated

Question 44

In what type of programming did recursive list processing become an important building block?

A) procedural programming
B) object-oriented programming
C) sequential programming
D) functional programming

Question 45

In the following code for the __iter__ method in the ArrayList class, what is the missing code? def __iter__(self):
Cursor = 0
While cursor < len(self):
Yield self.items[cursor]
< missing code >

A) self.items[ cursor ] = self.item[ cursor-1 ]
B) cursor += 1
C) cursor -= 1
D) self.items[ cursor+1 ] = self.item[ cursor ]

Question 46

In the __init__ method for the ArrayListIterator class, what is the missing code? def __init__(self, backingStore):
Self.backingStore = backingStore
Self.modCount = backingStore.getModCount()
< missing code >

A) self.first()
B) self.last()
C) self.next()
D) self.previous()

Question 47

What is the missing code in the contains method for a Lisp-like list? def contains(item, lyst):
If isEmpty(lyst):
Return False
Elif item == first(lyst):
< missing code >
Else:
Return contains(item, rest(lyst))

A) return True
B) return contains(item-1)
C) return False
D) return first(lyst)

Question 48

What is the extra node needed to easily manipulate a doubly linked structure?

A) mid
B) next
C) tail
D) sentinel

Question 49

What does the rest function do on a Lisp-like list?

A) returns the list cursor to the head position
B) returns all the data items in the list
C) returns a list of items after the first one
D) returns the list cursor to its previous position

Question 50

Which structure is the ideal one to support a list iterator?

A) array
B) circular array
C) doubly linked
D) singly linked