Question 1

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.

Accepted Answer

To remove a node in the middle of the list, the previous node's previous reference does not need to be updated. It is only necessary to update the previous node's next reference to point to the node following the one being removed.

Question 2

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

Accepted Answer

The use of an iterator with a LinkedList provides sequential access to its elements. This means that the iterator allows us to loop through the elements in the same order in which they were added to the list. It is not possible to access elements randomly or in a sorted order using the iterator alone.

Question 3

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

Accepted Answer

The answer of Suppose we maintain a linked list of...

Question 4

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

Accepted Answer

The reference to the first node needs to be updated in scenarios I and II. In scenario I, when inserting into an empty list, the first node reference needs to be updated to the newly inserted node. In scenario II, when deleting from a list with one node, the first node reference needs to be updated to null as there are no nodes left in the list. However, in scenario III where an inner node is being deleted, the first node reference does not need to be updated as only the reference of the previous node needs to be updated to the next node.

Question 5

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

Accepted Answer

A LinkedList would be inefficient for algorithms that require random access like binary search or reading elements in random order. However, it is efficient for removing elements from the front of the list, as the nodes only need to be rearranged, and no copying of values is required. Therefore, removing the first n/2 elements from a LinkedList is an efficient algorithm to execute. Tracking paths in a maze may require the use of a graph data structure to efficiently represent the maze and search for paths, which is outside the scope of a LinkedList.

Question 6

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.

Accepted Answer

The LinkedListIterator class needs to access the instance variables of the LinkedList class, such as the head of the list, to iterate through the list. Making it a non-static inner class allows it direct access to the LinkedList's instance variables. Static inner classes, on the other hand, do not have access to the instance variables of the outer class.

Question 7

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

Accepted Answer

The answer of Adding or removing an element at an...

Question 8

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

Accepted Answer

The answer of Suppose we maintain a linked list of...

Question 9

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

Accepted Answer

To create a third list with only common elements, we need to traverse both linked lists once. Since both lists are sorted, we can start from the head of both lists and compare the elements. If the elements are the same, we add them to the third list and move both pointers to the next element. If they are not the same, we move the pointer of the list with the smaller element to the next element. This process takes O(n) time, as we need to compare all n elements in the worst case. Therefore, the big-Oh notation for creating the third list is O(n).

Question 10

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

Accepted Answer

To add a node X at the end of a doubly-linked list, we need to update the next reference in the last node of the list (which will become the second last node after the addition of X) to point to X and update the previous reference of X to point to the second last node. Additionally, we need to update the list's last reference to point to X. Therefore, options I and III are correct. We do not need to update the previous reference in the node before the position where X will be placed because the last node in the list already has a reference to its previous node.

Question 11

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

Accepted Answer

When we remove a node from the beginning of a doubly-linked list, we need to update the next reference of the previous node (if there is one) to point to the new first node, as well as the previous reference of the new first node to point to the previous node (which would be null in this case). Therefore, we need to update a total of two references.

Question 12

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

Accepted Answer

When we remove a node from the middle of a doubly-linked list, we need to update the next reference of the previous node to point to the next node, and the previous reference of the next node to point to the previous node. So, two references need to be updated.

Question 13

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

Accepted Answer

The answer of Suppose we maintain two linked lists of...

Question 14

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

Accepted Answer

Random access of an element in a LinkedList is least efficient, as it requires traversing the list from the beginning until the desired element is reached. LinkedLists do not have direct access to elements like arrays do, so accessing a specific element requires iterating through the list.

Question 15

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

Accepted Answer

To remove a node from the middle of a doubly-linked list, we need to update the next reference in the node before X to point to the node after X (which becomes X's next node after it is removed). We also need to update the previous reference in the node after X to point to the node before X (which becomes X's previous node after it is removed). Therefore, both actions I and II must be taken to remove node X correctly. We do not need to update the list's first reference, so option III is not necessary.

Question 16

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.

Accepted Answer

Declaring the Node class to be a static inner class prevents the storage of an outer-class reference that is not needed. This helps to save memory and improve performance.

Question 17

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

Accepted Answer

The answer of Which of the following actions must be...

Question 18

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

Accepted Answer

We need to traverse the entire list to check for elements occurring exactly once, so the time complexity would be O(n).

Question 19

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

Accepted Answer

To add a node X into the middle of a doubly-linked list, we need to update both the next and previous references appropriately.

I. We need to update the next reference in the node before the position where X will be placed to point to X. This is because X will become the next node of the previous node.

II. We also need to update the previous reference in the node after the position where X will be placed to point to X. This is because X will become the previous node of the next node.

III. We don't need to update the list's first reference since we are only adding a node in the middle of the list and not at the beginning.

Therefore, the correct choice is C, as we need to take both actions I and II.

Question 20

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

Accepted Answer

In order to maintain the linked list in sorted order, we need to find the appropriate position where the new element needs to be added. This requires traversing the linked list from the beginning until we find the correct position, which takes O(n) time. Therefore, the big-Oh notation for the add operation is O(n).

Quiz 16: Basic Data Structures

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?

What type of access does the use of an iterator with a LinkedList provide for its elements?

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

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

Which of the following algorithms would be efficiently executed on a LinkedList?

Using the textbook's implementation of a linked list, why is the LinkedListIterator inner class NOT declared as an inner static class?

Adding or removing an element at an arbitrary iterator position in a singly linked list of length n takes ____ time.

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

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?

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?

Which of the following operations is least efficient in a LinkedList?

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

Using the textbook's implementation of a linked list, what is the purpose of declaring the Node class to be a static inner class?

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?

Suppose we maintain a linked list of length n in sorted order. What would be the big-Oh notation for the add operation?