一、单选题
1、在二进制下，1011001 + （ ）= 1100110。
A 1011
B 1101
C 1010
D 1111
解析：【喵呜刷题小喵解析】：
在二进制下，我们需要找到一个数，当它与1011001相加时，结果为1100110。
首先，将两个数转换为十进制，1011001（二进制） = 105（十进制），1100110（二进制） = 102（十进制）。
接下来，从十进制角度考虑，105 + x = 102。显然，x = 102 - 105 = -3，但在二进制中，-3无法直接表示。我们需要找到一个二进制的数，当它与1011001相加时，结果为1100110。
观察发现，1100110 - 1011001 = 1111，即选项B。
因此，在二进制下，1011001 + 1111 = 1100110。
2、字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（ ）。
A 66
B 5A
C 50
D 视具体的计算机而定
解析：【喵呜刷题小喵解析】：在ASCII编码中，字符“A”的十六进制值为41，字符“Z”的ASCII码值比“A”大25（因为英文字母表从A到Z共有26个字母，而Z是最后一个）。因此，字符“Z”的ASCII码值为41 + 25 = 66，即十六进制的5A。所以，正确答案是B选项。
3、右图是一棵二叉树，它的先序遍历是（ ）。
A ABDEFC
B、 DBEFAC
C、
DFEBCA
D、
ABCDEF
解析：【喵呜刷题小喵解析】：二叉树的先序遍历顺序是：根节点 -> 左子树 -> 右子树。根据题目中的二叉树，我们可以按照先序遍历的规则进行遍历：首先访问根节点A，然后遍历左子树DBEF，最后遍历右子树C。所以，该二叉树的先序遍历是：ADBEFC。与选项B相匹配，因此答案是B。
4、寄存器是（ ）的重要组成部分。
A 硬盘
B 高速缓存
C 内存
D 中央处理器（CPU）
解析：【喵呜刷题小喵解析】：寄存器是中央处理器（CPU）的重要组成部分。中央处理器是计算机的大脑，负责执行指令和处理数据。寄存器是CPU内部的高速存储单元，用于存储指令、数据和地址信息，以便CPU能够快速地访问和处理这些数据。因此，寄存器是CPU的重要组成部分，而不是硬盘、高速缓存或内存。所以，正确答案是D。
5、广度优先搜索时，需要用到的数据结构是（ ）。
A 链表
B 队列
C 栈
D 散列表
解析：【喵呜刷题小喵解析】：广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。在这种搜索中，首先访问从根节点开始的所有相邻节点，然后对每个已访问的相邻节点，再访问它们的未访问过的相邻节点，如此继续。这个过程需要使用一个数据结构来保存待访问的节点，这种数据结构就是队列（Queue）。因此，选项B“队列”是广度优先搜索需要用到的数据结构。
6、在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（ ）。
A 程序运行时理论上所占的内存空间
B 程序运行时理论上所占的数组空间
C 程序运行时理论上所占的硬盘空间
D 程序源文件理论上所占的硬盘空间
解析：【喵呜刷题小喵解析】：在计算机科学中，空间复杂度通常是指算法在运行过程中所需存储空间的量。对于使用高级语言编写的程序来说，这里的“空间”通常是指程序运行时理论上所占的内存空间。选项A描述的是程序运行时理论上所占的内存空间，这是空间复杂度中提到的“空间”通常所指的含义。选项B、C和D分别描述了数组空间、硬盘空间和源文件所占的硬盘空间，这些都不是空间复杂度中通常提到的“空间”的含义。因此，正确答案是A。
7、应用快速排序的分治思想，可以实现一个求第 K 大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（ ）。
A O (n2)
B O (n log n )
C O (n)
D O (1)
解析：【喵呜刷题小喵解析】：
快速排序是一种分治算法，其时间复杂度在平均情况下为O(n log n)。虽然题目中提到了“不考虑极端的最坏情况”，但快速排序在平均情况下的性能已经足够好，因此理论上可以实现的最低的算法时间复杂度为O(n log n)。所以正确答案为B。
8、为解决 web 应用中的不兼容问题，保障信息的顺利流通，（ ）制定了一系列标准，涉及 HTML、XML、CSS 等，并建议开发者遵循。
A 微软
B 美国计算机协会（ACM）
C 联合国教科文组织
D 万维网联盟（W3C）
解析：【喵呜刷题小喵解析】：万维网联盟（W3C）负责制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循，以解决web应用中的不兼容问题，保障信息的顺利流通。因此，正确答案为D。其他选项如微软、美国计算机协会（ACM）和联合国教科文组织并不是负责制定这些标准的机构。
9、体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。
A 快速排序
B 插入排序
C 冒泡排序
D 归并排序
解析：【喵呜刷题小喵解析】：插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。题目中描述的站队方法，每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面，这种站队的方法类似于插入排序算法。因此，答案为B，插入排序。
10、1956 年（ ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain）
A 诺贝尔物理学奖
B 约翰·冯·诺依曼奖
C 图灵奖
D 高德纳奖 （Donald E. Knuth Prize）
解析：【喵呜刷题小喵解析】：1956年诺贝尔物理学奖授予了肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain），他们因共同研发出晶体管（固体放大器）而获奖。因此，正确答案为A选项，即诺贝尔物理学奖。其他选项如约翰·冯·诺依曼奖、图灵奖和高德纳奖与本题无关。
二、多选题
11、如果根结点的深度记为 1，则一棵恰有 2011 个叶子结点的二叉树的深度可能是（ ）。
A 10
B 11
C 12
D 2011
解析：【喵呜刷题小喵解析】：对于一棵恰有 2011 个叶子结点的二叉树，由于叶子结点都位于最底层，且每层的节点数至少为 2，那么二叉树的最小深度就是使得节点总数大于或等于 2011 的最小整数层数。我们可以从深度为 1 的情况开始计算，即根节点。然后，每一层节点数都是前一层节点数的两倍，即 1，2，4，8，16，32，64，128，256，512，1024，2048，4096，8192，16384，32768，65536，131072，262144，524288，1048576。这样计算下去，直到节点总数超过或等于 2011。我们可以看到，深度为 11 时的节点总数是 2048，这是小于 2011 的最大的节点总数，因此深度至少为 11。而深度为 12 时的节点总数为 4096，大于 2011。因此，一棵恰有 2011 个叶子结点的二叉树的最小深度为 11。所以，选项 B 是正确的。
12、在布尔逻辑中，逻辑“或”的性质有（ ）。
A 交换律：PVQ = QVP
B 结合律：PV（QVR）=（PVQ）VR
C 幂等律：PVP = P
D 有界律：PV1 = 1（1 表示逻辑真）
解析：【喵呜刷题小喵解析】：
在布尔逻辑中，逻辑“或”的性质包括交换律、结合律、幂等律和有界律。
交换律：PVQ = QVP，表示逻辑“或”运算满足交换律，即逻辑“或”运算的顺序不影响结果。
结合律：PV（QVR）=（PVQ）VR，表示逻辑“或”运算满足结合律，即无论逻辑“或”运算如何分组，结果都是相同的。
幂等律：PVP = P，表示如果同一个命题P多次进行逻辑“或”运算，结果仍然是P。
有界律：PV1 = 1（1 表示逻辑真），表示任何命题与逻辑真进行逻辑“或”运算，结果都是逻辑真。
因此，选项A、B、C和D都是正确的。
13、一个正整数在十六进制下有 100 位，则它在二进制下可能有（ ）位。
A 399
B 400
C 401
D 404
解析：【喵呜刷题小喵解析】：
首先，我们需要了解十六进制和二进制之间的转换关系。
在十六进制中，每一位可以表示0-9和A-F共16个数字，即2^4=16。
在二进制中，每一位可以表示0和1共2个数字，即2^1=2。
假设一个正整数在十六进制下有100位，那么它的范围是从000000000000...00000（96个0）到FFFFFFFFFFFFFFFF（16个F）。
将这个十六进制数转换为二进制数，最大的数FFFFFFFFFFFFFFFF转换为二进制是1后面跟400个0，即10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000由于十六进制的每一位在二进制下需要4位来表示，所以一个100位的十六进制数在二进制下需要400位来表示。因此，一个正整数在十六进制下有100位，则它在二进制下可能有400位。
所以，答案是C，即401位。
14、汇编语言（ ）。
A 是一种与具体硬件无关的程序设计语言
B 在编写复杂程序时，相对于高级语言而言代码量大，且不易调试
C 可以直接访问寄存器、内存单元、I/O 端口
D 随着高级语言的诞生，如今已被完全淘汰，不再使用
解析：【喵呜刷题小喵解析】：
汇编语言是一种依赖于具体硬件的程序设计语言，故A选项错误。汇编语言编写的程序虽然相对于高级语言而言代码量可能较大，且不易调试，但它具有可以直接访问寄存器、内存单元、I/O端口的特性，故B、C选项正确。汇编语言并未完全淘汰，它仍然在一些特定领域中使用，如底层系统开发、嵌入式系统开发等，故D选项错误。
15、现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、400。那么，“也”字的编码长度可能是（ ）。
A 1
B 2
C 3
D 4
解析：【喵呜刷题小喵解析】
哈夫曼编码是一种用于无损数据压缩的算法，它的基本思想是根据字符出现的频率来为其分配编码。频率越高的字符，其编码长度越短；频率越低的字符，其编码长度越长。
在本题中，给定的四个汉字“之”、“乎”、“者”、“也”出现的次数分别为700、600、300、400。根据哈夫曼编码的原则，出现次数最多的“之”字应该被赋予最短的编码长度，而出现次数最少的“也”字应该被赋予最长的编码长度。
由于题目要求找出“也”字的编码长度，而“也”字是出现次数最少的，所以其编码长度应该是最长的。因此，正确答案是C，即“也”字的编码长度可能是3。
16、生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（ABD）。
A、 指静脉验证
B 
步态验证
C 
ATM 机密码验证
D 
声音验证
解析：【喵呜刷题小喵解析】：生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。指静脉验证属于生物特征识别技术，其应用的是人体内部的生物特征；步态验证也是生物特征识别技术，其应用的是人体行走时的特征；声音验证也是生物特征识别技术，其应用的是人的声音特征。而ATM机密码验证不属于生物特征识别技术，因为它使用的是传统的密码验证方式，而不是人体本身的生物特征。因此，属于生物特征识别技术及其应用的是指静脉验证、步态验证和声音验证，即选项A、B、D。
17、对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少 3。
A 7
B 5
C 3
D 6
解析：【喵呜刷题小喵解析】：
首先，我们需要理解什么是逆序对。在一个序列中，如果前面的数比后面的数大，那么它们就构成了一个逆序对。
对于序列“7、5、1、9、3、6、8、4”，我们可以计算出初始的逆序对个数。
* 7 和 5 不构成逆序对
* 7 和 1 构成1个逆序对
* 7 和 9 构成1个逆序对
* 7 和 3 构成1个逆序对
* 7 和 6 构成1个逆序对
* 7 和 8 构成1个逆序对
* 7 和 4 构成1个逆序对
* 5 和 1 不构成逆序对
* 5 和 9 构成1个逆序对
* 5 和 3 构成1个逆序对
* 5 和 6 构成1个逆序对
* 5 和 8 构成1个逆序对
* 5 和 4 构成1个逆序对
* 1 和 9 构成1个逆序对
* 1 和 3 构成1个逆序对
* 1 和 6 构成1个逆序对
* 1 和 8 构成1个逆序对
* 1 和 4 构成1个逆序对
* 9 和 3 构成1个逆序对
* 9 和 6 构成1个逆序对
* 9 和 8 构成1个逆序对
* 9 和 4 构成1个逆序对
* 3 和 6 不构成逆序对
* 3 和 8 构成1个逆序对
* 3 和 4 构成1个逆序对
* 6 和 8 不构成逆序对
* 6 和 4 构成1个逆序对
* 8 和 4 不构成逆序对
初始的逆序对个数为 31。
现在，我们需要找出哪个数去掉后，逆序对的个数会减少3。
* 如果去掉 7，逆序对的个数变为 28，减少了 3
* 如果去掉 5，逆序对的个数仍然是 31，没有减少
* 如果去掉 3，逆序对的个数仍然是 31，没有减少
* 如果去掉 6，逆序对的个数仍然是 31，没有减少
因此，去掉 7 会使逆序对的个数减少 3。所以答案是 D。
18、计算机中的数值信息分为整数和实数（浮点数）。实数之所以能够表示很大或者很小的数，是由于使用了（ ）。
A 阶码
B 补码
C 反码
D 较长的尾数
解析：【喵呜刷题小喵解析】：
实数在计算机中的表示方式通常使用浮点数表示法，包括阶码和尾数两部分。阶码用于表示数值的大小，尾数用于表示数值的精度。浮点数的表示范围主要取决于阶码，因此可以表示很大或者很小的数。较长的尾数虽然可以提供更高的精度，但表示范围仍然受限于阶码。因此，选项 A“阶码”和选项 D“较长的尾数”都是正确的。选项 B“补码”和选项 C“反码”与实数的表示无关，因此是错误的。
19、对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程中还会出现的值有（ ）。
A 3
B 7
C 6
D、
5
解析：【喵呜刷题小喵解析】：在Dijkstra算法中，到B点的距离d[B]初始时赋为8，随着算法的执行，如果找到从S点到B点的更短路径，d[B]的值会被更新。但根据题目，初始值已经为8，所以算法执行过程中d[B]的值不会小于8。因此，选项B（7）是可能出现的值。其他选项（3、6、5）都小于初始值8，所以在算法执行过程中不会出现。
20、为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。下列英文缩写中，（ ）是网络协议
A HTTP
B TCP/IP
C FTP
D、
WWW
解析：【喵呜刷题小喵解析】：网络协议是计算机网络中进行数据交换而建立的规则、标准或约定的集合。TCP/IP是一组协议，包括传输控制协议（TCP）和网络协议（IP），用于在互联网络上实现数据传输和寻址。HTTP、FTP和WWW都是基于TCP/IP协议的应用层协议，不是网络协议本身。因此，只有TCP/IP是网络协议。
三、简答题
21、平面图可以在画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如右图所示。那么，5个顶点的平面图至少有 条边。
参考答案：5个顶点的平面图至少有10条边。
解析：【喵呜刷题小喵解析】：
根据题目描述，4个顶点的平面图至少有6条边。我们可以推测，每增加一个顶点，平面图至少需要增加4条边，以满足所有顶点都在边上，并且边仅在顶点上相交的条件。因此，5个顶点的平面图至少有6+4=10条边。
22、定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将 A 移到 B 之前，变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要________次操作。
参考答案：最少需要8次操作。
解析：【喵呜刷题小喵解析】：要将字符串“DACHEBGIF”变成“ABCDEFGHI”，我们可以按照目标字符串的顺序进行移动操作，首先将D移动到字符串开头，进行1次操作；然后将A移动到D后面，进行2次操作；然后将C移动到A后面，进行3次操作；然后将H移动到C后面，进行4次操作；然后将E移动到H后面，进行5次操作；然后将F移动到E后面，进行6次操作；然后将G移动到F后面，进行7次操作；最后将I移动到G后面，进行8次操作。因此，最少需要8次操作。
23、
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
int n,i,sum,x,a[SIZE];
cin>>n;
memset(a,0,sizeof(a));
for(i=1;i<=n;i++){
cin>>x;
a[x]++;
}
i=0;
sum=0;
while(sum<(n/2+1)){
i++;
sum+=a[i];
}
cout<<i<<endl;
return 0;
}
输入：
11
4 5 6 6 4 3 3 2 3 2 1
输出：
参考答案：6
解析：【喵呜刷题小喵解析】：
首先，该程序的主要目的是找出数组中前n/2+1个元素中最大的元素的索引。
程序首先读入一个整数n，表示接下来要输入n个整数。然后，程序创建了一个大小为SIZE的整数数组a，并初始化所有元素为0。
接着，程序读取n个整数，并在数组a中对应的索引位置上增加1，以记录该整数的出现次数。
然后，程序使用一个循环来累加数组a中前i个元素的和，直到和大于n/2+1。此时，i就是前n/2+1个元素中最大的元素的索引，因为数组a中每个元素表示的是对应整数的出现次数，所以前i个元素的和就是前i个整数在输入中出现的总次数。
最后，程序输出i，即前n/2+1个元素中最大的元素的索引。
对于输入11 4 5 6 6 4 3 3 2 3 2 1，数组a为[0, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1]。前6个元素的和为1+2+2+1+1+2=9，大于11/2+1=6，所以最大的元素的索引为6。因此，输出为6。
24、
#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
if(x<n)
f2(y,x+y);
}
void f2(int x,int y)
{
cout<<x<<' ';
f1(y,x+y);
}
int main()
{
cin>>n;
f1(0,1);
return 0;
return 0;
}
参考答案：该代码的主要逻辑是从输入读取一个整数n，然后调用f1函数，其中x从0开始，y从1开始。f1函数根据当前x的值判断是否继续调用f2函数。f2函数输出当前x的值，并再次调用f1函数，此时x和y都增加了相同的值。此代码并没有明确输出结束的标志，所以它会持续输出，直到达到用户输入的n值为止。
解析：【喵呜刷题小喵解析】：首先，该代码从`main()`函数开始执行，该函数从输入读取一个整数n，然后调用`f1(0,1)`。`f1`函数检查其参数x是否小于n，如果x小于n，则调用`f2`函数，将y和x+y作为参数传递。
`f2`函数输出当前x的值，并调用`f1`函数，此时x和y都增加了相同的值。然后`f1`函数再次检查x是否小于n，如果仍然小于n，则再次调用`f2`函数，如此循环。
因此，此代码会持续输出，直到达到用户输入的n值为止。因为`f1`和`f2`函数中的x和y都在每次调用时增加相同的值，所以输出的序列会形成一个等差数列。
需要注意的是，`main()`函数中有两个`return 0;`，其中一个是多余的，可以删除。
25、
#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
int i;
visited[x]= true;
if(len>ans)
ans=len;
for(i=1;i<=n;i++)
if( (!visited[i]) && (e[x][i]!=-1) )
dfs(i,len+e[x][i]);
visited[x]=false;
}
int main()
{
int i,j,a,b,c;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
e[i][j]=-1;
for(i=1;i<=m;i++)
{
cin>>a>>b>>c;
e[a][b]=c;
e[b][a]=c;
}
for(i=1;i<=n;i++)
visited[i]=false;
ans=0;
for(i=1;i<=n;i++)
dfs(i,0);
cout<<ans<<endl;
return 0;
}
输入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
输出：
参考答案：输出为70
解析：【喵呜刷题小喵解析】：该程序是一个求解图中最长路径的程序，使用了深度优先搜索（DFS）算法。程序首先读入图的节点数n和边数m，然后读入每条边的起点、终点和权值，将边的权值保存在二维数组e中。在主函数中，首先将所有节点标记为未访问，初始化最长路径长度ans为0。然后从每个节点开始进行深度优先搜索，更新最长路径长度。最后输出最长路径长度ans。
对于输入数据，程序首先读入节点数n=4和边数m=6，然后读入每条边的起点、终点和权值。根据这些输入数据，程序构建了一个4x4的二维数组e，表示图的邻接矩阵。
接下来，程序从每个节点开始进行深度优先搜索，更新最长路径长度。对于节点1，程序搜索到节点2和节点3，更新最长路径长度为10和50。对于节点2，程序搜索到节点3和节点4，更新最长路径长度为20和60。对于节点3，程序搜索到节点4，更新最长路径长度为30。对于节点4，程序搜索到节点1，更新最长路径长度为40。最终，程序输出的最长路径长度为70，即节点1到节点4的路径长度10+60=70。
26、
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
int ans,i;
ans=0;
for(i=1;i<=n;i++)
if( a[u][i]!=a[v][i])
ans++;
return ans;
}
int main()
{
int sum,i,j;
cin>>n;
memset(a,0,sizeof(a));
m=1;
while(1)
{
i=1;
while( (i<=n) && (a[m][i]==1) )
i++;
if(i>n)
break;
m++;
a[m][i]=1;
for(j=i+1;j<=n;j++)
a[m][j]=a[m-1][j];
}
sum=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
sum+=h(i,j);
cout<<sum<<endl;
return 0;
}
输入：7
输出：_________
参考答案：输出：21
解析：【喵呜刷题小喵解析】：
首先，我们需要理解程序的主要逻辑。程序首先读入一个整数n，然后生成一个n×n的矩阵a，其中每行只有一个1，其余元素为0。这个矩阵的生成方式是从上到下，从左到右，每生成一个新行，都会复制上一行的元素，并在当前行的某个位置（从第一个位置开始）放置一个1。
然后，程序计算所有行对之间的汉明距离（即两个二进制数对应位上不同的位数）之和，并输出结果。
对于输入7，程序生成的矩阵如下：
```
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
```
计算汉明距离，得到：
```
1 2 3 4 5 6 7
2 1 2 3 4 5 6
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 1 2 3
6 5 4 3 2 1 2
7 6 5 4 3 2 1
```
将每行的和加起来，得到21。
四、实操题
27、(大整数开方) 输入一个正整数n（1≤n≤10100），试用二分法计算它的平方根的整数部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中 len 表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数 a 和 b 的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
① +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
② ;
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数 a 和 b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= ③ ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数 a 和 b 的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=( ④ )*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数 a 加 2 之后的结果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
⑤ ;
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数 a>b 则返回 true，否则返回 false
{
int i;
if( ⑥ )
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]- ⑦ ;
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over( ⑧ ))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}
参考答案：```① a.num[i]*b.num[j]② ans.num[i]%=10③ a.num[i]④ ans.num[i-1]⑤ ans.len++⑥ a.len!=b.len⑦ '0'⑧ middle```
解析：【喵呜刷题小喵解析】：
1. 在`times`函数中，`a.num[i]*b.num[j]`是计算两个大整数的乘积，即`a`的第`i`位与`b`的第`j`位的乘积。
2. 在`add`函数中，`ans.num[i]%=10`是将`ans.num[i]`的值取模10，得到该位的数字。
3. 在`add`函数中，`a.num[i]`是将`a`的第`i`位数字加到`ans.num[i]`上。
4. 在`average`函数中，`ans.num[i-1]`是`ans`的第`i-1`位数字，用于存储平均值。
5. 在`plustwo`函数中，`ans.len++`是在`ans`的位数上加1，因为加2后可能需要进位。
6. 在`over`函数中，`a.len!=b.len`是判断`a`和`b`的位数是否相等。
7. 在`main`函数中，`s[target.len-i]-'0'`是将字符串`s`的第`i`位字符转换为数字。
8. 在`main`函数中，`middle`是计算`left`和`right`的平均数，用于二分法搜索。
这些填空都是根据函数的功能和上下文来推断的。
28、（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n<100）和序列的 n 个元素，试求其对应的笛卡尔树的深度 d（根节点深度为1），以及有多少个叶子节点的深度为d。
#include<iostream>
using namespace std;
const int SIZE=100+5;
const int INFINITY=1000000;
int n,a[SIZE],maxDeep,num;
void solve(int left,int right,int deep)
{
int i,j,min;
if(deep>maxDeep){
maxDeep=deep;
num=1;
}
else if(deep==maxDeep)
① ;
min= INFINITY;
for(i=left;i<=right;i++)
if(min>a[i]){
min=a[i];
② ;
}
if(left<j)
③ ;
if(j<right)
④ ;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
maxDeep=0;
solve(1,n,1);
cout<<maxDeep<<' '<<num<<endl;
return 0;
}
参考答案：1. 在else if(deep==maxDeep)处，应添加代码统计叶子节点深度为d的数量，并初始化num为0。2. 在②处，找到最小值后，需要将其设为当前节点，即j=i。3. 在③处，需要递归处理左子树，调用solve(left, j-1, deep+1)。4. 在④处，需要递归处理右子树，调用solve(j+1, right, deep+1)。
解析：【喵呜刷题小喵解析】：
题目要求求解笛卡尔树的深度d以及深度为d的叶子节点数量。首先，需要理解笛卡尔树的性质：它是一个最小堆，且中序遍历就是给定的序列。
在solve函数中，我们需要根据当前处理的区间[left, right]和当前深度deep来构建笛卡尔树。
1. 如果当前深度deep大于最大深度maxDeep，则更新最大深度，并将叶子节点数量num设为1。
2. 如果当前深度deep等于最大深度maxDeep，我们需要统计叶子节点的数量。由于叶子节点是值最小的节点，所以我们需要找到当前区间[left, right]中的最小值，并统计有多少个这样的节点。
3. 找到最小值后，我们需要将其设为当前节点，即j=i，然后递归处理左右子树。
在main函数中，我们先读入序列的规模和序列元素，然后调用solve函数构建笛卡尔树，并输出最大深度和叶子节点数量。
根据上述分析，我们可以得出答案。在solve函数中，我们需要添加统计叶子节点数量的代码，并正确设置当前节点和递归处理左右子树。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
