-J组预赛第1-21轮真题分析

2022 年 9 月 15 日 5,801

分析1

测试题： 1.下列哪项不属于面向对象的编程语言（ ）。

A.C++

B.

Java语言

直流

分析：

背景知识：

从描述客观系统的角度来看，编程语言可以分为：

(1)面向过程的语言

由“数据结构+算法”编程范式组成的编程语言称为面向过程的语言。代表性语言包括C等。

(2)面向对象语言

由“对象+消息”编程范式组成的编程语言称为面向对象语言。 比较流行的面向对象语言有Basic、Java、C++等。

知识点分类：

计算机基础知识-计算机语言

答案分析：

本题中选项A、B、C都是面向对象的编程语言。 只有选项D中的C语言是面向过程的编程语言，所以正确答案应该是D。

分析2

测试问题： 2.下列哪个奖项与计算机领域最相关（ ）。

A.奥斯卡奖

B、图灵奖

C、诺贝尔奖

D.普利策奖

分析：

背景知识：

奥斯卡奖

奥斯卡一般指奥斯卡金像奖。 奥斯卡金像奖（ ），又称奥斯卡金像奖（中文为学院奖），是由美国电影艺术与科学学院主办的电影奖项，创立于1929年。该奖项是历史最悠久、最权威、最专业的电影奖项在美国，也是世界上最具影响力的电影奖。 PS：你听说过小金人吗？ 奥斯卡是一座10.25英寸高的男性人体雕像。 铜像手持剑，站在胶片上。 表面镀金，故称奥斯卡奖。

图灵奖

图灵奖，全称AM图灵奖（ACM AM Award），是计算机协会（ACM）于1966年设立的计算机奖项，以阿兰·图灵（1912年1954年6月23日—1954年6月7日）的名字命名。英国数学家、逻辑学家，被誉为计算机之父、人工智能之父。 旨在奖励对计算做出重要贡献的个人。 图灵奖获奖要求极高，颁奖流程极其严格。 一般来说，每年仅授予一名计算机科学家。 图灵奖是计算机领域的国际最高奖项，被誉为“计算机界的诺贝尔奖”。

诺贝尔奖

诺贝尔奖（瑞典语：Nobel，英语：）是指根据诺贝尔1895年遗嘱设立的五个奖项，包括：物理奖、化学奖、和平奖、生理学或医学奖和文学奖。 诺贝尔经济学奖由瑞典中央银行于1968年设立，以表彰经济学领域的杰出贡献。 人们。

普利策奖

普利策奖（The ），也称为普利策新闻奖。 该奖项根据美国报业巨头约瑟夫·普利策（ ）的遗愿于1917年设立，后来发展成为美国新闻界的最高荣誉奖。 经过不断完善的评选制度，普利策奖已成为新闻领域的国际最高奖项，被誉为“新闻界的诺贝尔奖”。

知识点分类：

计算机基础知识-计算机通用知识

答案分析：

本题中，选项A奖项属于电影领域； C选项奖项属于物理、化学、和平、生理学、医学和经济学领域； D选项奖项属于新闻领域。 只有选项B图灵奖是在计算领域。 所以正确答案应该是选项B。

真题解析3

3、目前主流计算机存储数据最终都是转换成( )数据进行存储。

A.二进制

B、十进制

C、八进制

D、十六进制

分析：

背景知识：

基本系统又称为进位计数系统，是一种人为定义的带进位的计数方法。 对于任何基数制——X基数制，是指对每一位数字进行的数运算，每X一位进位。十进制每十分之一进位一位，十六进制每十六位进位一位，二进制结转每两个，依此类推，基于 x 的系统结转每个 x。

在我们的日常生活中，十六进制的例子有很多，比如：

一分六十秒，每六十加一，就是六十进制；

一天有二十四小时，每二十四小时加一，就是十六进制；

一周有七天，每第七天紧跟着一天，这就是七进制；

一年有十二个月，每十二个月加一，为十二基制；

计算机使用二进制的原因：

1、技术实现简单：计算机是由逻辑电路组成的。 逻辑电路通常只有两种状态，开关接通和断开。 这两种状态可以用“1”和“0”来表示。

2、简化运算规则：两个二进制数的和、积运算有三种组合。 运算规则简单，有利于简化计算机内部结构，提高运算速度。

3、适合逻辑运算：逻辑代数是逻辑运算的理论基础。 二进制只有两位数字，与逻辑代数中的“真”和“假”相符。

4、转换方便：二进制和十进制、八进制和十六进制数字很容易相互转换。

5、意味着数据抗干扰能力强，可靠性高：由于每一位数据只有高和低两种状态，当受到干扰到一定程度时，仍然可以可靠地区分是否为高或低。

知识点分类：

计算机基础知识库及基数转换

答案分析：

本题B选项是十进制。 由于人体解剖学的特点，双手都有十个手指。 因此，在人类自发采用的进位系统中，十进制是最常用的一种。 引入选项C八进制和D选项十六进制是因为它们很容易在二进制之间转换，并且比二进制更方便读、写和记忆（例如IPv6地址用十六进制表示）。 只有选项A二进制被广泛应用于计算机数据处理中。 所以正确答案应该是A。

真题解析8

8. 如果一棵二叉树只有根节点，那么二叉树的高度为 1。高度为 5 的完全二叉树有哪些 () 不同形式？

A.16

B、15

C.17

D.32

分析：

背景知识：

二叉树：二叉树（Tree）是n（n>=0）个节点的有限集合。 该集合要么是一个空集（称为空二叉树），要么由一个根节点和两个不相交的树组成。 二叉树由根节点的左子树和根节点的右子树组成。

满二叉树：在二叉树中。 如果所有分支节点都有左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树。

完全二叉树：有n个节点的二叉树按层编号。 如果数字是 i(1

后序遍历：

遍历过程为：

其左子树的后序遍历和右子树的后序遍历均访问根节点。

后序遍历顺序 =>

前缀表达式、中缀表达式和后缀表达式都是四种算术运算的表达式，用于对四种算术运算求值。

中缀表达式：

中缀表达式是常见的运算表达式，如(1+2)×3-4

前缀表达式：

前缀表达式也称为波兰表达式。 前缀表达式的运算符位于操作数之前，如 × + 3 4 5

后缀表达式：

后缀表达式也称为逆波兰式表达式，与前缀表达式类似，只不过运算符位于操作数之后，例如 1 2 + 3 × 4 –

知识点分类：

编程基础-树

答案分析：题干中的表达式a*(b+c)*d是一个中缀表达式。 转换成二叉树后，就是中序遍历的结果。 后缀表达式就是按后序遍历二叉树（如下图）

后序遍历顺序 => abc + * d *

结果序列为：abc+*d*，所以正确答案应该是B。

真题解析10

10、有6人，两人组成一队，一共组成三队。 团队编号不区分。 有( )种不同的组队情况。

A.10

B、15

C.30

D.20

分析：

背景知识：

安排（）：

从n个不同的元素中，随机选择m(m≤n)个元素，并按一定的顺序排列在一列中，称为从n个元素中m个元素的排列。

从n个不同元素中提取m(m≤n)个元素的所有排列数称为从n个不同元素中提取m个元素的排列数，用符号P(n,m)表示。

计算公式为：P(n,m)=n(n-1)(n-2)...(n-m+1)=n!/(nm)!

嗯！ 表示n(n-1)(n-2)…1，且指定0!=1。

例如：P(6,2) = 6!/(6-2)! = 6!/4! = 6*5*4*3*2*1/4*3*2*1 = 30

组合（）

从n个不同的元素中，取出任意m(m≤n)个元素组合成一个组，称为从n个元素中取出m个元素的组合。

从n个不同元素中取出的m(m≤n)个元素的所有组合数称为从n个不同元素中取出的m个元素的组合数，用符号c(n,m)表示。

计算公式为：C(n,m)=P(n,m)/m！

嗯！ 表示n(n-1)(n-2)…1，且指定0!=1。

例如：C(6,2) = P(6,2) / 2！ = 6*5*4*3*2*1/2*1 = 15

知识点分类：

解决应用问题——排列组合

答案分析：

本题要求六人中两人组成一队，总共组成三队，则：

对于第一队：

此时有6人可供选择，共有C(6,2)=15种组合

对于第二队：

此时有4人可供选择，共有C(4, 2) = 6种组合

对于第三队：

此时只剩下2人可供选择，组合也只有1种。

所以一共有15*6*1=90种不同的组合。

题目要求团队编号不要区分（这里可以假设6个人编号为A、B、C、D、E、F），因此同一团队在组合中会出现6次。

例如：队伍组合为AB一队、CD一队、EF一队

那么AB、CD、EF AB、EF、CD CD、AB、EF CD、EF、AB EF、AB、CD EF、CD、AB这六种组合按照题目要求都视为同一个队伍情况。

因此，无论队伍数量多少，都有90/6=15种不同的组队情况。

正确答案应该是选项B。

真题解析11

11、数据压缩编码中的哈夫曼编码方法本质上是一种（ ）策略。

A、枚举

B、贪婪

C、递归

D.动态规划

分析：

背景知识：

枚举算法：根据问题本身的性质，在有限的可能解集合中，一一列出问题的所有可能解，并在一一列出的过程中，利用问题给出的测试条件来判断每个可能的解是否是问题的真正解，如果不是，则丢弃； 如果有，请采纳。

贪心算法：贪心算法是指在解决问题时，总是做出当前最好的选择，以便尽快得到更好的解决方案。 当求解达到算法中的某个步骤并且无法继续时，算法停止。

递归算法：通过反复将问题分解为相似的子问题来解决问题的算法。 递归算法可以将大规模问题转化为小规模的相似子问题来解决。

动态规划算法：通过将要解决的问题分解为若干个子问题，首先求解子问题，然后从这些子问题的解中得到原问题的解。

知识点分类：

解决应用问题-基础算法

答案分析：

霍夫曼提出了一种贪心算法来构造最优前缀码，所得到的编码方案称为霍夫曼编码。 哈夫曼编码是一种非常有效的编码方法，广泛用于数据文件压缩。 其压缩率通常在20%至90%之间。 霍夫曼编码算法利用文件中字符的频率表来建立每个字符作为0和1的字符串的最佳表示。霍夫曼编码是使用贪心算法的典型例子，所以这道题的正确答案应该是B.

真题解析12

12. 由 1、1、2、2、3 五个数字组成的三位数共有 ( ) 个。

A.18

B、15

C.12

D.24

分析：

背景知识：

安排（）：

从n个不同的元素中，随机选择m(m≤n)个元素，并按一定的顺序排列在一列中，称为从n个元素中m个元素的排列。

从n个不同元素中提取m(m≤n)个元素的所有排列数称为从n个不同元素中提取m个元素的排列数，用符号P(n,m)表示。

计算公式为：P(n,m)=n(n-1)(n-2)...(n-m+1)=n!/(nm)!

知识点分类：

解决应用题-排列

答案分析：

这个问题可以分两种情况来考虑：

1、三位数的百位、十位、个位中没有重复的数字，如下图：

此时有P(3,3)=6个三位数组合：

123、132、213、231,312、321

2、三位数的百位、十位、个位中有重复的数字，如下图：

此时有4*3=12个三位数组合：

112,121,,131,311

221,212,122 223,232,322

将两种情况相加：6+12=18。 有 18 种不同的三位数组合，所以正确答案应该是 A。

真题解析13

13.考虑以下递归算法

solve(n)  
 if n <=1 return 1   
  else if n>=5 return n*solve(n-2)  
 else return n*solve(n-1)

那么调用solve(7)得到的返回结果为( )

A.105

B.840

C.210

D.420

分析：

背景知识：

通过一系列调用语句直接或间接调用自身的函数称为递归函数。 递归通常将一个大而复杂的问题转化为与原始问题类似的较小问题。 如果一个问题要使用递归函数（方法）来解决，它必须满足两个条件：

1.这个问题可以转化为一个新问题。 新问题的解与原问题一模一样，但问题的规模变小了。

2、递归必须有明确的结束条件（边界）

知识点分类：

C++ 编程-函数与递归

答案分析：

首先分析一下问题中给出的代码：

solve(n)  //定义名为solve的函数，参数为n 
if n <=1 return 1  //如果参数n小于或等于1，返回值为1  
else if n>=5 return n*solve(n-2)// 如果参数n大于或等于5，则返回值为：n*solve(n-2) 
 else return n*solve(n-1)//其他情况下，返回值为：n*solve(n-1)

本题递归算法的递归函数调用流程如下图所示：

求解(7)=7*求解(5)

求解(5)=5*求解(3)

求解(3)=3*求解(2)

求解(2)=2*求解(1)

求解(1)=1

所以求解(7)=7*5*3*2*1=210，正确答案应该是C。

真题解析14

14、以a为起点，对右边的无向图进行深度优先遍历，则b、c、d、e这四个点中可能最后遍历到的点数为()。

A.1

B.2

C.3

D.4

分析：

背景知识：

从图中的某个顶点开始，依次访问图中剩余的顶点，使得每个顶点只被访问一次的过程称为图的遍历。

图的遍历有两种类型：深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历（）从图中的某个顶点v开始，访问这个顶点，然后从v的未访问过的相邻点开始深度优先遍历图，直到图中所有与v有路径相连的顶点都有被访问过。 到达。 如果此时图中还有未访问的顶点，则选择另一个未访问的顶点作为新的源点，重复上述过程，直到图中的所有顶点都被访问过。

广度优先遍历()从图中的某个顶点v开始，先访问起始点v，然后依次访问v的所有相邻点w1,w2,...,wt，然后依次访问所有相邻点wl， w2,..., wt 未访问的顶点。 依此类推，直到图中所有具有连接到源点v的路径的顶点都被访问过。

知识点分类：

算法-图论算法-图的深度优先遍历算法

答案分析：

深度优先遍历算法的流程图如下：

本题存在三种可能的深度优先遍历顺序：

=>abdce=>acedb=>acdbe

有可能最后遍历的点只能是e或b，所以有可能最后遍历的点数是2，所以正确答案应该是B。

真题解析15

15、四个人想从A点坐船过河到B点，船从A点出发，船一次最多可容纳两人。 已知四人单独乘船过河的时间各为1、2、4、8，两人乘船过河的时间为两人时间中较大者人们独自过河。 那么最短的（）时间可以让四个人过河到达B点（包括从B点开船回到A点的时间）。

A.14

B.15C。 16D。 17 号

分析：

背景知识：

这道题是新奥比赛中的一道经典题——过河题。 典型描述如下：

有 X 个人想要过河，每个人过河需要时间 T。 河上只有一艘船，一次最多可容纳两人划过河。 两个人划船过河所需的时间取决于谁过河时间更长的人。 例如，两个人A和B过河所需的时间分别为Ta、Tb。 那么，他们划船过河所花的时间为：max{Ta,Tb}（即花时间多的人过河所花的时间为Time计算），求最短的时间每个人都需要过河。

问题分析：

假设X=4，即有四个人要过河。 假设四个人分别用a、b、c、d表示，所需时间Ta

1、过河顺序为：ac、a、ad、a，耗时：t1=2Ta+Tc+Td

让需要时间最少的a 分别送c 和d 过河。 因为a需要的时间最少，所以a每次将船送回的时间也最少。 所以选择发送可能是最好的方式。

2、过河顺序为：ab,a(b),cd,b(a) 耗时：t2=Ta+2Tb+Td

如果c和d都需要很长时间才能过河，那么就让他们一起过去。 这样可以有效去掉c的过河时间比较少，然后提前放走其中一个。 让b留在对岸（之前被a送到对岸），然后还船。

以上两种是唯一有希望送C、D过河的方法。

t1−t2=Ta+Tc−2Tb

显然，这两个选项选择哪一个与Ta+Tc−2Tb的值有关。

当n≥4人要过河时，首先采用上述两种方法中较好的一个，送最大的两人过河。 那么问题就变成了：找到最优策略，将剩下的n-2人送过河。 重复这个策略，直到n=2，两个人就可以直接走。

知识点分类：

算法-基本算法-贪心法

答案分析：

本题有4个人（假设a、b、c、d）过河。 由题可知，过河次数为Ta=1，Tb=2，Tc=4，Td=8。

通过背景知识分析可知，选择哪种过河序列是由t1-t2的值决定的。 计算t1-t2=Ta+Tc-2Tb=1+4-2*2=1>0

所以选择第二个过河顺序。 ab、a(b)、cd、b(a)、ab所需时间为：Ta+3*Tb+Td=1+3*2+8=15，所以正确答案应该是B。

真题解析16

#include 
using namespace std;
int n;int a[1000];
int f(int x)
{    int ret = 0;
    for (; x; x &=x-1) ret++;
    return ret;
 }
  int g(int x)
 {
     return x & -x;
 }
  int main()
 {
     cin >> n;
     for (int i = 0; i < n; i++)
 cin >> a[i];
     for (int i = 0; i < n; i++)
         cout << f(a[i]) + g(a[i]) << '';
     cout << endl;
     return 0;
 }

16、当输入n等于1001时，程序不会导致下标越界（ ）。

注：第16-20题为阅读程序题型中的判断题，第21题为阅读程序题型中的选择题。

分析：

背景知识：

数组是相同数据类型的元素的集合。 定义数组时，需要指定元素的类型、数组名称以及数组包含的元素数量。

数组定义

语法格式为：

数组类型数组名[常量表达式]；

例如：int book[100]；

数组类型是数组中元素的数据类型，数组名是表示数组首地址的符号常量，常量表达式是数组中元素的个数，数组下标从0开始。

数组存储

通过添加数组名和下标值即可访问数组中对应的元素。 下标值从0开始。对于n个元素的一维数组，下标值的范围是0到n-1。

数组越界

给数组元素赋值或者引用数组元素时，一定要注意下标值不能超出数组定义的范围，否则数组就会越界。

知识点分类：

C++编程-数组-数组定义、数组和数组下标的含义

答案分析：

首先分析一下问题中给出的代码：

#include 
using namespace std;
int n;//定义数组中元素的个数
int a[1000];//定义一个可以存储1000个元素的数组a 
int f(int x)  //定义函数f，对x与x-1循环做位运算，并返回循环执行的次数
 {
    int ret = 0;
    for (; x; x &=x-1) ret++;
    return ret;
 }
  int g(int x) //定义函数g，返回x与-x做位运算的值
 { 
    return x & -x;
 } 
int main( )
 { 
 cin >> n;   //输入数组元素的个数  
 for (int i = 0; i < n; i++)   cin >> a[i];//初始化数组a 
 for (int i = 0; i < n; i++)   //对数组的每个元素调用函数f和g，将结果相加并输出   
    cout <
  cout << endl;
  return 0;
}

#include 
using namespace std;
int n;
int a[1000];
int f(int x)
{
    int ret = 0;
    for (; x; x &=x-1) ret++; 
   return ret;
 }
  int g(int x)
 { 
    return x & -x;
 } 
 int main()
 {  
   cin >> n; 
    for (int i = 0; i < n; i++)
 cin >> a[i];
     for (int i = 0; i < n; i++) 
        cout << f(a[i]) + g(a[i]) << ''; 
    cout << endl; 
    return 0;
 }

#include 
using namespace std;
int n;//定义数组中元素的个数
int a[1000];//定义一个可以存储1000个元素的数组a 
int f(int x)  //定义函数f，对x与x-1循环做位运算，并返回循环执行的次数 
{
    int ret = 0; 
   for (; x; x &=x-1) ret++;
    return ret;
 }
  int g(int x) //定义函数g，返回x与-x做位运算的值 
{
     return x & -x;
 } 
int main( ) 
{
  cin >> n;   //输入数组元素的个数  
 for (int i = 0; i < n; i++) 
  cin >> a[i];//初始化数组a 
 for (int i = 0; i < n; i++)   //对数组的每个元素调用函数f和g，将结果相加并输出    
   cout <
  cout << endl;
  return 0;
}