广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新

广西工学院 2010 — 2011 学年第 1 学期考试试题

考核课程 数据结构与算法 （ A 卷）考核班级 计y091~096 学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟

【说明】试题满分共100分；考试时间为2个小时；

一、选择题（每小题2分，共30分）

1、设一序列为：1，2，3，

4，

5，6。通过栈操作不可能产生的序列为。 A、3，2，5，6，4，1 B、1，5，4，6，2，3 C、2，4，3，5，1，6 D、4，5，3，6，2，1

这题考栈的性质:先进先出。进栈的序号是1最先6最后，但不规定要同时进，然后再出栈。可以1进去，1出来，然后2进去，2出来，也可以1进去，2进去，2出来，1出来。

按照这个原则，先看：A）是可能的，进出栈情况如下：1,2,3依次进栈，3出栈2出栈；4,5进栈，5出栈；6进栈，6出栈；4再出栈，最后是1出栈。

B）不可能：原因：1进栈1出栈；2,3,4,5进栈，5出栈4出栈；6再进栈，6出栈，此时3在栈顶，2不可能比3还要先出栈。其他的答案依此可以得出。

2、设有向图G=（V，E），V={1，2，3，4，5，6}；E={<1，2>，<2，1>，<6，3>，

<2，3>，<5，6>，<2，4>，<3，5>}。则其强连通分量个数为 A、3 B、4 C、5 D、6

考有向图中的强联通分量问题：首先要把强联通分量概念弄清楚：有向图强连通分量在有向图G中，如果两个顶点vi,vj间（vi<>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。记主要特征：强联通分量图中两两都可达，也可见下图实例。按照这个定义，得到图G 中的强联通分量共3个： <1,2>,<3,5,6>,<4>

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新全文阅读和word下载服务。