GESP-C++七级 题库
一个简单无向图有10个结点、30条边。再增加多少条边可以成为完全图。( )
n个结点的完全无向图,最多有n*(n-1)/2条边。10个结点最多:10*9/2=45条边,所以还需要15条边。
上题中程序的时间复杂度为( )。
代码的核心部分是一个双重循环,每个循环从1~n,所以时间复杂度为O(N2)
下列选项中,哪个可能是下图的广度优先遍历序列( )。

1, 3, 5, 7, 4, 2, 6, 8, 9
9, 4, 2, 1, 3, 7, 5, 6, 8
1, 3, 5, 7, 6, 8, 9, 4, 2
9, 4, 7, 2, 1, 3, 5, 6, 8
根据广度优先搜索的概念,从1个点出发,首先搜索所有与该点相邻的点,再进一步搜索相邻点的相邻点。 根据全面扩散,逐层递进。
对于如下图的二叉树,说法正确的是( )。

先序遍历为123,中序遍历为132,后序遍历为321,答案选D
关于图的深度优先搜索和广度优先搜索,下列说法错误的是( )。
广度优先搜索往往使用队列按照节点的深度有序的方式依次遍历,很容易发现,后序遍历中节点的深度并不有序。
下面关于图的说法正确的是( )。
每条有向边都会贡献一个入度和一个出度,所以所有顶点的⼊度和出度的总和就是图的边数的两倍,选项D正确。
图的存储和遍历算法,下面说法错误的是( )。
图的深度优先搜索和⼆叉树的先序遍历都基于深度优先的原理。
如下图所示的邻接表结构,表示的是下列哪个选项中的图?





注意到存边方式是邻接表,0号点(V1)连向的是3号点(V4)和1号点(V2),1号点连向的是4,2,0号点,2号点连向的是4,3,1号点,依次类推,可以选出正确选项C。
如下图所示的邻接矩阵(inf表示无穷大),表示的是下列哪个选项中的图?





注意到存边方式是邻接矩阵,0连向2,3,距离分别是12和30,1不连向任何人,2连向4,距离是32,依次类推,可以选出正确答案A。
下面 count_triple 函数的时间复杂度为( )。
两层for循环,每层for循环的上界均为n,总时间复杂度为%O(n^2)%
下列选项中,哪个可能是下图的深度优先遍历序列( )。

深度优先遍历需要按照能走就走的原则进行遍历,A选项5后面应该是6,B选项3后面应该是7,D选项8后面应该是5
下列选项中,哪个可能是下图的深度优先遍历序列( )。

下面代码可以用来求最长上升子序列(LIS)的长度,如果输入是: 5 1 7 3 5 9 ,则输出是( )。

9 7 5 1 1 9
1 2 2 3 4 4
1 3 5 7 9 9
1 1 1 1 1 1