下列哪个选项是C++中的关键字?( )
查看答案与解析
本题考察 C++ 语法知识。 class 是类的关键字。(C++关键字)
下列哪个选项是C++中的关键字?( )
本题考察 C++ 语法知识。 class 是类的关键字。(C++关键字)
下面代码输出的是?( )
输出 5>>2 ,应该是 1。(位运算)
以下代码的输出是什么?( )
*p 是—个指向 a 的指针, *&q 相当于对 *p 进行引用,所以修改 *q 就修改了 a 的值。(指针)
下面代码输出的是?( )
应该输出 arr 的第三个元素。(指针)
下列关于排序的说法,正确的是?( )
归并排序可以不改变相同元素的相对位置。(排序算法)
下面关于C++类构造和析构函数的说法,【错误】的是?( )
析构函数不—定必须是虚函数,当类有虚函数并且可能被继承时才必须声明为虚函数。(面向对象:类的相 关知识)
下列关于树和图的说法,【错误】的是?( )
B 应该是—个有向无环图。(树和图结构)
2025 是个神奇的数字,因为它是由两个数 20 和 25 拼接而成,而且 2025 =(20+25)2 。
小杨决定写个程序找找小于 N 的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是?( )
此时应该判断两半的和的平方是否等于原数,而原数是 n2 ,n 是其平方根,所以选择 A。(阅读模拟程序、 字符串函数)
给定一个无向图,图的节点编号从 0 到 n - 1,图的边以邻接表的形式给出。
下面的程序使用深度优先搜索(DFS)遍历该图,并输出遍历的节点顺序。横线处应该填入的是?( )
标记 neighbor 已经入栈并且将 neighbor 入栈,选择 D。(图结构、深度优先搜索)
给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。
子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。
下面的程序横线处应该填入的是?( )
考察 DP 解决最长上升子序列问题,如果 nums[i] > nums[j] ,则以 i 结尾的最长上升子序列可以从以 j 结尾 的最长上升子序列转移而来,所以选择 D 项。(动态规划)
给定一个整数数组 nums,找到其中最长的严格上升子序列的长度。
子序列是指从原数组中删除一些元素(或不删除)后,剩余元素保持原有顺序的序列。
该程序的时间复杂度为?( )
11, 12 两行执行了 O(n2) 次循环,所以复杂度为 O(n2)。(动态规划)
给定两个无向图 G1和 G2 ,判断它们是否同构。图的同构是指两个图的节点可以通过某种重新编号的方式完全匹配,且边的连接关系一致。
为了简化问题,假设图的节点编号从 0 到 n-1,并且图的边以邻接表的形式给出。下面程序中横线处应该给出的是?( )
应该将所有 neighbor ⽤ , 隔起来,因此选择 C。(图结构)
给定一个 m×n的二维网格 grid,每个格子中有一个非负整数。
请找出一条从左上角 (0, 0) 到右下角 (m-1, n-1) 的路径,使得路径上的数字总和最小。每次只能向右或向下移动。
横线处应该填入的是?( )
B。(i, j) 可以从 (i 1 , j) 或者 (i, j 1) 走过来,因此 grid[i][j],选择 B。(动态规划)
给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
下面横线处应该填入的是?( )
dp[i] 表示以 i 结尾的最大子段和。如果 i-1 也在最大子段和中,对应 dp[i-1] + nums[i] ,否则只有 i 在最 大子段和,对应 nums[i] ,所以选择 B。(动态规划)
在哈希表的实现中,冲突解决是一个重要的问题。以下哪种方法 不是 常见的哈希表冲突解决策略?( )
二分查找法用于有序数组中的查找,和哈希表冲突无关。(哈希表)
在C++语法中,表达式 1e6 、 1000000 和 10^6 的值是相同的。( )
1e6 - 这是科学计数法表示的浮点数,值为1000000.0(double类型)
1000000 - 这是整型字面量,值为1000000(int类型)
10^6 - 这是按位异或运算,实际计算的是10 XOR 6 = 12(int类型)
在C++语言中,函数调用前必须有函数声明或定义。( )
本题考查 C++ 语法,函数调用前必须声明或定义过该函数。(C++语法)
快速排序一般是不稳定的。( )
正确, —般的快速排序,和标兵相同的数字的相对顺序可能会发生变化。(快速排序)
long long 类型能表达的数都能使用 double 类型精确表达。( )
long long 可以表示 264 个整数, double 只能表示其中的—部分整数。(数据类型)
使用 math.h 或 cmath 头文件中的函数,表达式 cos(60) 的结果类型为 double 、值约为 0.5 。( )
C++ cos 函数使用的是弧度制。(三角函数)
一颗 N 层的满二叉树,一定有 个结点。( )
满二叉树的节点数只和层数有关。(满二叉树)
邻接表和邻接矩阵都是图的存储形式。为了操作时间复杂度考虑,同一个图可以同时维护两种存储形式。( )
两种维护方式并不冲突。(图结构的存储)
子类对象包含父类的所有成员(包括私有成员)。从父类继承的私有成员也是子类的成员,因此子类可以直接访问。( )
父类的私有成员子类不能直接访问。(面向对象:类的相关知识)
动态规划算法通常有递归实现和递推实现。但由于递归调用在运行时会由于层数过多导致程序崩溃,有些动态规划算法只能用递推实现。( )
递归算法还需要在栈中存储返回地址等信息,内存开销相对递推写法更大,容易导致栈溢出。(动态规划、 递归)
按照下面的规则生成一棵二叉树:
以一个人为根节点,其父亲为左子节点,母亲为右子节点。对其父亲、母亲分别用同样规则生成左子树和右子树。
以此类推,记录30代的直系家谱,则这是一棵满二叉树。( )
当记录的代数较多时,不同的后代可能有相同的祖先,这导致形成的并不—定是—棵树。(二叉树)
图上移动
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一张包含 个n 结点与 m 条边的无向图,结点以 1、2、……、n 标号。
小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。
对于每个结点 i(1<=i<=n),小 A 想知道从结点 i 出发恰好移动步1、2、……、k 之后,小 A 可能位于哪些结点。
由于满足条件的结点可能有很多,你只需要求出这些结点的数量。
【输入描述】
第一行,三个正整数 n、m、k,分别表示无向图的结点数与边数,最多移动的步数。
接下来 m 行,每行两个正整数 ui、vi,表示图中的一条连接结点 ui 与 vi 的无向边。
【输出描述】
共 n 行,第 i 行(1<=i<=n )包含 k 个整数,第 j 个整数( 1<=j<=k)表示从结点 i 出发恰好移动 j 步之后可能位于的结点数量。
【样例输入1】
【样例输出1】
【数据范围】
对于 20% 的测试点,保证 k=1。
对于另外 20% 的测试点,保证 1<=n<=50,1<=m<=50 。
对于所有测试点,保证 1<=n<=500,1<=m<=500 ,1<=k<=20 ,1<=ui、vi<=n 。
等价消除
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一个仅包含小写英文字母的字符串 。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。
小 A 想知道 S 有多少子串是可以被等价消除的。
一个字符串 S' 是 S 的子串,当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。
【输入描述】
第一行,一个正整数 |S|,表示字符串 S 的长度。
第二行,一个仅包含小写英文字母的字符串 S。
【输出描述】
一行,一个整数,表示答案。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 S 中仅包含 a 和 b 两种字符。
对于另外 20% 的测试点,保证 1<=|S|<=2000。
对于所有测试点,保证 1<=|S|<=200000。