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

Given a hash table of size 13 and the hash function h(x)=x%13h(x)=x\%13. double hashing is used to solve collisions with h(x)=(h(x)+ih2(x))%13h(x) = (h(x) + ih_2(x)) \% 13 for i=1,2,,12i = 1,2,…,12, where h2(x)=(x%11)+1h_2(x) = (x \% 11) + 1. After filling in the hash table one by one with input sequence {92,81,58,21,57,45,161,38,117}\{92,81,58,21,57,45,161,38,117\}, which number is placed in the position of index 6?

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

R2-2

How many articulation points are there in the undirected graph below?

51c0b049-8a57-4d23-88c7-cb678964feb5.png

(3分)
作者
田文杰
单位
浙江大学
2-2
答案正确
(3 分)

R2-3

A binary tree with 2825 nodes must have a height ____. (Assume the height of a single node tree is 0.)

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

R2-4

Let nn be a non-negative integer representing the size of input. The time complexity of the following piece of code is:

void func(int n){
  int i = 0;

  while(i * i * i <= n)
    i++;
}
(3分)
作者
ganhonghua
单位
浙江大学
2-4
答案正确
(3 分)

R2-5

A "full tree" of degree 3 (every non-leaf node has 3 children) has 61 nodes. Then its height hh is at most ____. Note: h=0h=0 for a single node tree.

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

R2-6

Insert {18,23,4,26,33,31,17,39}\{18, 23, 4, 26, 33, 31,17, 39\} one by one into a hash table of size 13 with the hash function H(x)=x%13H(x)=x\%13, and linear probing is used to resolve collisions. What is the loading density when the first collision occurs?

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

R2-7

Given a weighted undirected graph as shown below, with a given starting vertex. Which of the following is a possible sequence of edges collected by Prim's minimum spanning tree algorithm?

65d7c051-a542-4368-aa08-101c426528f6.png

(3分)
作者
田文杰
单位
浙江大学
2-7
答案正确
(3 分)

R2-8

Let us convert a general tree T into a binary tree BT. Suppose that there are n0n_0 leaf nodes in T and m0m_0 leaf nodes in BT. Which of the following relationship between n0n_0 and m0m_0 is true?

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

R2-9

To obtain an ascending sequence, which of the following sorting methods gives {16, 17, 20, 7, 8, 10, 28, 5, 3} after 2 runs?

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

R2-10

Which of the following is the sufficient and necessary condition that an undirected connected graph has Euler path or circuit?

(3分)
作者
田文杰
单位
浙江大学
2-10
答案正确
(3 分)

R2-11

Which one of the following statement is FALSE about a tree?

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

R2-12

If a complete binary tree with 1000 nodes is represented by an array (root index is 1), then the index of the lowest (deepest) common ancestor of the node at index 900 and the node at index 470 is ____.

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

R2-13

When Dijkstra's algorithm is used to find the shortest paths from v1v_1 to every other vertices in an undirected graph G, a distance set dist[v]dist[v] is maintained for every vertex vv, as the shortest distance from v1v_1 to vv, passing through only the vertices whose shortest path to v1v_1 has been determined.

Suppose that the destinations are obtained in the order of { v2v_2, v3v_3, \cdots, vnv_n }. If there is a vertex ww in G so that dist[w]dist[w] is decreased during every iteration (except the last one) of the algorithm, how many statements of the following are correct?

(1) ww is vnv_n.

(2) ww is adjacent to every other vertices.

(3) (v1v_1, ww) (if it exists) is the longest edge among all the edges that are adjacent to ww.

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

R2-14

Which sorting method can find the final position of at least one element within the sorted list after each run?

  1. selection sort
  2. quick sort
  3. Shell sort
  4. merge sort
  5. heap sort
(3分)
作者
郑友怡
单位
浙江大学
2-14
答案正确
(3 分)

R2-15

Given a binary search tree as shown below, which one of the following insertion orders is valid?

0cbab85f-4ff5-432b-a9cc-9a4e1faad652.png

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

R2-16

For the given directed weighted graph of 6 vertices, which one of the following sets of vertices satisfies that the earliest completion time of every member is equal to its latest completion time?

0efa3545-bd03-499c-9827-09ebd86018cf.jpg

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

R2-17

For a given binary tree, if its post-order traversal sequence is { 3, 4, 1, 6, 2, 5 }, pre-order traversal sequence is { 5, 3, 2, 1, 4, 6 }, then its in-order traversal sequence must be:

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

R2-18

Push 4 characters oppo onto a stack. In how many different ways that we can pop these characters and still obtain oppo?

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

R2-19

Given a disjoint set S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } with array representation. S[i] is initialized to be -1, hence the height of root is 1. If union-by-rank (union-by-height and find-with-path-compression) is used, please list the resulting array after invoking Union(1,2), Union(3,4), Union(1,3), Union(3,5), Union(6,7), Union(1,7), Union(7,8), and Union(4,10).

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

R2-20

The inorder traversal sequence of the given tree is { 3, 1, 2, 5, 4 }. Which of the following statements is FALSE?

a.png

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