已知DAG图中,顶点i与j之间不存在先决关系,如果交换拓扑序列中i和j的位置后得到的序列一定也是拓扑序列

已知DAG图中,顶点i与j之间不存在先决关系,如果交换拓扑序列中i和j的位置后得到的序列一定也是拓扑序列


参考答案和解析
错误

相关考题:

在有向无环图中,若存在一条从顶点i到顶点j的弧,则在顶点的拓扑序列中,顶点i与顶点j的先后次序是()。

若有向图中含有一个或多个环,则其顶点间不存在拓扑序列。() 此题为判断题(对,错)。

●下面算法是实现对n个整数的序列进行选择排序,其中序列的"长度"n为问题的规模。该算法的时间复杂度为 (23) 。void select_sort(int a[],int n){//将a中整数序列重新排列成从小到大有序的整数序列for(i=0;in-1;++i){j=i;for(k=i+1;kn;++k)if(a[k]a[j])j=k;if(j!=i){w=a[j];a[j]=a[i];a[i]=w;}}//select- sort(23) A.O(n3)B.O(n2)C.O(n)D.O(n4)

拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系,(52)为下图所示有向图的一个拓扑序列。A.1 2 3 4 5 6 7B.1 5 2 6 3 7 4C.5 1 2 6 3 4 7D.5 1 2 3 7 6 4

● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点 vi 必然在顶点 vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说明该有向图一定 (57)(57)A. 包含回路B. 是强连通图C. 是完全图D. 是有向树

已知某二叉树的前序遍历序列为:C,B,F,E,G,A,D,H,I,J;中序遍历序列为:F,B,G,E,C,H,D,I,J,A;该二叉树的后序遍历序列为:()。

阅读以下说明和C代码,将应填入(n)处的字句写在对应栏内。【说明】将一正整数序列{K1,K2,…,K9}重新排列成一个新的序列,新序列中,比K1小的数都在K1的前面(左面),比K1大的数都在K1的后面(右面),最后调用writeDat()函数的新序列输出到文件out.dat中。在程序中已给出了10个序列,每个序列有9个正整数,并存入数组a[10][9]中,分别求出这10个新序列。例:序列{6,8,9,1,2,5,4,7,3}经重排后成为{3,4,5,2,1,6,8,9,7}【函数】include < stdio. h >include < conio. h >void jsValue( int a [10] [9] ){ int i,j,k,n,temp;int b[9];for(i=0;i<10;i++){ temp=a[i] [0];k=8;n=0;for(j=8;j=0;j--){ if(temp < a[i] [j]) (1)=a[i][j];if(temp >a[i] [j]) (2)=a[i][j];if(temp =a[i] [j]) (3)= temp;}for(j=0;j<9;j++) a[i][j] =b[j];}}void main( )int a[10] [9] = {{6,8,9,1,2,5,4,7,3},{3,5,8,9,1,2,6,4,7},{8,2,1,9,3,5,4,6,7}, {3,5,1,2,9,8,6,7,4},{4,7,8,9,1,2,5,3,6}, {4,7,3,5,1,2,6,8,9},{9,1,3,5,8,6,2,4,7}, {2,6,1,9,8,3,5,7,4},{5,3,7,9,1,8,2,6,4}, {7,1,3,2,5,8,9,4,6}};int i,j;(4);for(i=0;i<10;i++) {for(j=0;j<9;j++) {printf("%d",a[i] [j] );if((5))printf(",");}printf(" \n" );}getch( );}

已知一个栈的进栈序列是1,2,3,…,n,其输出序列的第一个元素是i(1≤i≤n),则第j(1≤j≤n)个出栈元素是()。 A.iB.n-iC.j-i+1D.不确定

任何有向图的顶点都可以排成拓扑有序序列,而且拓扑序列不唯一。() 此题为判断题(对,错)。

下面算法是实现对n个整数的序列进行选择排序,其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。 void select_sort(int a[],int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i=0;i<n-1;++i){ j=i; for(k=i+1;k<n;++k)if(a[k]<a[j])j=k; if(j!=i){w=a[j];a[j];a[i];a[i]=w} )//select_sortA.O(n2)B.O(n3)C.O(n4)D.O(n)

阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是:(1)初始时拓扑序列为空;(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为vl,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如图4-1所示,其邻接表如图4-2所示。函数TopSort中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如下表所示:【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=Gn;j++){ /*初始化*/topOrder[j]=0;inDegree[j]=0;}for(j=1;j=Gn;j++) /*求图G中各顶点的入度*/for(p=G.Vhead[j].firstarc;p;p=p-nextarc)inDegree[P-adjvex]+=1;for(j=i;j=G.n;J++) /*将图G中入度为0的顶点保存在队列中*/if(0==inDegree[j]) EnQueue(Q,j);while(! IsEmpty(Q)){(2); /*队头顶点出队列并用w保存该顶点的编号*/topOrder[k++]=w; /*将顶点W的所有邻接顶点的入度减l(模拟删除顶点w及该顶点出发的弧的操作)*/for(p=G.Vhead[w].firstarc;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)

下列语句序列执行后,j的值是( )。 int j=0; for (int i=3 i>0; i- -)j+=i;A.3B.4C.6D.5

下列语句序列执行后,j的值是( )。 int j=9,i=6; while(i-->3)--j;A.5B.6C.7D.8

对于n个元素的关键字序列K1,K2,…,Kn,若有Ki≤K2i≤且Ki≤2i+1(i=1,2,…,[n/2],2i+1≤n),则称其为小根堆。以下关于小根堆及其元素关系的叙述中,错误的是( )。A.关键字序列K1,K2,…,Kn呈非递减排序时一定为小根堆B.小根堆中的序列K1,K2,K4…,K2j(2j≤n)一定为非递减序列C.小根堆中元素K2i与K2i+1(2i≤n,2i+1≤n)之间的大小关系不能确定D.小根堆的最后一个元素一定是序列的最大元素

下列语句序列执行后,j的值是( )。 int j=3,i=2; while(--i!=i/j)j=j+2;A.2B.4C.6D.5

阅读以下说明和 C 代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基准值,然后根据基准值进行划分,从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列),然后再对左子序列和右子序列分别进行快速排序, 最终得到非递减的有序序列。 函数 quicksort(int a[],int n)实现了快速排序,其中,n 个整数构成的待排序列保存在数组元素 a[0]-a[n-1]中。【C 代码】 include stdio.h void quicksort(int a[] ,int n) { int i ,j; int pivot = a[0]; //设置基准值 i =0; j = n-l; while (i j) { while (ij (1)) j-- //大于基准值者保持在原位置 if (ij) { a[i]=a[j]; i++;} while (i,j (2)) i++; //不大于基准值者保持在原位置 if (ij) { a[j]=a[i]; j--;} } a[i] = pivot; //基准元素归位 if ( i1) (3) ; //递归地对左子序列进行快速排序 if ( n-i-11 ) (4) ; //递归地对右子序列进行快速排序 } int main () { int i,arr[ ] = {23,56,9,75,18,42,11,67}; quicksort ( (5) ); //调用 quicksort 对数组 arr[ ]进行排序 for( i=0; isizeof(arr) /sizeof(int); i++ ) printf( %d\t ,arr[i]) ; return 0; }

拓扑序列是有向无环图中所有顶点的一个线性序列,若有向图中存在弧或存在从顶点v到w的路径,则在该有向图的任一拓扑序列中,V一定在w之前。下面有向图的拓扑序列是( )A.41235B.43125C.42135D.41=325

拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图中的有向图, ( ) 不是其的一个拓扑序列。A.1526374B.1526734C.5123764D.5126374

阅读以下说明和C代码,填补代码中的空缺,将解答填入答题纸的对应栏内。[说明]对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基准值,然后根据基准值进行划分,从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列),然后再对左子序列和右子序列分别进行快速排序,最终得到非递减的有序序列。函数quicksort(int a[],int n)实现了快速排序,其中,n个整数构成的待排序列保存在数组元素a[0]~a[n-1]中。[C代码] #inclLade<stdi0.h> void quicksort(inta[], int n) { int i,j; int pivot=a[0]; //设置基准值 i=0; j=n-1; while (i<j){ while (i<1 //大于基准值者保持在原位置 if (i<j) { a[i] =a[j]; i++;} while(i<j //不大于基准值者保持在原位置 if (i<1) { a[j] =a[i]; 1--;} } a[i]=pivot; //基准元素归位 if (i>1 ) ______; //递归地对左孔序列进行快速排序 if (n-i-1>1 ) ______; //递归地对右孔序列进行快速排序 } int main() { int i, arr[]={23,56,9,75,18,42,11,67}; quicksort(______); //调用quicksort对数组arr[]进行排序 for( i=0; i<sizeof(arr)/sizeof(int); i++ ) printf("%d\t",arr[i]); return 0; }

若一个栈的输入序列为1,2,3…,n,输出序列的第一个元素是i,则第j个输出元素是()。A.i-j-1B.i-jC.j-i+lD.不确定

拓扑序列是有向无环图中所有顶点的一个线性序列,若有向图中存在弧或存在从顶点v到w的路径,则在该有向图的任一拓扑序列中,v一定在w之前。下面有向图的拓扑序列是( )。A.41235B.43125C.42135D.41325

在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。

通过拓扑排序能够得到拓扑序列的图一定是一个()的图。

在一个有向图中,若存在弧,则在其拓扑序列中,顶点vi,vj,vk的相对次序为()。

不存在拓扑序列的()是图中存在回路。

如果一个有向图不存在(),则该图的全部顶点可以排列成一个拓扑序列。

若Aj-i-I=0,根据推论1:n阶递推关系式产生的任意序列的周期是什么?()A、ijB、j-iC、j+iD、j/i

填空题不存在拓扑序列的()是图中存在回路。