Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
28 Cards in this Set
- Front
- Back
|
The Big One of accessing a vector item by index (where the number of elements of a vector is n) is: |
O (1) |
|
|
In linked lists, what are the advantages of iterators over indexed based navigation |
Index is not defined on lists |
|
|
In a singly linked list, the big One of searching for an item |
O (n) |
|
|
Stacks can be implemented using |
Vectors and singly linked lists |
|
|
Evaluating arithmetic expressions |
Is a realistic application of stacks |
|
|
The big O of popping an item from a queue |
O (1) |
|
|
The advantage of using a circular array based queue over a regular array based queue is |
A circular array queue is more efficient |
|
|
Print jobs |
Is a real application of queues |
|
|
In the best case, the number of exchanges for selection sort is |
O (1) |
|
|
Worst case scenario for bubble sort comparison |
O(n^2) |
|
|
Which algorithm is best for sorting medium sized arrays? |
Shell Sort |
|
|
On average, which sorting algorithm has the least number of comparisons? |
Merge Sort |
|
|
Which of the following sorting algorithms is not a quadratic sorting algorithm? 1. Selection Sort 2. Bubble Sort 3. Merge Sort 4. Insertion Sort |
Merge Sort |
|
|
Which algorithm is particularly good for an array that is already sorted? |
Bubble Sort |
|
|
What's the big O to insert a node after a referenced node in a singly linked list? Before a referenced node? Remove a node after a referenced node? Remove a node before a referenced node? |
After: O (1) Before: O (n) After remove: O (1) Before remove: O (n) |
|
|
What's the big O to insert a node after a referenced node in a double linked list? Remove a node after a referenced node? Insert a node before a referenced node? Remove a node before a referenced node? |
All O (1) |
|
|
What are stacks based on? |
LIFO last in first out |
|
|
What are the arithmetic expressions? |
Infix a*b Postfix ab* Prefix *ab |
|
|
What are Queues based on? |
FIFO first in first out |
|
|
What is Recursion? |
A programming technique in which a method calls itself |
|
|
What is the performance of Selection Sort? |
Comparisons: worst = O (n^2) Best = O (n^2) Exchanges: Worst = O (n) Best = O (1) Space: O (1) |
|
|
What is the performance of Bubble Sort? |
Comparisons: Worst = O(n^2) Best = O(n) Exchanges: Worst = O(n^2) Best = O(1) Space: O(1) |
|
|
What are the three quadratic algorithms? |
Selection Sort Bubble Sort Insertion Sort |
|
|
What is the performance of Insertion Sort? |
Comparisons: Worst = O(n^2) Best = O(n) Shifts: Worst = O(n^2) Best = O(1) Space: O(1) |
|
|
What is the performance of Shell Sort? |
Average performance is O(n^3/2) or better Uses divide and conquer method |
|
|
What is the performance of Merge Sort?7 |
Time: O(nlogn) Space: O (n) |
|
|
What is the difference between a shallow copy and a deep copy? |
A shallow copy duplicates an element but does not copy the elements content. A deep copy duplicates the lement and also all of the content within that element. |
|
|
Quicksort Big O |
Best: O (nlogn) Worst: O(n^2) Space: O (logn) |
