uopeople-cs2114-data-structure-final-exam

pdf

School

University of the People *

*We aren’t endorsed by this school

Course

3303

Subject

Computer Science

Date

Dec 6, 2023

Type

pdf

Pages

Uploaded by HighnessDeerPerson908

UoPeople cs2114 Data structure final exam written by pontkachepa Did you know a seller earn an average of $250 per month selling their study notes on Docmerit Scan the QR-code and learn how you can also turn your class notes, study guides into real cash today. Docmerit.com - The Best Study Notes Uploaded by: pontkachepa on Docmerit. Distribution of this document is illegal

What does resume do in the debugger? It runs the code until the next breakpoint What does the text at the bottom mean when hovering over a toString() method? It represents the return value of toString() If a debugger runs until a breakpoint has been reached has the line with the breakpoint run yet? No In the variables pane of the debugger what do the variables highlighted in yellow signify? That those variables have changed since the last step. The node that is easiest to access in a linked-chain is the head node In the Ch 6 linked-chain implementation of a Stack ADT, the performance of popping an entry from the stack is O(1) In the Ch 6 linked-chain implementation of a Stack ADT, when a node is popped from the stack the original first node will no longer be referenced the original first node will be deallocated the new first node will reference what was the second node in the chain In the Ch 6 array-based implementation of a Stack ADT, the entry peek returns may be found at the last occupied location in the array In the Ch 6 an array-based implementation of a Stack ADT, what value for the topindex of the stack indicates that it is empty? -1 What question should you keep in mind when debugging a recursive method? Does each base case produce a result that is correct for that case? Are there enough base cases? Is at least one of the cases a base case that has no recursive call? When too many recursive calls are made creating more activation records than the allocated program memory can handle, what kind of error occurs? Stack Overflow What type of behavior defines a queue? first-in first-out (FIFO) Where does a queue add new items?

at the back Where will you find the item added earliest to a queue? at the front After the following statements execute, what item is at the front of the queue? QueueInterface zooDelivery = new LinkedQueue(); zooDelivery .enqueue("lion"); zooDelivery .enqueue("tiger"); zooDelivery .enqueue("cheetah"); String next = zooDelivery .dequeue(); next = zooDelivery .dequeue(); zooDelivery .enqueue("jaguar"); "cheetah" What item is at the front of the list after these statements are executed? DequeInterface waitingLine = new LinkedDeque(); waitingLine.addToFront("Jack"); waitingLine.addToFront("Rudy"); waitingLine.addToBack("Larry"); waitingLine.addToBack("Sam"); String name = waitingLine.getFront(); Rudy What item is at the front of the list after these statements are executed? DequeInterface waitingLine = new LinkedDeque(); waitingLine.addToFront("Jack"); waitingLine.addToFront("Rudy"); waitingLine.addToBack("Larry"); waitingLine.addToBack("Sam"); String name = waitingLine.getBack(); Rudy What item is at the front of the list after these statements are executed? DequeInterface waitingLine = new LinkedDeque(); waitingLine.addToFront("Jack"); waitingLine.addToBack("Rudy"); waitingLine.addToBack("Larry"); waitingLine.addToFront("Sam"); String name = waitingLine.getFront(); name = waitingLine.getBack(); Sam In a circular array-based implementation of a queue, the initial size of the array should be one more than the queue's initial capacity In a circular array-based implementation of a queue, what is the performance when the dequeue operation ? O(1) In a linked chain implementation of a queue, the performance of the enqueue operation is O(1) In the linked chain implementation of a queue, the chain's first node contains the queue's front entry To efficiently remove a node at the end of a linked chain implementation of a queue requires a

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

extra reference in the node pointing to the previous node When a linked chain contains nodes that reference both the next node and the previous node, it is called a(n) doubly linked chain In the Carrano ListInterface, the method with the signature: public void add(int newPosition, T newEntry); adds a new entry to the specified position in the list increases the list size by 1 moves entries originally at or above the specified position one position higher You can add a new entry in a list at the beginning at the end in between items In the Carrano ListInterface, the method with the signature: public T remove(int givenPosition); does which of the following: removes the entry at a given position from the list When adding an entry to an array-based implementation of the ADT list at a specified location before the end of the list entries must be shifted to vacate a position for the new item In an array-based implementation of the ADT list, the makeRoom method does the most work when newPosition is 1 In a chain of linked nodes you can add nodes from the beginning of a chain add nodes from the end of a chain add nodes that are between other nodes In the Carrano LList implementation of a list, when a list is empty the firstNode is _____ and the numberOfEntries is _____. null, 0 In the LList implementation of a list, given a node called currentNode, which statement moves the node's reference to the next node? currentNode = currentNode.getNextNode();

In a linked-based implementation of the ADT list with a tail reference, what is the performance of adding an entry at the end of the list? O(1) Selecting the smallest element of an array and swapping it with the smallest entry is an operation in which sorting method? selection sort Java sorting implementations sort objects that implement the _____ interface. Comparable The selection sort requires ____ comparisons for an array of n items O(n^2) Which method does the interface iterator specify? hasNext() next() remove() If iteration has ended, the next method throws a NoSuchElementException After a call to remove, the nextPosition data field should be decrimented How do you find out how many jobs are currently in the queue without submitting an assignment? Web-Cat --> System Status --> Queued Jobs Can you view past scores? If so, how would you do that? Yes. Web-Cat-->Results-->Past Results Can you view other students' scores anonymously? If so, where would that information be? Yes. Web-Cat Assignment Results-->Graphs Drop Down Arrow-->Graphical Performance Graph What are the parts of your code that Web-Cat looks at when grading? Style Coding and Correctness Testing Web-Cat only shows you your most recent submission per assignment. False

Web-Cat doesn't tell you exactly where and how to correct your code. It simply says that your code has bugs and that you have to figure it out on your own. False Web-Cat shows you how it calculates your final grade for an assignment. True I will get points off of my assignment if my lines of code are too long. True What does a primitive type represent? What does a reference type represent? Simple Indecomposable Values A memory address for a stored value The operator == tests to see if two objects contain the same values A class uses composition when it declares an instance of another class as a data field Composition? Inheritance? Has-A Relationship Is-A Relationship Why do we use inheritance? To have a general class with common properties and behaviors shared by multiple more specialized classes. super()? this()? Parent's Constructor Local Constructor When one method has the same name but a different set of parameters than a second method, the methods are overloaded A key benefit of inheritance is an object can have several types, it is type compatible with any of its superclasses

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Encapsulation Abstraction Client Interface Implementation Enclosing data within a class in order to hide the classes implementation details focus on what and not how What the client needs to understand a class all the data fields and details of the method definitions A variable declared as an interface type can reference any object of a class that implements that interface Why is it important to include @Override in front of an overridden method? The complier will issue an error if it does not find a corresponding method to override Consider whether you call Employee's weeklyPay method on a ExternalContractor object? Does overloading a method prevent access to the parent method (such as when overriding a method)? No, overloading does not prevent access ot the parent method because the method signatures are different. What if the Employee class didn't have the weeklyPay method, but the PartTimeEmployee class still did? Would the line of code mary.weeklyPay(); still work? (Think about why or why not? Tinker with your code to convince yourself) no, it would be a compiler error because weeklyPay is undefined for the type mary is declared as Which weeklyPay method would be called? Employee's or PartTimeEmpoyee's? (Think about why) PartTimeEmployee The use of a generic data type is preferred over using Object as a general class in a collection because It ensures that all the members of the collection are objects related by inheritance. Which behavior is not represented in a bag? reorder the bag Which method returns a count of the current number of items in a bag? getCurrentSize() Why would the add method return false?

when the addition of a new item was not successful Which method removes all entries of a bag? clear() When adding an item to a bag, which of the following statements are true? You cannot specify the position of the item in the bag. Which behavior(s) change the contents of a bag? add() Which of the following are good reasons to write tests that use your bag ADT before the implementation is done? it helps confirm the design it helps check the suitability of the specification it helps check your understanding of the specification What are the consequences of returning a reference to the bag array in the toArray method? the return variable is an alias for the private instance array variable the client will have direct access to the private instance array variable the client could change the contents of the private instance array variable without using the public access methods A fixed size array has a limited capacity can waste memory prevents expansion when the bag becomes full The most efficient approach to dealing with a gap left in an array after removing an entry from a bag is to replace the entry being removed with the last entry in the array and replace the last entry with null An incomplete definition of a method is called a stub The fixed array implementation of the method remove that has no parameter in the bag removes the last entry in the array

What is a limitation of using an array concerning capacity? An array has a fixed length, so if you add more than the the declared amount of movies to the structure, the array needs to be expanded and to do that, a new array needs to be created. What is the difference between size and capacity? Size represents how many Movie objects are currently in the NetvidsDatabase and capacity represents how many Movie objects can fit into the NetvidsDatabase before the underlying array needs to be expanded. What is the length of the following array: int [] data = { 12, 34, 9, 0, -62, 88 }; 6 Which of the following is usually an advantage of using an array to implement the ADT bag? adding an entry to a bag is fast What is usually an advantage of using a chain to implement the ADT bag? It avoids moving data when adding or removing bag entries. Placing the Node class inside the LinkedBag class makes it a(n) inner class A reference to the first node in a linked list is called the _____ reference. head What does the"new" operator do in the following code from the LinkedBag add method: Node newNode = new Node(newEntry); a new node is created the JRE allocates memory for a node object a new object is instantiated An algorithm has time requirements space requirements You should express the complexity of an algorithm in terms of it problem size Problem size is defined as the number of items an algorithms processes For large values of n which statement is true?

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

(n^2 + n ) / 2 behaves like n^2 If an algorithm requires 7 basic operations for an algorithm with a problem size of n, the algorithmic complexity is O(1) What is the time complexity for adding an entry to a fixed-size array-based bag ADT? O(1) What is the time complexity for adding an entry to a linked-based bag ADT? O(1) What is the worst-case time complexity for searching a linked-based bag ADT for a particular entry? O(n) When you remove an item from a stack, you remove it from the top In your reading, the pop and peek methods throw a(n) ________ exception when the stack is empty. runtime An expression that has correctly paired delimiters is called a(n) balanced expression Given the following infix expression, which one of the following is the corresponding postfix expression? (a + b) * (c - d) / (e + f) a b + c d - * e f + / At the time a method is called during program execution, the activation record is pushed onto the program stack Why does the blue line slope upward? Every miss appends to the end of the linked list, which is O(n). What is the largest factor in the misses being slower than the hits? Misses need to fetch from memory, which is slower than fetching from cache. Why does the blue extend over the entirety of the graph instead of the start as with Question 2? Requests are random instead of sequential. Why does this graph look flat while the others look sloped? Data becomes cached quickly, and accesses are random.

A subclass is also called a(n) derived class A superclass is also called a(n) base class If the SortedList class inherited the remove by position method from the LList class we would not have to implement it again Because SortedList is derived from LList, you write _____.add(newPosition, newEntry) to invoke the add operation of the ADT list super If you plan for a future subclass to be allowed to manipulate a class's data fields, provide _____ methods to enable the subclass to do this safely and efficiently. protected To prevent a subclass from overriding protected methods, we declare them to be final When you declare a method to be protected and final, who can access it? a subclass What issue should you weigh when considering an implementation for an ADT? execution time memory use extensibility The average-case time efficiency of a sequential search on an array is O(n) In an array of 100 items sorted in ascending order, if you are searching for the number 165 and the entry at array index [50] has a value of 72, what can we conclude? the value will not be found at indexes [0] through [50] if the value is in the array, it will be found somewhere at indexes [51] through [99] one half of the array can be ignored in the next step What is the base case in the recursive algorithm for a binary search of a sorted array? first index > last index The worst-case time efficiency of a binary search on a sorted array is O(logn)

The worst-case time efficiency of a sequential search on an unsorted chain of linked nodes is O(n) An example of a data organization that is hierarchical is a(n) family tree university administration structure file directories A tree is a set of nodes connected by _____ that indicate the relationships among the nodes. edges At the top level of a tree is a single node called the _____. root A node with no children is called a(n) _____. leaf A tree in which each node may have at most two children is called a(n) _____ tree. binary When a binary tree of height h has all of its leaves at level h and every nonleaf has exactly two children, the tree is said to be full When a binary tree is full to its next-to-last level and its leaves on the last level are filled from left to right, the tree is said to be complete A node in a binary tree whose subtrees differ in height by no more than 1 is known as a(n) _____ node. balanced The height of a complete tree that has n nodes is log2(n+1) How many nodes are in a full binary tree of height 5? 31 What is the height of a complete tree that contains 11 nodes? 4 In a _____ traversal of a binary tree, you visit the root of a binary tree after you visit the root's subtrees. postorder

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

How does the HashMap Cache improve upon the LinkedKVStore Cache? Constant-time lookup How does the Capped Hashmap Cache improve upon the Hashmap Cache? Bounded size Consider the CacheList. CacheNode's methods moveToFront() and removeLast(). Their runtime complexity is (let n be the number of items in the list). moveToFront is O(1) and removeLast is O(1) When using average latency as a performance gauge, the LRU Cache improved upon the Capped Hashmap Cache (which lacked a suitable eviction policy) by a factor of 15:1 Which of the following statements is false? If a cache of size S can absorb a workload without causing cache misses, then so can a cache of 2 * S. If a cache can perform key lookup in constant time, and assuming that that the miss penalty is constant as well, then its average latency depends solely on the miss rate Increasing the cache size will always improve the miss rate (i.e., lower it). Increasing the cache size will always improve the miss rate (i.e., lower it). Consider an LRU Cache with capacity 3. When faced with a sequence of requests whose keys are "A", "B", "C", "A", "D", the lookup of key "D" and subsequent insertion of its value will: Cause a cache miss and "B" to be evicted An iterative version of a preorder traversal for a binary tree uses a(n) stack An iterative version of a level order traversal for a binary tree uses a(n) queue A complete traversal of an n-node binary tree is a(n) _____ operation if visiting a node is O(1) for the recursive implementation. O(n) The data in a BST's node's _____ subtree are less than the data in a node's _____ subtree. left, right In the interface SearchTreeInterface, what does the method getEntry return if the object being sought doesn't exist? null

In the interface SearchTreeInterface, what does the method add return if the object being added already exists in the tree? the existing entry that matched the parameter In a binary search tree, the getInorderIterator inherited from the class BinaryTree sorts data in ascending order The inorder predecessor of a node N is the largest entry in N's left subtree The inorder successor of a node N is he smallest entry in N's right subtree The largest entry in a node N's right subtree is the subtree's rightmost node What is the worst-case performance of the add method in a full binary search tree with linked nodes? O(log n) Which option below is not a benefit of inheritance: duplicate code reduction via sharing of common code among several subclasses focus on what the object does instead of how it does it an object can have several types, it is type compatible with any of its superclasses ability to override the methods from the parent class focus on what the object does instead of how it does it What would be the result of the client code of a generic Bag ADT forgetting to define an equals() method for the class used as the type parameter to the Bag? Bag elements could only be identified as being contained or removed only by using the same instances passed to the add method. private int sum = 2; private int product = 2; public static final int AMOUNT = 5; public void output(){ System.out.print("The sum of the numbers from 1 to " + AMOUNT + " is " + sum); System.out.println(" The product of the numbers from 1 to " + AMOUNT + " is " + product); }

public void calculate(){ int sum = this.sum; int product = 1; for (int i = 1; i <= AMOUNT; i++){ sum = product + i; product = sum * i; } output(); } The sum of the numbers from 1 to 5 is 2 The product of the numbers from 1 to 5 is 2

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

uopeople-cs2114-data-structure-final-exam

Related Documents