一、单选题
1、在计算机内部用来传送、存贮、加工处理的数据或指令都是以（ ）形式进行的。（2015年提高组）
A 二进制码
B 八进制码
C 十进制码
D 智能拼音码
解析：【喵呜刷题小喵解析】：计算机内部使用二进制形式来处理和传输数据或指令，这是计算机的基本工作原理。二进制是一种只有0和1两个数字的数制，它非常适合计算机处理，因为计算机内部所有的操作都是基于电信号的开和关，即逻辑电平的高和低，这与二进制中的0和1相对应。因此，选项A“二进制码”是正确的答案。
2、下列说法正确的是（ ）。
A CPU 的主要任务是执行数据运算和程序控制
B 存储器具有记忆能力，其中信息任何时候都不会丢失
C 两个显示器屏幕尺寸相同，则它们的分辨率必定相同
D 个人用户只能使用 Wifi 的方式连接到 Internet
解析：【喵呜刷题小喵解析】：
A选项正确，CPU的主要任务是执行数据运算和程序控制，这是CPU的基本功能。
B选项错误，存储器具有记忆能力，但其中的信息并不是任何时候都不会丢失。例如，RAM（随机存取存储器）中的信息在断电后会丢失。
C选项错误，两个显示器屏幕尺寸相同，并不意味着它们的分辨率必定相同。分辨率取决于显示器的物理尺寸和像素数量，与屏幕尺寸无必然联系。
D选项错误，个人用户连接到Internet的方式并不仅限于Wifi，还可以通过有线网络、移动网络等方式连接。
3、与二进制小数 0.1 相等的十六进制数是（ ）。
A 0.8
B 0.4
C 0.2
D 0.1
解析：【喵呜刷题小喵解析】：二进制小数0.1转换为十六进制小数时，首先需要将其转换为二进制。0.1（二进制）等于0.0001100110011...（二进制），这是一个无限循环小数。为了得到有限的二进制表示，通常需要保留一定数量的小数位。但是，为了找到一个与0.1（二进制）相等的十六进制数，我们需要一个无限循环的二进制表示。
最接近0.1（二进制）的有限二进制表示是0.00011（二进制），这等于0.375（十进制）。但是，这个值并不等于0.1（二进制）。
最接近0.1（二进制）的无限循环二进制表示是0.0001100110011...（二进制），这等于0.375 - 0.0001����������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������（这个部分被截断了，无法提供完整的解析）
因此，我们需要找到与0.1（二进制）相等的十六进制数，这个数并不存在，因为0.1（二进制）是一个无限循环小数，无法用有限的十六进制数表示。最接近0.1（二进制）的有限十六进制表示是0.2（十六进制），但它并不等于0.1（二进制）。
所以，本题中给出的选项中，没有一个是与0.1（二进制）相等的十六进制数。因此，正确答案应该是一个提示，说明没有与0.1（二进制）相等的十六进制数。如果选项中有这样的提示，那么它可能是正确答案。否则，本题可能存在问题，需要进一步核实。
4、下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（ ）。
A 120 82 50
B 144 100 68
C 300 200 C8
D 1762 1010 3F2
解析：【喵呜刷题小喵解析】：
首先，我们需要将每个选项中的八进制数转换为十进制数，以便进行比较。
对于选项A：
* 第一个数据120（八进制）转换为十进制是 120 ÷ 8 = 15
* 第二个数据82（十进制）已经是十进制
* 第三个数据50（十六进制）转换为十进制是 50 ÷ 16 = 3.125
对于选项B：
* 第一个数据144（八进制）转换为十进制是 144 ÷ 8 = 18
* 第二个数据100（十进制）已经是十进制
* 第三个数据68（十六进制）转换为十进制是 68 ÷ 16 = 4.25
对于选项C：
* 第一个数据300（八进制）转换为十进制是 300 ÷ 8 = 37.5
* 第二个数据200（十进制）已经是十进制
* 第三个数据C8（十六进制）转换为十进制是 C8 ÷ 16 = 200
对于选项D：
* 第一个数据1762（八进制）转换为十进制是 1762 ÷ 8 = 220.25
* 第二个数据1010（十进制）已经是十进制
* 第三个数据3F2（十六进制）转换为十进制是 3F2 ÷ 16 = 250
通过比较，我们可以发现只有选项D中的三个数据都是相同的，即1010。因此，正确答案是D。
5、线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。（2015年提高组）
A 必须连续
B 部分地址必须连续
C 一定不连续
D 连续不连续均可
解析：【喵呜刷题小喵解析】：链表存储结构是线性表的一种存储方式，它允许内存中的存储单元地址不连续。链表中的每个元素都包含数据域和指针域，指针域指向下一个元素的存储位置。因此，链表中的元素可以分散在内存中的不同位置，不需要连续的内存空间。所以，正确答案是D，即连续不连续均可。
6、今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为（ ）。
A f
B c
C a
D b
解析：【喵呜刷题小喵解析】栈是一种后进先出（LIFO）的数据结构，对元素序列a,b,c,d,e,f进行进栈、出栈操作后，栈顶元素为最后进栈的元素。根据题目中的操作顺序，元素a、b、c、d、e、f依次进栈，然后d、e、c出栈，此时栈中元素顺序为a、b、f，所以栈顶元素为f。因此，答案为A。
7、前序遍历序列与后序遍历序列相同的二叉树为（ ）。
A 非叶子结点只有左子树的二叉树
B 只有根结点的二叉树
C 根结点无右子树的二叉树
D 非叶子结点只有右子树的二叉树
解析：【喵呜刷题小喵解析】：对于二叉树的前序遍历和后序遍历，前序遍历的顺序是根节点->左子树->右子树，而后序遍历的顺序是左子树->右子树->根节点。若前序遍历序列与后序遍历序列相同，那么这棵树必然是一个右子树为空的情况，也就是根结点无右子树的二叉树。因此，正确答案为C。其他选项的非叶子结点只有左子树、只有根结点的二叉树、非叶子结点只有右子树的二叉树均不满足前序遍历和后序遍历相同的条件。
8、如果根的高度为1，具有61个结点的完全二叉树的高度为（ ）。（2015年提高组）
A 5
B 6
C 7
D 8
解析：【喵呜刷题小喵解析】：对于具有n个结点的完全二叉树，如果其高度为h，则它的结点个数可以表示为：2^(h-1) - 1。现在已知具有61个结点的完全二叉树，可以建立方程：2^(h-1) - 1 = 61。解这个方程，得到h=6。所以，具有61个结点的完全二叉树的高度为6。因此，答案为B。
9、6 个顶点的连通图的最小生成树，其边数为（ ）。
A 6
B 5
C 7
D 4
解析：【喵呜刷题小喵解析】：一个连通图的最小生成树是包含图中全部顶点，且权值和最小的子图。对于6个顶点的连通图，其最小生成树应该包含6个顶点，并且边数比顶点数少1，即6-1=5条边。因此，6个顶点的连通图的最小生成树的边数为5，选项C正确。
10、设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（ ）。
A O(log n)
B O(n log n)
C O(n)
D O(n2)
解析：【喵呜刷题小喵解析】：根据题目给出的递推关系式 $T(n) = T(n - 1) + n$，我们可以逐步展开得到：
$T(n) = T(n - 1) + n$
$T(n - 1) = T(n - 2) + (n - 1)$
$T(n - 2) = T(n - 3) + (n - 2)$
$\cdots$
$T(1) = T(0) + 1$
将上述各式相加，得到：
$T(n) = T(0) + 1 + 2 + 3 + \cdots + n$
$= 1 + \frac{n(n + 1)}{2}$
$= \frac{n^2 + n}{2}$
$= O(n^2)$
由此可见，该算法的时间复杂度为 $O(n^2)$。选项C中的 $O(n)$ 并不正确，因为从 $T(n)$ 的表达式可以看出，它的时间复杂度是 $n$ 的平方，而不是 $n$。因此，正确答案是 C。
11、具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）。
A Θ(n2)
B Θ(e2)
C Θ(ne)
D Θ(n + e)
解析：【喵呜刷题小喵解析】
对于具有n个顶点，e条边的图，邻接表存储结构可以将其表示为n个链表，每个链表表示一个顶点的所有邻接顶点。
深度优先遍历（DFS）和广度优先遍历（BFS）的基本思想都是从一个顶点开始，沿着边进行遍历。在邻接表存储结构中，从一个顶点出发，可以直接访问其所有邻接顶点，因此，无论是DFS还是BFS，从一个顶点出发，最多需要访问e个邻接顶点。
由于图中有n个顶点，因此最多需要进行n次这样的操作。因此，深度优先遍历和广度优先遍历的时间复杂度都是O(n + e)，其中n是顶点数，e是边数。
在题目中，要求的是时间复杂度的渐近表示，即Θ表示法。由于n和e都是图的参数，且n和e的数量级通常不同，因此不能简单地合并为n^2或e^2。因此，正确答案是Θ(n + e)。
12、在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。
A 贪心
B 分治
C 递推
D 回溯
解析：【喵呜刷题小喵解析】：哈夫曼编码是一种贪心算法，它每次选择两个最小的频率节点合并，生成一个新的节点，并赋予其频率值为原来两个节点频率值之和，然后按照频率值重新排列节点，重复进行直到只剩下一个节点。因此，哈夫曼算法采用了贪心思想。所以，正确答案是A。
13、双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ）。
A p->llink = q; q->rlink = p;
p->llink->rlink = q; q->llink = p->llink;
B q->llink = p->llink; p->llink->rlink = q;
q->rlink = p; p->llink = q->rlink;
C q->rlink = p; p->rlink = q;
p->llink->rlink = q; q->rlink = p;
D p->llink->rlink = q; q->rlink = p;
q->llink = p->llink; p->llink = q;
解析：【喵呜刷题小喵解析】：
在双向链表中，插入操作需要考虑插入点的前后节点的指针关系。首先，将q的rlink指针指向p。然后，p的前驱节点的rlink指针指向q。最后，将q的llink指针指向p的前驱节点。所以，选项D是正确的插入操作。
选项A：p->llink = q; q->rlink = p; 这个操作是错误的，因为p的前驱节点的rlink指针没有被更新。
选项B：q->llink = p->llink; p->llink->rlink = q; 这个操作也是错误的，因为q的rlink指针没有指向p，p的rlink指针也没有指向q。
选项C：q->rlink = p; p->rlink = q; p->llink->rlink = q; q->rlink = p; 这个操作也是错误的，因为p的rlink指针没有指向p的后继节点，而且q的llink指针也没有被正确设置。
14、对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常着色。正常着色图 G 所必需的最少颜色数，称为G的色数。那么下图的色数是（ ）。
A 3
B、 4
C、
5
D、
6
解析：【喵呜刷题小喵解析】：观察给定的图形，我们可以发现，图形中有四个节点，每个节点都与其它三个节点相邻。因此，为了使得相邻节点颜色不同，我们需要至少4种颜色。所以，该图的色数是4，对应选项B。
15、在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是（ ）。
A 鼠标
B 笔
C 身份证
D 准考证
解析：【喵呜刷题小喵解析】：在NOI系列赛事中，参赛选手必须使用由承办单位统一提供的设备。这意味着选手不能自带任何设备，包括鼠标、笔等。而身份证和准考证虽然不属于设备，但它们通常是由参赛选手自己保管并带入的。因此，根据题意，不允许选手自带的是选项C“身份证”。
二、多选题
16、以下属于操作系统的有（ ）。
A Windows XP
B UNIX
C Linux
D Mac OS
解析：【喵呜刷题小喵解析】：
操作系统的定义是管理计算机硬件与软件资源的计算机程序，它负责控制、调度一切系统资源，使得应用程序能够正常运行。
选项A Windows XP是微软公司开发的一款操作系统，广泛应用于个人计算机领域。
选项B UNIX是一种多用户、多任务、分时操作的计算机操作系统，最初由AT&T Bell Labs开发。
选项C Linux是一种自由和开放源码的类Unix操作系统，它有许多不同的发行版本。
选项D Mac OS是苹果公司开发的操作系统，用于其Macintosh系列计算机。
因此，以上四个选项都属于操作系统。
17、下列属于视频文件格式的有（ ）。
A AVI
B MPEG
C WMV
D JPEG
解析：【喵呜刷题小喵解析】：视频文件格式是用于存储视频数据的文件格式。选项中给出的文件格式有AVI、MPEG、WMV和JPEG。其中，AVI、MPEG和WMV都是常见的视频文件格式，而JPEG是一种图像文件格式，不是视频文件格式。因此，正确答案是A、B、C。
18、下列选项不是正确的IP地址的有（ ）。
A 202.300.12.4
B 192.168.0.3
C 100:128:35:91
D 111-120-35-21
解析：【喵呜刷题小喵解析】：
IP地址由四个数字组成，每个数字之间用点号（.）分隔。每个数字的范围是0到255。选项A "202.300.12.4" 和选项B "192.168.0.3" 都是合法的IP地址，因为它们都符合这个格式。
选项C "100:128:35:91" 不是一个合法的IP地址。IP地址不使用冒号（:）分隔数字，而是使用点号（.）。此外，IPv4地址只包含四个数字，而选项C包含五个数字，因此它也不符合IPv4地址的格式。
选项D "111-120-35-21" 也不是一个合法的IP地址。IP地址不使用连字符（-）分隔数字，而是使用点号（.）。此外，每个数字的范围是0到255，而选项D中的数字超出了这个范围。
因此，选项C和D不是正确的IP地址。
19、下列有关树的叙述中，叙述正确的有（ ）。
A 在含有n个结点的树中，边数只能是(n-1)条
B 在哈夫曼树中，叶结点的个数比非叶结点个数多 1
C 完全二叉树一定是满二叉树
D 在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先
解析：【喵呜刷题小喵解析】：
A选项：在含有n个结点的树中，边数只能是(n-1)条。这是正确的，因为每个节点（除了根节点）都有一个父节点，所以树中的边数比节点数少1。
B选项：在哈夫曼树中，叶结点的个数比非叶结点个数多 1。这是错误的，哈夫曼树是一种特殊的二叉树，它的构造方式使得权值最小的两个节点先合并，所以叶节点的个数并不一定比非叶节点多1。
C选项：完全二叉树一定是满二叉树。这是错误的，完全二叉树除了最后一层外，每一层都被完全填满，并且所有节点都紧密地靠左排列，而满二叉树则是每一层都被完全填满的二叉树，所以完全二叉树不一定是满二叉树。
D选项：在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先。这是错误的，前序遍历的顺序是根节点-左子树-右子树，即使u在v之前，也不能保证u一定是v的祖先，因为u和v可能处于同一层。
20、以下图中一定可以进行黑白染色的有（ ）。（黑白染色：为各个结点分别指定黑白两种颜色之一，使相邻结点颜色不同。）
A 二分图
B 完全图
C 树
D 连通图
解析：【喵呜刷题小喵解析】黑白染色问题是图论中的一个问题，目的是为图中的每个顶点指定一种颜色（黑色或白色），使得相邻的顶点颜色不同。
A选项，二分图：二分图是一种特殊的图，其顶点集可以分为两个子集，使得任意一条边的两个顶点分别属于这两个子集。在二分图上，一定可以进行黑白染色，因为可以将一个子集的所有顶点染成黑色，另一个子集的所有顶点染成白色。
B选项，完全图：完全图是一种任意两个顶点之间都有边的图。对于完全图，不一定能进行黑白染色。例如，一个完全图可能有奇数个顶点，这时无法找到一个染色方案使得相邻的顶点颜色不同。
C选项，树：树是一种无环连通图。虽然树可以进行黑白染色，但不是“一定”可以。对于包含奇数个顶点的树，黑白染色存在矛盾，无法为所有顶点染色。
D选项，连通图：连通图是指任意两个顶点之间都存在路径的图。连通图不一定能进行黑白染色，与完全图类似，如果连通图包含奇数个顶点，黑白染色会存在矛盾。
因此，根据以上分析，只有二分图一定可以进行黑白染色。
三、简答题
21、在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数有_________个。
参考答案：在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数有335个。
解析：【喵呜刷题小喵解析】：本题要求找出在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数有多少个。首先，我们需要理解不能被4、5、6三个数任意一个数整除的含义，即这些数除以4、5、6的余数都不为0。
我们可以通过遍历1到2015之间的每一个数，检查它们除以4、5、6的余数是否都不为0。由于这是一个重复性的任务，我们可以使用编程来解决这个问题。
然而，为了简化计算，我们可以利用数学原理来减少需要检查的数的数量。具体来说，我们可以利用中国剩余定理（Chinese Remainder Theorem）来找出在特定范围内不能被特定数整除的数的规律。
然而，由于本题没有提供足够的信息来应用中国剩余定理，我们将采用遍历的方法来解决这个问题。
遍历1到2015之间的每一个数，检查它们除以4、5、6的余数是否都不为0。对于每个数，如果它们除以4、5、6的余数都不为0，则它们满足题目要求。
经过计算，我们发现在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数有335个。
22、结点数为5的不同形态的二叉树一共有_________种。（结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。）
参考答案：结点数为5的不同形态的二叉树一共有32种。
解析：【喵呜刷题小喵解析】：对于二叉树，当结点数为5时，我们需要考虑5个结点的所有可能组合方式。根据二叉树的定义，每个结点最多有两个子结点，且子结点的顺序（左子结点或右子结点）是重要的。因此，我们需要列举所有可能的组合方式，并计算它们的数量。
首先，考虑根结点，它可以有0个、1个或2个子结点。
1. 根结点有0个子结点：这种情况下，二叉树只有一个结点，即根结点。
2. 根结点有1个子结点：这种情况下，二叉树有两个结点，一个是根结点，另一个是它的子结点。
3. 根结点有2个子结点：这种情况下，二叉树有三个结点，一个是根结点，另外两个是它的子结点。
对于每个根结点，我们需要考虑其两个子结点的组合方式。
* 当根结点有0个子结点时，没有组合方式，因为只有一个结点。
* 当根结点有1个子结点时，子结点可以是左子结点或右子结点，有2种组合方式。
* 当根结点有2个子结点时，我们需要考虑两个子结点的顺序（左子结点、右子结点或右子结点、左子结点），共有3种组合方式。
因此，当根结点有1或2个子结点时，共有2+3=5种组合方式。
接下来，对于每个根结点的组合方式，我们需要递归地考虑其子结点的组合方式。
* 当根结点有1个子结点时，子结点可以是左子结点或右子结点。对于左子结点，它可以看作是一个新的二叉树，其结点数为4。对于右子结点，同样如此。因此，当根结点有1个子结点时，共有2 * (4种组合方式) = 8种组合方式。
* 当根结点有2个子结点时，两个子结点都可以看作是一个新的二叉树，每个的结点数为3。因此，当根结点有2个子结点时，共有2 * (3种组合方式) * 2 = 12种组合方式。
综上，当结点数为5时，共有5（根结点的组合方式）+ 8（当根结点有1个子结点时的组合方式）+ 12（当根结点有2个子结点时的组合方式）= 25种组合方式。但是，由于二叉树的形态是唯一的，即镜像的二叉树被视为同一种形态，所以实际的组合方式只有25/2=12.5种。但因为结点数是整数，所以我们需要向上取整，即13种。但实际上，结点数为5的不同形态的二叉树有32种，这涉及到更复杂的递归计算，涉及到卡特兰数（Catalan number）的计算。
最终，我们得出结论：结点数为5的不同形态的二叉树一共有32种。
23、
#include <iostream>
using namespace std;
struct point {
int x;
int y;
};
int main() {
struct EX{
int a;
int b;
point c;
} e;
e.a = 1;
e.b = 2;
e.c.x = e.a + e.b;
e.c.y = e.a * e.b;
cout << e.c.x << ',' << e.c.y << endl;
return 0;
}
输出：_________
参考答案：输出：3,2
解析：【喵呜刷题小喵解析】：
在代码中，定义了一个结构体`point`，它有两个整型成员变量`x`和`y`。然后定义了一个匿名结构体`EX`，它有三个成员变量：两个整型变量`a`和`b`，以及一个`point`类型的变量`c`。
在`main`函数中，创建了一个`EX`类型的变量`e`，并给它的成员变量`a`和`b`分别赋值为1和2。接着，将`e.a`和`e.b`的和赋值给`e.c.x`，将`e.a`和`e.b`的积赋值给`e.c.y`。
最后，使用`cout`输出`e.c.x`和`e.c.y`的值，中间用逗号隔开，并输出一个换行符`endl`。
根据代码逻辑，`e.c.x`的值为`e.a + e.b = 1 + 2 = 3`，`e.c.y`的值为`e.a * e.b = 1 * 2 = 2`。因此，输出的结果为`3,2`。
24、
#include <iostream>
using namespace std;
void fun(char *a, char *b) {
a = b;
(*a)++;
}
int main() {
char c1, c2, *p1, *p2;
c1 = 'A';
c2 = 'a';
p1 = &c1;
p2 = &c2;
fun(p1, p2);
cout << c1 << c2 << endl;
return 0;
}
输出：_________
参考答案：输出：Aa
解析：【喵呜刷题小喵解析】：在程序中，`fun`函数接收两个字符指针`a`和`b`作为参数。在函数内部，`a`被重新赋值为`b`，即`p2`的地址。然后，`*a`（即`c2`）的值增加1，从'a'变为'b'。在`main`函数中，`c1`和`c2`的初始值分别为'A'和'a'。`p1`和`p2`分别指向`c1`和`c2`。调用`fun(p1, p2)`后，`p1`（即`c1`）的值并未改变，而`p2`（即`c2`）的值变为'b'。因此，输出结果为'Aa'。
25、
#include <iostream>
#include <string>
using namespace std;
int main() {
int len, maxlen;
string s, ss;
maxlen = 0;
do {
cin >> ss;
len = ss.length();
if (ss[0] == '#')
break;
if (len > maxlen) {
s = ss;
maxlen = len;
}
} while (true);
cout << s << endl;
return 0;
}
输入：
I
am
a
citizen
of
China
#
输出：_________
参考答案：输出：citizen
解析：【喵呜刷题小喵解析】：
该程序从标准输入读取字符串，直到遇到以'#'开头的字符串为止。在读取过程中，程序会检查每个字符串的长度，如果长度大于之前记录的最大长度，则更新最大长度和对应的字符串。最后，程序输出最大长度的字符串。
在给定的输入中，程序首先读取"I"，长度为1，不满足条件。接着读取"am"，长度为2，同样不满足条件。然后读取"a"，长度为1，仍然不满足条件。接着读取"citizen"，长度为7，这是目前读取到的最长字符串，因此程序会更新最大长度为7，并将"citizen"存储在变量s中。接着读取"of"，长度为2，不满足条件。然后读取"China"，长度为5，不满足条件。最后读取"#"，因为以'#'开头，程序会跳出循环。因此，程序输出的最大长度的字符串是"citizen"。
26、
#include <iostream>
using namespace std;
int fun(int n, int fromPos, int toPos) {
int t, tot;
if (n == 0)
return 0;
for (t = 1; t <= 3; t++)
if (t != fromPos && t != toPos)
break;
tot = 0;
tot += fun(n - 1, fromPos, t);
tot++;
tot += fun(n - 1, t, toPos);
return tot;
}
int main() {
int n;
cin >> n;
cout << fun(n, 1, 3) << endl;
return 0;
}
输入：5
输出：_________
参考答案：15
解析：【喵呜刷题小喵解析】：首先，我们分析给定的函数`fun`。这个函数接受三个整数参数：`n`，`fromPos`和`toPos`。函数的主要目的是计算从`fromPos`到`toPos`（包括这两个位置）之间所有可能的子序列的数量，其中子序列的长度为`n`。
函数首先检查基本情况：如果`n`为0，则返回0。然后，它遍历从1到3的所有数字，并检查当前数字是否等于`fromPos`或`toPos`。如果当前数字不等于这两个位置中的任何一个，则跳出循环。
在循环结束后，函数调用自己两次，一次是将当前数字作为子序列的起始位置，另一次是将当前数字作为子序列的结束位置。每次调用都会返回从`fromPos`到当前数字或当前数字到`toPos`之间的子序列数量。
在`main`函数中，用户输入一个整数`n`，然后调用`fun`函数，将1作为起始位置，3作为结束位置，并打印结果。
对于输入5，函数会计算长度为5的子序列的数量，起始位置为1，结束位置为3。根据函数的实现，我们可以手动计算或通过观察发现，长度为5的子序列的数量为15。
因此，对于输入5，输出应为15。
四、实操题
27、双子序列最大和）给定一个长度为n（3≤n≤1000）的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为1，且两个连续子序列之间至少间隔1个数。（第五空4分，其余 2.5分）
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN];
// lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中，最大的序列和
int rmax[MAXN];
// rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中，最大的序列和
int main() {
cin >> n;
for (i = 0; i < n; i++)
cin >> x[i];
lmax[0] = x[0];
for (i = 1; i < n; i++)
if (lmax[i - 1] <= 0)
lmax[i] = x[i];
else
lmax[i] = lmax[i - 1] + x[i];
for (i = 1; i < n; i++)
if (lmax[i] < lmax[i - 1])
lmax[i] = lmax[i - 1];
(1) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i + 1] <= 0)
(2) ;
else
(3) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i] < rmax[i + 1])
(4) ;
ans = x[0] + x[2];
for (i = 1; i < n - 1; i++) {
sum = (5) ;
if (sum > ans)
ans = sum;
}
cout << ans << endl;
return 0;
}
参考答案：1. 初始化 `rmax[n-1] = x[n-1]`2. `rmax[i] = max(x[i], rmax[i+1] + x[i])`3. `rmax[i] = max(rmax[i], rmax[i+1])`4. `rmax[i] = max(rmax[i], x[i] + rmax[i+1])`5. `sum = x[i] + lmax[i+1]`
解析：【喵呜刷题小喵解析】：
根据题目要求，我们需要从整数序列中选出两个连续子序列，使得这两个连续子序列的序列和之和最大。由于每个连续子序列长度至少为1，且两个连续子序列之间至少间隔1个数，所以我们需要分别计算以每个数为起点的左侧最大子序列和，以及以每个数为终点的右侧最大子序列和。
对于左侧最大子序列和，我们可以使用动态规划的思想，定义一个数组 `lmax`，其中 `lmax[i]` 表示仅含 `x[i]` 及 `x[i]` 左侧整数的连续子序列的序列和中，最大的序列和。我们可以从前往后遍历数组 `x`，如果 `lmax[i-1] <= 0`，则 `lmax[i] = x[i]`，否则 `lmax[i] = lmax[i-1] + x[i]`。
对于右侧最大子序列和，我们可以使用类似的方法，定义一个数组 `rmax`，其中 `rmax[i]` 表示仅含 `x[i]` 及 `x[i]` 右侧整数的连续子序列的序列和中，最大的序列和。我们可以从后往前遍历数组 `x`，如果 `rmax[i+1] <= 0`，则 `rmax[i] = x[i]`，否则 `rmax[i] = max(rmax[i], rmax[i+1] + x[i])`。
然后，我们可以遍历数组 `x`，计算以每个数为起点的左侧最大子序列和与以每个数为终点的右侧最大子序列和之和，并更新最大和 `ans`。
需要注意的是，由于题目要求两个连续子序列之间至少间隔1个数，所以我们需要从 `x[1]` 开始计算左侧最大子序列和，从 `x[n-2]` 开始计算右侧最大子序列和。在计算右侧最大子序列和时，我们需要注意到 `rmax[n-1]` 是无法作为任何一个子序列的终点的，所以我们需要单独初始化 `rmax[n-1] = x[n-1]`。
最后，输出最大和 `ans` 即可。
28、（最短路径问题）无向连通图G有n个结点，依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点0为起点出发，到各结点的最短路径长度。
使用Dijkstra算法解决该问题：利用dist数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取dist值最小的结点v进行扩展，更新与v相邻的结点的dist值；不断进行上述操作直至所有结点均被扩展，此时dist数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i, j, v;
int w[MAXV][MAXV]; // 邻接矩阵，记录边长
// 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1
int dist[MAXV];
int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展）
int main() {
cin >> n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> w[i][j];
dist[0] = 0;
for (i = 1; i < n; i++)
dist[i] = -1;
for (i = 0; i < n; i++)
used[i] = 0;
while (true) {
(1) ;
for (i = 0; i < n; i++)
if (used[i] != 1 && dist[i] != -1 && (v == -1 || (2) ))
(3) ;
if (v == -1)
break;
(4) ;
for (i = 0; i < n; i++)
if (w[v][i] != -1 && (dist[i] == -1 || (5) ))
dist[i] = dist[v] + w[v][i];
}
for (i = 0; i < n; i++)
cout << dist[i] << endl;
return 0;
}
参考答案：(1) 找到未扩展的结点中dist值最小的结点v(2) dist[v] < dist[i](3) v = i(4) 将结点v标记为已扩展(5) dist[v] + w[v][i] < dist[i]
解析：【喵呜刷题小喵解析】：
1. (1)处，需要找到未扩展的结点中dist值最小的结点v。这可以通过遍历所有结点，并检查它们的dist值和used状态来实现。
2. (2)处，判断条件`dist[v] < dist[i]`用于确保我们选取的是当前未扩展结点中dist值最小的结点。
3. (3)处，将找到的最小dist值的结点赋值给v。
4. (4)处，将结点v标记为已扩展，表示该结点的最短路径长度已经确定。
5. (5)处，更新与v相邻的结点的dist值。这里需要满足两个条件：一是w[v][i] != -1，表示v和i之间有边；二是`dist[v] + w[v][i] < dist[i]`，表示通过v到达i的路径比之前的路径更短。
根据Dijkstra算法，每次从未扩展的结点中选取dist值最小的结点进行扩展，更新与其相邻的结点的dist值，直到所有结点均被扩展。最后，dist数组中记录的值即为各结点与起点的最短路径长度。
