信息学奥赛-提高级 题库
在KMP算法中,对于模式串P='abacaba',其next数组(next[i]定义为模式串P[0...i]最长公共前后缀的长度,且数组下标从0开始)的值是什么?
next[i]定义为P[0..i]最长公共前后缀(不能是P[0..i]本身,需同时是前缀与后缀)的长度。
i=0时,P[0..i]为“a”,长度0;
i=1时,P[0..i]为“ab”,长度0;
i=2时,P[0..i]为“aba”,长度1;
i=3时,P[0..i]为“abac”,长度0;
i=4时,P[0..i]为“abaca”,长度1;
i=5时,P[0..i]为“abacab”,长度2;
i=6时,P[0..i]为“abacaba”,长度3。
在一个大小为13的哈希表中,使用闭散列法的线性探查来解决冲突,哈希函数为H(key)=key mod 13,依次插入关键字18、26、35、9、68、74,插入74后,它最终被放置在哪个索引位置?
哈希冲突指key1≠key2但H(key1)=H(key2),计算各关键字哈希值及插入位置:
18 mod 13=5,插入下标5;
26 mod 13=0,插入下标0;
35 mod 13=9,插入下标9;
9 mod 13=9(冲突),插入下标10;
68 mod 13=3,插入下标3;
74 mod 13=9(冲突,9、10均被占),插入下标11。
给定地址区间为 0~9 的哈希表,哈希函数为 h(x) = x % 10,采用线性探查的冲突解决策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地址 0重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请问 89 存储在哈希表哪个地址中。( )
现有一个地址区间为 0~10 的哈希表,对于出现冲突情况,会往后找第一个空的地址存储(到 10 冲突了就从 0 开始往后),现在要依次存储(0,1, 2,3,4,5,6,7),哈希函数为 h(x)=x2 mod 11。请问 7 存储在哈希表哪个地址中( )。
将(2, 7, 10, 18)分别存储到某个地址区间为如0~10的哈希表中,如果 哈希函数h(x)=(),将不会产生冲突,其中a mod b表示a除以b的 余数。

将(2,6,10,17)分别存储到某个地址区间为0~10 的哈希表中,如果哈希函数 h(x)=( ),将不会产生冲突,其中 a mod b 表示 a 除以 b 的余数。
x mod 11
x2mod 11
2x mod 11
将(2, 7, 10, 18)分别存储到某个地址区间为如0~10的哈希表中,如果 哈希函数h(x)=(),将不会产生冲突,其中a mod b表示a除以b的 余数。

给定地址区间为 0~9 的哈希表,哈希函数为 h(x) = x % 10,采用线性探查的冲突解决策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地址 0重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请问 89 存储在哈希表哪个地址中。( )
现有一个地址区间为 0~10 的哈希表,对于出现冲突情况,会往后找第一个空的地址存储(到 10 冲突了就从 0 开始往后),现在要依次存储(0,1, 2,3,4,5,6,7),哈希函数为 h(x)=x2 mod 11。请问 7 存储在哈希表哪个地址中( )。
合并序列。有两个长度为N的单调不降序列A和B,序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和,求其中第k小的和。上述参数满足N≤105和1≤K≤N2。
次短路。已知有一个n个点m条边的有向图G,并且给定图中的两个点s和t,求次短路(长度严格大于最短路的最短路径)。如果不存在,输出一行“-1”。如果存在,输出两行,第一行表示此段路经的长度,第二行表示此段路的一个方案。
假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在int 表示范围内,完成下面的判断题和单选题: