问题 问答题

阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。

  【说明】

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

  (1)初始时拓扑序列为空;

  (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;

  (3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。

   函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号, 顶点序列为v1,v2,…,vn,图G采用邻接表表示,其数据类型定义如下:

  

  例如,某有向图G如图4-1所示,其邻接表如图4-2所示。

  

  函数TopSort中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如下表所示:

  

  【C代码】

  

  

【问题3】(4分)

  设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度是__(6)__。

  若有向图采用邻接矩阵表示(例如,图4-1所示有向图的邻接矩阵如图4-3所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时间复杂度是__(7)__。

  

答案

参考答案:

完形填空
When Amy wrote her first novel in secondary school, she never imagined(想象) that she would become a writer one day. Like many      writers on the Internet, the       woman got into this online world accidentally(偶然地).
Three years ago, Amy worked in a medical industry. Her job kept her busy for six months and left her almost        to do for the rest of the year. To fill the time, she started writing       on the Internet. Her first novel was about her neighbors and their life that        is familiar with. Amy has been interested in writing           she was a child. At first, she just wanted to share her novels       people she knew. Then one day an editor of a famous website emailed her, asking her       she would like to sell the electronic copyright(授权) of one of her novels. She        at once and the novel was moved to the VIP section of the website. She got $ 1,500 for that.
Now Amy is a full-time      . So far her eight novels have come out(出版) online, and five of them were printed. “The Internet       me famous and brought me        ,” she said. “I earn much more money now— about $60,000 a year. I am     with my career, but there is one problem — that my talent might run out after five years and I’ll have to     to work in the medical industry.” “Before that day comes, I’ll keep     for the readers with my light and close-to-everyday-life writing style,” said Amy with a smile.
小题1:
A.otherB.othersC.anotherD.the other
小题2:
A.28-year-oldB.28-years-oldC.28 years oldD.28-year old
小题3:
A.somethingB.anythingC.everythingD.nothing
小题4:
A.reportsB.novelsC.diariesD.plays
小题5:
A.herB.herselfC.sheD.hers
小题6:
A.whenB.whileC.sinceD.until
小题7:
A.aboutB.ofC.toD.with
小题8:
A.thatB.ifC.whyD.how often
小题9:
A.agreedB.disagreedC.refusedD.left
小题10:
A.housewifeB.editorC.saleswomanD.writer
小题11:
A.will makeB.makingC.madeD.makes
小题12:
A.successB.succeedC.successfulD.successfully
小题13:
A.unhappyB.angryC.happyD.proud
小题14:
A.comeB.goC.returnD.get
小题15:
A.to writeB.writingC.writeD.written
单项选择题