问题 单项选择题

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说明该有向图一定()。

A.包含回路

B.是强连通图

C.是完全图

D.是有向树

答案

参考答案:A

解析:

[分析]: 本题考查图数据结构。

对有向图进行拓扑排序的方法如下:

(1)在AOV网中选择一个入度为0(没有前驱)的顶点且输出它。

(2)从网中删除该顶点及其与该顶点有关的所有边。

(3)重复上述两步,直至网中不存在入度为0的顶点为止。

执行的结果会有两种情况:一种是所有顶点已输出,此时整个拓扑排序完成,说明网中不存在回路;另一种是尚有未输出的顶点,剩余的顶点均有前驱顶点,表明网中存在回路,拓扑排序无法进行下去。

阅读理解

English breakfast is a very big meal —eggs, tomatoes, tea, coffee….

For many people lunch is a quick meal. In cities there are a lot of sandwich (三明治)bars ,where office workers can buy brown or white bread or a roll (面包卷),and then all kinds of salad(色拉)and meat or fish to go in the sandwich. School children can have a hot meal at school, but many just take a sandwich, a drink and some fruit from home.

“Tea” means two things. It is a drink and a meal , some people have afternoon tea, with sandwiches, cakes and a cup of tea.

They usually have the evening meal quite early, between six o’clock and eight o’clock, and often all the family eats together. On Sundays many families have a traditional(传统的)lunch. They have chicken, pork,… with potatoes ,vegetables…

The Englishmen like food from other countries too, such as French, Chinese, Italian and Indian. People often get take-away meals---they buy the food outside and then bring it home to eat.

小题1:Many people in England have a ______ breakfast and a _____ lunch.

A.fast; small

B.little; slow

C.big; quick

D.slow; big小题2:In _____ there are a lot of sandwich bars.

A.small towns

B.villages

C.countries

D.cities小题3:The office workers can buy the ______ bread for lunch.

A.white

B.black

C.red

D.orange小题4:What don’t they have when they have afternoon tea in this passage?

A.Sandwiches

B.Chicken

C.Cakes

D.A cup of tea小题5:When they get a take-away meal , they have it _______

A.at home

B.in the school

C.outside

D.in the bars

判断题