2008年数据结构习题集

四、解答题

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的线性表时,每个元素的平均查找长度为 A、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 -

联系客服:779662525#qq.com(#替换为@)