Problem 1 ( / 8)
Answer the following with true or false. No justification is necessary, and none will be read.
A. (1 point)
If a function runs in time proportional to the base 2 logarithm of the size of its input, that function is O(2n).
Copyright By PowCoder代写 加微信 powcoder
B. (1 point)
n3 log n2 ≫ n4
C. (1 point)
Abstract data types must specify the algorithms used by their operations.
D. (1 point)
All directed acyclic graphs are trees.
E. (1 point)
All trees are weighted graphs.
F. (1 point)
The in-degree of a node in a directed graph must be equal to its out-degree.
G. (1 point)
The sum of all the in-degrees and out-degrees of all the nodes in a weighted directed graph must be an even number.
H. (1 point)
An adjacency list can be used to implement a weighted undirected graph.
Problem 2 ( / 3)
What is the complexity of each of the following functions in terms of their input n?
Clearly mark your final answer; it is the only thing we will consider.
Assume that the function do_constant_time_work runs in constant time, and that the function do_linear_time_work
runs in time proportional linearly to its input.
A. (1 point)
def ride_the_lightning(n):
for i in range(10):
for j in range(20):
for k in range(n):
do_constant_time_work()
B. (1 point)
Note: / is integer division; it rounds down.
def master_of_puppets(n):
if n == 0:
do_linear_time_work(n)
do_linear_time_work(n)
master_of_puppets(n/5)
do_constant_time_work()
C. (1 point)
def and_justice_for_all(n):
if n == 0:
do_constant_time_work()
do_constant_time_work()
and_justice_for_all(n-2)
Problem 3 ( / 5)
Answer the following with a single word, term, or mathematical expression. No justification is necessary, and none will be read.
A. (1 point)
I want to add and remove elements in a FIFO order. Which ADT should I use? (1 ADT name)
B. (1 point)
I want to store a collection of elements, and the order in which they are stored is significant. Which ADT should I use? (1 ADT name)
C. (1 point)
I want to represent a network of connected things, where the presence or absence of a unidirectional link is the only information we have about connections. Which ADT should I use? (1 ADT name)
D. (1 point)
What is the maximum load factor of a linear probing hash table with n elements? (1 mathematical expression)
E. (1 point)
What is the maximum load factor of an open addressing hash table n elements? (1 mathematical expression)
Problem 4 ( / 11) For each question, circle ALL the options that apply.
A. (1 point)
Consider the following code:
struct posn: let x; let y
let posns = [posn(1,2), posn(2,2), posn(2,3)]
posns[0].x = _____
assert posns[2].x == 2
Which value(s) would cause the assertion to fail when used in place of the _____? • A.1
• D. No such value exists
B. (1 point)
Consider the following code:
struct posn: let x; let y
let bob = posn(1,2)
let posns = [bob, bob, bob]
posns[1].x = 2
posns[1].y = 3
posns[2].x = 2
posns[2].y = 4
posns[0].x = _____
assert posns[2].x == 2
Which value(s) would cause the assertion to fail when used in place of the _____? • A.1
• D. No such value exists
C. (1 point)
Consider the following code:
struct posn: let x; let y
let bob = None
let posns = [bob, bob, bob]
for i in range(3):
posns[i] = posn(2, i+1)
posns[0].x = _____
assert posns[2].x == 2
Which value(s) would cause the assertion to fail when used in place of the _____? • A.1
• D. No such value exists
D. (1 point)
Which of these are NOT invariants of doubly-linked lists:
• A. There must always be at least one node in the list.
• B. The number of next arrows must be equal to the number of prev arrows. • C. Nodes cannot be the target of both a next and a prev arrow.
• D. Nodes must be the target of an equal number of next and prev arrows.
• E. All of the above are invariants of doubly-linked lists
E. (1 point)
Which of the following would make removing at the end of a singly-linked list O(1)? • A. Adding a tail pointer
• B. Adding a length field
• C. Adding an additional arrow to each node i that connects node i to node i+2 • D. Getting rid of the header
• E. None of the above
F. (1 point)
Which of these behaviors are allowed by the laws of the dictionary ADT for the following expression? {1:2, 2:1, 4:5, 5:4} .get(5)
• A. Returning 3
• B. Returning 4
• C. Returning 5
• D. Raising an error
• E. Modifying the dictionary
G. (1 point)
Which of these behaviors are allowed by the laws of the stack ADT for the following expression? |12 56 92 ”potato”⟩ .pop()
• A. Returning 12
• B. Returning 56
• C. Returning “potato” • D. Raising an error
• E. Modifying the stack
H. (1 point)
Which of these behaviors are allowed by the laws of the dictionary ADT for the following expression? {1:2, 2:1, 4:5, 5:4} .get(3)
• A. Returning 3
• B. Returning 4
• C. Returning 5
• D. Raising an error
• E. Modifying the dictionary
I. (1 point)
For the next three questions, consider the following linear probing hash table: Bucket 0 1 2 3 4
KeyÑValue BÑ2 CÑ3 AÑ1
Only get and put operations were used to get to this state.
Your task is to understand how we could have gotten to said state.
A blank cell represents an empty bucket, and X Ñ Y represents a bucket mapping key X to value Y . Assume hash is the hash function this hash table is using.
Whichofthesearepossiblevaluesforhash(A) % 5?Selectallthatapply. • A.0
• D. 3 • E.4 • F. 5
J. (1 point)
Whichofthesearepossiblevaluesforhash(B) % 5?Selectallthatapply. • A.0
• B.1 • C.2 • D. 3 • E.4 • F. 5
K. (1 point)
Whichofthesearepossiblevaluesforhash(C) % 5?Selectallthatapply. • A.0
• B.1 • C.2 • D. 3 • E.4 • F. 5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com