QUIZ 2 Warm-up Questions - KEY

pdf

School

Pennsylvania State University *

*We aren’t endorsed by this school

Course

132

Subject

Computer Science

Date

Apr 3, 2024

Type

pdf

Pages

Uploaded by ChancellorEagle4123

CMPSC-132: Practice Exercises CODING QUESTIONS Question 1: Write the Python code for finding the second-to-last (item before the last) node in a Singly Linked list in which the last node is indicated by a next reference of None. If there is no second-to-last node, return None. def second_to_last(self): if not self.isEmpty(): current=head if current.next is not None: while current.next.next is not None: current = current.next return current Question 2 : Assume you have a Doubly Linked List with the head node and at least one other internal node C which is not the last node. You may assume that each node has a next pointer and prev pointer. Write few lines of code to accomplish the following. You may NOT swap data to accomplish any of the following operations. Remember that for each operation, you need to manipulate at least two pointers, next and prev . a) Delete the head Node head = head.next head.prev = None b) Swap head and C nodes, you cannot swap data A = head.next B = C.prev D = C.next B.next = head head.prev = B head.next = D D.prev = head C.next = A A.prev = C C.prev= None head = C

Note: if you are confused by the solution, it is always useful to draw a diagram to follow the pointers This is what the doubly linked list looks like before swapping: And this is what the list looks like after swapping, with the changed pointers highlighted Now that we see what has changed, let's take a look at what pointers changed, from what value to what new value Pointer Old New a.next afterA afterC a.prev None beforeC c.next afterC afterA c.prev beforeC None head A C afterA.prev A C beforeC.next C A afterC.prev C A In summary, you would have to keep track of five different nodes and change the values of eight different pointers.

Question 3: Recall the Stack data structure discussed in Module 5. You were asked to implement such structure in Homework 3. Such data structure contained a reference to the top node in the stack and can perform the operations len, isEmpty, push, pop and peek only. Write the Python code for the function smallest_at_top(stack_object) that takes a Stack object as a parameter and determines which value in stack_object is the smallest and move that Node to the top of the stack while leaving the remainder of the stack in its original order. For example, if the stack contains the elements 23, 72, 94, 3, 1, 60 (where 23 is the top Node and 60 is the bottom Node) then a call to smallest_at_top (stack_object) will update the original stack to 1, 23, 72, 94, 3, 60 (where 1 is the top Node and 60 is the bottom Node) and returns nothing. Your code may only declare Stack or scalar variables (int, float) if needed. You are not allowed to declare other variables such as Python lists, linked lists, dictionaries, etc., or use other methods or Classes from the Python library. You can assume the stack contains unique numerical values. When the stack is empty, smallest_at_top (stack_object) returns None def smallest_at_top(stack_object): if stack_object.isEmpty(): return None else: temp = Stack() smallest = stack_object.peek() while not stack_object.isEmpty(): value = stack_object.pop() temp.push(value) if value<smallest: smallest = value while not temp.isEmpty(): value = temp.pop() if value!=smallest: stack_object.push(value) stack_object.push(smallest) Question 4: Write the implementation for the pop() method for a Doubly Linked List with a) a reference to the tail node and b) no reference to the tail node. The Node class is defined as: Pop from a Doubly Linked List with reference to tail def pop(self): if self.isEmpty(): return None else: deleted = self.tail.value self.tail = self.tail.prev if self.tail: self.tail.next.prev = None self.tail.next = None else: self.head=None return deleted

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

Pop from a Doubly Linked List without reference to tail def pop(self): if self.isEmpty(): return None else: current=self.head while current.next is not None: current=current.next if current.prev is None: self.head=None else: current.prev.next=None current.prev=None return current.value Question 5: Below is the partial implementation of a FIFO Queue using only Stacks. The constructor, isEmpty and enqueue methods have been implemented for you and should not be modified. Write the implementation of the dequeue method for the Queue class using only stack_1 and stack_2 operations only. You are not allowed to use Python lists. class Queue: def __init__(self): self.stack_1=Stack() self.stack_2=Stack() def isEmpty(self): if self.stack_1.isEmpty() and self.stack_2.isEmpty(): return True return False def enqueue(self, value): self.stack_1.push(value) def dequeue(self): if self.isEmpty(): return None if self.stack_2.isEmpty(): while not self.stack_1.isEmpty(): out=self.stack_1.pop() self.stack_2.push(out) return self.stack_2.pop()

Question 6: Consider a real-time stock trading platform where traders need to quickly respond to market changes. In such a platform, each trader might have a list of buy or sell orders they've placed, which need to be processed in a specific order (LIFO - Last In, First Out) as market conditions change. However, traders also need to keep track of their most advantageous (minimum) price point among their active orders to make informed decisions swiftly. Design a class `StockTrader` that supports all three of these operations without requiring any looping. Hint : consider having two stacks, one that stores the stocks in the order they come in, and one that keeps a "running minimum". class StockTrader: def __init__(self): self.orders = Stack() self.min_prices = Stack() def place_order(self, price): self.orders.push(price) if self.min_prices.is_empty() or price <= self.min_prices.peek(): self.min_prices.push(price) def cancel_last_order(self): if not self.orders.is_empty(): last_order = self.orders.pop() if last_order == self.min_prices.peek(): self.min_prices.pop() return last_order def get_minimum_price(self): if not self.min_prices.is_empty(): return self.min_prices.peek() Question 7: Write the method double_them that takes a queue and replaces every node in the queue with two occurrences of that node. For example, suppose a queue contains the following values: 3 -> 7.5 -> “ 1 ” -> 14-> 9, when 3 is the head and 9 the tail. After the method ends the queue should contain the following values: 3 -> 3 -> 7.5 -> 7.5 -> “ 1 ” -> “ 1 ” -> 14-> 14 -> 9 ->9 (3 is head and 9 tail). Notice that you must preserve the original order. You may use one queue for additional storage. class Queue: def __init__(self): self.head=None self.tail=None # isEmpty(), dequeue and enqueue are properly implemented def double_them(self): temp_queue = Queue() while not self.isEmpty(): front_element = self.dequeue() temp_queue.enqueue(front_element) temp_queue.enqueue(front_element) while not temp_queue.isEmpty(): self.enqueue(temp_queue.dequeue())

Question 8: Complete the definition of the get_sum method in the BinaryTree class. This method returns the sum of the values contained in all of the Nodes of the binary tree with root node . It does not modify the original tree. You can assume the values of the nodes are numeric. You are not allowed to copy values of the Nodes into other data structures def get_sum(self, node): if node is None: return 0 else: left_sum = self.get_sum(node.left) right_sum = self.get_sum(node.right) return node.value + left_sum + right_sum Question 9: Write the implementation of the __contains__ method in the BinaryTree class that returns True if value is present in the tree, False otherwise. Note that the tree is not necessarily a binary search tree. This requires an entire traversal of the tree, since there is not guarantee we have a BST. Any of the tree traversals discussed in lectures can be used to implement contains (using preorder) def __contains__(self,value): if self.isEmpty(): return None else: return self._containsHelper(self.root, value) def _containsHelper (self, node, value): if node is not None: if node.value == value: return True else: left= self._containsHelper(node.left, value) right= self._containsHelper(node.right, value) return left or right else: return False Question 10: Write the implementation of the reverse method in the LinkedList class discussed and implemented in Module 5. This method reverses the list in-place (modifies the original list). def reverse(self): if self.isEmpty(): return None current = self.head prev = None self.head, self.tail = self.tail, self.head while current is not None: prev_next = current.next current.next = prev prev = current current = prev_next

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

Question 11: Write the implementation of the reversed_bsf method in the BinarySearchTree class discussed and implemented in Module 6.1. This method visits the nodes of the tree in reversed level-order (bottom to top). The method should not modify the original tree. You might use Stacks and Queues in your solution assuming all basic Stack and Queue operations are implemented correctly. def reversed_bfs(self): if self.root is None: return 'Tree is Empty' s = Stack() q = Queue() visited=[] q.enqueue(self.root) while not q.isEmpty(): node = q.dequeue() s.push(node) #Right if node.right is not None: q.enqueue(node.right) #Left if node.left is not None: q.enqueue(node.left) while not s.isEmpty(): visited.append(s.pop().value) return visited Question 12: Write the implementation of the rotate method in the LinkedList class discussed and implemented in Module 5. This method takes an integer n and modifies the original list by rotating nodes to the right n places. You are not allowed to use Pythons lists or creates new Linked Lists. When n>size of the list, rotations circle back to the front of the list. A rotation is simply moving the last node to the front. Module 5 implementation has a head and tail reference: def rotate(self, n): if not self.isEmpty() and (self.head.next is not None) and n > 0: size=len(self) if n>size: n=n%size if n!=0: self.tail.next=self.head for i in range(size-n): # Locate pivot node self.tail = self.tail.next self.head=self.tail.next self.tail.next=None

If the tail reference does not exist, first we need to locate the last node: if n!=0: last = self.head while last.next: last = last.next Question 13: Write the implementation of the _to_lst_helper method in the BinarySearchTree class discussed and implemented in Module 6.1. This method creates a sorted linked list with the nodes from the tree. To avoid conflict, the node for the LinkedList is named ListNode. This method is called by the to_lst method shown below: def to_lst(self): if self.root is not None: lst=LinkedList() prev_node = ListNode(None) #Create a dummy LinkedList Node to attach the nodes from the BST self._to_lst_helper(self.root, prev_node) lst.head=prev_node.next # Head is the node after prev_node prev_node.next=None # Unlink dummy node return lst In a BST, an inorder traversal visits the nodes in ascending order, thus, _to_lst_helper performs an inorder traversal and links the node according to the order they are visited def _to_lst_helper(self,node, prev=None): if node is None: return prev prev = self._to_lst_helper(node.left, prev) new_node = ListNode(node.value) prev.next = new_node return self._to_lst_helper(node.right, new_node)

QUIZ 2 Warm-up Questions - KEY

Related Documents