CSCI 1302 Computer Science Exam Quiz!

The given answer states that the recursive method should still handle the base case of an empty list, even though the scientists never ask for the size of an empty list. This is because an empty list is a valid case and should be accounted for in the recursive method. Additionally, the answer suggests that the recursive method can be modified to use a list of size 1 as the base case, which implies that the method can be optimized by considering a smaller input size as the base case. Both of these statements are correct.

The correct answer is to assign the successor reference in the node with index k to the successor reference in the node with index k-1. This means that the node at index k will be removed from the linked list by bypassing it and directly connecting the previous node to the next node. This effectively removes the node from the linked list without any gaps or breaks in the sequence.

A traversal is a systematic method that starts at the beginning of the list and processes every node. It involves moving through the list, visiting each node in a specific order, such as from left to right or from top to bottom. This process allows for the examination or manipulation of data stored in each node of the list. Therefore, a traversal is the correct term to describe this systematic method.

The correct answer is "uses sequential search to locate the element". This is because the sequential search algorithm iterates through each element in the ArrayList one by one until it finds a match with the given element. This is an efficient implementation as it does not require any specific order or sorting of the elements in the list. If the element is not found, the search will continue until the end of the list and then return a result indicating that the element was not found.

The stack method "peek" returns an element from the stack without removing it. This means that when the "peek" method is called, it will allow us to access the top element of the stack without actually removing it from the stack. This can be useful when we want to check the value of the top element without modifying the stack's contents.

In a linked list, the objects that form the units of memory allocation are called nodes. Each node contains data and a reference (or link) to the next node in the list. These nodes are connected in a sequential manner, allowing for efficient insertion and deletion operations. Therefore, the correct answer is nodes.

The correct answer is "return first == null;". In a linked list implementation, the reference "first" points to the first node of the list. If the list is empty, the "first" reference will be null. Therefore, the statement "return first == null;" checks if the list is empty by comparing the "first" reference to null. If it is null, it means the list is empty and the method will return true. Otherwise, it will return false.

A list is a collection that assigns an index to each of its elements. This means that each element in the list can be accessed using its corresponding index value. The list maintains the order of the elements based on their indices, allowing for efficient retrieval and manipulation of data. This characteristic distinguishes a list from other types of collections, such as dictionaries or sets, which may associate keys with elements or have no specific order. The JList class mentioned in the options is a specific implementation of a list in the Java programming language.

The capacity of an array-based list such as ArrayList refers to the size of its internal array. This means that the capacity determines the maximum number of elements that the list can hold. It is important to note that the capacity is not necessarily the same as the number of elements currently stored in the list. The capacity can be greater than the number of elements, allowing for potential future additions to the list without the need for resizing the internal array.

A list can be considered a recursive data structure because if you remove the head of the list, what remains is also a list. This is because a list is made up of nodes, where each node contains a value and a reference to the next node in the list. When the head node is removed, the reference of the second node becomes the new head, and the rest of the nodes are still connected in the same way, forming a new list. This recursive nature allows for operations like traversing the list or performing recursive algorithms on it.

A collection that is accessed in first in first out fashion is called a queue. In a queue, the element that is inserted first is the first one to be removed. This data structure follows the principle of "First-In-First-Out" (FIFO), similar to waiting in a queue for a service. Elements are added at the end of the queue and removed from the front, maintaining the order in which they were added. This makes a queue suitable for scenarios where the order of insertion and removal is important, such as processing tasks in the order they were received.

The statement is false because the head of a linked list is not a linked list itself. The head of a linked list is a reference to the first node of the linked list. It contains the address of the first node and does not possess the properties or methods of a linked list.

A node in a binary tree cannot have two parents because by definition, a binary tree is a tree data structure in which each node has at most two children. Each node can have a maximum of one parent, except for the root node which has no parent. Therefore, the statement that a node in a binary tree can have two parents is incorrect.

An array-based list such as ArrayList uses contiguous allocation to allocate storage for its elements. This means that the elements are stored in adjacent memory locations, allowing for efficient access and retrieval of elements using their indices. Contiguous allocation also ensures that the elements are stored in a continuous block of memory, which can improve cache performance and reduce memory fragmentation.

The correct answer is "ref = new node(e, ref.next)". This statement creates a new node with the element "e" and sets its next reference to the node that was originally referenced by "ref.next". By assigning this new node to "ref", we update the reference to point to the newly created node, effectively adding the element "e" just after the node referenced by "ref".

In a complete binary tree, all levels except the last level must be completely filled, and the last level must be filled from left to right. Therefore, it is not necessary for the subtrees of a node in a complete binary tree to be equal in height. Some nodes may have subtrees of different heights depending on the structure of the tree.

The size of an array-based list such as ArrayList refers to the number of elements that are currently stored in the list. This means that it represents the actual number of items that have been added to the list and are accessible. It does not refer to the length of the internal array or the number of bytes of memory that the list can hold.

In a doubly-linked list, each node has references to both its previous and next nodes. The last item in a doubly-linked list does not have a successor because there is no node after it. Therefore, the statement that the last item in a doubly-linked list can sometimes have a successor is false.

When using an array to implement a stack, the push method does not wrap around to the beginning of the stack when it reaches the end. Instead, it throws an error or returns a stack overflow message indicating that the stack is full. To implement a stack that wraps around to the beginning, a circular array or a linked list can be used.

A binary tree is a type of tree data structure in which each item can have at most two successors, known as left child and right child. This means that each item in a binary tree can have either zero, one, or two successors. Therefore, the correct answer is "has at most two successors".

The int indexOf(Object o) method of the List interface searches a list for the occurrence of an object and returns its index. This means that it checks each element in the list to see if it matches the given object, and if it finds a match, it returns the index of that element. If the object is not found in the list, it returns -1.

When the stack method push is called on an empty stack, it does not call the stack empty, throw an EmptyStackException, or add its argument to the stack. Instead, it simply adds the argument to the stack.

The constructor for an array-based list should throw an IllegalArgumentException if its parameter is zero or negative. This is because an IllegalArgumentException is typically thrown when a method or constructor receives an invalid argument. In this case, a zero or negative capacity for the internal array is considered invalid as it would not be able to store any elements.

A list can be considered a recursive data structure because if you remove the head of the list, what remains is also a list. This means that the structure of the list can be defined in terms of smaller versions of itself, leading to a recursive definition. Each element in the list can be seen as a node that contains a value and a reference to the rest of the list, which is another list. This recursive structure allows for operations such as traversing the list or performing recursive algorithms on it.

An ArrayList is implemented as a class that uses an internal array to hold the elements of the list. This means that the ArrayList class internally manages an array to store the elements and provides methods to add, remove, and access elements in a flexible manner. The use of an internal array allows for dynamic resizing of the ArrayList as elements are added or removed, making it a convenient data structure for storing and manipulating collections of objects.

The correct answer is "no changes to the node class are necessary" because recursion can be implemented on linked lists without modifying the node class. Recursion relies on the recursive function calling itself on a smaller or simpler version of the problem. In the case of linked lists, the recursive function can be implemented in a separate function that takes the current node as a parameter and calls itself on the next node. This can be done without modifying the node class itself.

AVL tree is a kind of binary search tree that is self-balancing. It ensures that the heights of the left and right subtrees of any node differ by at most 1, which helps in maintaining a balanced tree structure. This self-balancing property allows for efficient operations such as insertion, deletion, and searching in logarithmic time complexity. Unlike other options mentioned, an AVL tree is specifically designed to maintain balance, making it a specialized type of binary search tree.

When a new element is added to an ArrayList at index k, the existing elements from index k to the end of the list (positions k..s-1) need to be moved toward the end of the array to make space for the new element. The elements at positions 0..k-1 do not need to be moved. Therefore, the correct answer is "the elements at current positions k..s-1 must be moved toward the end of the array".

A typical circular doubly linked list node has a field to store the element and two references to keep track of the successor and predecessor nodes. These references allow for easy traversal in both directions, making it possible to navigate the list forwards and backwards. By having these two references, the node can maintain a circular structure, where the last node points to the first node and the first node points to the last node, creating a loop.