ECE 4050 Final Exam Review

Question 1

What is the ordering for stack ADT?

Answer 1

Last in is first out

Question 2

What are the main functions used in stack ADT?

Answer 2

bool isEmpty()
bool push(itemType newItem)
bool pop()
itemType peek()

Question 3

What are the main functions of list ADT?

Answer 3

bool isEmpty()
int length()
int itemCount()
bool insert(location, item)
bool remove(location)
itemType return(location)
bool replace(itemType)

Question 4

How is ADT list different from other ADTs?

Answer 4

The user specifies WHERE the data goes
Working with location instead of the items/values themselves

Question 5

What happens when you want to insert or remove an item in an array-based ADT list?

Answer 5

Insert: shift everything under that position downward by 1.
Remove: shift everything up after removal

Question 6

T/F: We don’t use the 0 index for array-based ADT list implementation

Answer 6

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.

Question 7

Compare the advantages/disadvantages of array-based ADT list and link-based ADT list

Answer 7

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.

Question 8

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

Answer 8

Replace

Question 9

Which list method has only 1 parameter?
isEmpty
setEntry
insert
remove

Answer 9

remove - just need location

isEmpty doesn’t take parameters
setEntry needs value and location
insert needs value and location

Question 10

What should be returned by the list operation (aList.insert(2,x)).getEntry(2) ?
false
2
x
an exception is thrown

Answer 10

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

Question 11

What would be returned by the list operation (bList.insert(3,x)).remove(3)?
2
x
false
bList

Answer 11

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.

Question 12

T/F: In an array based implementation of a stack, the stack can grow and shrink dynamically.

Answer 12

False
We cannot change arrays dynamically

Question 13

T/F: The ADT list can have an arbitrary length.

Answer 13

True - in an array, we get to set the length arbitrarily
In a linked implementation, the list can grow to any length

Question 14

What is the range of entry numbers for which it is legal to insert a new entry in a list?

Answer 14

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

Question 15

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?

Answer 15

position - lists work based on positions

Question 16

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

Answer 16

Locate the node you want to delete
can’t delete things if you can’t find them

Question 16

Which of the following is NOT part of the human cost of developing a computer program?

efficiency
readability
modifiability
maintainability

Answer 16

efficiency - it is solely dependent on the algorithm used and not the human
all other ones require a human to work on

Question 16

Algorithm efficiency is a concern for
small problems only
large problems only
medium sized problems only
all sizes

Answer 16

large problems only
for small sized problems, the difference in efficiency is minimal

Question 17

Which of these growth rates increases the fastest?
1
n
n^2
logn

Answer 17

n^2 is fastest
followed by n, logn, 1

Question 18

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

Answer 18

1 - an O(1) means it takes the same amount of time to complete any size, so it is independent of size

Question 19

A linear function has the growth rate of
1
n
2^n
logn

Answer 19

n - if you don’t know this, you’re cooked

Question 20

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

Answer 20

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

Question 21

Each merge step of the mergesort requires __ major operations
3n-1
4n-1
(n-1)/2
n-1

Answer 21

3n-1

Question 22

Which sorting algorithm