信息学奥赛-入门级 题库
假设输入的a数组和k均为正整数,执行第18行代码时,一定满足的条件不包括()。
假设输入的a数组和k均为正整数,但a数组不一定有序,若误删去第13行的"std::sort(a+1,a+n+1);",程序有可能出现的问题有()。
如果输入的a={1,2,…,n},而且b数组中数字均为1~n中的正整数,则上述代码等价于下面哪个问题:()。
以下哪个序列对应数组 0 至 8 的 4 位二进制格雷码(Gray code)?
当输入的 cost 数组为{1,100,1,1,1,100,1,1,100,1}时,程序的输出为( )。
如果输入的 cost 数组为{10,15,30,5,5,10,20},程序的输出为( )
若将代码中的 min(dp[i-1],dp[i-2])+cost[i-1]修改为 dp[i-1]+cost[i-2],输入 cost 数组为{5,10,15}时,程序的输出为( )
考虑一个有向无环图,该图包括4条有向边:(1,2),(1,3),(2,4),和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序?( )
访问2,3之前要先访问1,访问4之前要先访问3或4,所以一个有效的拓扑序列为:1,2,3,4。
链表和数组的区别包括( )。
这个题其实不太严谨,但C相比其他更正确。
一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。
考察完全二叉树的线性数组表示法。根节点i的左右孩子分别是2i和2i+1。也可以直接画出二叉树观察。
以下排序算法的常见实现中,哪个选项的说法是错误的:( )。
考察排序的稳定性。选择排序是不稳定的,冒泡、插入、归并都是稳定的。
一棵二叉树如右图所示,若釆用顺序存储结构,即用一维数组元素存储该二叉 树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i 处,右孩子位于下标2i+l处),则该数组的最大下标至少为?

堆式编号,最大值是最深的那层最靠右侧的节点, 编号为((1*2+1)*2+1)*2+1=15
当n=10时,若b数组满足,对任意0<=i<n,都有b [i]=i + 1,那么输出最 大为()。
当n二100时,若b数组满足,对任意0 S i < 71,都有b [i]二1,那 么输出最小为()。
给定一个含N个不相同数字的数组,在最坏情况下,找出其中最大或最小的 数,至少需要N - 1次比较操作。则最坏情况下,在该数组中同时找最大与 最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整, ⌊ ⌋表示向下取整)
设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个排好序 的数组,任何以元素比较作为基本运算的归并算法在最坏情况下至少要做 ( ) 次比较。
一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1 ,若某结点的下标为i ,则其左孩子位于下标2i 处、右孩子位于下标(2i+1)处) ,则图中所有结点的最大下标为 ( ) 。

给定含有n个不同的数的数组L=<x1,x2, ...,xn>。如果 L 中存在xi(1<i<n) 使得 x1<x2< ... <xi-1<xi>xi+1>... >xn, 则称L是单峰的,并称xi 是L的“峰顶”。现在已知 L 是单峰的,请把a-c 三行代码补全到算法中使得算法 正确找到L的峰顶。
Search(k+1, n)
Search(1, k-1)
return L[k]
Search(1, n)
1. k←⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5. then
6. else
正确的填空顺序是( )。
( )的平均时间复杂度为 O(nlog n),其中 n 是待排序的元素个数。