2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Quiz 3 (Remotely Proctored)
Due Jul 8 at 8am Points 50 Questions 26
Available Jul 6 at 7pm – Jul 8 at 9:15am 1 day Time Limit 60 Minutes
Copyright By PowCoder代写 加微信 powcoder
Instructions
This is an open-book, open-notes exam. However, you are not allowed to discuss this exam with anyone, including asking for help on the Internet. You are also not allowed to use other devices, nor listen to music, treat this as if you were in a classroom taking an exam. Although in principle you are allowed to use Eclipse and search the Internet while taking the test, you should not need to, and we strongly discourage you from wasting time trying to type code in Eclipse or looking for answers on the Internet. You should be able to answer all the questions on your own. If needed, you may consult the OSU/CSE Javadoc APIs at http://web.cse.ohio- state.edu/software/common/doc/ (http://web.cse.ohio-state.edu/software/common/doc/) .
Do not discuss this exam with anyone in CSE 2231 who has not yet taken the exam. Failure to observe these restrictions will be treated as academic misconduct.
I will be available at my office hour Zoom link: Office Hours (https://osu.zoom.us/j/92361574385? pwd=NGluaC9zRDRIdEUvalVrcG5yb1hvZz09) use this link only if you have questions (it is not a room to wait for something to happen and you will be kicked out if you do not have questions).
https://osu.instructure.com/courses/102483/quizzes/554345 1/21
Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
This quiz was locked Jul 8 at 9:15am. Attempt History
Attempt LATEST Attempt 1
59 minutes
29 out of 50
Correct answers are no longer available. Score for this quiz: 29 out of 50
Submitted Jul 8 at 9:14am This attempt took 59 minutes.
https://osu.instructure.com/courses/102483/quizzes/554345
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Heaps vs. Binary Search Trees
In a non-empty binary search tree with all distinct integer entries and total preorder ≤, the node of the largest element
is a leaf node.
none of the other answers. has no right child.
is the root.
has no left child.
I assert that the answers provided are my own, and that I have read, understood and agree to abide by the restrictions above.
True False
Given a non-empty heap with all distinct integer entries and total preorder ≤, the smallest element is at the root. The largest element
https://osu.instructure.com/courses/102483/quizzes/554345 3/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
In a non-empty binary search tree with all distinct integer entries and total preorder ≤, the node of the smallest element
has no right child.
none of the other answers. has no left child.
is a leaf node.
is the root.
has to be the right-most element of the bottom level in the tree. has to be a leaf node.
may be anywhere but the root.
has to be to the right of the root.
Which one of the following statements about heaps is false?
https://osu.instructure.com/courses/102483/quizzes/554345 4/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Consider a heap of integers based on the usual ≤ ordering implemented using an array as discussed in class. Which one of the following arrays represents a heap?
<8, 14, 12, 10, 13, 16, 25>
<8, 12, 10, 14, 13, 25, 16>
<8, 10, 16, 14, 13, 12, 25>
<8, 13, 12, 14, 10, 25, 16>
To build a heap we first sort the elements, and then place them into the heap.
A heap is a binary tree with extra constraints on its shape and organization.
The siftDown method is used to adjust the root of the tree to its proper position in a heap.
Heaps require the use of a total preorder.
https://osu.instructure.com/courses/102483/quizzes/554345 5/21
Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
The array value below is a heap of integers of size 6, based on the usual ≤ ordering (Note that the array is longer than 6). Which one of the following array representation of heaps would result from removing the smallest item, using the algorithm discussed in class?
< 5, 6, 8, 27, 13, 11, 3 >
Note: a ? symbol represents an unknown/irrelevant value in our heap.
< 6, 13, 8, 27, 11, ?, 3 >
< 6, 11, 8, 27, 13 >
< 3, 6, 8, 27, 13, 11, 5 >
< 8, 6, 11, 27, 13, ?, 3 >
< 6, 11, 8, 27, 13, ?, 3 >
Consider the following method contract. The method smallestIsUnique is given an array of int and an int, where the array between indices 0 and last represents a heap of integer with ≤ ordering, and it returns true if and only if the smallest value in the heap occurs only once.
* @requires 0 < last < |array| and
* SUBTREE_IS_HEAP(array, 0, last, <=) and
* [subtree rooted at 0 is a complete binary tree]
* @ensures
* smallestIsUnique = [the smallest value in the heap between 0 and la
st appears only once in the heap]
public static boolean smallestIsUnique(int[] array, int last) {...}
https://osu.instructure.com/courses/102483/quizzes/554345 6/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 - SW 2: Dev & Dsgn (4626)
boolean unique = false;
if (last > 0) {
unique = array[1] != array[0];
} else if (last > 1) {
unique = array[2] != array[0];
return unique;
Incorrect Correct
boolean unique = true;
if (1 <= last && array[1] == array[0]) {
unique = false;
} else if (2 <= last && array[2] == array[0]) {
unique = false;
return unique;
Correct Incorrect
For each of the method bodies below, select correct if they are a correct implementation of the contract above. (There are no syntax errors; look for logical errors!)
https://osu.instructure.com/courses/102483/quizzes/554345 7/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 - SW 2: Dev & Dsgn (4626)
return (array.length < 1 || array[0] != array[1]) && (array.length < 2
|| array[0] != array[2]);
Incorrect Correct
Multiple Choice
Questions about Standard methods, Iterators, and Linked Lists
return !((last >= 1 && array[0] == array[1]) || (last >= 2 && array[0]
== array[2]));
Incorrect Correct
Which one of the following benefits can smart (sentinel) nodes provide?
https://osu.instructure.com/courses/102483/quizzes/554345 8/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Significantly faster performance when manipulating the elements of a linked list.
Quicker setup of the initial state of a linked list.
Prevention of run-time errors (e.g., NullPointerExceptions) arising from the code managing a linked list.
Removal of special cases from some methods that work with a linked list.
It is understandable to think that an implementation of interface Queue’s front() method layered upon interface QueueKernel’s methods must have time performance that is linear in the length of the Queue this. However, it is possible to write an implementation whose time performance is constant, regardless of the length of this. Which one of the following choices is this implementation?
T front = this.dequeue();
this.enqueue(front);
for (int i = 0; i < this.length() - 1; i++) {
this.enqueue(this.dequeue());
return front;
T front = this.dequeue();
this.enqueue(front);
this.rotate(this.length() - 1);
return front;
https://osu.instructure.com/courses/102483/quizzes/554345 9/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 - SW 2: Dev & Dsgn (4626)
Which one of the following statements about linked lists is always true?
The nodes in a linked list have consecutive memory addresses.
Any node in a linked list can be accessed in constant time.
Linked list implementations require at least one smart (sentinel) node.
The entire contents of a linked list can be accessed sequentially in linear time.
T front = this.dequeue();
Queue
temp.enqueue(front);
for (T x : this) {
temp.enqueue(x);
this.transferFrom(temp);
return front;
Iterator
T front = it.next();
return front;
When we are iterating through a container with a for-each loop, we should never pass the container as an argument of a call to any method. Exactly one of the choices offered is a true reason for this restriction. Based on your growing knowledge of software development and design, which one would you say it is?
https://osu.instructure.com/courses/102483/quizzes/554345 10/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
A for-each loop is a convenient shorthand for code that declares, for some type T, a variable of interface type Iterator
This question is a trick. The restriction is stated too strongly. Actually, it is permitted to pass the container as an argument of a call to a method as long as that method’s contract says that the corresponding formal parameter is restored. Clearly, it is a mistake to change the value of the container during iteration over the container, but, if the container’s value isn’t changed by a method call, that is no problem. Of course, this claim is based on the truth that a for-each loop is a convenient shorthand for code that declares, for some type T, a variable of interface type Iterator
A for-each loop is a convenient shorthand for code that declares, for some type T, a variable of interface type Iterator
https://osu.instructure.com/courses/102483/quizzes/554345 11/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
In the transferFrom() method, why do this and source need to be of the same dynamic type?
As long as source is in the same type family, transferFrom will work properly.
Because this and source end up as aliases.
The values of the instance variables need to be transferred from source to this.
They don’t really need to be the same dynamic type; it is just a CSE rule.
Implementing a Linked List
A for-each loop is a convenient shorthand for code that declares, for some type T, a variable of interface type Iterator
https://osu.instructure.com/courses/102483/quizzes/554345 12/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Consider Stack14, the implementation of Stack kernel using a singly linked list with a smart (dummy) node in the first location, and with only one instance variable to point to the start of the singly linked list; there is no length instance variable.
* Stack represented as a singly linked list, with implementations of
primary methods.
* @param
* type of Stack entries
* @convention
* [$this.start is not null] and
* [$this.start points to the first node of a singly-linked list of no
* one node longer than this] and
* [the instance variable named “next” in the last node of that list i
* @correspondence
* if [$this.start.next is null] then this = <>
* else this = [data in the nodes in the singly-linked list starting a
t $this.start.next]
public class Stack14
* Node class for singly linked list nodes.
private final class Node {
private T data;
private Node next;
* First node of singly linked list holding the stack’s elements.
private Node start;
/* Rest of class removed to reduce clutter… */
Make sure to carefully review the representation, the convention, and the correspondence. Then answer the following questions.
Assume T = Integer. For each of the pictures below, determine whether it is a valid representation or not. If it is valid, select the value of the Stack (this) it represents according to the correspondence, otherwise select invalid.
https://osu.instructure.com/courses/102483/quizzes/554345 13/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
< 2, 1 > invalid <>
< 1, 2 >
< ?, 1, 2 >
https://osu.instructure.com/courses/102483/quizzes/554345 14/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
invalid <>
< ?, 1, 2 > < 1, 2 >
< ?, 1, 2 > invalid
https://osu.instructure.com/courses/102483/quizzes/554345 15/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
< 1, 2 > <>
< ?, 1, 2 > invalid
invalid
https://osu.instructure.com/courses/102483/quizzes/554345 16/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
< ?, 1, 2 >
< 2, 1 > <>
< ?, 1, 2 > < 2, 1 > <>
In the next 4 questions, complete the bodies of the createNewRep and the kernel methods for Stack14. For full credit:
You must always use this explicitly when accessing a class member.
https://osu.instructure.com/courses/102483/quizzes/554345 17/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
* Creator of initial representation.
private void createNewRep() {
Your Answer:
this.start = new Node(); this.start.next = null;
private void createNewRep() {
this.start = new Node();
// The line below is optional
this.start.next = null;
In length, you must use only one return statement and no break statement.
Indent your code!
Make sure to indent your code by using spaces; do not use the Tab key because it does not enter a tab in the editor and instead it takes you to the next element on the page
In the editor, click on the tool labeled “Paragraph” and select “Preformatted” to get a monospaced font which will make it easier to indent and read your code
public final void push(T x) {
assert x != null: “Violation of: x is not null”;
https://osu.instructure.com/courses/102483/quizzes/554345 18/21
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Your Answer:
Node m = this.start.next; Node n = new Node(); n.next = m;
n.data = x;
public final void push(T x) {
Node n = new Node();
n.data = x;
n.next = this.start.next;
this.start.next = n;
-2 You never changed the list
public final T pop() {
assert this.length() > 0 : “Violation of: this /= <>“;
Your Answer:
Node m = this.start.next; T temp = m.data;
Node n = m.next; this.start.next = n;
return temp;
https://osu.instructure.com/courses/102483/quizzes/554345 19/21
Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
public final T pop() {
T data = this.start.next.data;
this.start = this.start.next;
// or this.start.next = this.start.next.next;
return data;
} @Override
public final int length() {
Your Answer:
int len = 0;
Node m = this.start.next; if(m.data == null){
return len; }
while(m.data != null){
m=m.next; }
return len;
https://osu.instructure.com/courses/102483/quizzes/554345
2021/9/27 Quiz 3 (Remotely Proctored): SU21 CSE 2231 – SW 2: Dev & Dsgn (4626)
Quiz Score: 29 out of 50
public final int length() {
Node n = this.start.next;
int len = 0;
while (n != null){
n = n.next;
return len; }
Multiple return statements? m.data?
https://osu.instructure.com/courses/102483/quizzes/554345 21/21
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com