Mid-Term Flashcards
What is an activation record?
An object that represents a method invocation
What is a doubly linked list?
A linked list in which each mode has references to both the next node and the previous node in the list.
What is a linked list?
A linked structure in which one object refers to the next, creating a linear ordering.
What is a linked structure?
A data structure that uses object reference variables to create links between objects.
What is a node?
A class that represents a single element in a linked structure.
What is a program stack?
A stack of activation records used to keep track of method invocations during program execution.
What is a sentinel node?
A node at the front or end of a linked list that serves as a marker and does not represent an element in the list.
How do object references help us define data structures?
An object reference can be used as a link from one object to another. A group of linked objects can form a data structure, such as a linked list, on which a collection can be based.
Compare and contrast a linked list and an array.
A linked list has no capacity limitations, whereas an array does. However, arrays provide direct access to elements using indexes, whereas a linked list must be traversed one element at a time to reach a particular point in the list.
What special case exists when managing linked lists?
The primary special case in linked-list processing occurs when dealing with the first element in the list. A special reference variable is maintained that specifies the first element in the list. If that element is deleted, or if a new element is added in front of it, the FRONT reference must be carefully maintained.
Why should a linked list node be separate from the element stored on the list?
It is unreasonable to assume that every object that we may want to put in a collection can be designed to cooperate with the collection implementation. Furthermore, the implementation details are supposed to be kept distinct from the user of the collection, including the elements that the user chooses to add to the collection.
What do the “LinkedStack<T>" and "ArrayStack<T>" classes have in common?</T></T>
These classes implement the “StackADT<T>" interface. This means that they both represent a stack collection, providing the necessary operations needed to us a stack. Although they both have distinct approaches to managing the collection, they are functionally interchangeable from the user's point of view.</T>
What would be the time complexity of the push operation if we chose to push at the end of the list instead of the front?
O(n)
What is the difference between a doubly linked list and a singly linked list?
A singly linked list maintains a reference to the first element in the list and then a “next” reference from each node to the following node in the list. A doubly linked list maintains two references: “front” and “rear”. Each node in the doubly linked list stores both a “next” and a “previous” reference.
What impact would the use of sentinel nodes or dummy nodes have on a doubly linked list implementation?
It would take two dummy records in a doubly linked list, one at the front and one at the rear, to eliminate the special cases when dealing with the first and last nodes.
What are the advantages of using a linked implementation as opposed to an array implementation?
A linked implementation allocates space only as it is needed and has a theoretical limit on the size of the hardware.
what are the advantages of using an array implementation as opposed to a linked implementation?
An array implementation uses less space per object since it only has to store the object and not an extra pointer. However, the array implementation will allocate much more space than it needs initially.
what are the advantages of the “java.util.Stack” implementation of a stack?
It’s implementation is an extension of the “Vector” class, it can keep track of the positions of elements in the stack using an index and thus does not require each node to store and additional pointer. This implementation also allocates space only as it is needed, like the linked list implementation.
What is the potential problem with the “java.util.Stack”?
It’s implementation is an extension of the “Vector” class and thus inherits a large number of operations that violate the basic assumption of a stack.
What is a Caesar cipher?
A simple message encoding technique in which letters are shifted along the alphabet by a constant amount.
What is a circular array?
An array that is treated as circular, meaning that incrementing the last index value in the array wraps around back to the first element.
What does a dequeue do?
Removes an element from the front of the queue.
What does an enqueue do?
Adds and element to the rear of the queue.
What if FIFO?
First In First Out, a description of a collection in which the first element added will be the first element removed.
What is a queue?
A linear collection whose elements are added on one end and removed from the other.
What is a repeating key?
A list of integer values used to shift letters by varying amounts in an improved version of a Caesar cipher.
what is the difference between a queue and a stack?
A queue is a FIFO collection, whereas a stack is a last in, first out (LIFO) collection.
What are the five basic operations on a queue?
enqueue - adds an element to the end of the queue
dequeue - removes an element from the front of the queue
first - returns a reference to the element at the front of the queue
isEmpty - returns true if the queue is empty, returns false otherwise
What are some of the other operations that might be implemented for a queue?
makeEmpty()
destroy()
full()
Is it possible for the “head” and “tail” references in a linked implementation to be equal?
Yes, it happens when the queue is empty (both “head” and “tail” are null) and when there is only one element on the queue.
Is it possible for the “front” and “rear” references in a circular array implementation to be equal?
Yes, it can happen under two circumstances: when the queue is empty and the when the queue is full.
Which implementation has the worst time complexity?
The noncircular array implementation with and O(n) “dequeue” or “enqueue” operation has the worst time complexity.
Which implementation has the worst space complexity?
Both of the array implementations waste space for unfilled elements in the array. The linked implementation uses more space per element stored.
What is an indexed list?
A list whose elements can be referenced using a numeric index.
What is the Josephus problem?
A classic computing problem whose goal is to find the order in which elements are selected from a list by taking every inth element cyclically until none remains.
What is an ordered list?
A list whose elements are ordered in terms of some inherent characteristic of the elements.
What is erialization?
A technique for representing an object as a stream of binary digits, which allows objects to be read and written from files with their state maintained.
What is an unordered list?
A list whose elements have no inherent order but are ordered by their placement in the list.
What is the difference between and index list, and ordered list, and an unordered list?
An indexed list is a collection of objects with no inherent order that are ordered by index value.
An ordered list is a collection of objects ordered by value.
An unordered list is a collection of objects with no inherent order
What are the basic methods for accessing and indexed list?
One of three ways:
Access a particular index position
Access the ends
Access and object in the list by value
what are the additional operations required of implementations that are part of the java Collections API framework?
All Java Collections API framework classes implement the “Collections” interface, the “Serializable” interface, and the “Cloneable” interface.
What are the trade-offs in space complexity between an ArrayList and a LinkedList?
The linked implementation requires more space per object to be inserted in the list simply because of the space allocated for the references. Keep in mind that the LinkedList class is actually a doubly linked list and thus requires twice as much space for references. the ArrayList class is more efficient at managing space because ArrayList collections are resizable and thus can dynamically allocate space as needed. Therefore there need not be a large amount of wasted space allocated all at once. Rather, the list can grow as needed.
What are the trade-offs in time complexity between and ArrayList and a LinkedList?
The major difference between the two is access to a particular index position of the list. The ArrayList implementation can access any element of the list in the same amount of time if the index value is known. the LInkedlist implementation requires the list to be traversed from one end or the other to reach a particular index position.
what is the time complexity of the “contains” operation and the “find” operation for both implementations?
The “contains” and “find” operations for both implementations are O(n) because they are simply linear searches.
Why is the time to increase the capacity of the array on an “add” operation considered negligible for the ArrayList implementation?
Averaged over the total number of insertions into the list, the time to enlarge the array has little effect on the total time.
What is a circular array implementation not as attractive as an implementation for a list as it was for a queue?
The circular array implementation of a queue improved the efficiency of the dequeue operation from O(n) to O(1) because it eliminated the need to shift elements in the array. That is not the case for a list because we can add or remove elements anywhere in the list, not just at the front or the rear.
What is a binary search?
A search that occurs on a sorted list and in which each comparison eliminates approximately half of the remaining viable candidates.
What is a bubble sort?
A sorting algorithm that sorts elements by repeatedly comparing adjacent values and swapping them.
What is a class method?
A method that is invoded through the calss name and that cannot refer to instance data. Also called a static method.
What is a generic method?
A method that includes the definition of a type parameter in the header of the method.
What is insertion sort?
A sorting algorithm that sorts elements by repetitively inserting a particular element into a previously sorted sublist.
What is a linear search?
A search that begins at one end of a list of items and continues linearly until the element is found or the end of the end of the list is reached.
What is a logarithmic algorithm?
An algorithm that has a time complexity of O(log2n), such as a binary search.
What is a logarithmic sort?
A sorting algorithm that requires approximately nlog2n comparisons to sort n elements.
What is merge sort?
A sorting algorithm that sorts elements by recursively dividing the list in half until each sublist has one element and then merges the sublists.
What is a partition in reference to sorting?
An element used by the quick sort algorithm to separate unsorted elements into two distinct partitions.
What is a partition element?
An element used by the quick sort algorithm to separate unsorted elements into two distinct partitions.
What is quick sort?
A sorting algorithm that sorts elements by partitioning the unsorted elements into two partitions and then recursively sorting each partition.
What is radix sort?
A sorting algorithm that sorts elements using a sort key instead of directly comparing elements.
What is searching?
the process of finding a designated target element within a group of elements or determining that the target is not in the group.
What is a search pool?
A group of items to be seardched.
What is selection sort?
A sorting algorithm that sorts elements by repetitively finding a particular element and putting git in its final position.
What is sequential sort?
A sorting algorithm that typically uses nested loops and requires approximately n^2 comparisons to sort n elements.
What is sorting?
the process of arranging a group of items into a particular order based on some criterion.
What is a static method?
A method that is invoked through the class name and that cannot refer to instance data. Also called a class method.
What is a target element?
the element that is being sought during a search oeprtaion.
What are viable candidates?
The elements in a search pool amoung which the target element may still be found.
When would a linear search be preferable to the logarithmic search?
A linear search would be preferable for relatively small, unsorted lists and in languages where recursion is not supported.
which searching method requires that the list be sorted?
Binary search
When would a sequential sort be preferable to a recursive sort?
A sequential sort would be preferable for relatively small data sets and in languages where recursion is not supported.
The insertion sort algorithm sorts using what technique?
The insertion sort algorithm sorts a list of values by repetitively insertinga particular value into a subset of the list that has already been sorted.
The bubble sort algorithm sorts using what technique?
The bubble sort algorithm sorts a list by repeatedly comparing adjacent elements in the list and swapping their positions if they are not already in order.
The selection sort algorithm sorts using what technique?
The selection sort algorithm, which is an O(n^2) sort algorithm, sorts a list of values by repetitively putting a particular value into its final sorted position.
The quick sort algorithm sorts using what technique?
The quick sort algorithm sorts a list by partitioning the list using an arbitrarily chosen partition element and then recursively sorting the sublists on either side of the partition element.
The merge sort algorithm sorts using what technique?
The merge sort algorithm sorts a list by recursively dividing the list in half until each sublist has one element and then recombining these sublists in order.
It woudlHow many queues would it take to use a radix sort to sort names stored as all lowercase?
It would require 27 queues, one for each of the 226 letters in the alphabet and one to store the whole list before, during, and after sorting.
What advantages can be gained by using “Comparator” objects instead of the natural ordering of objects?
The use of Comparator objects provides flexibility by providing multiple ways to sort a set of objects. Each “comparator” defines a unique set of criteria for the sort.
In regards to heaps, what is complete?
A balanced tree in which all of the leaves at level h (the lowest level of the tree) on the left side of the tree.
What is a heap?
A binary tree that is complete and is either a minheap or a maxheap.
What is a maxheap?
A binary tree with two added properties:
It is a complete tree and for each node, the node is greater than or equal to both the left child and the right child.
What is a minheap?
A binary tree with two added properties:
It is a complete tree and for each node, the node is less than or equal to both the left child and the right child.
What is a priority queue?
A collection that follows two ordering rules:
Items with higher priority go first, and items with the same priority are ordered in accordance with the first in first out principle.
