分数 3
作者 Yuchen Mao
单位

Consider the Knapsack Problem. How many of the following statements are true?

  • If all the items have the same weight, then we can obtain an optimal solution by selecting items in decreasing order of profits.
  • If all the items have the same profit, then we can obtain an optimal solution by selecting items in increasing order of weights.
  • If all the items have the same efficiency (that is, profit-to-weight ratio), then we can obtain an optimal solution by selecting items in increasing order of weights.
评测结果
答案正确
得分
3 分

分数 3
作者 Yuchen Mao
单位

Consider eight characters with the following frequencies. (We normalize the frequencies so that they sum to 1.)

Symbol Frequency
A 0.11
B 0.11
C 0.11
D 0.11
E 0.14
F 0.14
G 0.14
H 0.14

What is the average encoding length of an optimal prefix code?

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

分数 3
作者 Yuchen Mao
单位

Consider the hiring problem. Assume that the nn candidates arrive in random order, and that no two candidates have the same performance. Let kk be some even number (偶数) in the range [1,n][1, n]. We use the following algorithm:

interview the first k candidates, but hire none of them
for candidates i = k+1 to n
    if candidate i is better than at least half of the first k candidates
        hire candidate i

It is easy to see that the above algorithm may hire more than one candidates. How many candidates will be hired in expectation?

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

分数 3
作者 叶德仕
单位

Hamiltonian Cycle (or Circuit) in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex. Finding a Hamiltonian Cycle is a well-known NP-complete problem. Let’s consider the following two new variants of the Hamiltonian problems:

P1) Long Cycle problem: A Long Cycle in a graph G is a cycle that goes through at least half of the vertices of G.

P2) Hamiltonian Path problem: A graph G has a Hamiltonian path from s to t if there is an s to t path that visits all of the vertices of G exactly once.

Which of the following statements is correct?

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

分数 3
作者 叶德仕
单位

In the Activity Selection Problem, we are given a set of activities S={a1,a2,,an}S = \{ a_1, a_2, …, a_n \} that wish to use a resource.  Each aia_i takes place during a time interval [si,fi)[s_i, f_i). Activities aia_i and aja_j are compatible if sifjs_i \geq f_j or sjfis_j \geq f_i (i.e. their time intervals do not overlap). Our goal is to select a maximum-size subset of mutually compatible activities.

We propose a greedy rule “Shortest-First” that select the interval which is the shortest (but not overlapping the already chosen intervals). What is the approximation ratio of the greedy algorithm for the activity selection problem?

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

分数 3
作者 刘一辰
单位

Insert 2,9,5,6,1,8, and 3 one by one into an initially empty Splay tree. Which one of the following statements is TRUE about the resulting tree?

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

分数 3
作者 叶德仕
单位

Merge the two leftist heaps in the figure. How many of the following statements is/are FALSE ?

  • 8 and 9 are siblings
  • 6 and 7 are siblings
  • 1 and 3 have the differernt NPL
  • along the left path from the root, we have 1, 3, 6,10
    leftist.png
评测结果
答案正确
得分
3 分

分数 3
作者 卜佳俊
单位

There are 100000 documents in the document collection. The statistic data for one query is shown in the following table.

Relevant Irrelevant
Retrieved 10000 40000
Not Retrieved 30000 20000

Which one of the following statements about the statistics is True?

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

分数 3
作者 卜佳俊
单位

The Traveling Salesman Problem (TSP) is a classic problem: given a set of cities and the distances between each pair of cities, the goal of TSP is to find the shortest cycle that visits each city exactly once and returns to the starting city.

The 2-opt method is a local search algorithm used to solve the TSP. Specifically, the searching strategy is as follows:
(1) Starting at a feasible solution to the TSP (a valid cycle which visits each city exactly once and returns to the starting city).
(2) In each iteration, the current cycle is denoted as PP. The neighboring solution PP' is obtained by a 2-opt move. The 2-opt move contains the following steps:
i) Choosing two non-adjacent edges (i,i+1)(i,i+1) and (j,j+1)(j,j+1) from the cycle;
ii) Removing these two edges, and replacing them with new edges (i,j)(i,j) and (i+1,j+1)(i+1,j+1), forming a new cycle PP'.
If the new cycle obtained by the 2-opt move is shorter than the current cycle, updating the current cycle as the new cycle.
(3) Repeating the step (2) until no further improvement can be made by applying 2-opt moves.
Here is an illustration of a 2-opt move.
图片 1.png

Which of the following statements is true?

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

分数 3
作者 陈越
单位

In the theory of parallel algorithms using PRAM, which one of the following statements is FALSE?

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

分数 3
作者 陈越
单位

Consider two parallel algorithms for the same problem, with a total of Wi(n)W_i(n) operations in Ti(n)T_i(n) time (i=1,2i=1, 2). If W1(n)=O(n)W_1(n)=O(n), T1(n)=O(n)T_1(n)=O(n), and W2(n)=O(nlogn)W_2(n)=O(n\log n), T2(n)=O(logn)T_2(n)=O(\log n). Then:

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

分数 3
作者 陈越
单位

Suppose we have 4 types of fruit for 3 monkeys. Each monkey has its favorite types of fruit, and the matrix t.PNG gives the corresponding relations between the monkeys and fruits -- that is, tij=1t_{ij} = 1 means the iithe monkey loves the jjth type of fruit, or 00 means the opposite. Use backtracking to find a way to send each monkey its favorite fruit, with the following restrictions:

  1. one monkey may get only one type of fruit; and
  2. one type of fruit can be sent to at most one monkey.

Which one of the following game trees corresponds to a backtracking process?
Note: the black nodes are the ones being pruned, and the white ones are never visited. The nodes with a flag correspond to the solution.

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

分数 3
作者 陈昊
单位

There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color changes. We shall prove that any sequence of mm RB-INSERT and RB-DELETE operations on an initially empty red-black tree causes O(m)O(m) structural modifications in the worst case. We count the structural modifications in each step (e.g. Case 1 in RB-DELETION) as one unit operation (cost = 1).

We define the weight of each node based on its state, and the potential of the Red-Black Tree TT is represented by the following function:

Φ(T)=xTg(x)\Phi(T) = \sum_{x\in T} g(x)

where g(x)g(x) is calculated for all nodes xTx \in T of the Red-Black Tree.

We define the weight of a red node xx as g(x)=0g(x) = 0.

For black nodes, which of the following definitions work?

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

分数 3
作者 陈昊
单位

Suppose that replacement selection is applied in external sorting to generate longer runs with a priority queue of size 4. Given the sequence of numbers {51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100}. How many of the following states are TRUE?

  • 4 runs will be generated

  • 14 is in the first runs

  • The length of the longest run is 9

  • 90 is in the last runs

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

分数 3
作者 丁尧相
单位

If a binomial queue consists of 3 trees, which of the following numbers can NOT be its number of nodes?

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

分数 3
作者 丁尧相
单位

A key advantage of binomial queue is that its amortized time cost of insertion is O(1)O(1). To prove this argument, a key observation is that if inserting one new key in the queue takes time cost cc, it will lead to increasing mm trees in the queue, where mm equals to

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

分数 3
作者 丁尧相
单位

What is the tightest solution to the recurrent function T(n)=2T(n/2)+nlognT(n) = 2T(n/2) + n\log n?

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

分数 3
作者 丁尧相
单位

How many of the following arguments are TRUE?

  1. In comparison to dynamic programming, divide-and-conquer algorithms are usually more suitable for problems with highly overlapping sub-problems.

  2. In the divide-and-conquer solution to the “closest pair of points in the plane” problem, sorting the points in both X and Y axes at the beginning of the whole algorithm is essential to achieve the O(nlogn)O(n\log n) time complexity.

  3. Consider the view point of treating function T(n)=aT(n/b)+ncT(n)=aT(n/b) + n^c as a recursion tree. If T(n)=O(nc)T(n) = O(n^c), then the time cost is dominated by the root of the tree.

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

分数 3
作者 杨洋
单位

Suppose a red-black tree TT contains N(N2)N (N \geq 2) internal nodes, we denote the height of TT as h(T)h(T) and the black-height of TT as bh(T)bh(T). Which of the following statements must be FALSE (assume the height of an empty tree is 0)?

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

分数 3
作者 叶德仕
单位

Merge the two skew heaps in the following figure. How many of the following statements is/are FALSE?

  • the null path length of 1 is 2
  • 12 is the left child of 6
  • the depths of 4 and 9 are the same
    skew.png
评测结果
答案正确
得分
3 分

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