Deck 16: Basic Data Structures

Question 1

Insert the missing code in the following code fragment. This fragment is intended to remove a node from the head of a linked list:
Public class LinkedList
{
) . .
Public Object removeFirst()
{
If (first == null) { ________________ }
Object element = first.data;
First = first.next; 1
Return element;
}
) . .
}

A) throw new NoSuchElementException();
B) throw new IllegalStateException();
C) throw new NullPointerException();
D) throw new IllegalArgumentException();

Answer 1

A

Question 2

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.

Answer 2

C

Question 3

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:
Public class LinkedList
{
) . .
Public void addFirst(Object element)
{
Node newNode = new Node(); 1
NewNode.data = element;
_________ 2
_________ 3
}
) . .
}

A) first = newNode;
NewNode.next = first;
B) newNode.next = first;
First = newNode;
C) first = newNode.next;
NewNode.next = first;
D) first = newNode.next;
NewNode = first;

Answer 3

B

Question 4

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 5

Consider the following code snippet:
LinkedList words = new LinkedList();
Words.addFirst("xyz");
Words.addLast("jkl");
Words.addLast("def");
System.out.print(words.removeFirst());
System.out.print(words.removeLast());
System.out.print(words.removeLast());
What does this code print?

A) xyzjkldef
B) defxyzjkl
C) xyzdefjkl
D) defjklxyz

Question 6

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).

Question 7

Insert the missing code in the following code fragment. This fragment is intended to remove a node from the head of a linked list:
Public class LinkedList
{
) . .
Public Object removeFirst()
{
If (first == null) { throw new NoSuchElementException(); }
Object element = first.data;
________________
________________
}
) . .
}

A) first = first.next; 1
Return element;
B) first.next = first; 1
Return element;
C) first = element.next; 1
Return element;
D) first = element.next; 1
Return null;

Question 8

Consider the following code snippet:
LinkedList words = new LinkedList();
Words.addFirst("123");
Words.addLast("456");
Words.addFirst("789");
System.out.print(words.removeLast());
System.out.print(words.removeFirst());
System.out.print(words.removeLast());
What does this code print?

A) 123456789
B) 789123456
C) 123789456
D) 456789123

Question 9

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 10

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.

Question 11

Which Java package contains the LinkedList class?

A) java.lang
B) java.util
C) java.collections
D) java.io

Question 12

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 13

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 14

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 15

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 16

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 17

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 18

Which of the following statements about a linked list and its iterator is NOT correct?

A) The list is empty 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 beginning of the list if the previous reference is null.
D) The iterator is at the first node of the list if its position reference is null.

Question 19

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 20

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 21

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 22

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 23

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(n²)

Question 24

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 25

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 26

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 27

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(n²)

Question 28

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(nlog₂n)
D) O(n²)

Question 29

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(n²)

Question 30

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 31

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 32

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 33

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(n²)

Question 34

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 35

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 36

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 37

Which of the following actions must be taken to add a node X at the beginning 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 after the position where X will be placed
III Update the list's first reference

A) I
B) II
C) I and II
D) II and III

Question 38

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(n²)

Question 39

Which of the following actions must be taken to add a node X into the middle 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 after the position where X will be placed
III Update the list's first reference

A) I
B) II
C) I and II
D) II and III

Question 40

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(n²)

Question 41

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(n²)

Question 42

Array list operations that were studied included adding/removing an element at the end or in the middle, and retrieving the kth element. Which of the following statements about these array list operations is correct?

A) The least expensive operation of an array list is to add an element at the end.
B) The least expensive operation of an array list is to remove an element at the end.
C) The least expensive operation of an array list is to add an element in the middle.
D) The least expensive operation of an array list is to retrieve an arbitrary element.

Question 43

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 44

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
B) II
C) I and II
D) II and III

Question 45

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 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

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 48

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 49

Complete the following code, which is intended to add an element to the top of a stack implemented as a linked list.
Node newNode = new Node();
NewNode.data = element;
_________________
_________________

A) first = newNode;
NewNode.next = first;
B) newNode.next = first;
First = newNode;
C) newNode.previous = first;
First.next = newNode;
D) first = newNode;
NewNode.previous = first;

Question 50

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(n²)

Question 51

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(n²)

Question 52

On average, how many elements of an array list of size n need to be moved when an element is removed?

A) n
B) n²
C) 2n
D) n / 2

Question 53

An array list maintains a reference to an array of elements called a ____.

A) buffer
B) tree map
C) hash table
D) bucket

Question 54

On average, how many elements of an array list of size n need to be moved when an element is added?

A) n
B) n²
C) 2n
D) n / 2

Question 55

Reading or writing an array list element at an arbitrary index takes ____ time.

A) O(log (n))
B) O(n)
C) O(n²)
D) O(1)

Question 56

Array list operations that were studied included adding/removing an element at the end or in the middle, and retrieving the kth element. Which of the following statements about these array list operations is correct?

A) The most expensive operation of an array list is to add an element at the end.
B) The most expensive operation of an array list is to remove an element at the end.
C) The most expensive operation of an array list is to add an element in the middle.
D) The most expensive operation of an array list is to retrieve an arbitrary element.

Question 57

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(n²)

Question 58

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 59

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 add an element at the end.
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 60

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(n²)

Question 61

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 difference whether adding and removing elements at the beginning or the end.
D) If implementing the stack as a linked list, there is no cost difference whether adding and removing elements at the beginning or the end.

Question 62

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 difference in efficiency whether nodes are added at the front and removed at the back, or added at the back and removed at the front.
D) You cannot effectively implement a queue as a singly-linked list.

Question 63

Assume that you have a hash table in which there are few or no collisions. What is the time required to add a new element to this hash table?

A) O(log(n))
B) O(n)
C) O(n²)
D) O(1)

Question 64

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 65

Consider the following code snippet, which computes h, the array index for storing x in a hash table.
Int h = x.hashCode();
If (h < 0) { h = -h; }
H = h % size;
What does size correspond to?

A) The size of the hash table.
B) The number of elements to be stored.
C) The number of collisions.
D) The index of an empty hash table slot.

Question 66

Assume that you have a hash table in which there are few or no collisions. What is the time required to remove an element from this hash table?

A) O(n)
B) O(n²)
C) O(1)
D) O(log (n))

Question 67

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 difference whether adding and removing elements at the beginning or the end.
D) If implementing the stack as a linked list, there is no cost difference whether adding and removing elements at the beginning or the end.

Question 68

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 69

Complete the following code snippet, which is intended to compress a hash code to become a valid array index:
Int h = x.hashCode();
If (h < 0) { h = -h; }
_______________

A) position = arrayLength % h;
B) position = arrayLength / h;
C) position = h / arrayLength;
D) position = h % arrayLength;

Question 70

Why is it not typical to use the hashCode method result directly as an index for array storage?
I because the hashcode method returns a double
II the values are potentially very large
III the values are not type int

A) I
B) I and II
C) I and III
D) II

Question 71

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(n²)
D) O(1)

Question 72

Which of the following statements about hash tables is NOT correct?

A) Each entry in a hash table points to a sequence of nodes whose elements have the same compressed hash code.
B) Elements with the same hash code are stored as nodes in a bucket associated with that hash code.
C) A compressed hash code is used as an array index into the hash table.
D) All elements of a hash table must be searched sequentially to determine if an element already exists.

Question 73

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(n²)
D) O(1)

Question 74

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 75

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 76

Which of the following statements about adding an element to a hash table is NOT correct?

A) Add the new element at the beginning of the node sequence in the bucket referenced by the hash code.
B) Check the elements in the bucket to determine if the new element already exists.
C) If the element matches another element in the bucket referenced by the hash code, add the new element to that bucket.
D) To add an element, its compressed hash code must be computed.

Question 77

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(n²)
D) O(1)

Question 78

Complete the following code snippet, which is intended to compress a hash code to become a valid array index:
_____________________
If (h < 0) { h = -h; }
Position = h % arrayLength;

A) double h = x.hashCode();
B) double h = x.getHashCode();
C) int h = x.hashCode();
D) int h = x.getHashCode();

Question 79

What technique is used to store elements that hash to the same location?

A) colliding
B) bucketing
C) deletion
D) sharing

Question 80

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.