给出深度优先搜索（dfs）进行拓扑排序的算法如下，则空白处应填入____

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路)()

A.对

B.错

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路)。( )【中南大学2003一、9(1分)】

此题为判断题(对，错)。

下面给出了部分背包问题的贪心算法的伪代码，其中空白处应分别填入 输入：商品数量,各商品的价值,各商品的体积，背包容量输出：商品价格的最大值 计算商品性价比并按降序排序 //分别表示性价比第大的商品的性价比、价格和体积//根据贪心策略求解 whiledo ifthen 选择商品end else 选择体积的商品endend return

A、

B、

C、

D、

对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为O的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2)定义在算法中使用的全局辅助数组。 (3)写出在遍历图的同时进行拓扑排序的算法。

快速排序算法的关键为数组的划分，下面给出了一种划分数组的方法，其中空白处应填入____ 输入：数组，起始位置，终止位置输出：划分位置whiledo whileanddoend ifthenend whileanddoend ifthenend endreturn

A、

B、

C、

D、

对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中的所有顶点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义(结构)。(4分) (2)定义在算法中使用的全局辅助数组。(4分) (3)写出在遍历图的同时进行拓扑排序的算法。(10分)【东北大学1999五(1 8分)】【清华大学1997一(18分)】【中科院研究生院2003十一(15分)】

阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。

【说明】

为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)

[算法]

1．变量声明

X: Data Type

i,j,low, high,mid,r:0..n

2．每循环一次插入一个R[i]

循环：i以1为步长，从2到n，反复执行。

(1)准备

X←R[i];(1); high←i-1;

(2)找插入位置

循环：当(2)时，反复执行。

(3)

若X.key＜R[mid].key

则high←mid-1;

否则 (4)

(3)后移

循环：j以-1为步长，从(5)，反复执行。

R[j+1]←R[j]

(4)插入

R[low]←X

3．算法结束

假设有向图采用邻接表表示法，其定义如下：

typedef struct{

VertexNode adjlist[MaxVertexNum];

int n,e; //图的当前顶点数和弧数

}ALGraph //邻接表类型

下列算法f33的功能是，对以邻接表表示的有向图进行拓扑排序。

(1)阅读算法f33，并在空缺处填入合适的内容，使其成为一个完整的算法；

(2)对于如图所示的邻接表，将执行算法f33后的topo[]结果填入给定的数组中。

void f33(ALGraph G,int topo []){

int i,j,k,count=0;

int indegree[MaxVertexNum];

EdgeNode*p;//p为指向边表结点的指针

Queue Q;//Q为队列

FindIndegree(G,indegree);//求各顶点的入

度，并置于入度向量indegree

InitQueue(&Q);

for(i=0;i＜G.n;i++)

if(!indegree[i])EnQueue(&Q,i);

while(!QueueEmpty(&Q)){

j=[ ① ];

topo[j]=++count

for(p=G.adjlist[j].firstedge;p;p=p—＞next){

k=p—＞adjvex;

if(!(--indegree[k]))[ ② ];

}

}

if(count＜G.n)printf("\n图G中存在有环路");

}

①

②

●试题二

阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：

【流程图】

图3流程图

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。

【算法】

void sort (int A[]， int 1，int H){

if ( L<H){

k=p(A，L，R)；//p()返回基准数在数组A中的下标

sort( (4) )；//小于基准数的元素排序

sort( (5) )；//大于基准数的元素排序

}

}