第四章
FSA（finite state automaton）是指_____？A
? ? ?
A 有限状态自动机 B 非确定有限自动机 C 确定有限自动机
解决循环赛日程安排问题采用的是_____？
? ?
A 递归法 B 分治法
关于有限状态自动机，下列说法正确的是_____？ABCD
? ? ?
A “有限”（finite）是指在逻辑图中有有限数量的状态（如岛） B “状态”（state）在“金银岛游戏”中是游戏中岛屿的别称
C “自动机”（automaton）是指能遵循简单规则自主运行的机器，即根据当前状态和
输入决定所转移的下一个状态的机制
D 如果某个输入的序列（例如BBAB），能够从初始状态，经过状态转移之后，到
达“终结状态”，则说明这一输入是“可接受的”
?
以下哪些是分治法的应用_____？ABC
? ? ?
A 归并排序 B 快速排序 C 二分法
关于递归算法，下列说法正确的是_____？ABCD
? ? ? ?
A 递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性 B 它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具 C 递归算法是一种自身调用自身的算法 D 递归算法的运行效率较低
下列哪些是自动机的应用场景_____？ABCD
? ? ? ?
A BBS信息监测系统 B 自动售货机
C 图像压缩和图像增强 D 网络入侵检测
德罗斯特效应（一张图片的某个部分与整张图片相同，如此产生无限循环），是_____的一种视觉形式？A
? ?
A 递归 B 分治
第五章
关于深度优先搜索，下列说法正确的是________?ABCD
? ? ?
A 深度优先搜索（depth first search）是一个不断探查和回退的过程。
B 在探查的每一步开始之前，算法都有一个当前顶点（最开始即是起始顶点）。 C 每一步探查中，我们在当前顶点v的所有邻接顶点中，找出尚未访问过的一个，
将其作为下一步探查的当前顶点，即我们永远希望向着更“深”的层次去探索。
D 深度优先搜索的过程可以使用栈来模拟，当然也可以使用递归的形式来完成
?
常见的数据结构操作有_________?ABCD
? ? ? ?
A 查找 B 插入 C 删除 D 遍历
关于图，下列说法正确的是_________?ABCD
? ? ?
A 图的每一个顶点可以与多个其它顶点相关联，各顶点之间的关系是任意的。 B 图可以分为有向图和无向图。
C 在有向图中，顶点对(x，y)是有序的，称为从x到y的一条有向边，这里(x，y)
与(y， x)是不同的两条边。
D 在无向图中，顶点对(x，y)是无序的，(x，y)和(y，x)是同一条边。
?
关于“队列”，下列说法正确的是_________?ABCD
? ? ? ?
A 队列也是一种限定存储位置的线性表。
B 队列允许在表的一端进行插入，在另一端进行删除操作。
C 在队列中插入一个元素的过程叫做“入队”，删除一个元素的操作叫做“出队”。 D 与栈不同，队列的操作遵循“先进先出”的规则。
_________指的是从有向图G=(V，E)中得到一个顶点的线性序列，满足如果G包含边(u，v)，则在该序列中，u就出现在v的前面。D
? ? ? ?
A 图
B 深度优先搜索 C 广度优先搜索 D 拓扑排序
常见的数据结构有_________?ABCD
? ? ? ?
A 线性表 B 栈 C 队列 D 树：
对于二叉搜索树的查询过程，下列说法正确的事________?AD
? ? ? ?
A 如果查询关键词等于当前结点的关键词，则宣布查找成功。 B 如果查询关键词大于当前结点的关键词，则查找其左子树。 C 如果查询关键词小于当前结点的关键词，则查找其右子树。 D 如果已没有儿子节点，则宣布查找失败。
关于广度优先搜索，下列说法正确的是________?ABCD
?
A 与深度优先搜索不同，广度优先搜索（breadth first search）没有探查和回退的过
程，而是一个逐层遍历的过程。
B 从起始点开始作为首层，然后对每层的所有顶点，都向外扩展访问那些未被访问
过的邻接顶点，而这些扩展出来的顶点就作为下一层的顶点 ，依此类推，直到所有顶点都被访问为止。
?
? ?
C 广度优先搜索还能用来计算起始点到所有可达顶点之间的距离（即最少的边数） D 广度优先搜索一般使用队列，以记忆正在访问的这一层和上一层的结点，以便于
向下一层的结点进行访问。
关于“树”，下列说法正确的是________?ABCD
? ? ? ?
A “树”是一种能够表达层次关系的数据结构。
B 树中的每一个位置称为一个结点，树根部的结点称为根结点。 C 通常把从根结点到叶子结点的最长路径上的结点数称为树的深度。 D 对于树中任意一个结点，该结点与其下层的结点也构成树结构，称为子树。
关于“栈”，下列说法正确的是_________?ABCD
? ? ?
A 栈其实是一种特殊的线性表。
B 栈只允许在一端进行插入和删除操作。
C 在栈顶插入一个元素的过程叫做入栈，删除一个元素的过程叫做出栈。
? D 栈的操作遵循“后进先出”的规则。
第六章
关于”最小生成树”，下列说法正确的是________?ABC
? ? ?
A “最小”，即连接网络的总代价最小。
B 用全部顶点和部分边组成的树，生成树代价最小意味着树中无环。 C 解决最小生成树问题的两种算法：Kruskal算法和Prim算法
关于“封锁”，下列说法正确的是_________?ABCD
?
A 封锁就是事务在对某个数据对象（例如表、记录等）操作之前，先向系统发出请
求，对其加锁。：
B 一个事务对某个数据对象加锁后究竟拥有什么样的控制由封锁的类型决定。 C 排它锁又称为写锁 D 共享锁又称为读锁
? ? ?
某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，这就发生了_______?A
? ? ?
A 死锁 B 封锁 C 活锁
关于并发与死锁的解决方法有________?ABCD
? ? ? ?
A 服务生解法 B 资源分级解法
C Chandy-Misra-Hass解法 D Chandy/Misra解法
计算出活动网络中的______，就可以辨明哪些是影响整个工程进度的关键活动，以便科学合理地安排工作 。
? ? ?
A 关键路径 B 关键活动 C 最小生成树
关于Prim算法和Kruskal算法，下列说法正确的是________?ABCD
?
A Kruskal算法在执行过程的中间结果可能有多棵树（称为森林），最终才合并成我
们所需的最小生成树。
B Prim算法在生成树集合扩展时，总是形成单棵树。
?
? C 有效实现Prim算法的关键是设法较为高效地选择出已经在生成树内和尚不在生
成树内的顶点之间的最小权值边。
D 二叉搜索树是一种能满足Prim算法的数据结构。
?
________是指在带权图的源点出发，找出一条通往汇点的路径，其组成边的权值之和最小。A
? ? ?
A 最短路径问题 B 关键路径问题 C 最小生成树问题
关于“死锁”与“活锁”，下列说法正确的是________?ABCD
?
A 封锁技术可以有效地解决并行操作的一致性问题，但也带来了“死锁”与“活锁”的问
题。
B 采用先来先服务的策略，能够有效避免“活锁”。 C 解决死锁的方法有“预防死锁”及“死锁的诊断与拆除”。 D 预防死锁的发生就是要破坏产生死锁的条件。
? ? ?
并发操作带来的数据不一致性的情况有_________?ABC
? ? ?
A 丢失修改 B 不可重复读 C 读“脏”数据
第七章
________的发明，使得截获密文易如反掌？B
? ? ?
A 维吉尼亚密码 B 无线电报 C ENIGMA
________和_________一直是密码学互相对抗又互相促进的两面。A
? ?
A 加密 解密 B 密钥 密文
关于手工编码的密码，下列说法正确的是_______?ABCD
? ? ?
A 直到第一次世界大战结束为止，所有密码都是使用手工来编码的。 B 手工编码的方式给使用密码的一方带来很多的不便。
C 手工编码使得许多复杂的保密性能更好的加密方法不能被实际应用。