Deck 4: Arrays and Linked Structures

Question 1

The first item in a singly linked structure is accessed using a head link.

Answer 1

True

Question 2

It's easier to get to an item's predecessor in a singly linked structure than in a doubly linked structure.

Answer 2

False

Question 3

A linked structure can be stored in noncontiguous memory.

Answer 3

True

Question 4

If the logical size of an array equals the physical size of the array, a new array must be created to add elements to the array.

Question 5

When an item is inserted into an array, the logical size of the array increases.

Question 6

In Python, a node in a doubly linked structure contains two fields: a data item and a reference to the next node.

Question 7

Time performance is improved if you double the size of the array when you need to increase its size.

Question 8

When an array object is traversed in a for loop, the object's __iter__ method is called.

Question 9

When an array is instantiated, it is filled with zeros by default.

Question 10

If an array's logical size is greater than zero, the index of the last item in the array is the logical size plus 1.

Question 11

When a list's append method results in memory wasted beyond a threshold, the size of the underlying array is decreased.

Question 12

The list is the primary implementing structure in Python collections.

Question 13

A ragged grid has a fixed number of columns and a variable number of rows.

Question 14

To start a traversal of a linked structure, initialize a variable to the structure's head pointer.

Question 15

Similar to an array, linked structures support random access.

Question 16

A linked structure can have items that have a maximum of one link to another item.

Question 17

In a doubly linked structure, the first and last item have an empty link.

Question 18

A traversal of a singly linked structure terminates when the temporary variable is equal to the head pointer.

Question 19

On a linked structure, index-based operations must be emulated by manipulating links within the structure.

Question 20

To access a two-dimensional array, you use two subscripts.

Question 21

In the Array class defined in Chapter 4, how do you instantiate an array object that can hold 10 values?

A) myArray(10) = Array
B) Array myArray, 10
C) myArray = Array(10)
D) Array(10) myArray

Question 22

What type of memory scheme does a linked list use?

A) overlapping
B) noncontiguous
C) sequential
D) random

Question 23

The insertion and removal of the first node of a singly linked structure require that the head pointer be reset.

Question 24

How does a programmer access the first item in a singly linked structure?

A) by using the 0 index
B) with the first() method
C) by following a head link
D) by a call to getLink(1)

Question 25

In the following code to insert an item in an array, what is the missing code? for x in range(logicalSize, targetIndex, -1):
MyArray[x] = myArray[x - 1]
A[targetIndex] = newItem
< missing code >

A) targetIndex += 1
B) targetIndex -= 1
C) logicalSize += 1
D) logicalSize -= 1

Question 26

What does the last item in a singly linked structure contain?

A) an empty link
B) a link to the first item
C) a link to the previous item
D) a method for appending an item

Question 27

The following code sums all the values in the two-dimensional array. What is the missing code?
Sum = 0
For row in range(grid.getHeight()):
For column in range(grid.getWidth()):
< missing code >

A) sum += grid[ column ][ row ]
B) sum += grid[ row-1 ][ column-1 ]
C) sum += grid[ column+1 ][ row+1 ]
D) sum += grid[ row ][ column ]

Question 28

What is the primary implementing structure of Python collections?

A) list
B) array
C) linked list
D) dictionary

Question 29

Older programming languages implement arrays as static data structures which are inefficient. What do modern languages use to remedy the problems of static arrays?

A) dynamic arrays
B) linked lists
C) data stacks
D) hash tables

Question 30

Inserting data at the beginning of a linked structure uses constant time and memory.

Question 31

The process for resizing an array named myArray is shown below. What is the missing code? if logicalSize == len(myArray):
Temp = Array(len(myArray) + 1)
For i in range(logicalSize):
< missing code >
A = temp

A) myArray[ temp ] = myArray[ i ]
B) temp [ i ] = myArray[ i ]
C) myArray[ i ] = temp[ i ]
D) temp = myArray(len(myArray))

Question 32

Which of the following is true about Python's array module?

A) it is limited to storing numbers
B) it behaves much like a dictionary
C) it can only hold character values
D) you can define its size at run time

Question 33

What process is required to avoid wasting memory if successive calls to the pop method on a list are made?

A) delete the array
B) grow the array
C) reset the array
D) shrink the array

Question 34

Which of the following best describes an array?

A) a collection of data points that represent an object
B) a list of values that are indexes to a database
C) a numeric value that points to a position in RAM where data can be found
D) a sequence of items that can be accessed at given index positions

Question 35

Which of the following is an advantage of a doubly linked structure over a singly linked structure?

A) it is less complex to implement
B) you can easily access the predecessor of an item
C) you can easily access the successor of an item
D) it uses less memory

Question 36

The run-time complexities of the operations on a doubly linked structure are typically double compared to the corresponding operations on the singly linked structure.

Question 37

A circular linked structure contains a link from the last node back to the first node in the structure.

Question 38

The operation of removing an item at the end of a linked structure is constant in time and memory.

Question 39

Which of the following statements accesses the second column in the third row of a two-dimensional array?

A) twoDim[ 2 ][ 1 ]
B) twoDim[ 4 ][ 3 ]
C) twoDim[ 1 ][ 2 ]
D) twoDim[ 2 ][ 3 ]

Question 40

What method does Python's list type use to increase the size of the underlying array?

A) size
B) append
C) increase
D) augment

Question 41

What type of operation is the following code performing? probe = head
While probe != None and targetItem != probe.data:
Probe = probe.next
If probe != None:
Probe.data = newItem
Return True
Else:
Return False

A) sum of all items
B) replacement
C) insertion
D) deletion

Question 42

What is the operation on a linked structure called that visits each node without deleting it?

A) probe
B) insertion
C) removal
D) traversal

Question 43

Which statement tests if a singly linked node variable named myItem has been initialized?

A) if myItem is Null:
B) if myItem != None:
C) if myItem = None:
D) if myItem is not Null:

Question 44

How does the class definition of a doubly linked structure differ from a singly linked structure?

A) by adding a previous pointer
B) by adding another head pointer
C) by adding an extra data field
D) by removing the tail pointer

Question 45

On average, what is the performance of a sequential search on a singly linked structure?

A) logarithmic
B) linear
C) exponential
D) random

Question 46

What are almost all operations on arrays based upon?

A) hashes
B) keys
C) links
D) indexes

Question 47

What action does the following code perform assuming the Node class defined in Chapter 4? ​ head = Node(newItem, head)

A) deletion of an item in a linked list
B) appending an item to the end of a linked list
C) replacing an item at the beginning of a linked list
D) insertion of an item at the beginning of a linked list

Question 48

The following code searches a linked structure. What is the missing code?
Probe = head
While probe != None and targetItem != probe.data:
< missing code >
If probe != None:
Print("Target item found!")
Else:
Print("Target item not found!")

A) probe.data = next.data
B) probe.next = targetItem.data
C) probe = probe.next
D) probe.head = probe.next

Question 49

What type of linked structure operation is the following code performing?
Z = 0
Probe = head
While probe != None:
Z = probe.data + z
Probe = probe.next

A) traversal
B) initialization
C) visit with removal
D) insertion

Question 50

Why are the insertion and removal of the first node special cases of the insert and remove i th node on singly linked structures?

A) the tail pointer must be reset
B) the first item must be deleted
C) the head pointer must be reset
D) the last item must be deleted