信息学奥赛-提高级 题库
对于一个包含n个结点和m条边的有向无环图(DAG),其拓扑排序的结果有多少种可能?
只有1种
最多n种
等于n-m种
以上都不对
拓扑排序是找到n个节点的排列顺序,使图中每一条a指向b的边,在排列中a都出现在b前面。举例n=3、m=0时,任何1-3的排列都符合要求,数量为3!=6种,A、B、C选项均不符合。
假设一个包含n个顶点的无向图,且该图是欧拉图。以下关于该图的描述中哪项不一定正确?( )
通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图,称为欧拉图。很容易构造一个偶数条边的欧拉图
设有一个10个顶点的完全图,每两个顶点之间都有一条边,有多少个长度为4的环( )?
完全图,所以任意找四个点都可以构成长度为4的环,选4个点的方案数是C(10,4)=210。4个点的圆排列4!/4=6;无向图,所以正反方向视为同一种环,6/2=3。210*3=630
设有一个长度为n的01字符串,其中有k个1,每次操作可以交换相邻两个字符。在最坏的情况下将这k个 1移到字符串最右边所需要的交换次数是( )?
最坏的情况是距离目标位置最远,也就是K个1都在最左侧,此时,第K个1移到第n,需要(n-k)步,一共k*(n-k)
如图是一张包含7个顶点的有向图。如果要删除一些边,使得从节点1到节点7没有可行路径,且删除的边数最少,请问总共有多少种可行的删除边的集合( )?

首先发现至少需要删除两条边。枚举,可以找到四种删除方案,删除②→⑤和④→⑥、删除⑤→⑦和⑥→⑦、删除①→②和④→⑥、删除⑤→⑦和④→⑥
以下连通无向图中,( )一定可以用不超过两种颜色进行染色
完全三叉树
平面图
边双连通图
欧拉图
能用两种颜色染色的图必须是二分图,而任何一棵树都可以按照深度划分成二分图。
最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,…,xm}和Y={y1,y2,y3,…yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,Z2,Z3,…,Zk},使得序列Z既是序列X的子序列,又是序列Y的子序列,且序列Z的长度k在满足上述条件的序列里是最大的。(注:序列A是序列B的子序列,当且仅当在保持序列B元素顺序的情况下,从序列B中删除若干个元素,可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和"ABABCBABA"的最长公共子序列长度为( )
可以使用经典的动态规划算法,可以看出最长公共子序列是“ABAABA”。
假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?
如果数组已经排序,并且每次都取第一个元素作为基准元素。那么每次递归时,待排序区间都只会减少一个数,所以深度会达到n层,总复杂度是O(n2)。
如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?

拓扑排序的前提条件是有向无环图,图中存在一个1→3→4→1的环,删除环上任意一条边就可以了。
强连通图的性质不包括( ):
每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图,其中包含欧拉回路的不同 2 正规图的数量为( )
G 是一个非连通简单无向图(没有自环和重边),共有 36 条边,则该图至少有( )个点。
设一个三位数
a, b, c 均为 1~9 之间的整数,若以 a、 b、 c 作为三角形的三条边可以构成等腰三角形(包括等边),则这样的 n 有( )个。
现有一段8分钟的视频文件,它的播放速度是每秒24帧图像,每帧图像是 一幅分辨率为2048x1024像素的32位真彩色图像。请问要存储这段原始无 压缩视频.需要多大的存储空间?()。
二分图是指能将顶点划分成两个部分,每一部分内的顶点间没有边相连的简单无向图。那么,24个顶点的二分图至多有()条边。
(2.5分)若输入的第一个字符串长度由100个不同的字符构成,第二 个字符串是第一个字符串的倒序,输入的m为0,则输岀为()。
(4分)若两个字符串的长度均为n, 且0<m<n-1,且两个字符串的构 成相同(即任何一个字符在两个字符串中出现的次数均相同),则下列 说法正确的是()。提示:考虑输入与输出有多少对字符前后顺序不 一样。