问题 判断题

华侨是我们的同胞,血浓于水,所以导游人员可向华侨介绍他们希望知道的所有情况,帮助他们更多的了解祖国。

答案

参考答案:

填空题

阅读下列说明,回答问题1和问题2,将解答填入对应栏内。

[说明]

现需要在某城市中选择一个社区建一个大型超市,使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。

现设计一个算法来找到该大型超市的最佳位置,即在给定图中选择一个顶点,使该顶点到其他各顶点的最短路径之和最小。首先,算法需要求出每个顶点到其他任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后,对每个顶点计算其他各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。

[问题1]

本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V=1,2,…,n),W=Wijn*n为权重矩阵。

为从顶点i到顶点j的一条最短路径的权重。

当k=0时,不存在中间顶点,因此;当k>0时,该最短路径上所有的中间顶点均属于集合1,2,…,k。

若中间顶点包括顶点k,则;若中间顶点不包括顶点k,则

于是得到如下递归式:

因为对于任意路径,所有的中间顶点都在集合1,2,…,n内,因此矩阵给出了任意两个顶点之间的最短路径,即对所有i,j∈V,表示顶点i到顶点j的最短路径。

下面是求解该问题的伪代码,请填充其中的空缺(1)~(6)。

伪代码中的主要变量说明如下:

W:权重矩阵;

n:图的顶点个数;

SP:最短路径权重之和数组,SP[i]表示顶点i到其他各顶点的最短路径权重之和,i取值为1~n;

min_SP:最小的最短路径权重之和;

min_v:具有最小的最短路径权重之和的顶点;

i:循环控制变量;

j:循环控制变量;

k:循环控制变量。

LOCATE -SHC)PPINGNALL(W,n)

1 D(0)=W

2 for (1)

3 for i=1 to n

4 for j=1 to n

5 if

6 (2)

7 else

8 (3)

9 for i=1 to n

10 SP[i]=0

11 for j=1 to n

12 (4)

13 min_SP=SP[1]

14 (5)

15 for i=2 to n

16 if min_SP>SP[i]

17 min_SP=SP[i]

18 min_v=i

19 return (6)

[问题2]

问题1中伪代码的时间复杂度为 (7) (用O符号表示)。

(4)处填()。

阅读理解

A young woman carrying a three-year-old child got on a bus. The conductor hurried to give her a warm welcome and then kindly asked the other passengers to make more room for the woman and her child. On seeing this, people began to talk. "You know this conductor used to be very rude. Now suddenly he has changed his bad behavior , "said a middle-aged man.

"Yes, he should be praised and we must write a letter to the company," said a second passenger. "That's right," another lady said, "I wish a newspaper reporter were here so that more people could learn from this conductor. "

Just then a gentleman who looked like a teacher turned to the conductor and said , "Excuse me, but can I know your name, please? Your excellent service must be praised..."

Before he could open his mouth, the three-year-old child sitting on the young woman's lap interrupted, "I know his name. I call him Dad."

56. One passenger suggested writing a letter to the com­pany to ______    .

A. make a demand for more buses         B. thank the conductor for his good service

C. criticize the conductor for his rude behavior

D. invite a newspaper reporter to write about the conductor

57. What was the gentleman?

A. A teacher.                 B. A newspaper reporter.

C. Not known from the story.    D. The conductor's friend from his company.

58. The word "him" in the last paragraph refers to _______.

A. the gentleman    B. the conductor     C. the middle-aged man     D. the three-year-old child

59. It is clear from the story that the conductor _______.

A. has changed his attitude towards his work     B. has now been kind and polite to all passengers

C. has not changed his rude behavior to passen­gers

D. has now been kind and polite to women with children