[SOLVED] CS SU21 CSE 2231 SW 2: Dev & Dsgn (4626)

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 Assignmentchef assignmentchef

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 ChoiceQuestions about Standard methods, Iterators, and Linked Listsreturn !((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 Queues front() method layered upon interface QueueKernels 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 = this.newInstance();
temp.enqueue(front);
for (T x : this) {
temp.enqueue(x);
this.transferFrom(temp);
return front;
Iterator it = this.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 and calls the hasNext() and next() methods. The inner class that implements Iterator is understood to be within its rights to include in its representation invariant the restriction that the value of each instance variable of the containers representation remains unchanged (is always restored) between calls to the iterator object (the inner classs this). A container method that changes the containers value would certainly violate this restriction by changing at least one of the instance variables values. Yet even a container method that restores the containers value may change an instance variables value because one abstract value can have many representations. Hence, the iterators representation invariant could be falsified if a container method is called. To prevent such a call, we must not pass the container as an argument to any method.
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 methods 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 containers value isnt 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 and calls the hasNext() and next() methods.
A for-each loop is a convenient shorthand for code that declares, for some type T, a variable of interface type Iterator and calls the hasNext() and next() methods. Good practice allows the bodies of container methods to make use of calls to hasNext() and next(). Hence, a call to a container method could cause the iterator to unexpectedly lose its proper place. To prevent such a call, we must not pass the container as an argument to any method.
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 dont 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 and calls the hasNext() and next() methods. The inner class that implements Iterator is understood to be within its rights to include in its representation invariant the restriction that the value of each instance variable of the containers representation remains unchanged (is always restored) between calls to the iterator object (the inner classs this). Every container method changes the containers value. Hence, calling any container method would certainly violate this restriction by changing at least one of the instance variables values. Hence, the iterators representation invariant could be falsified if a container method is called. To prevent such a call, we must not pass the container as an argument to any method.
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 extends StackSecondary {
* 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 stacks 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 > invalid
< 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: assignmentchef QQ: 1823890830 Email: [email protected]