问题 问答题

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

[说明]

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

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

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

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

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

#define MAXVNUM 50 /*最大顶点数*/

typedef struct ArcNode /*表结点类型*/

int adjvex; /*邻接顶点编号*/

Struct ArcNode *nextarc; /*指示下一个邻接顶点*/

ArcNode;

typedef struct AdjList /*头结点类型*/

char vdata; /*顶点的数据信息*/

ArcNode *firstarc; /*指向邻接表的第一个表结点*/

AdjList;

typedef struct LinkedDigraph /*图的类型*/

int n; /*图中顶点个数*/

AdjList Vhead[MAXVNUM]; /*所有顶点的头结点数组*/

LinkedDigraph;

例如,某有向图G如图21-13所示,其邻接表如图21-14所示。

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

[C代码]

int *TopSort;(LinkedDigraph G)

ArcNode *p; /*临时指针,指示表结点*/

Queue Q; /*临时队列,保存入度为0的顶点编号*/

int k=0; /*临时变量,用作数组元素的下标*/

int j=0,w=0; /*临时变量,用作顶点编号*/

int *topOrder,*inDegree;

topOrder=(int *)malloc((G.n+1) * sizeof(int));/*存储拓扑序列中的顶点编号*/

inDegree=(int *)malloc((G.n+1) *siZeof(int));/*存储图G中各顶点的入度*/

if(!inDegree || !topOrder)return NULL;

(1) ; /*构造一个空队列*/

for(j=1;j<=G.n;j++) /*初始化*/

topOrder[j]=0; inDegree[j]=0;

for(j=1;j<=G.n;j++) /*求图G中各顶点的入度*/

for(p=G.Vhead[j].firstarc;p;p=p->nextarc)

inDegree[p->adjvex]+=1;

for(j=1;j<=G.n;j++) /*将图G中入度为0的顶点保存在队列中*/

if(0==inDegree[j]) EnQueue(&Q,j);

while(!IsEmpty(Q))

(2) ; /*队头顶点出队列并用W保存该顶点的编号*/

topOrder[k++]=w;

/*将顶点w的所有邻接顶点的入度减1(模拟删除顶点W及从该顶点出发的弧的操作)*/

for(p=G.Vhead[w].firstare;p;p=p->nextarc)

(3) -=1;

if(0== (4) ) EnQueue(&Q,p->adjvex);

/*for*/

/*while*/

free(inDegree);

if( (5) )

return NULL;

return topOrder;

/*TopSort*/

根据以上说明和C代码,填充C代码中的空(1)~(5)。

答案

参考答案:

(1)InitQueue(&Q)

(2)DeQueue(&Q,&w)

(3)inDegree[p->adjvex],或其等价形式

(4)inDegree[p->adjvex],或其等价形式

(5)k<Gn

选择题
单项选择题

問題Ⅰ 次の文章を読んで、後の問いに答えなさい。答えは、1 2 3 4から最も適当なものを一つ選びなさい。日本は、1950年代後半から経済の成長が(注1)いちじるしく、供給がどんどん増加し、国民一人あたりの(注2)所得(しょとく)も上がってきました。この時期を境にして、需要(じゅよう)と供給のバランスが(注3)逆転(ぎゃくてん)しました。現在の日本は完全に供給が過剰(かじょう)、需要が不足している時代です。 ものをつくる企業(きぎょう)は①こういうときにどうするでしょうか。なんとか買ってもらって、利益(りえき)を生(う)み出さねばなりません。他の企業に負けないで自分たちのつくった商品を買ってもらうためには、他とちがうこと、いわゆる②差別化をしなければいけません。 ( ③ )宣伝(せんでん)が必要になります。新聞の(注4)折(お)り込(こ)み広告、(注5)ダイレクトメールテレビといった(注6)メディアから毎日送られてくる(注7)コマーシャルを見ると④わかります。コマーシャルを熱心にする商品ほど消費者のとりあいがはげしい商品といってよいでしょう。 供給過剰状態(じょうたい)を(注8)解消(かいしょう)するには、需要を作り出せばよいわけです。ふつうの状態では消費者が100のものを消費するところを、いろいろな工夫によって120とか150とか、場合によっては、200も300も消費者が使うように(注9)仕向(しむ)けます。あるいは、10年間使えるものを、2年、3年で新しいものに買い替えたいと思うようにもってゆきます。 こうして消費者が買った商品がいずれごみになるわけですから、ものをつくること 売ること、そして買うこと 使うことはごみを出すことになります。⑤供給過剰を解消しようとする経済活動がそのままごみを増やす(注10)行為(こうい)になっているわけです。 しかし、それだけではありません。商品を買うと、いっしょについてくるものがあります。包み紙や入れものです。(注11)デザイン、形や色を工夫して、それ自体(じたい)で消費者の目をひくようにされています。商品の中身ではなく、外見(がいけん)でちがいを生み出そうとする生産者の努力が、ごみを増加させているのです。供給に対し、需要を増やそうとして実際それに成功しているのは( ⑥ )です。ごみを増やす(注12)主導権(しゅどうけん)をとっているのは( ⑦ )ではなく( ⑧ )といえるでしょう。                   (八太昭道『新版 ごみから地球を考える』による) (注1)いちじるしく:ここでは、非常に大きく(注2)所得(しょとく):収入(注3)逆転(ぎゃくてん):反対になること(注4)折(お)り込(こ)み広告:新聞などにはさまれている広告(注5)ダイレクトメール:郵便などで直接届く広告(注6)メディア:伝える手段、方法(注7)コマーシャル:テレビやラジオなどの放送を使って行う広告(注8)解消(かいしょう)する:なくす(注9)仕向(しむ)ける:そのようにさせる(注10)行為(こうい):行い、行動(注11)デザイン:ここでは、模様(もよう)や字の形、がらなど(注12)主導権(しゅどうけん)をとる:中心になってものごとを動かす

⑤「供給過剰(かじょう)を解消しようとする」のは、どれか。

A.消費者

B.企業(きぎょう)

C.コマーシャル

D.メディア