四、解答题
1、 已知无向图的邻接表如下，①在给出顶点的图上，画出这个图的边；②写出该图的邻接
矩阵A；③根据邻接表，写出从顶点V1出发，深度优先遍历该图所得到的顶点序列。
1 2 3 4 5
提示：
V1 V3 V4 V2 V5 2、 己知一无向图有 6 个结点， 9 条边，这 9 条边依次为（ 0 , l ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 0 ,
5 ) ,( l , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) , ( 4 , 5 ）。试画出该无向图，并从顶点 0 出发分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。 3、 已知如图1 所示的有向图，给出该图的：
① 每个顶点的出度和入度； ② 强连通分量； ③ 最长的简单路径； ④ 最长的简单回路；
⑤ 进行拓扑排序，给出顶点的拓扑序列。
4、 对如图2所示的连通图，列出分别从顶点 A 、 D 开始，深度优先和广度优先搜索遍
历该图所得到的顶点序列，画出相应的生成树。
图1 图2
5、 设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），
（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。
- 29 -
6、 下图是以边为活动的网（AOE_网），以V1为开始点，以V10为终止点，计算该AOE_
网的关键路径长度（即，从开始点到终止点的最长路径长度）。
7、 对如下无向图，试给出：
① 用普里姆算法构造最小生成树的过程 ② 用克鲁斯卡尔算法构造最小生成树的过程
五、算法设计题
1、 图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作：
DeleteArc(G,v,w)。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返回“OK”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0 ），完成该算法。 Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G上删除边(v,w) { if ((i=LocateVex(G, v))<0) return if ((j=LocateVex(G, w))<0) return if (G.arcs[i][j].adj)
{ G.arcs[i][j].adj= ;
G.arcnum ; （或 G.arcnum=G.arcnum-1 ） } return }
;
; ;
3 E B 5 6 6 4 F 6 A 1 C 5 2 5 D - 30 -
2、 一个图采取以下结构，完成下列遍历算法。
void BFSTraverse(Graph G, Status (*Visit)(int v)) { for (v=0; v visited[v] = FALSE; //初始化访问标志 InitQueue(Q); // 置空的辅助队列Q for ( v=0; v if ( ) { // v 尚未访问 visited[v] = TRUE; Visit(v); // 访问u EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u); // 队头元素出队并置为u for(w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]= ; Visit(w); EnQueue(Q, w); // 访问的顶点w入队列 } // if } // while } //if } // BFSTraverse 3、编程实现：用邻接表的存储方法创建一个图。 4、编程实现：对3题建立的图进行深度优先搜索。 - 31 - 第 9 章 查找 一、单选题 1、静态查找表与动态查找表两者的根本差别在于 A、逻辑结构不同 B、 存储实现不同 C、施加的操作不同 D、 数据元素的类型不同 2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 Ａ、n B、n/2 C、(n+1)/2 D、(n-1)/2 。 。 。 3、对线性表进行二分查找时，要求线性表必须 A、以顺序方式存储 B、以链式方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链式方式存储，且结点按关键字有序排序 4、在表长为n的顺序表中进行顺序查找，在查找不成功时，与关键字比较的次数为 。 A、n B、1 C、 n+1 D、n-1 5、对于有序表（2，5，7，11，22，45，49，62，71，77，90，93，120），折半查找值为90的结点时，经过 比较后查找成功。 A、 1 B、 2 C、4 D、5 6.快速排序在最坏情况下的时间复杂度是( )。 A、O(log2n) B、O(nlog2n) C、O(n2) D、O(n3) 7、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。 A、分块 B、顺序 C、二分 D、散列 8、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下查找成功所需的平均比较次数为 。 A、35／12 B、37／12 C、39／12 D、43／12 9、当采用分块查找时，数据的组织方式为 A、数据分为若干块，每块内数据有序 B、数据分为若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） - 32 - 。