ComputerScienceAbilityTest

Computer Science Ability Test (CSAT) aims to evaluate objectively, through unified examinations with 10 true or false questions, the abilities of testees in computer science.

Kotori is taking the test, but soon she discovers with dismay that she cannot answer even a single question. Now she presents you with these 10 questions. Can you tell her the correct answer to each question?

(On linear algebra) Two vectors $v_1$ and $v_2$ are linearly dependent if there exists two scalars $k_1$ and $k_2$ such that $k_1v_1 + k_2v_2 = \overrightarrow{0}$ .
(On calculus) $\frac{y\text{d}x - x\text{d}y}{x^2-y^2} = \text{d}(\frac{1}{2}\ln \left| \frac{x-y}{x+y} \right|)$ .
(On discrete mathematics) $\emptyset \subseteq \{\emptyset\}$ .
(On physics) One mole of ideal gas is expanded from $V_0$ to $2V_0$ in a reversible adiabatic process. If the temperature of the gas decreases by 25%, the gas may be a type of monatomic gas.
(On data structure) The amortized time complexity of an insert operation of a Fibonacci heap is $O(1)$ .
(On approximation algorithm) If $P \ne NP$ , there does not exist a polynomial-time 2-approximation algorithm for the traveling salesman problem on a complete graph, but there exists a polynomial-time $2^n$ -approximation algorithm for this problem.
(On quantum algorithm) There exists a comparison-based quantum sorting algorithm which takes less than $\Omega(n\log n)$ steps and is better than classical algorithms.
(On operating system) A system consists of 4 resources with the same type. Suppose that at most 3 processes simultaneously apply the resource and every process applies at most 2 resources, so the system is deadlock free.
(On theory of computation) Let $L(M)$ be the language that the Turing machine $M$ accepts, then the language $\{\text{"}M\text{"} | M \text{ is a Turing machine and } L(M) \text{ is uncountable} \}$ is recursively enumerable but not recursive.
(On compiler principles) There exists a grammar which is LL(1) but not LALR(1).

详情