信息学奥赛-提高级 题库
在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?( )
考虑一条链的情况下,如果树的结点是偶数个数,那么中间的两个点都可以是重心,所以必须是奇数个结点的树。
如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?

拓扑排序的前提条件是有向无环图,图中存在一个1→3→4→1的环,删除环上任意一条边就可以了。
若n = ∑ki=016i·xi,定义f(n) = ∑ki=0xi;其中x∈{0,1,…,15},对于给定自然数n0,存在序列n0, n1, n2, …, nm,其中对于1≤i≤m都有nm=nm-1,称nm为n0关于f的不动点。问在10016至1A016中,关于f的不动点为9的自然数个数为()。
10
11
12
13
题目大意:n是一个16进制的数字,f(n)表示n的16进制状态下各位之和,如果不断计算n=f(n),最终n会停在某个数字不再改变。询问(100)16到(1A0)16中有多少个数字会停在数字9。
考虑位数只有3位,并且最高位是1,第二位最多是A,第一次的f(n)只能是9或者(18)16,f(n) = 9一共9种方案(均为16进制):108, 117, 126, 135, 145, 154, 163, 171, 180。f(n) = 9一共2种方案(均为16进制):18F, 19E。
.将第10行中的">"替换为">=",那么原输出与现输出的大小关系为()
③处应填()
你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下:
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为( )
若元素 a、b、c、d、e、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次退栈操作,则不可能得到的出栈序列是( )。
假设在基数排序过程中,受宇宙射线的影响,某项数据异变为一个完全不同的值。请问排序算法结束后,可能出现的最坏情况是( )
一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第 100 号结点的父结点是第( )号。
强连通图的性质不包括( ):
每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图,其中包含欧拉回路的不同 2 正规图的数量为( )