计算机等级考试二级C++模拟题及解析2笔试部分

　　1.栈和队列的共同特点是( )

　　C.只允许在端点处插入和删除元素

　　2.链表不具有的特点是( )

　　A.不必事先估计存储空间 B.可随机访问任一元素

　　C.插入删除不需要移动元素 D.所需空间与线性表长度成正比

　　3.为了提高测试的效率，应该( )

　　A.随机选取测试数据 B.取一切可能的输入数据作为测试数据

　　C.在完成编码以后制定软件的测试计划 D.集中对付那些错误群集的程序

　　4.软件生命周期中所花费用最多的阶段是( )

　　A.详细设计 B.软件编码 C.软件测试 D.软件维护

　　5.下列有关数据库的描述，正确的是( )

　　A.数据库是一个DBF文件

　　B.数据库是一个关系

　　C.数据库是一个结构化的数据集合

　　D.数据库是一组文件

　　6.算法的空间复杂度是指( )

　　A.算法程序的长度 B.算法程序中的指令条数

　　C.算法程序所占的存储空间 D.执行过程中所需要的存储空间

　　7.数据结构中，与所使用的计算机无关的是数据的( )

　　A.存储结构 B.物理结构 C.逻辑结构 D.物理和存储结构

　　8.软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指( )

　　A.模块间的关系 B.系统结构部件转换成软件的过程描述

　　C.软件层次结构 D.软件开发过程

　　9.数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是( )

　　A.控制流 B.加工 C.数据存储 D.源和潭

　　10.在数据库设计中，将E-R图转换成关系数据模型的过程属于( )

　　A.需求分析阶段 B.逻辑设计阶段

　　C.概念设计阶段 D.物理设计阶段

　　【参考答案】 B　11.以下C++语言中用于单行注释的是( )

　　12.若变量已正确定义并赋值，以下符合C++语言语法的表达式是( )

　　执行后输出结果是( )

　　15.若运行时给变量x输入12，则以下程序的运行结果是( )

　　16.以下关于C++类的说法中正确的是( )

　　B.C++语言中的类定义，用户一定要自己定义一个构造函数用于实例化类

　　C.C++语言中的成员函数的实现部分一定要写在类定义外

　　D.C++语言中的类不能够嵌套定义

　　【参考答案】 A　17.派生类对象对其基类中的什么成员是可访问的?( )

　　A.公有继承的私有成员 B.私有继承的公有成员

　　C.私有继承的保护成员 D.保护继承的保护成员

　　18.下列关于运算符重载不正确的是( )

　　A.运算符重载不能改变运算符的操作数个数

　　B.运算符重载不能改变运算符的优先级

　　C.运算符重载不能改变运算符的结合性

　　D.运算符重载能改变对预定义类型数据的操作方式

　　19.对于重载的运算符>>，它是一个( )

　　A.用于输入的友元函数 B.用于输入的成员函数

　　C.用于输出的友元函数 D.用于输出的成员函数

　　20.若调用一个函数，且此函数中没有return语句，则正确的说法是该函数( )

　　B.返回若干个系统默认值

　　C.有返回值，但返回一个不确定的值

　　D.能返回一个用户所希望的函数值

　　21.以下能对二维数组a进行正确初始化的语句是( )

　　该程序的输出结果是( )

　　【参考答案】 C　23.C++中，表示一条语句结束的标号是( )

　　则下列选项错误的是( )

　　25.下面程序的功能是把316表示为两个加数的和，使两个加数分别能被13和11整除，在划线处应填入的选项是( )

　　其中o≤i≤9,则对a数组不正确的引用是( )

　　A.字符串a的长度 B.字符串b的长度

　　C.字符串a和b的长度之差 D.字符串a和b的长度之和

　　28.下面程序的结果为( )

1. 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
• 关键：数字都在0到n-1的范围内

2. 二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
• 思路：注意数组是有顺序的。从右上角开始比较，大于target就只可能在左边，小于就只能在下面。若从中间开始找就会很麻烦。

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
• O(n)复杂度，先遍历一遍根据空格数计算出替换后的字符串长度，再从后往前复制字符。

4. 从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

6. 二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
• 解法：分两种情况，有右节点和没有右节点。有右节点：下一个节点就是右子树的最左边的节点。没有右节点：下一个节点就是（是父亲节点左子树的节点）

7. 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
• 思路：一个栈是先进后出，从一个栈出栈再入到第二个栈，第二个栈就是先进先出了，就完成了模拟队列。

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
• 解法：其实就是斐波那契数列，第n级台阶可以由第n-1级跳一步达到，也可以有第n-2级跳两步达到。

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n 的大矩形，总共有多少种方法？
• 解法：也是斐波那契数列

12. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
• 回溯法 -- 隐式图的深度优先搜索

14. 机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

15. 剪绳子（待定）

16. 二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
• 解法：从低位依次右移数一，不要从高位往低位数，因为负数的符号位右移一直是1。

17. 数值的整数次方

18. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
• 冒泡排序保持稳定性，插入排序也可以。注意，有没有黑体字的解法是不一样的。

19. 链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。
• 双指针，让一个指针先走k-1步，再两个指针一起走。简单题要考虑鲁棒性。

20. 链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

输入一个链表，反转链表后，输出新链表的表头。

22. 合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

• 题目描述: 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

操作给定的二叉树，将其变换为源二叉树的镜像。
• 扩展：用循环来做（模拟栈）。

由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时，最简单的办法就是用一个辅助栈来模拟递归。首先把树的头结点放入栈中。在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中；如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

26. 顺时针打印矩阵

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

28. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

29. 从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

30. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
• 解法：后序遍历根节点在最后，根据根节点将数组分为左右两部分（若无法分成两部分，则不是搜索树），再递归检查左右子树。

31. 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

32. 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
• 方法一：先按next复制节点，用哈希表将复制前后的节点一一对应起来，这样就可以用O(1)的时间复杂度找到random节点。
• 方法二：第一步，将复制节点连在旧节点后面；第二步，复制random节点；第三步，剪开。

33. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
• 众所周知，BST的中序遍历是顺序的。我想到的方法是：中序遍历，将树的节点依次存入一个数组，再把节点连起来。书上给的方法不需要额外的空间。

34. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

35. 连续子数组的最大和

36. 整数中1出现的次数

• 题目描述: 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

38. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对取模的结果输出。 即输出P%
• 归并排序，时间复杂度O(logN).

39.两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。
• 解法：长的链表先走几步，然后找第一个公共节点

40. 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

• 这个也算后序遍历。。。树的深度等于左右子树深度加一。

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
• 解法：用后序遍历的方式，先求出左右子树的高度，判断左右子树均为平衡二叉树后，再判断左右子树的高度差是否小于2

43. 数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
• 解法：因为有两个不同的数字，所有数字异或完后必不为0；再根据异或完的数某一位的1，将数组中的数分成两组，再分别异或。

44. 和为S的连续正数序列

输入一个正数s,打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15；所以打印出三个连续序列1~5 , 4~6, 7~8；

45. 翻转单词顺序列

• 解法：先翻转整个句子，再翻转每个单词

• 例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

47. 滑动窗口的最大值

• 解法：deque双向队列

48. 二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
• 思路：BST的中序遍历是顺序的。

49. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
• 思路：不用加减乘除意思就是用位运算。用异或代替无进位的求和，用与运算代替进位。

• 思路：先累乘左边，再累乘右边。

51. 二叉树两结点的最低公共祖先结点

给定二叉树中的两个结点，输出这两个结点的最低公共祖先结点（LCA）。注意，该二叉树不一定是二叉搜索树。

Time Limit: 1 Sec Memory Limit: 12 MB Submit: 3559 Solved: 2146 Description 有一个已排好序的数组，要求输入一个数后，按原来排序的规律将它插入到数组中。 假设数组长度为10，数组中前9个数（这9个数要求从键盘上输入，输入时要满足自小到大的输入顺序）已经按从小到大进行排序。 然后再从键盘上输入一个整数，将此整数插入到前有序的9个数中，使得最终的10个数依然是从小到大有序的。

Input 第一行输入以空格分隔的9个整数数，要求按从小到大的顺序输入。 第二行输入一个整数

代码（C语言） 代码1（有错，但是不知错在哪）

杨辉三角的原理： 每一行的下一行的最左侧a的指数都比上一行要多1而b的指数不变。

即第一个字母变成第26个字母，第i个字母变成第（26-i+1)个字母，非字母字符不变。要求根据密码译回原文，并输出。

例如："A"与"C"相比，由于"A"<"C"，应输出负数，同时由于"A"与"C"的ASCII码差值为2，因此应输出"-2"。 同理："And"和"Aid"比较，根据第2个字符比较的结果，"n"比"i"大5，因此应该输出"5"

Input 输入2行字符串 Output 一个整数，表示这两个字符串 比较的差值，单独占一行。 Sample Input

代码（C语言） 代码1

疑问：中间排序for循环的体中为什么是j不是i？(已解决)

代码（C语言） 代码1

注意：两个元素之间有空格，scanf的&取地址符号要有。

Input 输入3行，每行均为一个字符串。 Output 一行，输入三个字符串中最大者。 Sample Input

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：，尊重他人劳动成果，谢过~