USTC算法习题课.pdf

17 1 2 证明 在k位计数器的例子中 如果包含一个 DECREMENT操作 n个操作可能花费 nk 的时间 计数器初始状态为全0 假设有以下操作序列 DECREMENT INCREMENT DECREMENT INCREMENT 每次操作都会有k次的翻转 一共进行n次操作即可 17 1 3 对某个数据结构执行n个操作的序列 如果i为2的整数 幂 则第i个操作的代价为i 否则为1 请利用聚集分析来确定 每次操作的平摊代价 从而得到每个操作的平摊代价为O 1 17 3 2 用势能方法重做练习17 1 3 设i 2j k j 0 k 0且j取值尽可能大 势能函数 2k 如果k 0 则 否则 17 2 1 对一个大小始终不超过k的栈上执行一系列的栈操作 在每k 个操作之后 复制整个栈的内容以作备份 证明 在对各种栈操作 赋予合适的平摊代价之后 n个栈操作的代价为O n 对PUSH操作征收3元即可 每个元素入栈时消耗1元 每个在栈里 的元素都有2元存款 足够支付复制操作 出栈一次 进栈一次 各 消耗1元 或者出栈操作 消耗1元 注 复制操作和出栈操作不会连续发生 即一个元素出栈之后就不 会再被复制 复制之后就不会再被出栈 因为已经被留作备份 每个操作的平摊代价为1 故n次操作的代价为O n 设数组为A 新增一个域 max A 对每次INCREMENT操作征收4元 RESET操作征收1元即可 具体来说 数组里的每个1都会有3元的存款 由0变为1消耗1 元 这3元存款里预留出1元作为以后该位翻转为零时用 再 留出1元作为维护max 1 的费用 每个1都会有一次机会作为 max A 再留出1元作为RESET时使用 此时max A 被置为 1 只需要1元的代价 这样就可以满足所有的操作需求 因 此每个操作的平摊代价为O 1 从而包含n个操作的序列需要 时间为O n 17 2 3 假设我希望们不仅能使一个计数器增值 也能使之复位 至零 请说明如何将一个计数器实现为一个数组 使得对一个 初始为零的计数器 任一个包含n个INCREMENT和RESET操 作的序列的时间为O n 17 3 6 说明如何使用两个普通的栈来实现一个队列 使得每个 ENQUEUE和DEQUEUE操作的平摊代价都为O 1 设有两个栈S1 S2 ENQUEUE 往S1里push DEQUEUE 如果S2不为空 则直接pop S2 否则popall S1 接 着全部push S2 再pop S2 平摊分析 每次ENQUEUE收费4元 1元用于PUSH入S1 剩下3 元存款 在最坏的情况下 其中2元用于从S1转移到S2 1元用于 POP 平摊代价为O 1 22 2 4 证明在广度优先搜索算法中 赋给顶点u的值d u 与顶点在邻接 表中的次序无关 利用图22 3作为例子 说明由BFS计算出来的广度优 先树与邻接表中的顺序是有关的 第一问 BFS的伪代码里没有任何关于邻接顶点访问次序的信息 因而 是次序无关的 第二问 当BFS算法运行到w节点的时候 如果程序先访问t节点 则t 就是x的前驱 反之如果先访问到x节点 则x就是t的前驱 22 2 6 题目略过 见书中329页 第二版 第一步 做尽可能多的BFS 为了访问到每个节点 O n r 第二步 把所有d值为偶数的节点标记为好选手 把d值为奇数的节点标 记为差选手 O n 第三步 检查所有的边 如果都满足边上的两个顶点分别是好选手 差 选手 则可以做出这样的指定 否则就是不可以 O r 22 3 5 证明 在一个无向图中 如果是根据在深度优先搜索中 u v 和 v u 哪一个先被遇到作为标准来将 u v 归类为树边或者反向边的话 就等价于根据边分类方案中的各类型的优先级来对它进行分类 如果访问到边一端是白的 另一端是灰的 一定是访问灰色到白色方 向的边 这是一条Tree edge 如果访问到边两端都是灰的 一定是 Back edge 不可能有其他情况 这等价于根据边分类方案中的各类 型的优先级来对它进行分类 22 3 8 对于 在一个有向图G中 如果有一条从u到v的路径 则 任何深度优先搜索都必定能否得到d v f u 这一推测 给出它 的一个反例 22 4 3 给出一个算法 用它来确定一个给定的无向图G V E 中是否包含一个回路 所给出算法的运行时间应为O V 这一时 间独立于E 根据引理22 11即可得到一个合适的算法 对图G做DFS 如果在循 环里找到一条反向边 则说明有环 如果循环次数达到V次 则说明 有环 无环图的边数E V 1 否则无环 22 4 4 证明或者反证 如果一个有向图G包含回路 则 TOPOLOGICAL SORT G 能产生一个顶点的排序序列 它可以最 小化 坏 边的数目 所谓 坏 边 即那些与所生成的顶点序列 不一致的边 不正确 例如下图 从0运行DFS生成序列0 1 2 有1条bad edge 2 0 而从1运行DFS生成序列1 2 0 有2条bad edge 0 1 0 1 22 5 3 Deaver教授声称 用于强连通分支的算法可以这样简化 即在第二 次深度优先搜索中使用原图 并按完成时间递增的顺序来扫描各顶点 这 位教授的说法正确吗 以图22 9为例 书中338页 第二版 如果按照Deaver教授的说法做 则 我们会依次访问f g和h节点 显然它们不属于同一个强连通分量 22 5 5 给出一个O V E 时间的算法 以计算一个有向图G V E 的分支 图 注意在算法产生的分支图中 两个顶点之间至多只能有一条边 算法根据书339页 第二版 SCC算法下面的内容得到 STEP1 求强联通分量 结果用scc u 表示 即顶点u属于第scc u 个强联 通分量 O V E STEP2 按照scc u 从小到大对顶点排序 计数排序 O V STEP3 把每个强联通分量的第一个顶点加入到VSCC中 O V STEP4 计算集合S x y edge u v E x scc u y scc v x y O E STEP5 对S做基数排序 即两次计数排序 O V E STEP6 把每个不同的 x y 加入到ESCC中 O E 总时间O V E 23 1 4 给出一个连通图的例子 使得边集 u v 存在着一个割 S V S 使得 u v 是一条通过 S V S 的轻边 不会形成一颗最 小生成树 每条边都是一条轻边 对于任意一个割来说 但是该图不 是一个MST 11 1 23 1 7 论证 如果图中所有边的权值都是正的 那么 任何连接所有 顶点 且有着最小总权值的边的子集必为一棵树 请给出一个例子来 说明如果允许某些权值非正的话 这一结论就不成立了 证明 1 此图不包含回路 反之 若包含回路 那么可以选择构成回路的 边集合中权重最大的边 将这条边从边集中删除 经过变换之后 此 图连通性不改变 而且总权重减少 所以总权重最小的连接所有结点 的一个边集 必然不包含回路 所以形成一棵树 2 画个三角形即可 3条边权重是 1 那么如果边集只有2个边 总 权重是最少是 2 边集如果是3边 那么权重是 3 3 2但是3边是圈 2边是树 所以不成立 23 2 4 假设在某个图中 所有边的权值均为1到 V 之间的整数 在这一条件下 Kruskal算法的运行时间能达到多快 如果各边的 权值都是1到W之间的常数 情况又怎样呢 如果所有边的权值均为1到 V 之间的整数 那么可以采用计数排 序 时间为O V E 又因为图是连通的 所以V O E 因而排 序时间又可以表示为O E 除此之外 Kruskal算法的初始化时间 为O V 不相交集合操作时间为O E V 所以总的运行时间 为O E V 如果各边的权值都是1到W之间的常数 答案也是相同的 23 2 6 假设在某个图中 所有边的权值都分布在 1 0 之间 对于 Kruskal算法和Prim算法 你可以让哪一个运行的更快一些 Kruskal排序能更快 边长分布在 0 1 排序可以使用桶排序 期望运行时间O E 总时间O E O E V O E V 课堂测试 30 1 2 求一个次数界为n的多项式A x 在某已知点x0的值也可以用一下方法获得 把多 项式A x 除以多项式 x x0 得到一个次数界为N 1的商多项式q x 和余项r 并满 足 A x q x x x0 r 显然A x0 r 试说明如何根据x0和A的系数 在 n 的时间计算出余项r以及 q x 中的系数 解 设A x 和q x 的系数分别为Ak Bk 30 1 7 考察两个集合A和B 每个集合包含取值范围在0到10n之间的n个整数 要计算出 A与B的笛卡尔和 它的定义如下 C x y x A y B 注意 C中整数的取值范围在0到20n之间 我们希望计算出C中的元素 并且求 出C的每个元素可为A与B中元素和的次数 证明 解决这个问题需要 nlgn 的 时间 提示 用10n次多项式来表示A和B 解 用10n次多项式A10n和B10n来表示A和B Ai 1当且仅当i在集合A中出现 0 i1 以 为分隔符把P分为k个部分P1 P2 Pk 然后 先后在文本T中使用NAIVE算法查找这k个部分 当查找到Pi时 就从查找所 在位置的后一位开始查找Pi 1 时间复杂度为 假设k个部分的长度为a1 a2 ak O n a1 1 a1 O n a1 a2 a2 O n m k 1 ak O n 1 a1 O n 1 a2 O n 1 ak O m n 1 代码见下页 32 2 1 如果取模q 11 那么当Rabin Karp匹配算法在文本T 3141592653589793中搜 寻模式P 26时 会遇到多少伪命中点 解 26模11为4 文本中模11为4的两位数字包括 15 59 92 26 其中15 59 92是伪命中点 共三个 32 2 3 试说明如何扩展Rabin Karp方法以处理下列问题 在一个nXn二维字符组成中搜寻一个给 定的mXm模式 可以使该模式在水平方向和垂直方向移动 但不可以把模式旋转 解 1 对mXm模式矩阵的每行计算模q的结果 得到一个m维向量P mX1 2 对以nXn文本矩阵1 n m行 1 n m列的位置为 0 0 元素的mXm矩阵 同样 分别计算得到一个m维向量T mX1 3 在文本矩阵中寻找能匹配P的位置 4 对匹配位置显式测试以决定是否为真正的有效位置 类似一维情况 32 4 1 当字母表为 a b 时 计算相应于模式ababbabbabbababbabb的前缀函数 解 32 4 3 试说明如何通过检查字符中PT的 函数 来确定模式P在文本T中的出现位置 由P和T并 置形成的长度为m n的字符串 解 假设 k P length 则模式P在文本T中的出现位置是k 2 P length 可以 参考32 4 1 假设P ababbabb T abbababbabb 32 4 5 写出一个线性时间的算法 以确定文本T是否是另一个字符串T 的循环旋转 例如 arc和 car是彼此的循环旋转 解 文本T是另一个字符串T 的循环旋转 KMP MATCH T T T TRUE 时间复杂度为O length T 附加题 已知 T 1 30 ACGCTDAGAAGDCAGADGTDAGCDGDAGCA P 1 10 DAGCDGDAGC 1 计算Shift Or算法中