问题 单项选择题

迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题,该算法运用了()算法策略。

A.贪心

B.分而治之

C.动态规划

D.试探+回溯

答案

参考答案:A

解析:

[分析]: 本题考查最短路径问题。

贪心算法通过一系列的选择得到问题的解。它所做出的每一次选择是当前状态下局部最优选择,即贪心选择。

分治法的基本思想是把大问题分解成一些较小的问题,然后由小问题的解方便地构造出大问题的解。

动态规划策略设计算法利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。

迪杰斯特拉(Dijkstra)提出的按路径长度递增的次序产生最短路径的算法,其思想是把网中所有的顶点分成两个集合S和T,S集合的初态只包含顶点v0,T集合的初态为网中除v0之外的所有顶点。凡以v0为源点,已经确定了最短路径的终点并入S集合中;顶点集合厂则是尚未确定最短路径的顶点的集合。按各顶点与v0间最短路径长度递增的次序,逐个把T集合中的顶点加入到S集合中去,使得从v0到S集合中各顶点的路径长度始终不大于从v0到了集合中各顶点的路径长度。

从迪杰斯特拉算法求最短路径的过程可知,其算法策略属于贪心策略。

解答题
阅读理解

Britain and other nations should be well on with the building of huge industrial complexes (工业园区)for the recycling of wastes within fifteen years. The word rubbish could lose its meaning because everything that goes into the dumps would be made into something useful. Even the most dangerous and unpleasant wastes would provide energy if nothing else.

The latest project is to take a city of around half a million inhabitants (居民) and discover exactly what raw materials go into and what go out. The aim is to find out how much of these raw materials could be provided if a plant for recycling waste was built just outside the city. This plant would recycle not only metal such as steel, lead (铅) and copper, but also paper and rubber as well.

Another new project is being set up to discover the best way of sorting and separating the rubbish. When this project is completed, the rubbish will be processed  like this: First, it will pass through sharp metal bars which will tear open the plastic bags in which rubbish is usually packed; then it will pass through a powerful fan to separate the lightest elements from the heavy solids; after that rollers will break up everything that can be broken. Finally, the rubbish will pass under magnets (磁铁), which will remove the bits of iron and steel; the rubber and plastic will then be sorted out in the final stage.

The first full-scale (完全的) giant recycling plants are perhaps fifteen years away. Indeed, with the growing cost of transporting rubbish to more distant dumps, some big cities will be forced to build their own recycling plants before long.

64. The underlined phrase “be well on with…” (Para. 1) most probably means _______.

A. have completed what was started      B. get ready to start

C. put an end to                               D. have achieved a great deal in

65. What is NOT mentioned as a part of the recycling process described in paragraph three?

A. Sharpening metal bars.            B. Sorting out small pieces of metal.

C. Breaking up whatever is breakable.   D. Separating lightest elements from the heavy ones.

66. What’s the main reason for big cities to build their own recycling plants?

A. To get raw materials locally.             B. To deal with wastes in a better way.

C. To get iron and steel from those plants.     D. To protect the environment from pollution.

67. The first full-scale huge recycling plants ______.

A. will be built fifteen years later      

B. began to operate fifteen years ago

C. will probably be in operation in fifteen years

D. will probably take less than fifteen years to build

68. The passage is mainly about _______. 

A. a cheap way to get energy       B. the location of recycling plants 

C. new ways of recycling          D. the probability of city environment