信息学奥赛-提高级 题库
以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S,输出S中第二小的数SecondMin。在最坏情况下,该算法需要做( )次比较。
if (S[1] < S[2]) {
FirstMin = S[1];
SecondMin = S[2];
} else {
FirstMin = S[2];
SecondMin = S[1];
}
for (i = 3; i <= n; i++)
if (S[i] < SecondMin)
if (S[i] < FirstMin) {
SecondMin = FirstMin;
FirstMin = S[i];
} else {
SecondMin = S[i];
}
下面的故事与( )算法有着异曲同工之妙。
从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事....’?
枚举
递归
贪心
分治
1948年,( )将热力学中的熵引入信息通信领域,标志着信息论研究的开端。
已知一棵二叉树有2013个节点,则其中至多有( )个节点有2个子节点。
在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。右图是一个有 5 个顶点、8 条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边。

2
3
4
5
斐波那契数列的定义如下:F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果用下面的函数计算斐波那契数列的第 n 项,则其时间复杂度为( )。
int F(int n)
{
if(n<=2)
return 1;
else
return F(n-1)+F(n-2);
}
二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么,二叉查找树的( )是一个有序序列。
将(2,6,10,17)分别存储到某个地址区间为0~10 的哈希表中,如果哈希函数 h(x)=( ),将不会产生冲突,其中 a mod b 表示 a 除以 b 的余数。
x mod 11
x2mod 11
2x mod 11
IPv4 协议使用 32 位地址,随着其不断被分配,地址资源日趋枯竭。因此,它正逐渐被使用( )位地址的 IPv6 协议所取代。
二分图是指能将顶点划分成两个部分,每一部分内的顶点间没有边相连的简单无向图。那么,12个顶点的二分图至多有( )条边。
( )是一种通用的字符编码,它为世界上绝大部分语言设定了统一并且唯一的二进制编码,以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。
对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为( )。
T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数,且有递归式T(n)=2*T(n/2)+2n,那么 T(n)=( )。
目前计算机芯片(集成电路)制造的主要原料是( ),它是一种可以在沙子中提炼出的物质。(2012年提高组初赛)
( )是主要用于显示网页服务器或者文件系统的 HTML 文件内容,并让用户与这些文件交互的一种软件。
无论是TCP/IP模型还是OSI模型,都可以视为网络的分层模型,每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”,以下最恰当的是( )。



