在Hash函数中,找出任意两个不同的输入x、y,使得H(y)=H(x)在计算上是不可行的。这一性质称为()。
A.单向性
B.抗弱碰撞性
C.抗强碰撞性
D.唯一性
A.单向性
B.抗弱碰撞性
C.抗强碰撞性
D.唯一性
第2题
给定两个长度分别为n和m的序列x[0...n-1|]和y[0...m-1],以及一个长度为p的约束字符串s[0...p-1].带有子串排斥约束的最长公共子序列问题就是要找出x和y的不包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC.字符串s=TG时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而不包含s为其子串的最长公共子序列是ATCGGC.
算法设计:设计一个算法,找出给定序列x和y的不包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x和y及约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的不包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
第3题
(a)在图8.10中找出两个不同大小的最小支配集。
(b)设棋盘的64个方块用64个顶点表示,如果两顶点对应的两个方块是在同一行,同一列或同一对角线上,则这两顶点之间有一条边。已知5个皇后能被放在棋盘上,使它们支配所有64个方块,而且5是必须的最小皇后数,再用图论名词叙述这一结论.
第4题
第7题
),则
第8题
第9题
算法设计:对于给定的罗密欧与朱丽叶的迷宫,计算罗密欧通向朱丽叶的所有最少转弯道路.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m、k,分别表示迷宫的行数、列数和封闭的房间数.接下来的k行中,每行2个正整数,表示被封闭的房间所在的行号和列号.最后的2行,每行也有2个正整数,分别表示罗密欧所处的方格(p,q)和朱丽叶所处的方格(r,s).
结果输出:将计算的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的最少转弯道路输出到文件output.txt.文件的第1行是最少转弯次数.第2行是不同的最少转弯道路数.接下来的n行每行m个数,表示迷宫的一条最少转弯道路.A[i][j]=k表示第k步到达方格(i,j):A[i][j]=-1表示方格(i,j)是封闭的.
如果罗密欧无法通向朱丽叶,则输出“NoSolution!".
第10题
算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1,2,...,n).设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.第2行的n个正整数是完成n个任务需要的时间.
结果输出:将计算的完成全部任务的最早时间输出到文件output.txt.