Deck 16: Basic Data Structures

Question 1

Assume that the linked list implementation includes a reference to the last node as well as to the first node.Which of the following statements about the efficiency of the linked list is correct?
A.Adding an element to the middle of the linked list at the current position of the iterator is O(n).
B.Removing an element other than the last element from the linked list at the current position of the iterator is O(n).
C.Accessing an element in the linked list using an iterator is O(n).
D.Adding an element to the end of the linked list is O(1).

Answer 1

Adding an element to the end of the linked list is O(1).

Question 2

Insert the missing code in the following code fragment.This fragment is intended to remove a node from the head of a linked list:

Answer 2

A

Question 3

When using the textbook's implementation of a singly linked list to remove an element in the middle of the list, why it is necessary to check whether the previous reference equals the position reference?
A.If previous equals position, the action does not follow a call to next.
B.If previous equals position and an attempt is made to remove the node, the iterator would have to start at the beginning of the list to rebuild the links.
C.If previous equals position, the iterator is at the beginning of the list and does not point to a valid node.
D.If previous equals position, the iterator is at the end of the list and does not point to a valid node.

Answer 3

If previous equals position, the action does not follow a call to next.

Question 4

What type of access does the use of an iterator with a LinkedList provide for its elements?
A.Sequential
B.Semi-random
C.Random
D.Sorted

Question 5

In the textbook implementation, the LinkedListIterator class is a private inner class of the LinkedList class.Which of the following statements regarding this implementation is NOT correct?
A.The methods of the LinkedList class can access the public features of the LinkedListIterator class.
B.The methods of the LinkedListIterator class can access the public features of the LinkedList class.
C.The methods of the LinkedListIterator class can be directly accessed by other classes.
D.Clients of the LinkedListClass do not know the name of the LinkedListIterator class.

Question 6

Which of the following statements about a linked list iterator is NOT correct?
A.The iterator is at the end of the list if the linked list's first node reference is null.
B.The iterator is at the end of the list if the position.next reference is null.
C.The iterator is at the end of the list if the position reference is null.
D.The list is empty if the linked list's first node reference is null.

Question 7

Assume that the linked list implementation includes a reference to the last node as well as to the first node.Which of the following statements about the efficiency of a singly linked list is NOT correct?
A.Adding an element to the middle of a linked list using an iterator is O(1).
B.Removing the last element from a linked list using an iterator is O(1).
C.Accessing an element in a linked list using an iterator is O(n).
D.Adding an element to the end of a linked list is O(1).

Question 8

The linked list iterator described in the textbook maintains a reference to the last visited node, called position, and a reference to the last node before that, called previous.Which of the following statements is NOT correct regarding advancing this iterator?
A.If another node exists, when the iterator is to be advanced, the position reference must be updated to position.next.
B.If the iterator currently points before the first element of the list, when the iterator is to be advanced, position must be set to point to the first node in the linked list.
C.If another node exists, when the iterator is to be advanced, the previous reference must be updated to point to the current location of the iterator
D.If the iterator currently points before the first element of the list, when the iterator is to be advanced, the position reference must be set to position.next and the previous reference must be set to point to the first node in the linked list.

Question 9

Using the textbook's implementation of a linked list, which of the following statements about changing the data stored in a previously visited element is correct?
A.The node that will be updated is the most recently visited node.
B.The position.next reference must be updated when the data is updated.
C.The set method can be called again immediately after calling the add method.
D.The previous reference must be updated when the node is updated.

Question 10

Which of the following operations is least efficient in a LinkedList?
A.Adding an element in a position that has already been located
B.Linear traversal step
C.Removing an element when the element's position has already been located
D.Random access of an element

Question 11

What is included in a linked list node?
I a reference to the next node
II an array reference
III a data element
A.I
B.II
C.II and III
D.I and III

Question 12

Which Java package contains the LinkedList class?
A.java.lang
B.java.util
C.java.collections
D.java.io

Question 13

Consider the following code snippet: What does this code print?
A.xyzjkldef
B.defxyzjkl
C.xyzdefjkl
D.defjklxyz

Question 14

Adding or removing an element at an arbitrary iterator position in a singly linked list of length n takes ____ time.
A.O(n)
B.O(log n)
C.O(1)
D.O(n2)

Question 15

In the textbook implementation, the Node class is a private inner class of the LinkedList class.Which of the following statements regarding this implementation is NOT correct?
A.The methods of the LinkedList class can access the public features of the Node class.
B.The methods of the Node class can access the public features of the LinkedList class.
C.The methods of the Node class can be directly accessed by other classes.
D.The Node class's instance variables that represent the node element and its next node reference are declared as public.

Question 16

Using the textbook's implementation of a singly linked list and linked list iterator, the following steps are required to remove a node from the middle of a linked list.Place these steps into the order in which they should be performed.
I The preceding node's next reference must be updated to skip the removed node.
II The iterator's position reference must be set to the previous reference.
III The previous reference must be checked to see if it is equal to the position reference.
A.III, I, II
B.I, III, II
C.II, I, III
D.III, II, I

Question 17

If we want a create a doubly-linked list data structure so that we can move from a node to the next node as well as to a previous node, we need to add a previous reference to the Node class.Each such DNode (doubly-linked Node) will have a data portion and two DNode references, next and previous.How many references need to be updated when we remove a node from the middle of such a list? Consider the neighboring nodes.
A.1
B.2
C.3
D.4

Question 18

Which of the following algorithms would be efficiently executed on a LinkedList?
A.Tracking paths in a maze
B.Binary search
C.Remove first n / 2 elements from a list of n elements
D.Read n / 2 elements in random order from a list of n elements

Question 19

Which of the following statements about removing a node from a linked list is correct?
A.A node's data is discarded when it is removed from the linked list, and its memory space is immediately reclaimed.
B.A node's data is returned to the program when the node is removed from the linked list, and its memory space is immediately reclaimed.
C.A node's data is discarded when it is removed from the linked list, and its memory space is reclaimed later by the garbage collector.
D.A node's data is returned to the program when the node is removed from the linked list, and its memory space is reclaimed later by the garbage collector.

Question 20

Insert the missing code in the following code fragment.This fragment is intended to add a new node to the head of a linked list:

Question 21

Suppose we maintain a linked list of length n in random element order.What would be the big-Oh notation for printing out those elements which occur exactly once in the list (without sorting the list)?
A.O(1)
B.O(n)
C.O(n log n)
D.O(n2)

Question 22

Suppose we maintain a linked list of length n in sorted order.What would be the big-Oh notation for the add operation?
A.O(1)
B.O(n)
C.O(n log n)
D.O(n2)

Question 23

Given the partial LinkedList class declaration below, select a statement to complete the size method, which is designed to return the number of list elements.
A.temp = temp.next;
B.temp = first.next;
C.first = temp.next;
D.first = first.next

Question 24

Given the partial LinkedList class declaration below, select an expression to complete the empty method, which is designed to return true if the list contains no elements.
A.first != null
B.first == null
C.first.data == null
D.first.next == null

Question 25

In a linked list data structure, when does the reference to the first node need to be updated?
I inserting into an empty list
II deleting from a list with one node
III deleting an inner node
A.I
B.II
C.I and II
D.III

Question 26

Suppose we maintain a linked list of length n in random element order.What would be the big-Oh notation for an algorithm that prints each list element and the number of times it occurs in the list (without sorting the list)?
A.O(1)
B.O(n)
C.O(n log n)
D.O(n2)

Question 27

Given the partial LinkedList class declaration below, select a statement to complete the printFirst method, which is designed to display the contents of the first list element.
A.System.out.println(first);
B.System.out.println(first.data);
C.System.out.println(first.next);
D.System.out.println(Node.data);

Question 28

Suppose we maintain a linked list of length n in sorted order.What would be the big-Oh notation for printing out those elements that occur exactly once in the list?
A.O(1)
B.O(n)
C.O(n log n)
D.O(n2)

Question 29

Suppose we maintain two linked lists of length n in random element order.What would be the big-Oh notation for the creating a third list that includes only elements common to both lists, without sorting the first two lists?
A.O(1)
B.O(n)
C.O(n log n)
D.O(n2)

Question 30

Suppose we maintain two linked lists of length n in sorted order.What would be the big-Oh notation for the creating a third list, which included only elements common to both lists?
A.O(1)
B.O(n)
C.O(n log n)
D.O(n2)

Question 31

A doubly-linked list requires that each node maintain two references, one to the next node and one to the previous node.Which of the following statements about a doubly-linked list is NOT correct?
A.If a node's next reference is null, it is at the end of the list.
B.To remove a node in the middle of the list, the previous node's next reference must be updated.
C.To add a node in the middle of the list, you must update the next reference of the node after which the new node will be added.
D.To remove a node in the middle of the list, the previous node's previous reference must be updated.

Question 32

What is a

Question 33

If we want a create a doubly-linked list data structure so that we can move from a node to the next node as well as to a previous node we need to add a previous reference to the Node class.Each such DNode (doubly-linked Node) will have a data portion and two DNode references, next and previous.How many references need to be updated when we remove a node from the beginning of a list with many nodes? Consider the first reference and neighboring node(s).
A.1
B.2
C.3
D.4

Question 34

Which of the following actions must be taken to add a node X at the end of a doubly-linked list?
I Update the next reference in the node before the position where X will be placed
II Update the previous reference in the node before the position where X will be placed
III Update the list's last reference
A.I
B.II
C.I and II
D.I and III

Question 35

Using the textbook's implementation of a linked list, what is the purpose of declaring the Node class to be a static inner class?
A.To create an outer-class reference.
B.To create a this reference to itself.
C.To prevent storage of an outer-class reference that is not needed.
D.To create an outer-class reference that is needed.

Question 36

What is never present in a static inner class?
A.an outer-class reference.
B.the this reference to itself.
C.static properties.
D.static methods.

Question 37

Given the partial LinkedList and LinkedListIterator class declarations below, select an expression to complete the get(index) method of the LinkedList class, which returns the element at the position indicated by index.You can assume that the method is only called when the index is less than the size of the linked list.
A.it.next()
B.it.previous
C.it.position
D.it.next().data

Question 38

Using the textbook's implementation of a linked list, why is the LinkedListIterator inner class NOT declared as an inner static class?
A.Because the LinkedList class must have access to the instance variables of the LinkedListIterator class.
B.Because the Node class must have access to the instance variables of the LinkedListIterator class.
C.Because the LinkedListIterator class must have access to Node class instance variables.
D.Because the LinkedListIterator class must have access to LinkedList class instance variables.

Question 39

Which of the following actions must be taken to remove a node X from the middle of a doubly-linked list?
I Update the next reference in the node before X
II Update the previous reference in the node after X
III Update the list's first reference
A.I
B.II
C.I and II
D.II and III

Question 40

Which of the following statements are true about the Node class?
I The instance variables are private
II It holds a reference first to the first node
III It is a private inner class of the LinkedList class
A.I
B.II
C.III
D.All of the above

Question 41

Given the partial ArrayList class declaration below, select an expression to complete the empty method, which is designed to return true if the list contains no elements.
A.elements.length == 0
B.elements.currentSize == 0
C.elements[0] == null
D.currentSize == 0

Question 42

Which of the following is true about the efficiency of inserting an element into an array list?
A.It always has O(n) efficiency
B.When the insertion happens before the last element, it is O(1)
C.When the insertion happens on the last element, it is O(n)
D.When the insertion happens after the last element, it is O(1)

Question 43

If the current size of an array list is less than the length of the buffer, adding an element at the end of an array list takes ____ time.
A.O(n)
B.O(1)
C.O(log(n))
D.O(n2)

Question 44

In the textbook implementation of the LinkedListIterator class, when updating the position, what happens if the iterator tries to point before the first element of the list?
A.The position is set to position.next
B.The position is set to null
C.The position is set to first
D.The position is set to previous

Question 45

On average, how many elements of an array list of size n need to be moved when an element is added?
A.n
B.n2
C.2n
D.n / 2

Question 46

What feature of the ArrayList class makes it much better for a binary search than the LinkedList class?
A.indexing
B.has no link references
C.it is a generic class
D.it is an abstract class

Question 47

Array lists and linked lists both have the same ____.
A.add/remove efficiency
B.concrete implementations
C.random element access efficiency
D.linear traversal step efficiency

Question 48

Which of the following statements about array list and doubly-linked list operations is correct?
A.It is more efficient to add an element in the middle of an array list than a doubly-linked list.
B.It is more efficient to add an element to the beginning of an array list than a doubly-linked list.
C.It is more efficient to remove an element in the middle of an array list than a doubly-linked list.
D.It is more efficient to retrieve an element in the middle of an array list than a doubly-linked list.

Question 49

Linked list operations that were studied included adding/removing an element at the end or in the middle, and retrieving the kth element.If the iterator is currently pointing to the correct location for insertion or removal, which of the following statements about these doubly-linked list operations is correct?
A.The least expensive operation of a doubly-linked list is to iterate over the list.
B.The least expensive operation of a doubly-linked list is to retrieve an arbitrary element.
C.The least expensive operation of a doubly-linked list is to add an element in the middle.
D.All of these operations have the same time cost.

Question 50

Adding or removing an arbitrary element in the middle of an array list takes ____ time.
A.O(n)
B.O(1)
C.O(log(n))
D.O(n2)

Question 51

When the buffer for an array list must be grown, a single reallocation operation takes ____ time.
A.O(n)
B.O(1)
C.O(log(n))
D.O(n2)

Question 52

Given the partial ArrayList class declaration below, select an expression to complete the contains method, which is designed to return true if the element is contained within the list.
A.i < currentSize
B.i <= currentSize
C.i < elements.length
D.i <= elements.length

Question 53

Reading or writing an array list element at an arbitrary index takes ____ time.
A.O(log (n))
B.O(n)
C.O(n2)
D.O(1)

Question 54

An array list maintains a reference to an array of elements called a ____.
A.buffer
B.tree map
C.hash table
D.bucket

Question 55

Linked list operations that were studied included adding/removing an element at the end or in the middle, and retrieving the kth element.If the iterator is currently pointing to the correct location for insertion or removal, which of the following statements about these doubly-linked list operations is correct?
A.The most expensive operation of a doubly-linked list is to add an element at the end.
B.The most expensive operation of a doubly-linked list is to remove an element at the end.
C.The most expensive operation of a doubly-linked list is to add an element in the middle.
D.The most expensive operation of a doubly-linked list is to retrieve an arbitrary element.

Question 56

Using the textbook's implementation of a linked list, which of the following statements about adding a node to the middle of a linked list is correct?
A.The new node will be added before the last visited node.
B.The position.next reference will be updated to point to the new node.
C.The remove method can be called immediately before or after adding the new node.
D.The previous reference must be updated when adding the new node.

Question 57

Suppose we maintain an array A of n int values as follows:
A[0] < A[1] < ...< A[i] > A[i + 1] > A[i + 2] > ...> A[n - 1]
The ith element is the maximum in the array.What would be the lowest big-Oh notation for finding that element? Consider a variation of the binary search.
A.O(1)
B.O(log n)
C.O(n)
D.O(n2)

Question 58

When considering the reallocation operation for a list whose buffer is full, on average it will take ____ time.
A.O(n)
B.O(1)
C.O(1)+
D.O(n2)

Question 59

An iterator is currently pointing to the correct location for insertion or removal of a doubly-linked list.Which of the following statements about doubly-linked list operations is correct?
A.The most expensive operation of a doubly-linked is to add an element at the end.
B.The most expensive operation of a doubly-linked is to remove an element at the end.
C.The most expensive operation of a doubly-linked is to add an element in the middle.
D.The most expensive operation of a doubly-linked is to add an element at the front.

Question 60

Using the textbook's implementation of a linked list, which of the following statements about managing nodes within a linked list using an iterator is correct?
A.The node that will be removed is the node pointed to by the position.next reference.
B.The set method can be called immediately after adding a new node using the add method.
C.The set method can be called immediately after removing an existing node using the remove method.
D.The position reference must be updated when a new node is added.

Question 61

In the separate chaining technique for handling collisions in a hash table, ____.
A.colliding elements are stored in a nested hash table.
B.colliding elements are placed in empty locations in the hash table.
C.colliding elements are stored in linked lists associated with the hash code.
D.the hash code is compressed to obtain unique hash codes.

Question 62

In the open addressing technique for handling collisions in a hash table, ____.
A.colliding elements are stored in a nested hash table.
B.colliding elements are placed in empty locations in the hash table.
C.colliding elements are stored in linked lists associated with the hash code.
D.the hash code is compressed to obtain unique hash codes.

Question 63

Complete the following code, which is intended to add an element to the top of a stack implemented as a linked list.

Question 64

Given the LinkedListQueue class implementation discussed in section 16.3 (partially shown below), select the appropriate statements to complete the add method.

Question 65

Given the LinkedListStack class implementation discussed in section 16.3 (partially shown below), select the statement(s) to complete the peek method.

Question 66

When implementing a queue as a singly-linked list, which of these statements is correct?
A.For better efficiency, nodes should be added at the back and removed at the front.
B.For better efficiency, nodes should be added at the front and removed at the back.
C.There is no

Question 67

Given the HashSet class implementation discussed in section 16.4 (partially shown below), select the statement needed to complete the clear method, which is designed to remove all elements from the set.
A.buckets[j] = 0;
B.buckets[j] = new Node();
C.buckets[j] = null;
D.buckets[j] = new LinkedList();

Question 68

Assume that you have a hash table in which there are few or no collisions.What is the time required to locate an element in this hash table?
A.O(log n)
B.O(n)
C.O(n2)
D.O(1)

Question 69

Which operations from the array list data structure could be used in the implementation of the push and pop operations of a stack data structure?
I addLast
II addFirst
III removeFirst
A.I and III
B.I and II
C.II and III
D.None of the above

Question 70

Complete the following code snippet, which is intended to compress a hash code for an element x to become a valid array index:
A.position = arrayLength % h;
B.position = arrayLength / h;
C.position = h / arrayLength;
D.position = h % arrayLength;

Question 71

Which of the following operations from the array list data structure could be used in the implementation of the push and pop operations of a stack data structure?
I addLast
II addFirst
III removeLast
A.I
B.II
C.I and III
D.II and III

Question 72

Which of the following statements about hash tables is correct?
A.The hash code is used to determine where to store each element.
B.Elements in the hash table are sorted in hash code order.
C.A hash table allows duplicate elements.
D.No two elements of a hash table can have the same hash code.

Question 73

Elements in a hash table are said to ____ when they have the same hash code value.
A.be equivalent
B.compress
C.collide
D.buffer well

Question 74

A hash function is considered good if it ____.
A.does not require compression.
B.detects duplicate elements.
C.results in low integer values.
D.minimizes collisions.

Question 75

You have implemented a queue as a singly-linked list, adding elements at the end and removing elements at the front.What is the cost of the add operation?
A.O(log n)
B.O(n)
C.O(n2)
D.O(1)

Question 76

A stack can be implemented as a sequence of nodes in a linked list or an array list.Which of the following statements about this is correct?
A.If implementing the stack as a linked list, it is more expensive to add and remove elements at the end than at the beginning.
B.If implementing the stack as an array list, it is more expensive to add and remove elements at the end than at the beginning.
C.If implementing the stack as an array list, there is no cost

Question 77

How do you symbolize amortized big-Oh time?
A.O()
B.O()+
C.O()*
D.O()"

Question 78

Given the ArrayStack class implementation discussed in section 16.3 (partially shown below), select the statements needed to complete the push method.

Question 79

A stack can be implemented as a sequence of nodes in a linked list or an array list.Which of the following statements about this is correct?
A.If implementing the stack as a linked list, the least expensive approach is to add and remove elements at the end.
B.If implementing the stack as an array list, the least expensive approach is to add and remove elements at the end.
C.If implementing the stack as an array list, there is no cost

Question 80

You have implemented a queue as a singly-linked list, adding elements at the end and removing elements at the front.What is the cost of the remove operation?
A.O(log(n))
B.O(n)
C.O(n2)
D.O(1)