分数 2
作者 Yuchen Mao
单位

Let Σ\Sigma be a set of at least two characters, each having a frequency. In any optimal prefix-free code for Σ\Sigma, at least two characters have the same coding length.

评测结果
答案正确
得分
2 分

分数 2
作者 Yuchen Mao
单位

Let T(n)T(n) be the running time of quicksort on an input of size nn. We already know that T(n)T(n) is a random variable whose value depends on the random choices of quicksort, and that the expectation of T(n)T(n) is O(nlogn)O(n \log n). Is the following statement true or false? The minimum possible value of T(n)T(n) can be as small as Θ(n)\Theta(n), and the maximum possible value can be as large as Θ(n2)\Theta(n^2).

评测结果
答案错误
得分
0 分

分数 2
作者 叶德仕
单位

If NP \neq co-NP, then P \neq NP.

评测结果
答案正确
得分
2 分

分数 2
作者 叶德仕
单位

We have an approximation algorithm ALG for a minimization problem X. For any given ε>0\varepsilon > 0, the approximation ratio of ALG is 1+ε1 + \varepsilon and the running time is O(31/εn2)O( 3^{1/\varepsilon} n^2), where nn is the input size of the problem X. Then the algorithm ALG is an FPTAS.

评测结果
答案正确
得分
2 分

分数 2
作者 刘一辰
单位

Insert 2,9,5,6,1,8, and 3 one by one into an initially empty AVL tree. Then the postorder traversal sequence of the resulting tree must be {1,3,2,6,9,8,5}.

评测结果
答案正确
得分
2 分

分数 2
作者 叶德仕
单位

For a leftist heap, the NPL of each node is 1 greater than the NPL of its right child.

评测结果
答案正确
得分
2 分

分数 2
作者 卜佳俊
单位

In the dynamic indexing situation, the main index is usually updated when a new document comes to the document collection.

评测结果
答案正确
得分
2 分

分数 2
作者 卜佳俊
单位

There are two statements about Local Search:

  • For any local search algorithm, searching a better solution in the neighborhood may not be done in polynomial time.
  • For any local search algorithm, it takes polynomial time to find the local minimum.

Only one of the statements above is correct.

评测结果
答案正确
得分
2 分

分数 2
作者 陈越
单位

Priority CRCW allows concurrent access for both reads and writes, while the processor with the smallest number has the highest priotity.

评测结果
答案正确
得分
2 分

分数 2
作者 陈越
单位

The time taken to backtrack -- that is, to recover the previous state of a solution is relatively hard (that is, no definite polynomial-time method works) to estimate during backtracking.

评测结果
答案错误
得分
0 分

分数 2
作者 陈昊
单位

In amortized analysis, the change in potential should be negative for low-cost operations and positive for high-cost operations.

评测结果
答案正确
得分
2 分

分数 2
作者 陈昊
单位

Given 2000 runs and 10 tapes. If simple k-way merge is used, the minimum number of passes required is 5 (runs generation pass is not counted).

评测结果
答案正确
得分
2 分

分数 2
作者 丁尧相
单位

The recurrent equation T(n)=nT(n/2)+nT(n) = n T(n/2) + n can be solved by the master theorem.

评测结果
答案正确
得分
2 分

答题已结束,仅供题目浏览
高速下载