Section #1 ARRAY BASED BAG ADT
java – 该题目是一个常规的java的练习题目代写, 是比较有代表性的java等代写方向
Assume the following ArrBag objects of type T where type T is actually String type and assume those ArrBags contain the following elements respectively.
This ArrBag class is the one you wrote for your project.
ArrBag A –> [bravo][delta][alpha][golf][india][hotel][echo] // elements not in sorted order
ArrBag B –> [foxtrot][baker][xray][zebra][charlie][victor] // elements not in sorted order
You are to assume that size() is O(1). It just returns the count You are to assume the elements on the backing array are not necessarily sorted. Assume that .size() .get() .contains() .add() methods are correctly written.
Look at this union method for the ArrBag class:
#1 Is the union code above completely correct? i.e. does it produce the correct union of these 2 sets with no dupes introduced into the result set?
A YES, it correctly produces the union of those 2 sets with no dupes B It works on these two sets but if either set had dupes, it could put a dupe into the result C NO, it misses the last element of both sets D YES but inefficient. Should add all elements from both then remove dupes from result
#2 What is the big Oh runtime of the above union code?
A O(1) B O(log2N) C O(Nlog2N) D O(NN)
E O(2 to the N) F O(N!)
Look at this intersection method for the ArrBag class:
#3 Is the intersection code as written completely correct? i.e. does it produce the correct intersection of these 2 sets with no dupes introduced into the result set?
A YES, it correctly produces the intersection of those 2 sets with no dupes B It works on these two sets but if either set had dupes, it could put a dupe into the result C NO, it makes the wrong if test. Should be: && !other.contains( this.get(i) ) D YES but inefficient. Should add all elements from both then remove dupes from result
#4 What is the big Oh runtime of the above intersection code?
A O(1) B O(log2N) C O(Nlog2N) D O(NN) E O(2 to the N)
Look at this difference method for the ArrBag class:
#5 Is the difference code above completely correct? i.e. does it produce the correct difference of these 2 sets with no dupes introduced into the result set?
A YES, it correctly produces the difference of those 2 sets with no dupes B It works on these two sets but if either set had dupes, it could put a dupe into the result C NO, it misses the last element or both sets D YES but inefficient. Should add all elements from both then remove dupes from result
#6 What is the big Oh runtime of the above difference code?
A O(1) B O(log2N) C O(Nlog2N) D O(NN) E O(2 to the N) F O(N!)
Section #2 ONE WAY LINKED LIST ADT
Assume the following LinkedList objects of type T where type T is actually String type and assume those Linked Lists contain the following elements respectively.
This LinkedList class is the one you wrote for your project.
LinkedList A –> bravo -> delta -> alpha -> india -> hotel -> echo // again elements not in sorted order
LinkedList B –> foxtrot -> baker -> xray -> zebra -> Charlie -> victor // not in sorted order
You are to assume that size() is O(1). It just returns the count You are to assume the elements in the list are not necessarily ordered. Assume that .size() .get() .contains() .add() methods are correctly written.
Look at this search method for the LinkedList class:
Assume incoming key is NOT null
#7 Is the search code above completely correct? i.e. does it always return the reference to the node containing the specified key (or null if not found) in all cases?
A YES, it correctly returns the reference the node continuing key (or null if not in List) B NO, it fails on head == null C NO, it misses the last element D YES but inefficient. Should add all elements from both then remove dupes from result
Look at this pair of methods you could have written for your linked list
project. Assume incoming key is NOT null
#8 Does the above pair of methods (working together) correctly return the reference to the node that contains key (or null if not in list)?
A YES, completely correct and does not fail on any edge cases B NO, it is close but fails on an edge case. C NO, it has a flaw such that it only gets it right on the base case D NO, it has a flaw such that it never gets any cases right.
#9 Assuming the above search is called on a list that has N elements in it, what is the total number of times the searchHelper method will be invoked. Do not count the public search().
A N B N- 1 C N+ D log2N + n E (n squared + n) / 2
#10 Why didnt we just make that searchHelper() method public, and then call it from main?
A You cant call recursive methods from a main method B It creates a risk of stack overflow C We could have. D none of the above
#12 Why is insert at tail easier on an array easier than on a linked list?
A Because you can remove a node in O(1) time B Tail node is always at head.getPrev() C Its not easier! This operation same complexity for Linked List or array D List has to start at front and walk to the end
#13 If I have an operation X that performs both a logarithmic operation and then a linear operation, then operation X is said to be logarithmic.
A TRUE B FALSE
#14 In an array based ADT, the remove at front operation is faster than a Linked List based remove at front.
A TRUE B FALSE
#15 What is the advantage of a Linked List over an Array?
A Linked List does not require large chunks of contiguous memory B Linked List only uses more memory as more elements are added C Linked List is faster for sorting and searching D A and B E A and B and C
#16 IGNORE THIS LINE A
B On a CDLL you can search for it in either direction from the head D There are no nulls in a CDLL
Which of these operations are O(1)?
A indexing into an array
B comparing primitives
C copying a primitive to another primitive
D A, B & C
E just A and B
Which of these operations are O(N)
A remove at front on an array
B remove at front on a singly linked list
C insert at front on an array
D insert at front on a singly linked list
E A and C
F B and D
The complexity of binary searching a sorted CDLL is the same as on a sorted array
IGNORE THIS QUESTION
Why does the java language offer us Generics ( the <T> stuff )?
A so that we may write the definition of a container once instead of having to write separate
version of it for each data type we might want to store in it
B so that it can enforce compliance on code (programs) that want to use the container.
C It is a form of code re-use one of the fundamental principles of software engineering D
all of the above
#21 OPEN RESPONSE In our ArrBag project, when we upSized our arrays, we created a new array that was twice the length of the one that got full. Why didnt we just increase it by one – and avoid having an array that has a lot of wasted extra unused capacity when we reach end of file?