首页 > 期末考试真题 > 中国科学技术大学

中国科学技术大学

 http://yz.ustc.edu.cn/
返回全部试卷 >
题目 题型
假设动态表的扩张和收缩策略为：α=1 时插入一个元素表扩张一倍，α=1/2 时删除一个元素表缩小一半。如果势函数定义为Φ(T)=2num[T]-size[T]。请用该势函数分析第一次操作的平摊时间。 问答
请画出在包含 14 个结点的二项堆上完成一次删任一结点(Binomial-Heap-Delet)操作后的根表。 问答
请用活动选择问题算法 Recursive-Activity-Selector 从下表活动中选出一个最优解。 问答
请写出以下算法的时间函数 T(n)的表达式。 问答
写出以下流网络的最小截(S,T)及容量值 C(S,T)。 问答
给定 n 件物品及一个背包，物品 i 的重量为wi ，其价值为Vi，背包可装载物品的总重量为 W。求在不超过背包总重量 W 的前提下，如何选择装入背包的物品，使装 入背包中的物品总价值最大，考虑物品是可拆分的，即该问题是一个零头背包问题。 要求： (1). 写出解此问题的贪心选择策略； (2). 编写求此问题的贪心算法。 问答
写出一个有效算法在区间树中，查找给定区间 i 重叠且有最小起点的区间，并给出算法的时间复杂度。 问答
假设有 n 个人需排队等候处理事务，已知每个人需要处理的时间为 ti，(0<i<=n)，请给出一种最优排队次序，使所有人排队等候的总时间最小。 要求： (1). 给出你的贪心选择策略； (2). 证明贪心选择的正确性； (3). 写出解此问题的贪心算法。 问答
用LCS的动态规划方法计算X={B,D,B,C,A,B,A}与Y={A,B,C,B,D,A,B,A}的最大公共子序列。 问答
贪心算法中求单位任务调度(注意节制时间有相同情况)。 问答
利用调和级数证明​下式。 问答
请给出 的渐进上界，并用数学归纳法证明之。. 问答
在一棵有 n 个关键字、高度为 h 的红黑树中，根的高度至少是多少？至多是多少？ 问答
在一个加权 M=(S,I)中，M 的最优子集一定是最大独立子集吗？为什么？ 问答
设二项堆 H 中有 11 个结点，请问 H 由哪几棵二项树构成？画出这些二项树。 问答
Fib 堆中是哪一个操作合并度数相同的根，其原因是什么？ 问答

热门试题

他们也在学

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号