compsci midterm

What is a Stack?

A Stack is a Last-In, First-Out (LIFO) Abstract Data Type (ADT) that supports operations like push (add an element) and pop (remove the most recently added element).

What are ADT Bags?

An ADT Bag (or multiset) is a collection of items where the order of elements does not matter, and duplicate elements are allowed. It supports operations like adding an item, removing an item, and checking the number of occurrences of an item.

To expand the size of an array bag, the common practice is to:

Double the size of the array

When removing from an ArrayBag dealing with a gap the most common practice is to:

Replace entry being removed with the last entry in array and replace last entry with null

A new node is added at the:

Beginning of a list

A call to remove() Linkedbag will:

Remove the first node

Removing a node that is not first in a LinkedBag:

Replaces it with the first node

What big O notation represents exponential time

O(2^n)

What are Links (in data structures)?

In data structures, 'links' typically refer to references or pointers that connect nodes in a linked data structure (e.g., a linked list or tree). Each node contains data and one or more links to other nodes.

What is a Queue?

A Queue is a First-In, First-Out (FIFO) Abstract Data Type (ADT) that supports operations like enqueue (add an element to the rear) and dequeue (remove the element from the front).

What is the primary way elements are added and removed from a Stack?

Elements are added using the 'push' operation and removed using the 'pop' operation, both typically affecting the 'top' of the stack.

How does an ADT Bag handle duplicate elements compared to a Set?

An ADT Bag allows and keeps track of duplicate elements, whereas a Set only stores unique elements.

What is the role of a 'link' when implementing a singly linked list?

In a singly linked list, each node contains a 'link' (or pointer) that points to the next node in the sequence, forming a chain.

When an element is 'dequeued' from a Queue, from which end is it removed?

An element is always removed from the 'front' of the Queue.

Name one advantage of using a Deque over a traditional Queue or Stack.

A Deque offers greater flexibility as elements can be added or removed from both ends, accommodating scenarios where both LIFO and FIFO behavior might be needed.

How is the order of removal determined in a Priority Queue?

Elements are removed based on their assigned priority, typically with the highest (or lowest) priority element being removed first, regardless of its insertion order.

What are the two essential components every recursive method must have?

Every recursive method must have a 'base case' (a condition that stops the recursion) and a 'recursive step' (which calls the method itself with a modified input that moves closer to the base case).

What is the main benefit of using an Iterator to access elements in a collection?

Iterators provide a standardized way to traverse a collection without exposing its underlying internal structure, promoting encapsulation and allowing consistent traversal across different collection types.

What is a Stack?

A Stack is a Last-In, First-Out (LIFO) Abstract Data Type (ADT) that supports operations like push (add an element) and pop (remove the most recently added element).

What are ADT Bags?

An ADT Bag (or multiset) is a collection of items where the order of elements does not matter, and duplicate elements are allowed. It supports operations like adding an item, removing an item, and checking the number of occurrences of an item.

What are Links (in data structures)?

In data structures, 'links' typically refer to references or pointers that connect nodes in a linked data structure (e.g., a linked list or tree). Each node contains data and one or more links to other nodes.

What is a Queue?

A Queue is a First-In, First-Out (FIFO) Abstract Data Type (ADT) that supports operations like enqueue (add an element to the rear) and dequeue (remove the element from the front).

What is the primary way elements are added and removed from a Stack?

Elements are added using the 'push' operation and removed using the 'pop' operation, both typically affecting the 'top' of the stack.

How does an ADT Bag handle duplicate elements compared to a Set?

An ADT Bag allows and keeps track of duplicate elements, whereas a Set only stores unique elements.

What is the role of a 'link' when implementing a singly linked list?

In a singly linked list, each node contains a 'link' (or pointer) that points to the next node in the sequence, forming a chain.

When an element is 'dequeued' from a Queue, from which end is it removed?

An element is always removed from the 'front' of the Queue.

Name one advantage of using a Deque over a traditional Queue or Stack.

A Deque offers greater flexibility as elements can be added or removed from both ends, accommodating scenarios where both LIFO and FIFO behavior might be needed.

How is the order of removal determined in a Priority Queue?

Elements are removed based on their assigned priority, typically with the highest (or lowest) priority element being removed first, regardless of its insertion order.

What are the two essential components every recursive method must have?

Every recursive method must have a 'base case' (a condition that stops the recursion) and a 'recursive step' (which calls the method itself with a modified input that moves closer to the base case).

What is the main benefit of using an Iterator to access elements in a collection?

Iterators provide a standardized way to traverse a collection without exposing its underlying internal structure, promoting encapsulation and allowing consistent traversal across different collection types.

Imagine you are managing the "undo" functionality in a text editor. Which data structure would be most suitable to keep track of previous states for undo operations?

A Stack, because the last action performed is the first one to be undone (LIFO principle).

If you're counting the frequency of words in a document (e.g., "apple", "banana", "apple", "orange") and you want to store these words allowing duplicates, which ADT would you use?

An ADT Bag (or multiset), as it effectively stores all occurrences, allowing you to count them later.

In a linked list, if a node's 'link' reference is set to 'null', what does this typically signify?

It signifies that this node is the last node in the linked list, as it points to no subsequent node.

When printing multiple documents, they are usually processed in the order they were sent to the printer. Which data structure models this behavior?

A Queue, as it processes tasks on a First-In, First-Out (FIFO) basis.

Consider a web browser's history feature, where you can go 'back' or 'forward'. Which ADT could efficiently manage both recent pages (for 'back') and future pages (for 'forward') by adding/removing from both ends?

A Deque (Double-Ended Queue), as it allows adding and removing elements from both front (for 'forward') and rear (for 'back').

In a hospital emergency room, patients are often treated based on the severity of their condition, not necessarily their arrival time. Which data structure design principle does this situation exemplify?

A Priority Queue, where elements (patients) are removed and processed based on their priority (severity of condition).

When calculating the factorial of a number n (i.e., n! = n \times (n-1)!), the calculation for n! depends on the calculation for (n-1)!. This is an example of which programming concept?

Recursion, where a function calls itself to solve a smaller instance of the same problem until a base case (e.g., 0! = 1) is reached.

You have a list of students' names stored in an ArrayList and another list in a LinkedList. What mechanism allows you to process each student's name in both lists using the same loop structure, without knowing their underlying implementation?

An Iterator, which provides a standard way to traverse elements in any collection that implements the Iterable interface.

What is a Stack?

A Stack is a Last-In, First-Out (LIFO) Abstract Data Type (ADT) that supports operations like push (add an element) and pop (remove the most recently added element).

What are ADT Bags?

An ADT Bag (or multiset) is a collection of items where the order of elements does not matter, and duplicate elements are allowed. It supports operations like adding an item, removing an item, and checking the number of occurrences of an item.

What are Links (in data structures)?

In data structures, 'links' typically refer to references or pointers that connect nodes in a linked data structure (e.g., a linked list or tree). Each node contains data and one or more links to other nodes.

What is a Queue?

A Queue is a First-In, First-Out (FIFO) Abstract Data Type (ADT) that supports operations like enqueue (add an element to the rear) and dequeue (remove the element from the front).

What is the primary way elements are added and removed from a Stack?

Elements are added using the 'push' operation and removed using the 'pop' operation, both typically affecting the 'top' of the stack.

How does an ADT Bag handle duplicate elements compared to a Set?

An ADT Bag allows and keeps track of duplicate elements, whereas a Set only stores unique elements.

What is the role of a 'link' when implementing a singly linked list?

In a singly linked list, each node contains a 'link' (or pointer) that points to the next node in the sequence, forming a chain.

When an element is 'dequeued' from a Queue, from which end is it removed?

An element is always removed from the 'front' of the Queue.

Name one advantage of using a Deque over a traditional Queue or Stack.

A Deque offers greater flexibility as elements can be added or removed from both ends, accommodating scenarios where both LIFO and FIFO behavior might be needed.

How is the order of removal determined in a Priority Queue?

Elements are removed based on their assigned priority, typically with the highest (or lowest) priority element being removed first, regardless of its insertion order.

What are the two essential components every recursive method must have?

Every recursive method must have a 'base case' (a condition that stops the recursion) and a 'recursive step' (which calls the method itself with a modified input that moves closer to the base case).

What is the main benefit of using an Iterator to access elements in a collection?

Iterators provide a standardized way to traverse a collection without exposing its underlying internal structure, promoting encapsulation and allowing consistent traversal across different collection types.

Imagine you are managing the "undo" functionality in a text editor. Which data structure would be most suitable to keep track of previous states for undo operations?

A Stack, because the last action performed is the first one to be undone (LIFO principle).

If you're counting the frequency of words in a document (e.g., "apple", "banana", "apple", "orange") and you want to store these words allowing duplicates, which ADT would you use?

An ADT Bag (or multiset), as it effectively stores all occurrences, allowing you to count them later.

In a linked list, if a node's 'link' reference is set to 'null', what does this typically signify?

It signifies that this node is the last node in the linked list, as it points to no subsequent node.

When printing multiple documents, they are usually processed in the order they were sent to the printer. Which data structure models this behavior?

A Queue, as it processes tasks on a First-In, First-Out (FIFO) basis.

Consider a web browser's history feature, where you can go 'back' or 'forward'. Which ADT could efficiently manage both recent pages (for 'back') and future pages (for 'forward') by adding/removing from both ends?

A Deque (Double-Ended Queue), as it allows adding and removing elements from both front (for 'forward') and rear (for 'back').

In a hospital emergency room, patients are often treated based on the severity of their condition, not necessarily their arrival time. Which data structure design principle does this situation exemplify?

A Priority Queue, where elements (patients) are removed and processed based on their priority (severity of condition).

When calculating the factorial of a number n (i.e., n! = n \times (n-1)!), the calculation for n! depends on the calculation for (n-1)!. This is an example of which programming concept?

Recursion, where a function calls itself to solve a smaller instance of the same problem until a base case (e.g., 0! = 1) is reached.

You have a list of students' names stored in an ArrayList and another list in a LinkedList. What mechanism allows you to process each student's name in both lists using the same loop structure, without knowing their underlying implementation?

An Iterator, which provides a standard way to traverse elements in any collection that implements the Iterable interface.

What is UML?

UML stands for Unified Modeling Language, which is a standardized general-purpose modeling language in the field of software engineering. It is used to visualize, specify, construct, and document the artifacts of a software system.