MIDTERM Flashcards
What should the vocabulary of pseudocode be?
Problem Domain
What is another word for list?
Collection
What kind of list is an array?
Linear List
What kind of data structure is Last In, First Out?
Stacks
What end of a stack do removals happen?
Head
What end of a stack do additions happen?
Head
What is it called when a stack is full?
an Overflow State
What operations does a stack have?
- Push
- Pop
- Peek
- isFull
What is a linked list?
A collection of nodes
What does a node consist of?
Data and pointer(s)
How many pointers are held in a node for a stack?
One: Pointer to next
What is it called when moving from one node to another by following a next reference?
Link Hopping, or Pointer Hopping
What is the first node in a list called?
Head
What is the last node in a list called?
Tail
What direction can a singly linked list be traversed?
From head to tail
What is the difference between a singly linked list and a doubly linked list?
Pointer to previous
What end of a queue do additions happen?
Tail
What end of a queue do removals happen?
Head
What kind of data structure is First in, First out?
Queue
What operations does a queue have?
- Clear
- Enqueue
- Dequeue
- Peek
- isEmpty
How is a priority queue different from a queue?
Removals based on priority, not first in first out
How must priority be stored for a priority queue?
Key Value
What are some operations that are different for a priority queue?
insert_with_priority
pull_highest_priority
Which algorithm only sorts the array if necessary?
Insertion sort
On which pass will an insertion sort algorithm consider the whole array?
Last pass
Which algorithm places the largest element in it’s position after the first pass?
Bubble Sort
Which algorithm finds the smallest element and places it in it’s final position on each pass?
Selection Sort
How is information for a function call stored in memory?
Dynamically on the runtime stack
What information is saved about a function?
Variables, parameter values, and return address
What is the function call information called in memory?
Activation Record or Stack Frame
How long does an activation record exist in memory?
As long as the function owning it is executing
Which activation record outlives every other one?
main()
What is the name of the last recursive call?
The Anchor
What is the purpose of the anchor?
Ensures we don’t fall into an infinite loop
What are the 3 types of recursion?
- Linear
- Binary
- Multiple
Which two algorithms use the divide and conquer approach?
Merge and QuickSort
Which algorithm uses a pivot?
QuickSort
How many subsets does QuickSort use?
3
What is the acronym for the subsets of a QuickSort?
L.E.G.
Less than
Equal to
Greater than
How is the type of data specified for a generic function or class?
A Parameter
What are the two types of templates?
- Function
- Class
What is the format for a template function definition?
template < typename T > returnType function_name(parameter list)
What is it called when the compiler creates a specific version of a generic function?
Specialization or Generated Function or Instantiating a function
What is the format for a generic class declaration?
template < typename T > class className {}
How do you instantiate an instance of a generic class?
className< dataType > obj;
