编写一个算法,判定给定的关键码值序列(假定关键码值互不相同)是否是二叉搜索树的搜索序列。若是则函数返回1,否则返回0。
(1)画出描述上述查找过程的判定树。
(2)计算等搜索概率下搜索成功的平均搜索长度。
(3)计算等搜索概率下搜索不成功的平均搜索长度。
问题描述:试设计一个素数测试的偏真蒙特卡罗算法,对于测试的整数n,所述算法是
一个关于logn的多项式时间算法.结合教材中素数测试的偏假蒙特卡罗算法,设计一个素数测试的拉斯维加斯算法.
算法设计:设计一个拉斯维加斯算法,对于给定的正整数,判定其是否为素数.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数p.
结果输出:将计算结果输出到文件output.txt.若正整数p是素数,则输出“YES",否则输出“NO".
给定三个n×n矩阵A、B和C,下面的偏假1/2正确的蒙特卡罗算法用于判定AB=C.
算法所需的计算时间为Q(n2).显然当AB=C时,算法Product(A,B,C,n)返回true.试证明当AB≠C时,算法返回值为false的概率至少为1/2(考虑矩阵AB-C并证明当AB≠C时,将该矩阵各行相加或相减最终得到的行向量至少有一半是非零向量).
(1)搜索失败;
(2)搜索成功,且表中只有一个关键码等于给定值k的元素;
(3)搜索成功,且表中有若千个关键码等于给定值k的元素,要求一次搜索找出所有元素。
已知k阶斐波那契序列的定义为
试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。
问题描述:给定k个排好序的序列用2路合并算法将这k个序列合并成一个序列.假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较.
试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少.
为了进行比较,还需要确定合并这个序列的最运合并顺序,使所需的总比较次数最多.
算法设计:对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待合并序列.接下来的1行有k个正整数,表示k个待合并序列的长度.
结果输出:将计算的最多比较次数和最少比较次数输出到文件output.txt.
问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及d个约束字符串多子串排斥约束的最长公共子序列问题就是要找出x和y的不含为其子串的最长公共子序列
算法设计:设计一个算法,找出给定序列x和y的不含为其子串的最长公共子序列.
数据输入:重文件input.txt提供输入数据.文件的第1行中给出正整数d,表示约束字符串个数.接下来的2行分别给出序列x和y.最后d行的每行给出一个约束字符串.
结果输出:将计算出的x和y的不含为其子串的最长公共子序列输出到文件output.txt中.文件的第1行输出最长公共子序列.第2行输出最长公共子序列的长度.
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.