数据结构电子教案 第七章
同步综合练习及参考答案
（一）基础知识题
7．1 在图7.23所是的各无向图中：
（1）找出所有的简单环。
（2）那些图是连通图？对非连通图给出其连通分量。
（3）那些图是自由树（或森林）？ //自由树的概念见 7.4节
解：
（1）简单环
（a）(1 2 3 1)
(b)无
(c)（1 2 3 1）（2 3 4 2）（1 2 4 3 1）
(d)无
（2）连通图（a）（c）（d）
非连通图（b）的连通分量为
（3）自由树（d）
森林（b）
7．2 在图7.24所是的有向图中：
（1）该图是强连通的码？若不是，则给出其强连通分量。
（2）请给出所有简单路径及有向环。
（3）请给出每个顶点的度、入度和出度。
（4）请给出其邻接表、邻接矩阵及逆邻接表。
解：
（1）图是强连通的。
（2）所有简单路径（重复环未计算）
（v1）（v2）（v3）（v4）
(v1 v2)(v2 v3)(v3 v1)(v1 v4)(v4 v3)
(v1 v2 v3)(v2 v3 v1)(v3 v1 v4)(v3 v1 v2)(v1 v4 v3)(v4 v3 v1)
（v1 v2 v3 v1）（v2 v3 v1 v4）（v3 v1 v4 v3）（v4 v3 v1 v2）
有向环
（v1 v2 v4 v1）（v4 v1 v4 v4）
(3)各顶点的度、入度、和出度。
(4)①邻接表
①邻接矩阵集。
②逆邻接表
7．3 假设图的顶点是A,B,…,请根据下属的邻接矩阵画出相应的无向图或有向图。
解：
7．4 假设一颗完全二叉树包含A,B,…,G第七个结点，写出其邻接表和邻接矩阵。
解：
①完全二叉树
②邻接矩阵
③邻接表
7．5 对n各顶点的无向图和有向图，采用邻接矩阵和邻接表表示，如何判别下列有关问题：（1）图中有多少条边？
（2）任意两个顶点I和j是否有边相连？
（3）任意一个顶点的度是多少？
解：
①对于无向图
（1）图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的一半。
（2）若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。
（3）顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j.
②对于有向图
（1）图中边树等于邻接矩阵中的个数；邻接表中的出边表中结点数。
（2）若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连；
邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。
（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；
邻接表中i得出边表结点个数加上边表中结点I的个数之和。
7．6 n个顶点的连通图至少有几条边？强连通图呢？
解：
①n个顶点的连通图至少有n-1条边。
②n个顶点的强连通图至少有n条边。
7．7 DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？
解：
①DFS采用了栈；BFS采用了队列。
②采用BFS。
7．8画出以顶点v1为初始源点遍历图7。25所示的有向图所得到的DFS和BFS生成森林。
解：
7．9按顺序输入顶点对：（1，2），（1，6），（2，6），（1，4），（6，4），（1，3），（3，4），（6，5），（4，5），（1，5），（3，5），根据第7.2.2节中算法CreateALGraph画出相应的邻接表，并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。
解：
依题意构造有向图：
①邻接表
②DFS和BFS序列
DFS序列：4 5 3 1 6 2
BFS序列：4 5 3 6 1 2
③DFS和BFS生成树
DFS生成树
BFS生成树
7.10什么样的图其最小生成树是唯一的？用Prim和Kruskal求最小生成数的时间各为多少？他们分别适合于哪个图？
解：①具有n的结点，n-1条边的连通图其生成树是唯一的。
①的结点，e条边的无向连通图求最小生成树的时间分别为
Prim: O(n2); Kruskal:O(e*log2e)
②Prim适应于稠密图（点少边多）；Kruskal 适应于稀疏图（点多边少）。
7．11 对图7.26所示的连通图，请分别用Pirm和Kruskal 算法构造其最小生成树。
解：
①Pirm算法构造的生成树。
②Kruskal 算法构造的生成树。
7．12 对图7.27所示的有向网，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行短发过程中扩充红点集的每天次循环状态（类似表7.2）.
解：
7．13 是写出图7.28所示有向图的所有拓扑序列，并指出应用教材中 NonPrefirtTopSort 算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。
解：
NonPreFirtTopSort算法求得的序列是：
V0 V1 V5 V2 V6 V3 V4
其余序列有多种（略）。
7．14 什么样的DAG的拓扑序列是唯一的？
解：
设DAG中有n个结点，则当DAG中有至少n-1个不同的后继结点且至少有n-1个前缀结点时其拓扑序列是唯一的。
7．15 以V4为源点，给出用DFS搜索7.28的道德你拓扑序列。
V4 V3 V2 V0 V1 V5 V6.
（二）算法设计题
7．16 试在无向图的邻接矩阵和邻接表上实现如下算法：
（1）往图中插入一个顶点
（2）往图中插入一条边
（3）删去图中某顶点
（4）删去图中某条边
解：
（1）插入给定结点
①邻接表
viod Inser-ALGraph(ALGraph *G,int k)
{
int i;
G->n++;
for(i=G->n;i>k;i--)
{
G->adjlist[i].vertex=G->adjlist[i-1].vertex;
G->adjlist[i].firstedge=G->adjlist[i-1].Firstedge;
}
G->adjlist[i].vertex=getchar();
G->adjlist[i].firstedge=Null;
}
② 邻接矩阵
void Inser-Mgraph (mGraph *G,int k)
{int i,j;
G->n++;
for(i=G->n;i>k;i--)G->vexs[i]=G->vexs[i-1];
G->cexs[k]=getchar();
for(i=G->n;i>k;i--)
{ for(j=G->n;j>k;j--)
G->e[i][j]=G->e[i-1][j-1];
G->e[i][j]=0;
for(j=k-1;j>=0;j--)
G->e[i][j]=G->e[i-1][j];
}
for(j=G->n;j>=0;j--)G->e[i][j]=0;
for(i=k-1;i>=0;j--)
{ for(j=g->n;j>k;j--)
G->e[i][j]=G->e[i][j-1];
G->e[i][j]=0
}
}
⑵插入一条边
①邻接表
InsertLAGraph (ALGraph *G,int m,INT n)
{ EdgeNode *E;
EdgeNode *sm=new EdgeNode;
EdgeNode *sn=new Edgenode;
Sm->adjvex=n;sm->next=Null;
Sn->adjvex=m;sn->next=Null;
for(E=G->adjlist[m].firstedge;E!=NULL;E=E->next) { }
E=sm;
for(E=G->adjlist[n].firstedge;E!=NULL;E=E->next) { }
E=sn;
}
②邻接矩阵
void InsertLMGraph(mGraph *G,int m,int n)
{ G->e[m][n]=1;
}
（3）删除某结点
①邻接表
void DelVALGraph(ALGraph *g,int k)
{ int I;
G->n--;
EdgeNode *e *s;
for(E=G->adjlist[k].firstdge;E!=NULL;E=E->next)
{ for (s=G->adjlist[E->adjvxe].firstedge;E!=NULL;E->E->next)
if(s->adjvex==k)
{s=s->next;break;}
}
for(i=k;i
{ G->adjlist[i].vertex=G->adjlist[i+1].vextex;
G->adjlist[i].first[i].firstedge=G->adjlist[i+1].firstedge; }
}
②邻接矩阵
void delvMGraph(mGraph *G,int k)
{int i,j;
G->n--;
for(i=k;i<=g->n;i++) G->vexs[i]=G->vexs[i+1];
for(i=0;i for(j=k;j<=n;j++) G->e[i][j]=G->e[i][j]; for(i=k;i<=G->n;i++) {for(j=0;j for(j=k;j<=n;j++) G->e[i][j]=G->e[i+1][j]; } } (4)删除某条边 ①邻接表 void dellALGraph(ALGraph *G,int m,int n) {EdgeNode *s; for(S=G->adjlist[m].firstedge; s->adjvex!=k;s=s->next) s=s->next; for(s=G->adjlist[n].firstedge; s->adjvex!=k;s=s->next) s=s->next; } ②邻接矩阵 void InsertLMGraph(mGraph *G,int m,int n) {G->e[m][n]=0; G->e[n][m]=0; } 7.17 下面的伪代码是一个广度优先搜索算法,试以图7.29中的V4为源点执行该算法,请回答下述问题: (1)对图中顶点Vn+1,它需要入队多少次?它被重复访问多少次? (2)若要避免重复访问同一个顶点的错误,应如何修改此算法? Void BFS(ALGraph *G,int k) {//以下省略局部变量的说明,visited各分量初值为假 InitQueue(&Q); //置空队列 EnQueue(&Q,k); //k入队 While(!QueueEmpty(&Q)) {I=DeQueue(&Q); //v i出队 visited[I]=true //置访问标记// printf(“%c”,G->adjilist[i],vertes); //访问j for(p=G->adjilist[i],firstedge;p;p=p->adjves=j)//依次搜索v i的邻接点v j (不妨设p->adjves=j) if(!Visited[p->adjves]) //若v j未被访问 EnQueue(&Q,p->adjves); //vj入队 } //endwhile } //BFS 解： 对图中顶点v n+1,它需入队n次？它被重复访问n-1次。 若要避免重复访问同一个顶点的错误，应修改算法如下： Void BFS(ALGraph*G,int K) { /*以下省略局部变量得说明，visited各分量初值为假*/ InitQueue(&Q); /*置空队列*/ EnQueue(&Q,k); /*k队列*/ While(!QueueEmpty(&Q)) {I=DeQueue(&Q); /*vi出队*/ visited[I]=true /*置访问标记*/ printf(“%c”,G->adjilist[i],vertes);/*访问vi*/ for(p=G->adjlist[i],firstedge;p;p->adjves=j) /*依次搜索vi的邻接点vj（不妨设p->adjves=j）*/ if(!Vvisit[p->adjves]) /*若vj未访问过*/ { EnQueue(&Q,p->adjves); /*/vj入队*/ Visited[p->adjvex]=TRUE; } } /*endwhile*/ } /*BFS*/ 7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点v i和vj(I<>j)之间是否有路径。 解： /*基于邻接表方式*/ /*所有数据类型*/ #define maxvn 10 typedef struct node { int vertex; int vertex; setuct node *list; } vertexNode vertexNode *head[maxvn]; bool JUDGE(vertexNode *adjl[maxvn],int n,int j); /*深度优先搜索判别n个顶点的有向图中顶点I到顶点j是否存在路径*/ { int stack[maxvn]; bool visit[maxvm]; int top,k; vertexNODE *p; bool yes; for(k=1;k<=n;k++) visit[k]=false; top=1; stack[top]=i; visit[i]=True; yes=false; do{ p=adjl[stack[top]]; while(!p=NULL&&visit[p->vertex]p=p->link); if(p==NULL) top=top-1; /*p之后无邻接结点，退栈*/ else {i=p->vertex; /*p指向的顶点未访问*/ if(i==j) yes=true; else { visit[i]=true; top=top+1; stack[top]=i; } }while(top1=0&&!yes); return(yes); } 7．19 试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。解： ①/*以Vi为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int ) { int j; printf(“visit vertex:%c”,G->vexs[i]); visitcd[i]=True; for(j=0;j<=G->n;j++) if(G->edges[i][j]==1&&!visit[j]) { print(“edye:%d %d\n”,i,j); DESM(G,j); } } ②/*以VI为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int k) { int i,j; SETNULL(Q); /*置空队Q*/ Printf(‘%/“，G.vexs[k]); Visited[k]=True; /*标志Vk+1已经访问过*/ ENQUEUE(Q,k); /* 已经访问过的顶点如队列*/ While(!EMPTY(Q)) /*队列非空时执行*/ {i=DEQUEUE(Q); /*队头元素序号出队列*/ for(j=0;j {print(“edye:%d %d\n”,i,j); /*访问过的边*/ print(“%c\n”,G,vexs[j]); visited[j]=True; ENQUEUE(Q,j); /*访问过的顶点如队*/ } } } 7.20写一算法切连通分量的个数并输出各连通分量的顶点集。 解： /*修改DFS函数，每当使visited[i]=true时打印printf（“%D”，i）；可输出各连通分量顶点集。*/ {int i; int m=0; for(i=0;i visited[i]=False; for(i=0;i if(!visited[i]) {DFS(i); m++; printf(“comp end\n”); } printf(“共有m个连通分量”); } 7.21 设图中各边上的权值均相等，是以邻接矩阵和邻接表为存储结构，分别写出算法： （1）求顶点 Vi到Vj(i<>j)顶点的最短路径； （2）求源点Vi 到其余各顶点的最短路径。 要求输出路径上的所有顶点（提示：利用BFS遍历的思想） 解： 利用BFS的遍历思想，同时构造一棵树，使每个孩子结点均指向双亲，当搜索到目标结点时，则从目标回溯到根结点即可，具体算法如下： typedef struct node { int data; struct node *parent; }Tree; void Path(ALGraph,*G,int i,int j) /*以邻接点存储*/ { int k; /*求vi到vj的最短路径*/ CirQueue Q; /*将DataType改为 int */ EdyeNode P; InitQueue(&Q) /*队列初始化*/ Visit[i]=TRVE; /*源点*/ S=(tree)mallo((sizeof(Tree)); 新建一个结点 s->data=i /*树根*/ s->patent=NULL; EnQueue(&Q,i); /*入队列*/ While(!Queue Empty(&Q)) { k=DeQueue(&Q); p=G->dajlist[k]->firstdeye; while(P) { if(! Visited[p->adjvex]) { visited[p->adjvex]=TRVE; *S=(Tree*)mallo((sizeof(Tree)); /*新结点*/ s->data=p->adkvex; s->parent->data=k; EnQueue(&Q,p->adjvex); } /*end if */ if(p->adjvex==j)bread; /*已搜索到j点*/ p-=p->next; } /*end if */ if(p->adjvex==j)break; /*已搜索到j点，结束搜索*/ } /*end if */ while(s!=NULL) /*此时打印出来的路径为反序*/ { printf(“%d”,G->adjlist[s->data]->vertex) s=s->parent; } （2）求源点到其余各顶点最短路径，则可调用上面算法。 Void PathALL(ALGraph *G.int i) {int j, for(j=0;f if(j!=i) path(G,i,j); } 对于用邻接矩阵存储的图: (1)求顶点v i到顶点v j(i≠j)最短路径 算法思想，采用弗洛伊德算法，可表示为 A[K][i,j]=Min(A k-1[i,j],A k-1[i,k]+A k-1[k.j])(1<=i<=n,1<=j<=n) 其中k表示第k次迭代运算。A[0][i,j]=A[i,j]. #define MAXVEX 100 void floyd(a,c,n) /*c为已知邻接矩阵，a为待求矩阵，n为源点数*/ int a[MAXVEX][MAXVEX] c[MAXVEX][MAXVEX],n; {int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=c[i][j]; for(i=1;i<=n;i++) a[i][j]=0; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][k]+a[k][j] a[i][j]=a[i][k]+a[k][j]; } 7.22以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点v k的简单回路（若存在）。 解： 算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。 Void dfscycle (ALGrph *G,int V4) {int i,j,top=0,V=V4,found=0,w; int Visitde[100],cycle[100]; EdgeNode *P; i=1; cycle[i]=Vi /*从V是开始搜索*/ Visitde[v]==1; P=G[v]->firstedge; While(p!=NULL!!top>0)&&!found) { while(p!=NULL&&!found) if(p->adjvex==V4&&i<2)found=1; /*找到回路*/ else if(visited[p->adjvex]==0)p=p->next; /*找到下一个邻接点*/ elst {w=p->adjvex; /*记下路径，继续搜索*/ visited[w]=1; i++; cycle[i]=w; top++; stack[top]=p; p=G[w]->firstedge; } if(!found&&top>0) /*沿原路径退回后，另选路径进行搜索*/ { p=attack[top]; top--; p=p->next; i--; } } /*end while*/ if(found) {for(j=1;j<=i;j++) printf(“%d,”,cycle[j]); /*打印回路的顶点序列*/ printf(“%d,\n”,V); } else printf(“设有通过点V4的回路！\n”) } 7．23 写一算法求有向图的所有根（若存在），分析算法的时间复杂度。 解： 算法思想：以有向图的每一个结点为源点对圆进行搜索，若能搜索到每个结点。则该结点为根。否则不是。 Void searchroot （ALGraph *G） { int i; for(i=0;i {for(j=0;j visited[j]=false; /*标志向量初始化*/ DPS(G,i); /*以Vi为源点开始DPS搜索*/ } } void DPS(ALGtaph *G,int i) { int count=0; EdgeNode *P; Visited[i]=true; count ++; p=G->adjlist[i]->firstedge; while(p) {if(!Visited[p->adjvex]) DPS(G,p->adjvex); P=p->next; } if(count==G->n) /*该结点是根结点*/ printf(“%c”,G->adjlist[i]->vertex); } 7．24 改写7.5节的算法print,试输出的从源点到各终点的最短路径是正想。（提示：使用栈暂存路径）。 解： 使用栈暂存路径 void Ptint(PathP,Distance D) { int i,pre; seqstack *S; s->top=-1 /*置空栈*/ for(i=0;i {printf(“\n distanck:%d,Path;”,D[i]); /*输出终点I的最短距离*/ s->top++; s->stack[s->top]=i; /*i入栈*/ pre=p[i]; /*栈终点的前趋*/ while(s->top>1) {printf(“%d”,s->stack[s->top]); /*输出路径*/ s->top--; } /*end while */ } /*end for*/ } 7.24改写7.5节的算法print，使输出的从源点到各终点的最短路径是正向。（提示：使用栈暂存路径）。 解： 使用栈暂存路径 void Print(PathP,Distance D) { int ,pre; seqstack *s; s->top=-1 /*置空栈*/ for(i=0;i {printf(“\n distanck:%d,path:”,D[i]); /*输出终点i的最短距离*/ s->top++; s->stack[s->top]=i; /*I入栈*/ pre=p[i]; /*栈终点的前趋*/ while(pre!=-1) {s->top++; s->stack[s->top]=pre; /*路径入栈保存*/ pre=p[pre]; /*继续上溯前趋*/ } while(s->top>-1) {printf(“%d”,s->stack[s->top]); /*输出路径*/ s->top--; } /*end while*/ } /*end for*/ } 7.25 对7.6节的NonSuccFirstTopSort算法，分别以邻接矩阵和邻接表作为存储结构， 写出其具体算法，并分析算法的时间。 解： ①用逆邻接表作为G的存储结构。 Void NonSuccPirstTopSort(G) {int outdehree[maxvertexNum]; /*出度向量，Maxvertexnum>=G,n*/ seqstack S,T; /*应将栈中data向量改为int类型*/ int i,j,count=0; Edgenode *P; for(i=0;i outdegree[i]=0; for(p=G->adjlist[i]->firstedge;p;p->next) /*扫描的入边表*/ outdegree[p->adjvex]++; /*出度为1*/ Initstack(&S); /*置空栈*/ Initstack(&T); for(i=0;i if(outdegree[i]==0) push（&S,i） /*出度为零的顶点i入栈 */ while(!stackEmpty(&S)) /*栈非空，即图中有出度为0的顶点*/ {i=pop(&S); push(&T,i); count++; for(p=G->adjlist[i]->firstedge;P;p=p->next); /*扫描的i入边表*/ {j=p->adjvex; /*j是i的入边的 outdegree[j]--; /*j的出度减肥。相当于删去边 if(!outdegree[i]) /*j无后继*/ push(&S,j); }/*end for*/ } /*end while*/ if(count printf(“\n The Graph is not a DAG.\n”); /*图中有环，排序失败*/ else {while(!stackEmpty(&S)) /*输出拓扑序列*/ {i=po(&T);print(“%d”,G->adjlist[i]->vertex);} } } ②用邻接矩阵作为存储结构。 Void NoSucePirstTopSort(Mgraph *G) {seqstack s,T; int i,j,count=0; /*用i,j代表Vi,Vj*/ Initstack(&S); Initstack(&T); for(i=0;i for(j=0;j if(G->edges[i][j]= =0) push(&S,i); /*出度为0，入栈*/ while(!sruckEmpty(&S)) { i=po(&S); push(&T,i); count+ +; for(j=0;j G->edges[i][j]=0; /*修改邻接矩阵*/ for(i=0;i for(j=0;j if(G->edges[i][j]= =0) push(&S,i); } /*end while */ if(count printf(“\n The Graph is not a DAG.\n”); else {while(!stackEmpty(&T)) /*输出拓扑序列*/ {i=pop(&T); printf(“%d”,G->adjlist[i]->vertex); } } } 7.26设有向图一个DAG，试以邻接矩阵和邻接表作为存储结构，写出对7.6节的DFSTopSort求精的算法。问什么有向图不是DAG时，该算法不能正常工作？ 解： ①用邻接矩阵作为存储结构。 Void DPSTopSort(Mgraph*G,i,Setstack T) {int j; visited[i]=true; for(j=0;j if(G->edges[i][j]= =1) if(!visited[j]) DPSTopSort(G,j,T); Push(&T,i); /*从I出发的搜索已完成，保存i*/ } ②用邻接表作为存储结构。 Void DPSTopSort(ALGraph G,i,T) {int j; visited[i]=true; for(p=G->adjlist[i]->firstedge;p;p=p->next) if(!visited[p->adjvex]) DPSTopSort(G,p->adjvex,T); Push(&T,i); } 由于有向图不是DAG时，从某点出发的搜索将陷入循环状态，所以算法不能正常工作。 7．27 利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时，输出构成环的顶点。 解： 设有向图用邻接表存储 Void SearckCycle(ALGraph G) {int i; EdgeNode *P; for(i=0;i for(p=G->adjlist[i]->firstedge;p;p=p->next) /*扫描i的出边表*/ if(p->next=G->adjlist[i]->firstedge) /*存在环*/ printf(“%d”,G->adjlist[i]->vertex); } 第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。 数据库教案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 课程名称：《数据库原理》 选课课号：(2013-2014-2)-2022-1 课程性质：学科基础课（必修） 学时：48（理论教学）+ 8（上机） 教材：（1）数据库原理及应用.李明等编（西南交大出版社） （2）DataBase Design and Frost，John Day，CraigVan Slyke（清华大学出版社影印版） （3）数据库系统概论.王珊等编（中国人民大学出版社） 课程班级：工程力学11级，信息与计算科学11级1、2班 教室：西教1-310, 授课时间：1-12周，星期一1,2节，星期三 3,4节 授课教师：庞淑侠 考核方式：闭卷 总评成绩=平时成绩(20%) + 期末考试成绩(80%) 参考书 1. 赵艳铎等(译). 数据库原理(第5版). 清华大学出版社, 2011 2. 杨冬青等(译). 数据库系统概念(第6版). 机械工业出版社, 2012 3. 金名等(译). 数据库系统设计、实现与管理(第8版). 清华大学出版社, 2012 4. 刘智勇. SQL Server 2008宝典. 电子工业出版社,2010 5. 苏金国等(译). Oracle Database 9i10g11g人民邮电出版社, 2011 6. 李华. PowerBuilder程序设计教程. 清华大学出版社,2010 第 1 次课授课时间：2013年3月5日 第 2 次课授课时间：2013年3月7日 第 3 次课授课时间：2013年3月12日 《工程结构抗震设计》习题与思考题 第一章地震基础知识与工程结构抗震设防 1、地震按其成因分为几种类型？按其震源深浅又分为哪几种类型？ 2、试述构造地震成因的局部机制和宏观背景？ 3、试分析地震动的空间分布规律及其震害现象 4、地震波包含了哪几种波？它们的传播特点是什么？对地面运动影响如何？ 5、什么是地震震级？什么是地震烈度？两者有何关联？ 6、地震基本烈度的含义是什么？ 7、为什么要进行设计地震分组？ 8、试列出三座城市的抗震设防烈度、设计基本地震加速度和所属的设计地震分组 9、什么是建筑抗震三水准设防目标和两阶段设计方法？ 10、我国规范根据重要性将抗震类别分为哪几类，不同类别的建筑对应的抗震设防标准是什么？ 11、什么是建筑抗震概念设计？包括哪些方面的内容？ 12、根据经验公式，某次地震释放的能量大约是5×1024尔格，它对应的里氏震级是多少？ 第二章场地、地基和基础抗震 1、什么是场地，怎样划分场地土类型和场地类别？ 2、简述选择建筑场地的相关规定 3、如何确定地基抗震承载力？简述天然地基抗震承载力的验算方法 4、已知某建筑场地的钻孔资料见下表，试计算该场地土层的自振周期，并按《抗震规范》 的规定来确定该建筑场地的类别 土层资料 5、什么是砂土液化？液化会造成哪些危害？影响液化的主要因素有哪些？ 6、怎样判别地基土的液化，如何确定地基土液化的危害程度？ 7、简述可液化地基的抗液化措施 第三章 工程结构地震反应分析与抗震验算 1、什么是地震作用？如何确定结构的地震作用？ 2、地震系数和动力系数的物理意义是什么？通过什么途径确定这两个系数？ 3、 影响地震反应谱形状的因素有哪些？设计用反应谱如何反映这些因素影响的？ 4、简述确定结构地震作用的底部剪力法和振型分解反应谱法的基本原理和步骤？ 5、何谓求水平地震作用效应的平方和开方法（SRSS ），写出其表达式，说明其基本假定和适用范围 6、简述计算地震作用的方法和适用范围 7、什么叫鞭端效应？设计时如何考虑这种效应？ 8、什么叫结构的刚心和质心？结构的扭转地震效应是如何产生的？ 9、哪些结构需要考虑竖向地震作用？如何计算竖向地震作用？ 10、 什么是结构或构件恢复力特征曲线，反映了结构或构件的什么性能？ 11、地震动的三要素是什么？采用时程分析法选取地震波时如何考虑这三要素？ 12、 抗震设计中如何考虑结构的地震作用？依据的原则是什么？ 13、什么是承载力抗震调整系数？为什么要引入这一系数？ 14、什么是楼层屈服强度系数？怎样确定结构薄弱层或部位？ 15、一单层单跨框架如图1所示。假设屋盖平面内 刚度为无穷大，集中于屋盖处的重力代表值G ＝ 1200kN,框架柱线刚度i c ＝3.0×104 kN.m ，框架刚度 h ＝5.0m ，跨度l=9.0m 。已知设防烈度为8度，设计 基本地震加速度0.2g ，设计地震分组为第二组，Ⅱ 类场地，结构阻尼比为0.05。试求该结构在多遇地 震和罕遇地震时的水平地震作用。 16、求图2所示体系的频率、振型. 已知：m1=m2=m,k1=k2=k 17、试用振型分解反应谱法计算图3所示框架多遇地震时的层间剪力。 抗震设防烈度为8度，Ⅱ类场地，设计地震分组为第二组。 18、试用底部剪力法计算图3所示框架多遇地震时的层间剪力。已知结构的基本周期T1=0.467s ,每层的层高均为3.5m,抗震设防烈度为8度,Ⅱ类场地,设计地震分组为第二组。 MN/m 245=MN/m 195=MN/m 98= 7.14 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m 《结构的强度和稳定性》教学设计 《技术与设计2》第一章第三节《结构的强度和稳定性》教学设计 《结构的强度和稳定性》教学设计 一、教材分析： 本节是“地质出版社”出版的教材《技术与设计2》中第一章第三节《结构的强度和稳定性》。共需2课时完成。本课为第1课时的学习。该章的总体设计思路是：认识结构——探析结构——设计结构——欣赏结构。“结构”与“设计”是该章的两个核心概念，结构的强度和稳定性则是结构设计中需要考虑的重要因素之一，是对结构及受力认识的基础上作进一步深入的学习。 二、教学目标： 知识与技能： 1、理解内力、强度、应力的概念，能进行简单的应力计算，掌握应力和强度的关系。 2、通过实验，明确强度与材料、强度与物体的形状及连接方式的关系。培养学生合作交流能力，对身边事物的观察能力。 3、理解稳定性的概念，及影响稳定性的因素。 过程与方法：通过观察生活和技术实验等方法使学生懂得应用相关的理论知识。 情感态度价值观：让学生亲身体验注重交流，通过分析讨论得到结论，培养学生的观察分析能力，合作交流能力。 三、教学重点与难点： 重点：影响结构强度和稳定性的主要因素。 难点：应力的计算，强度与应力的关系，结构设计需要在容许应力范围之内。 四、学情分析： 总体来说学生对通用技术这门课程比较感兴趣。他们的思维、生活经验已有一定基础，并在前面章节的学习中已经初步掌握了结构的一些相关知识，在此基础上帮助学生从其生活世界中选择通俗感兴趣的主题和内容，对结构问题进行进一步探讨，上升到理论的高度。 五、教学策略： 本课采用在教学中充分利用实验、讨论、小组合作的教学方法。多举生活中的案例，进行师生互动探讨，帮助学生加深对知识的理解。 六、教学安排 1课时 七、教学过程： （一）复习回顾，导入新课 教师引导学生回顾结构的概念，指出事物的性质：强度和稳定性 （二）知识构建 1、强度 对于结构变形，只给以“结实”“不结实”来评说是不够准确的，而对于结构的受力与变形应该有更科学的描述。通常，物体结构抵抗变形的能力，都以强度来表示，我们用应力来衡量强度。 （1）内力：外力使构件发生变形的同时，构件的内部分子之间随之产生一种抵抗变形的抵抗力，称为内力。 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 数据结构教案第七章图 第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 数据结构复习题：图 单选题 1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_____倍。A,1/2 B,1C,2 D,4 2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_____。 A,n B, n+1 C,n-1 D,n+e 3、具有n个顶点的无向完全图，边的总数为_____条。 A,n-1 B,n C,n+1 D,n*(n-1)/2 4、在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于_____ 。 A,i+j B,i-j C,1D,0 5、在n个结点的线索二叉树中,线索的数目为______. A,n-1 B,n C,n+1 D,2n 6、在二叉排序中,凡是新插入的结点,都是没有______的. A孩子B关键字C平衡因子D赋值 7、深度为5的二叉树至多有_______个结点. A,16 B,32 C,31 D,10 8、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为_________。 A,s B,s-1 C,s+1 D,n 9、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为_________。 A,s B,s-1 C,s+1 D,2s 10、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为_________。 A,n B,e C,n+e D,2e 11、在一个具有n个顶点的无向完全图中，所含的边数的_________。 A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/2 12、在一个具有n个顶点的有向完全图中，所含的边数为_________。 A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/2 13、在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为 数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题： 第7章 《图》习题参考答案 一、单选题（每题1分，共16分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。 A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 （ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 A ．0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 1 3 4 2 5 6 D. 0 3 6 1 5 4 2 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量 1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧 关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B） 数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧 (4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径 一、单选题 C01、在一个图中，所有顶点的度数之和等于图的边数的倍。 A)1/2 B)1 C)2 D)4 B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A)1/2 B)1 C)2 D)4 B03、有8个结点的无向图最多有条边。 A)14 B)28 C)56 D)112 C04、有8个结点的无向连通图最少有条边。 A)5 B)6 C)7 D)8 C05、有8个结点的有向完全图有条边。 A)14 B)28 C)56 D)112 B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A)O(n) B)O(e) C)O(n+e) D)O(n2) C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2 B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6 D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3 A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2 A13、图的深度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 D14、图的广度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 B15、任何一个无向连通图的最小生成树。 A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在 A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A)n、2e B)n、e C)n、n+e D)2n、2e C17、判断有向图是否存在回路，可以利用___算法。 A)关键路径 B)最短路径的Dijkstra C)拓扑排序 D)广度优先遍历 A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目 习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 任务引入 [5分钟] 课程介绍[20分钟] 新知识[45分钟] 任务实施[15分钟] 小结作业[5分钟] 认识数据库 提问：按自己的理解，说说数据库是什么？ 展示各类网站 商城网站页面是大家在熟悉不过的了，商城网站上的商 品琳琅满目，让人流连忘返。但是在大家欣赏自己喜爱的商 品之余，是否想过商城网站上的文字信息、图片信息等存放 在哪里呢？当大家在商城网站上进行注册用户时，自己的信 息又存在哪里呢？当客户在商城网站上留言的时候，留言信 息又放在哪里了呢？这就是本门课程——《WEB数据库应 用》要解决的问题。 主要让学生明确以下几个问题： 1．明确课程定位与作用 专业基础课，与《程序设计基础》一起，为《网站建设》 奠定基础。同时兼顾计算机二级考试相关内容。通过任务引 领型和项目活动形式，掌握简单的数据库设计、数据管理和 维护方法，能进行web服务器的设置，具备使用web数据库 与高级程序设计语言或动态网页结合完成简单程序开发的 基本职业能力。 提问 展示 展示课程 标准、课程 体系图 与教材配 合 演示 指导 2．明确课程内容 内容的确定遵循两个原则：一是满足后续课程的基本需求，二是为学生进一步的学习提供必要的准备。通过对学生就业岗位和用人单位对本专业毕业生设置的招聘岗位等分析，课程内容应基本包括数据库系统概述、关系理论、关系数据库查询语言SQL、数据库设计与关系规范化理论、MySQL 数据中管理系统与高级程序设计语言或动态网页技术结合的简单应用。 3．强调学习方法 （1）与以往《计算机基础》、《办公软件应用》在学习方法上不同，知识与操作的连续性更强，在学习上要坚持一贯，持之以恒。 （2）课程难度加大，要求大家认真听、认真做，尤其要认真思考。逐渐养成举一反三的习惯、锻炼独立进行逻辑思维的能力。 （3）要学会自学。 （4）要善于和老师沟通。 （5）要学会团队协作。 4．明确考核方式 课程简介 人们在运用程序设计语言编写程序的过程中发现所有的数据都可以抽象为三种结构，而对这些数据的所有操作都可以转化为对这三种数据的几种基本操作，而大多数的程序设计技巧都可以抽象为一些最基本的算法。于是人们逐步发展了一门称为数据结构（或数据结构与算法）的计算机科学，它广泛应用于计算机领域。 数据结构是信息与计算专业的核心基础课程之一。数据是计算机处理的对象，本课程研究的数据是非数值性、结构性的数据。学习本课程要求掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握。通过本课程的学习，使学生透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养基本的良好的程序设计能力。本课程主要包括如下三个方面的内容： 1．基本数据结构：线性表、栈、队列、串、数组和广义表，掌握它们的特点、表示和实现，对静态结构要求非常熟练的编程上机实现，对动态结构要求逐步熟悉链表的表示，通过模仿实验教程中的例子，掌握编程技巧。强调类C语言的书写规范，特别注意参数的区别，输入输出的方式和错误处理方式，以及抽象数据类型的表示和实现。能熟练完成以下的应用：多项式的计算、语法检查、回朔算法、递归算法、表达式求值、离散事件模拟、文字的编辑和稀疏矩阵进行矩阵运算采用的处理方法。 2．复杂数据结构：树、二叉树、图。掌握它们的定义和特点、表示和实现，特别注意与基本数据结构的区别，掌握各种遍历的递归和非递归算法，能熟练完成以下的应用：最优树、Huffman编码、拓扑排序、关键路径和最短路径问题。 3．数据结构的应用：查找和内部排序。熟练掌握静态查找表的查找方法和实现，了解哈希表的构造和查找方法。掌握各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复杂度分析。 7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1) 《数据库原理及应用》教案新乡学院计算机与信息工程学院 第1章数据库技术概论 ●教学目的：本章概述了数据库管理的进展、数据模型和数据库系统构成的 一般概念，说明什么是数据库设计以及为什么要发展数据库技术，使学生对数据库系统有一个初步的认识。 ●教学重点：1、数据管理的三个阶段及特点。 2、三种主要模型的概念。 3、 E-R图。 4、 DBS体系结构。 ●教学难点：E-R图 1.1 数据库系统概论 ●教学目的：从已有的知识对学生进行启发，认识到DB的重要性以及本课程 的任务和目的。 ●教学重点：1、数据管理种计算机化的三个阶段。 2、三个阶段的特点。 ●教学难点：数据库系统阶段的特点。 ●教学内容： 1.1.1 引言 1. 计算机的应用领域： 数值计算 数据处理 80%以上 实时控制 人工智能 辅助设计 2. 数据处理 指对各种形式的数据进行收集、存储、加工和传播等一系列活动的总和。 目的：是从大量、原始的数据中抽取、推导出对人们有价值的信息作为行为决策的依据。 方式：借助于计算机科学的保存和管理复杂的大量数据，以便能方便地利用信息资源。 3. 出现（存在）的问题： (1)大量的数据如何存放。（存储） (2)大量的数据如何组织。（结构） (3)大量的数据如何分类、查找、统计。（处理） (4)大量的数据如何有效使用。（共享、保护） (5)大量的数据如何维护。（维护） 正是这些问题的存在，迫使人们去形成一套数据处理的理论、方法、技术。-----数据库技术。 4. 基本概念 (1) 数据库技术-----是研究数据库结构、存储、设计、管理和使用的一门软件学科。 (2) 数据库（Data Base）-----是长期存储在计算机内有组织的、大量的、共享的数据集合，具有最小的冗余和较高的数据独立性，并为各种用户共享。 (3) 数据库管理系统（Data Base Management System）-----位于用户和OS之间的一层数据管理软件，包括DB的建立、查询、更新。 (4) 数据库系统（Data Base System）-----实现有组织地、动态地存储大量关联数据，方便用户访问的计算机软、硬件和数据资源组成的系统。 1.1.2 数据管理的进展 数据处理的中心问题是数据管理 数据的分类 数据的组织 数据的编码 数据管理包括数据的存储 数据的检索 数据的维护 依据其使用：技术的不同、设备的不同， 数据管理（处理）可分为： 人工式：人工处理数据阶段1800年以前，算盘，笔记 手工数据处理机械辅助式：机械辅助阶段1800—1890 手摇电动计算机 机械数据处理机电阶段 1890—1946年穿空机、验空机、分类机、卡片机、 制表机 电子数据处理电子阶段 1946年后 本书所讲的是电子数据处理发展经过的三个阶段： 人工管理 电子数据处理文件系统 DBS《数据结构》习题汇编07 第七章 图 试题
数据库教案
工程结构抗震设计电子教案
数据结构 第七章 图
《结构的强度和稳定性》教学设计电子教案
第三章栈和队列习题_数据结构电子教案
(完整版)数据结构详细教案——图
数据结构试题：第七章的练习
数据结构第七章图
数据结构第7章习题答案
数据结构第7章 图习题
数据结构第七章图练习及答案
数据结构第七章图练习及答案
最新数据结构第7章-答案
数据结构第7章 图习题
MySQL数据库教案
数据结构教案
数据结构作业系统_第七章答案
《数据库原理及应用》教案