Full Name:
• Make sure that your exam is not missing any sheets, then write your full name on the front.
• Read the instructions for each question in full. They contain a lot of useful information you’ll need to in order to answer.
• Write your answers in the space provided on the page with each problem. If you make a mess, clearly indicate your final answer.
Copyright By PowCoder代写 加微信 powcoder
• The problems are of varying difficulty. The difficulty is not correlated with the problem number or the number of points so make a first pass and solve some easy problems.
• This exam is closed book, no notes, no electronics, no nothing. Just you and your trusty pencil.
Total (20)
Disclaimer: This number is not a measure of your worth as a human being; it is merely an (imperfect) measure of your mastery of the material in (the first half of) this class. Don’t lose track of the big picture.
The next few questions involve a data structure you have (most likely) not seen before: the rope. Ropes are a possible implementation of the sequence ADT, for which a simplified interface is below:
interface SEQUENCE[T]:
def len(self) -> int?
def insert_front(self, new: T) -> NoneC
def remove_front(self) -> NoneC
def get_nth(self, n: int?) -> T
def set_nth(self, n: int?, new: T) -> NoneC
The representation of a rope is a linked list whose elements are vectors. The elements of the rope sequence are, in order, the elements from the first vector, then the ones from the second vector, and so on. The length of a rope sequence is therefore the sum of the lengths of the vectors.
Concretely, here’s the start of our rope class:
struct cons:
class Rope:
def __init__(self):
self.head = None
And the following example rope represents the sequence [1,1,2,3,5,8,13].
data data data next next next
Problem 1 ( / 2)
Draw diagrams for two possible ropes that represent the sequence: [17, 26, 3, -2, 26]
Problem 2 ( / 4)
A. (3 points)
Assuming the definitions from page 1, implement the get_nth operation (from the SEQUENCE interface) on ropes, as a method in the Rope class.
Please write as correct DSSL2 code as you can; we won’t be strict with the syntax, but please make sure your answer is clear.
B. (1 point)
What is the worst-case complexity of your get_nth operation, in terms of the length of the rope n?
Problem 3 ( / 5)
A. (1 point)
Suppose we want to modify our rope implementation to be able to get the length of a rope without counting, similar to what we did with linked lists in class.
Which changes would you make to the fields and the constructor (if any)?
B. (1 point)
Describe (no code necessary) the changes (if any) that would need to be made to operations (other than len) from the earlier SEQUENCE interface to support your len operation?
C. (2 point)
Assuming the class has been modified in the way you described in parts A and B, implement this efficient len operation, as a method in the Rope class.
Please write as correct DSSL2 code as you can; we won’t be strict with the syntax, but please make sure your answer is clear.
D. (1 point)
What is the worst-case complexity of your len operation, in terms of the length of the rope n?
Problem 4 ( / 3)
A. (2 points)
Describe how we could adapt ropes to implement the dictionary ADT.
B. (1 points)
What would be the complexity of dictionary lookup (i.e., get) on this rope dictionary?
Problem 5 ( / 2)
What is the complexity of the following function in terms of its input n? If you show your work, you may be eligible for partial credit.
def humerus (n):
let result = 0
for i in range(n/4):
for j in range(i):
result = result + 1
return result
Bonus. (0 points)
What is the humerus?
Problem 6 ( / 4)
Answer the following with true or false. No justification is necessary, and none will be read.
A. (1 point)
Trees are dense graphs. True or false?
B. (1 point)
Linear probing hash tables are efficient so long as their load factor is greater than 1. True or false?
C. (1 point)
Suppose a directed graph has a cycle involving nodes A, B, C, and D. Are A, B, C, and D strongly connected? True or false?
D. (1 point)
It is impossible for a change at index i of a vector to affect the data at a different index j of that same vector. True or false?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com