class Node: def __init__(self, node_data): self._data = node_data self._next = None

def get_data(self): return self._data

def set_data(self, node_data): self._data = node_data

data = property(get_data, set_data)

def get_next(self): return self._next

def set_next(self, node_next): self._next = node_next

next = property(get_next, set_next)

def __str__(self): return str(self._data)

def to_string(head: Node) -> str: """Return a string representation of the linked list referred to by head.

>>> head = build_linked_list([31, 77, 17, 93, 26, 54]) >>> to_string(head) '31 -> 77 -> 17 -> 93 -> 26 -> 54'

>>> head = build_linked_list([]) >>> to_string(head) 'None' """ if head is None: return 'None'

node = head # Traverse the list from head to tail, collecting the data # in the nodes as a list of strings. items = [] while node is not None: items.append(str(node.data)) node = node.next

# Concatenate the strings in items, with each pair separated by " -> " return " -> ".join(items)

def build_linked_list(lst: list) -> Node: """Build a linked list containing the data in lst and return a reference to the first node.

>>> head = build_linked_list([1, 2, 3, 4]) >>> to_string(head) '1 -> 2 -> 3 -> 4' """ head = None # Empty list has no nodes i = len(lst) - 1 # Traverse lst back to # front while i >= 0: # insert a node (3-step link-in) node = Node(lst[i]) node.next = head head = node i -= 1 return head

#-------------------------------- # Exercise 1

def power(x: float, n: int) -> float: """Return x raised to the power n.

Precondition: n >= 0.

>>> power(3.5, 0) 1.0 >>> power(3.5, 1) 3.5 >>> power(3.5, 2) 12.25 """ raise NotImplementedError("power hasn't been implemented.")

#-------------------------------- # Exercise 2

def num_digits(n: int) -> int: """Return the number of digits in n.

Precondition: n >= 0.

>>> num_digits(492) 3 >>> num_digits(63) 2 >>> num_digits(7) 1 """ raise NotImplementedError("num_digits hasn't been implemented.")

#-------------------------------- # Exercise 3

def count(head: Node, value: int) -> int: """Return the number of integers equal to value in the linked list of integers referred to by head.

>>> head = None >>> count(head, 5) 0 >>> head = build_linked_list([10, 20, 10, 30, 20, 10]) >>> to_string(head) '10 -> 20 -> 10 -> 30 -> 20 -> 10' >>> count(head, 10) 3 >>> count(head, 30) 1 """ raise NotImplementedError("count hasn't been implemented.")

#-------------------------------- # Exercise 4

def last(head: Node) -> int: """Return the last integer in the linked list of integers referred to by head.

Precondition: head is not None (the linked list is not empty).

>>> head = build_linked_list([1, 2, 4, 4, 6, 5]) >>> to_string(head) '1 -> 2 -> 3 -> 4 -> 5' >>> last(head) 5 >>> head = build_linked_list([10]) >>> to_string(head) '10' >>> last(head) 10 """ raise NotImplementedError("last hasn't been implemented.")

#-------------------------------- # Exercise 5

def copy(head: Node) -> Node: """Make a copy of the linked list referred to by head (duplicate all the nodes in the original list) and return a reference to the first node in the new linked list.

>>> head = build_linked_list([1, 2, 4, 4, 6, 5]) >>> to_string(head) '1 -> 2 -> 3 -> 4 -> 5' >>> copied = copy(head) >>> to_string(copied) '1 -> 2 -> 3 -> 4 -> 5' """ raise NotImplementedError("copy hasn't been implemented.")

Exercise 1: Calculating x", where n is a nonnegative integer, can be specified using this recursive formulation: r = 1 x"=x*x1,n> 0 Read the docstring for function power. Replace the raise statement with a recursive implementation of the function. Your function cannot have any loops and it cannot use Python's ** operator or call the pow function in Python's math module. Use the shell (or write a short script) to test power. Remember to test the base case and some recursive cases. Exercise 2: You're going to write a function that returns the number of digits in integer n, n >= 0. If n