浙江大学2021–2022学年秋冬学期 《数据结构基础》课程期末考试试卷
R1-1

Quadratic probing isn't equivalent to double hashing with a secondary hash function of Hash2(k)=kHash_2 (k)=k.

(2分)
作者
朱建科
单位
浙江大学
1-1
答案正确
(2 分)

R1-2

In an undirected acyclic graph G with 3 connected components, the number of edges will be 4 less than the number of vertices.

(2分)
作者
何钦铭
单位
浙江大学
1-2
答案正确
(2 分)

R1-3

Kruskal's minimum spanning tree algorithm implemented by disjoint set with union-by-rank strategy has O(ElogE)O(|E| log⁡|E| ) time complexity. Further optimization by introducing path compression improves it to O(Eα(E,V))O(|E|α(|E|,|V|)) where αα is the functional inverse of Ackermann's function.

(2分)
作者
田文杰
单位
浙江大学
1-3
答案错误
(0 分)

R1-4

Given a max-heap with unique keys, there are at least d-1 keys larger than any key in level d (the root level is 1).

(2分)
作者
陈翔
单位
浙江大学
1-4
答案正确
(2 分)

R1-5

Suppose that an array is used to store a circular queue, the value of front must be less than or equal to the value of rear.

(2分)
作者
ganhonghua
单位
浙江大学
1-5
答案正确
(2 分)

R1-6

In a tree of degree 3, we have n2+n3n0n_2+n_3 \ge n_0, where nin_i is the number of degree ii nodes for 0i30\le i\le 3.

(2分)
作者
陈越
单位
浙江大学
1-6
答案正确
(2 分)

R1-7

{ 5, 2, 9, 18, 14, 16, 72 } cannot be the result after the second run of quick sort (assuming the pivot is chosen randomly).

(2分)
作者
郑友怡
单位
浙江大学
1-7
答案正确
(2 分)

R1-8

Suppose we are now sorting an initial array (8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6)using Shellsort. If the sorting result after the first run is (1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8) and that after the second run is (1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9), then the increments used for the two sortings are 5 and 2.

(2分)
作者
郑友怡
单位
浙江大学
1-8
答案正确
(2 分)

R1-9

The FirstChild-NextSibling representation of a tree is unique.

(2分)
作者
陈越
单位
浙江大学
1-9
答案正确
(2 分)

R1-10

Let nn be a non-negative integer representing the size of input. The time complexity of the following piece of code is Θ(n2)\Theta (n^2).

int func(int n){
    int sum = 0;
        for(int i = 1; i < n; i *= 2)
            for(int j = 0; j < i; j++)
                sum++;
    return sum;
}
(2分)
作者
ganhonghua
单位
浙江大学
1-10
答案正确
(2 分)