ECE 4050 Final Exam Review Flashcards
What is the ordering for stack ADT?
Last in is first out
What are the main functions used in stack ADT?
bool isEmpty()
bool push(itemType newItem)
bool pop()
itemType peek()
What are the main functions of list ADT?
bool isEmpty()
int length()
int itemCount()
bool insert(location, item)
bool remove(location)
itemType return(location)
bool replace(itemType)
How is ADT list different from other ADTs?
The user specifies WHERE the data goes
Working with location instead of the items/values themselves
What happens when you want to insert or remove an item in an array-based ADT list?
Insert: shift everything under that position downward by 1.
Remove: shift everything up after removal
T/F: We don’t use the 0 index for array-based ADT list implementation
True, we have a 0 index, but we start at 1
The maximum is then +1 compared to the defaultSize since we don’t use the zero from default size.
Compare the advantages/disadvantages of array-based ADT list and link-based ADT list
Arrays are great for search and storing - O(1).
Arrays are not good for insert/remove - worst insert/remove at beginning means O(n) because shift everything up or down. Best insert/remove at end, no shifting.
Linked list: worst O(n) search and store, need to travel across all the nodes.
Good for insertion, removal (changes in general) because no shifting.
Changing the value of an entry at a given position on the list would probably be the task of which of these methods?
push
get
insert
replace
Replace
Which list method has only 1 parameter?
isEmpty
setEntry
insert
remove
remove - just need location
isEmpty doesn’t take parameters
setEntry needs value and location
insert needs value and location
What should be returned by the list operation (aList.insert(2,x)).getEntry(2) ?
false
2
x
an exception is thrown
x
insert(2,x) means insert a value x at position 2
getEntry(2) means return the value at position 2, which is x.
getEntry is not a bool, so not false
2 is the location, not the value
What would be returned by the list operation (bList.insert(3,x)).remove(3)?
2
x
false
bList
There are two options: true (not given as an option), and bList. This is because we insert a value x at position 3 and then remove the value at position 3. This is possible, so remove is true, but it also means the list is unchanged.
T/F: In an array based implementation of a stack, the stack can grow and shrink dynamically.
False
We cannot change arrays dynamically
T/F: The ADT list can have an arbitrary length.
True - in an array, we get to set the length arbitrarily
In a linked implementation, the list can grow to any length
What is the range of entry numbers for which it is legal to insert a new entry in a list?
From 1 to k+1 where k is item count (k+1 since we should always be able to add to the end of the list)
use k instead of n since n is often the max
In either the link based or array based implementation of the ADT List, what is the single parameter for both the remove and getEntry methods?
position - lists work based on positions
What is the first step in the deletion process for a linked implementation of the ADT List?
return the node to the system
disconnect the node from the linked chain by changing pointers
locate the node you want to delete
the order of these steps don’t matter
Locate the node you want to delete
can’t delete things if you can’t find them
Which of the following is NOT part of the human cost of developing a computer program?
efficiency
readability
modifiability
maintainability
efficiency - it is solely dependent on the algorithm used and not the human
all other ones require a human to work on
Algorithm efficiency is a concern for
small problems only
large problems only
medium sized problems only
all sizes
large problems only
for small sized problems, the difference in efficiency is minimal
Which of these growth rates increases the fastest?
1
n
n^2
logn
n^2 is fastest
followed by n, logn, 1
Which of the following growth-rate functions indicates a problem whose time requirement is independent of the size of the problem?
1
n
n^2
logn
1 - an O(1) means it takes the same amount of time to complete any size, so it is independent of size
A linear function has the growth rate of
1
n
2^n
logn
n - if you don’t know this, you’re cooked
T/F: If Algorithm A requires time proportional to n, and Algorithm B requires time proportional to n^2, B’s time requirement increases at a slower rate than A’s time requirement
False: if Algorithm B is O(n^2), then it grows faster than Algorithm A’s O(n), so the time it requires increases at a faster rate than A
Each merge step of the mergesort requires __ major operations
3n-1
4n-1
(n-1)/2
n-1
3n-1
Which sorting algorithm
