分类题库
信息学奥赛题库
按题型、年份与知识点筛选，快速定位练习题。
题目列表
共 45 题
A62791
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于? ( )
2025年
单选
A62635
G是一个非连通无向图(没有重边和自环)，共有 28条边，则该图至少有( )个顶点。
2024年
单选
A62595
假设一个包含 n 个顶点的无向图，且该图是欧拉图。一下关于该图的描述中哪一项不一定正确？（）
2024年
单选
A62587
如图是一张包含 7 个顶点的有向图。如果要删除一些边，使得从节点 1 到节点 7 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（）
2024年
单选
A62582
次短路：已知有一个 n 个点 m 条边的有向图 G，并且给定图中的两个点 s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示此段路经的长度，第二行表示此段路的一个方案
2024年
编程题
A62020
假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于m=θ(n)的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小。
2023年
单选
A62017
以下连通无向图中，( )一定可以用不超过两种颜色进行染色。
2023年
单选
A62010
在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少，一棵树可能有多个重心，请问下面哪种树一定只有一个重心？（）
2023年
单选
A61977
无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G有5个顶点，则它共有()条边。
2023年
单选
A61964
有n个顶点的无向连通图，至少有 n-1条边。( ）
2023年
判断
A61934
对一个n个顶点、m条边的带权有向简单图，用 Diikstra 算法计算单源最短路时，如果使用二叉堆进行优化，则其时间复杂度为( ）。
2023年
单选
A61933
有向图G入度是2023，则出度是（ ）。
2023年
单选
A61920
对同一个图而言，拓扑排序的结构是唯一的。
2023年
判断
A61914
有n个城市，编号为 1,2,3,... ,n。城市之间有 m条双向的公路，每条公路连接着两个城市。从公路一端的城市走到另一端的城市，会损失力气。每次经过一个城市，都会被收取一定的过路费(包括起点和终点)。路上并没有收费站。小明从城市1出发，最终要到达地市n停下，而他的力气最多为 s，出发时他的力气是满的。如果他到达目的地,所剩力气值变成负数了，则他就无法到达城市 n，在旅途中力气是不会恢复的。小…
2023年
编程题
A61871
旅游巴士(bus) 【
2023年
编程题
A61801
信息学奥赛练习题：电路维修【
2023年
编程题
A61742
如图，每条边上的数字表示该边的长度，则从A到 E 的最短距离是 ( ）。
2023年
单选
A61649
考虑N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素
2022年
单选
A61630
强连通图的性质不包括( )
2022年
单选
A61629
每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正 规图，其中包含欧拉回路的不同2正规图的数量为( )。
2022年
单选