#### 选择题

##### 选择题1

• 无法确定
• $\theta(k)$
• $\theta(m)$
• $\theta(n)$

##### 选择题2

• $\theta(n^2)$
• $\theta(m+n\log n )$
• $\theta(m+n)$
• $\theta(m\times n)$

##### 选择题3

• $r\ge d$
• $r\le d / 2$
• $r\ge d / 2$
• $r\le d$

• 总是
• 当且仅当图示有向图
• 有时候可以，有时候不行
• 从不

• 永远不会减少超过1
• 永远不会减少
• 肯定不会改变
• 可以保持不变

#### 思考题

##### 思考题1

In the 2SAT problem, you are given a set of clauses, where each clause is the disjunction of two literals (a literal is a Boolean variable or the negation of a Boolean variable). You are looking for a way to assign a value “true” or “false” to each of the variables so that all clauses are satisfied —- that is, there is at least one true literal in each clause. For this problem, design an algorithm that determines whether or not a given 2SAT instance has a satisfying assignment. (Your algorithm does not need to exhibit a satisfying assignment, just decide whether or not one exists.) Your algorithm should run in $O(m+n)$ time, where $m$ and $n$ are the number of clauses and variables, respectively. [Hint: strongly connected components.]