问题 单项选择题

拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系,()为图8-7所示有向图的一个拓扑序列。

A.1 2 3 4 5 6 7

B.1 5 2 6 3 7 4

C.5 1 2 6 3 4 7

D.5 1 2 3 7 6 4

答案

参考答案:B

解析:

拓扑排序是将AOV网中所有顶点排成一个线性序列,该序列满足:若在AOV网中从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。拓扑排序即指对AOV网构造拓扑序列的操作。

对AOV网进行拓扑排序的方法如下。

(1)在AOV网中选择一个入度为零的顶点且输出它;

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

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

若在AOV网中考查各项点的出度,并按下列步骤进行排序,则称为逆拓扑排序。

(1)在AOV网中选择一个没有后继的顶点且输出它;

(2)从网中删除该顶点,并删去所有到达该顶点的弧;

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

阅读理解与欣赏

阅读《陈涉世家》一文的节选文字,回答文后题目。(16分)

陈胜者,阳城人也,字涉。吴广者,阳夏人也,字叔。陈涉少时,尝与人佣耕,辍耕之垄上,怅恨久之,曰:“苟富贵,无相忘。”佣者笑而应曰:“若为佣耕,何富贵也?”陈涉太息曰:“嗟乎!燕雀安知鸿鹄之志哉!”

二世元年七月,发闾左適戍渔阳,九百人屯大泽乡。陈胜、吴广皆次当行,为屯长。会天大雨,道不通,度已失期。失期,法皆斩。陈胜、吴广乃谋曰:“今亡亦死,举大计亦死;等死,死国可乎?”陈胜曰:“天下苦秦久矣。吾闻二世少子也,不当立,当立者乃公子扶苏。扶苏以数谏故,上使外将兵。今或闻无罪,二世杀之。百姓多闻其贤,未知其死也。项燕为楚将,数有功,爱士卒,楚人怜之。或以为死,或以为亡。今诚以吾众诈自称公子扶苏、项燕,为天下唱,宜多应者。”吴广以为然。乃行卜。卜者知其指意,曰:“足下事皆成,有功。然足下卜之鬼乎?”陈胜、吴广喜,念鬼,曰:“此教我先威众耳。”乃丹书帛曰“陈胜王”,置人所罾鱼腹中。卒买鱼烹食,得鱼腹中书,固以怪之矣。又间令吴广之次所旁丛祠中,夜篝火,狐鸣呼曰:“大楚兴,陈胜王”。卒皆夜惊恐。旦日,卒中往往语,皆指目陈胜。

小题1: 解释下面句子中划线的词语。(4分)

(1)天大雨 (         )            (2)已失期 (         )

(3)今亦死 (         )             (4)陈胜 (         )

小题2:用现代汉语翻译下列句子。(6分)

①陈涉太息曰:“嗟乎!燕雀安知鸿鹄之志哉!”

②等死,死国可乎?

③扶苏以数谏故,上使外将兵。

小题3:你怎样看待陈胜所说的“苟富贵,无相忘”这句话?(2分)

小题4:陈胜、吴广的起义有偶然性,也有必然性。根据本段内容,作简要分析。(4分)

偶然性:                                                           

必然性:                                                           

判断题