Question 1

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

Accepted Answer

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

Question 2

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

Since we need to keep the list sorted, we cannot add the new element at a random position. Instead, we need to traverse the list in order to find the correct position for the new element. The worst case scenario is when we need to add the new element at the end of the list, which requires traversing the entire list. Therefore, the add operation has a big-Oh notation of O(n).

Question 3

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

Accepted Answer

The answer of Given the partial LinkedList class declaration below,...

Question 4

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

Accepted Answer

If the first node of the linked list is null, that means the list is empty and should return true. All other options check for properties of the first node or subsequent nodes, which could potentially be null or have null data even if the list is not completely empty.

Question 5

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 6

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

To print each element and the number of times it occurs, for each element, you would need to scan the entire list to count occurrences, resulting in O(n^2) complexity.

Question 7

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

Accepted Answer

We need to print the data of the first element, so we should access "first.data". Option A would print the reference to the first node object, not its data. Option C would print the reference to the second node object, which is not what we want. Option D is incorrect syntax, as "Node" is not a defined variable.

Question 8

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 would have to traverse the entire linked list to identify elements that occur exactly once, which would take O(n) time. Printing out these elements would also take O(n) time. Therefore, the overall time complexity would be O(n).

Question 9

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

To find common elements between two unsorted linked lists, you need to compare each element of the first list with each element of the second list, resulting in a time complexity of O(n^2).

Question 10

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

We can traverse both the linked lists simultaneously and compare each element. If the elements are same, we add it to the third list. This operation takes linear time, O(n), since we need to traverse both the linked lists once. Therefore, the overall time complexity of creating a third list with common elements is O(n).

Question 11

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

Option D is not correct since a doubly-linked list does not have a previous reference for the first node and hence updating the previous reference of the previous node will not be possible.

Question 12

What is a difference between a singly-linked list and a doubly-linked list?
A) A singly linked list node has a reference to the previous node.
B) A doubly linked list node has a reference to the previous node.
C) A singly linked list node has a reference to the next node.
D) A doubly linked list node has a reference to the next node.

Accepted Answer

In a doubly-linked list, each node contains references to both the previous and the next node, allowing traversal in both directions.

Question 13

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 with many nodes, we need to update two references: the reference of the header node and the previous reference of the second node in the list (if it exists). No other references need to be updated.

Question 14

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 of the last node to point to X and the previous reference of X to point back to the last node. We also need to update the list's last reference to point to X. Therefore, options I and III are required actions. Option II is not necessary in this case.

Question 15

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

By declaring the Node class as a static inner class, we prevent it from holding a reference to the outer class, which is not needed and can potentially use unnecessary memory. It also allows for easier creation and manipulation of nodes within the linked list.

Question 16

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.

Accepted Answer

Static inner classes do not have an implicit reference to an instance of the outer class, unlike non-static inner classes. This means they cannot directly access instance variables or methods of the outer class.

Question 17

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

Accepted Answer

The answer of Given the partial LinkedList and LinkedListIterator class...

Question 18

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 19

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 X 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 (i.e., update the next reference in the node before X to X's next node). We also need to update the previous reference in the node after X to point to the node before X (i.e., update the previous reference in the node after X to X's previous node). Therefore, options I and II are required. Updating the list's first reference is not necessary for removing a node from the middle of a doubly-linked list.

Question 20

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

Accepted Answer

The Node class is typically a private inner class within the LinkedList class, which allows it to encapsulate the details of the node structure and maintain encapsulation.

Quiz 16: Basic Data Structures

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 a linked list of length n in sorted order.What would be the big-Oh notation for the add operation?

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.

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.

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

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

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.

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

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 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 is a difference between a singly-linked list and a doubly-linked list?

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

What is never present in a static inner class?

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

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

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