附上汇总帖GESP认证C编程真题解析 | 汇总单选题第1题已知小写字母 b 的ASCII码为98下列C代码的输出结果是 。#includeiostreamusingnamespacestd;intmain(){charab^4;couta;return0;}A.bB.bbbbC.fD.102【答案】C【解析】C中运算符^表示对两个操作数进行按位异或的运算对表达式’b’^4其会将’b’类型转换得到ASCII 码98来与4运算。98和4的二进制表示分别为0110001000000100故98^4102。但结果保存至char 类型的变量a中故输出a时结果应为ASCII码102所对应的字符故选选C。第2题已知 a 为 int 类型变量 p 为 int * 类型变量下列赋值语句不符合语法的是 。A.*(p a) *p;B.*(p - a) a;C.p a p;D.p p a;【答案】C【解析】A选项中*p 表示指针p所指向的 int 型变量p与a的运算表示p 的地址向后偏移a *(类型所对应的字节)单位后的新地址例如若p 指向 int 型数组b[100]则pa指向其中的元素b[a]故A选项符合语法。同理B选项也符合语法。但需要注意的是符合语法只能确保通过编译程序运行时若pa、p-a指向了非法的地址则可能导致程序出现运行时错误(RTE)。C、D选项中pa 的运算结果仍为 int*型其可赋值为p即可以作为右值但其不能作为左值不能将 p 赋值给pa的整体故C选项不符合语法。第3题下列关于C类的说法错误的是 。A.如需要使用基类的指针释放派生类对象基类的析构函数应声明为虚析构函数。B.构造派生类对象时只调用派生类的构造函数不会调用基类的构造函数。C.基类和派生类分别实现了同一个虚函数派生类对象仍能够调用基类的该方法。D.如果函数形参为基类指针调用时可以传入派生类指针作为实参。【答案】B【解析】C中基类是用来提供基础功能或接口的类。它可以包含成员变量和成员函数并能够被其他类继承。派生类则是通过继承基类来扩展功能的类。其继承了基类的成员可以直接使用它们也可以重写或扩展。构造函数是用来初始化对象的特殊成员函数在创建对象时自动调用。它的名字与类名相同没有返回值类型。析构函数是用来清理对象或释放资源的特殊成员函数在对象销毁时自动调用。它的名字是类名的前面加~(如~Base)没有返回值也不能带参数。若基类的析构函数未声明为虚析构函数而使用基类指针删除派生类对象时可能只会调用基类的析构函数导致派生类对象未正确释放其资源。因此基类的析构函数应声明为虚析构函数以确保派生类的析构函数被调用。故A选项正确。构造派生类对象时会先调用基类的构造函数再调用派生类的构造函数。这是类继承对象构造的机制基类构造函数负责初始化基类部分派生类构造函数负责初始化派生类部分。故B选项错误。虽然基类和派生类实现了同一个虚函数但通过基类指针或引用调用时若未发生多态则可能调用基类版本的方法若发生多态(虚函数机制生效)则会根据对象的实际类型调用派生类版本的方法。故C选项正确。派生类指针可以隐式转换为基类指针因此基类指针形参可以接受派生类指针作为实参。这是基类和派生类之间向上类型转换的特点。故D选项正确。第4题下列C代码的输出是 。#includeiostreamusingnamespacestd;intmain(){intarr[5]{2,4,6,8,10};int*parr2;coutp[3]endl;return0;}A.6B.8C.编译出错无法运行。D.不确定可能发生运行时异常。【答案】D【解析】p是 int * 类型其为指向int 型的指针具体指向arr[2]6这一元素。对p[3]可按p[i]*(pi)理解从而有p[3]*(arr5)然而arr 是仅有5个元素的数组故p[3]会导致下标越界虽然能够通过编译但其为未定义行为可能会导致运行时错误故选D。第5题假定只有一个根节点的树的深度为1 11则一棵有N NN个节点的完全二叉树则树的深度为 。A.⌊ l o g 2 ( N ) ⌋ 1 \lfloor log_2(N)\rfloor 1⌊log2​(N)⌋1B.⌊ l o g 2 ( N ) ⌋ \lfloor log_2(N)\rfloor⌊log2​(N)⌋C.⌈ l o g 2 ( N ) ⌉ \lceil log_2(N)\rceil⌈log2​(N)⌉D.不能确定【答案】A【解析】对深度为k的完全二叉树其结点个数的取值范围为[ 2 k − 1 , 2 k ) [2^{k-1}, 2^k)[2k−1,2k)。令 N 满足2 k − 1 ≤ N 2 k 2^{k-1}≤N2^k2k−1≤N2k不等式串两边以2为底取对数则有k − 1 ≤ l o g 2 N k k-1≤log_2Nkk−1≤log2​Nk即k ⌊ l o g 2 N ⌋ 1 k \lfloor log_2N\rfloor 1k⌊log2​N⌋1故选A。第6题对于如下图的二叉树说法正确的是 。A.先序遍历是 ABDEC 。B.中序遍历是 BDACE 。C.后序遍历是 DBCEA 。D.广度优先遍历是 ABCDE 。【答案】D【解析】图中二叉树的先序遍历为ABDCE 中序遍历为DBAEC后序遍历为DBECA故A、B、C选项错误。二叉树的广度优先遍历为按层自顶向下每层从左向右图中二叉树的广度优先遍历确为 ABCDE故D选项正确。第7题图的存储和遍历算法下面说法错误的是 。A.图的深度优先遍历须要借助队列来完成。B.图的深度优先遍历和广度优先遍历对有向图和无向图都适用。C.使用邻接矩阵存储一个包含 个顶点的有向图统计其边数的时间复杂度为 。D.同一个图分别使用出边邻接表和入边邻接表存储其边结点个数相同。【答案】A【解析】图的深度优先遍历需要借助栈来完成但图上的两种遍历泛用性很高无论图是有向图还是无向图是否有重边或自环都可以使用深度优先遍历和广度优先遍历故A选项错误B选项正确。使用邻接矩阵存图时需要双重循环枚举边的起点、终点来分别统计两点间的边数。而使用邻接表存图时无论是对各点保存入边还是出边总边数都不变故C、D选项正确。第8题一个连通的简单有向图共有28条边则该图至少有 个顶点。A.5B.6C.7D.8若该简单有向图只有5个顶点则其为完全图时边数最多但此时也只有5*(5-1)20条边对于28条边的图需要在完全图的基础上再新增8条边必然产生重边这与图是简单图矛盾。可令图有6个顶点此时图最多可以有6*(6-1)30条边对于仅有28条边的图为使其(强)连通只需从6个顶点的完全图中删去某两点间直接相连的两条边可以保证这两个点仍能通过其他路径相互到达故B选项正确。第9题以下哪个方案不能合理解决或缓解哈希表冲突 。A.在每个哈希表项处使用不同的哈希函数再建立一个哈希表管理该表项的冲突元素。B.在每个哈希表项处建立二叉排序树管理该表项的冲突元素。C.使用不同的哈希函数建立额外的哈希表用来管理所有发生冲突的元素。D.覆盖发生冲突的旧元素。【答案】D【解析】哈希表是一种支持插入、查询元素的数据结构其将元素本身的值通过哈希函数计算得到需要插入至哈希表中的下标并结合某些策略完成元素的最终插入操作对于插入后的元素理应能在哈希表中再查询得到。以下分析中以插入若干整数取哈希函数H(×)×%10为例。在每个哈希表项处可使用不同的哈希函数再建立一个哈希表。例如插入1、11、21、…时这些元素会在哈希表中下标为1的表项处发生冲突此时在该表项处可取新哈希函数H2(×)×%10007这样可以将冲突元素在二级哈希表中散开故A选项可以缓解哈希表冲突。在每个哈希表项处可建立二叉排序树因为对于存在偏序关系的类型的元素二叉排序树也可以实现元素的快速插入和查找故B选项可以缓解哈希表冲突。对发生冲突的元素可使用不同的哈希函数建立额外的哈希表例如取新哈希函数H2(×)×%10007建立额外的哈希表则向哈希表插入1其会存入原哈希表中下标为1的表项而插入11、21、…时其先与已有元素的表项冲突然后能够再插入到额外的哈希表中故C选项可以缓解哈希表冲突。然而若只是简单地覆盖发生冲突的旧元素则不能保证哈希表查询元素的功能。例如插入1、11、21、…时每次插入元素都会导致下标为1的原有表项被覆盖而丢失从而再查询1时会判定为元素不存在使哈希表的功能失真。故D选项不能缓解哈希表冲突。第10题以下关于动态规划的说法中错误的是 。A.动态规划方法通常能够列出递推公式。B.动态规划方法的时间复杂度通常为状态的个数。C.动态规划方法有递推和递归两种实现形式。D.对很多问题递推实现和递归实现动态规划方法的时间复杂度相当。【答案】B【解析】动态规划方法一般可以列出递推式计算也称作状态转移方程例如最大子段和问题的递推式为f[i]max(f[i - 1], 0)a[i]。代码实现时既可以循环递推计算又可以实现为递归形式使用记忆化搜索的方式计算一般两种实现的时间复杂度相同故A、C、D选项正确。动态规划方法的时间复杂度不仅取决于状态的个数还应考虑各个状态计算时可以做的转移个数。例如最长上升子序列问题中以f[i] 表示以 a[i] 为结尾的上升子序列的最大长度可见状态只有n个但每个状态有O(n)个转移从而总时间复杂度复杂度达到O(n²)。故B选项错误。第11题下面程序的输出为 。#includeiostreamusingnamespacestd;intrec_fib[100];intfib(intn){if(n1)returnn;if(rec_fib[n]0)rec_fib[n]fib(n-1)fib(n-2);returnrec_fib[n];}intmain(){coutfib(6)endl;return0;}A.8B.13C.64D.结果是随机的【答案】A【解析】由代码实现可知 fib 函数的功能是求斐波那契数列且fib(1)1fib(2)1。故fib(6)即为斐波那契数列的第6项1、1、2、3、5、8A选项正确。第12题下面程序的时间复杂度为 。intrec_fib[MAX_N];intfib(intn){if(n1)returnn;if(rec_fib[n]0)rec_fib[n]fib(n-1)fib(n-2);returnrec_fib[n];}A.O ( 2 n ) O(2^n)O(2n)B.O ( ϕ n ) , ϕ 5 − 1 2 O(\phi^n),\phi \frac{\sqrt 5-1}{2}O(ϕn),ϕ25​−1​C.O ( n 2 ) O(n^2)O(n2)D.O ( n ) O(n)O(n)【答案】D【解析】由代码实现可知程序虽为递归实现但采用了记忆化搜索的技术对各个nfib(n) 只会递归计算一次便将结果保存在 rec_fib[n]中后续直接调用故选项D正确。第13题下面 search 函数的平均时间复杂度为 。intsearch(intn,int*p,inttarget){intlow0,highn;while(lowhigh){intmiddle(lowhigh)/2;if(targetp[middle]){returnmiddle;}elseif(targetp[middle]){lowmiddle1;}else{highmiddle;}}return-1;}A.O ( n l o g ( n ) ) O(nlog(n))O(nlog(n))B.O ( n ) O(n)O(n)C.O ( l o g ( n ) ) O(log(n))O(log(n))D.O ( 1 ) O(1)O(1)【答案】C【解析】由代码实现可知程序要在有序数组p中二分查找目标值 target二分查找算法的平均时间复杂度为 O(log n) 故c选项正确。第14题下面程序的时间复杂度为 。intprimes[MAXP],num0;boolisPrime[MAXN]{false};voidsieve(){for(intn2;nMAXN;n){if(!isPrime[n])primes[num]n;for(inti0;inumn*primes[i]MAXN;i){isPrime[n*primes[i]]true;if(n%primes[i]0)break;}}}A.O ( n ) O(n)O(n)B.O ( n × l o g n ) O(n\times log n)O(n×logn)C.O ( n × l o g l o g n ) O(n\times log log n)O(n×loglogn)D.O ( n 2 ) O(n^2)O(n2)【答案】A【解析】由代码实现可知程序枚举n构造得到必然不是质数的 n *primes[i]将其筛去且在 primes[i] | n 时不再考虑之后的数这是因为之后的 n * primes[i 1]、… 中primes[i 1] 等已经不再是 n 的最小质因子了也就是说筛法中每个合数都会被其最小质因子筛去恰好一次这就是线性筛法的思路故A选项正确。第15题下列选项中哪个不可能是下图的广度优先遍历序列 。A.1, 2, 4, 5, 3, 7, 6, 8, 9B.1, 2, 5, 4, 3, 7, 8, 6, 9C.1, 4, 5, 2, 7, 3, 8, 6, 9D.1, 5, 4, 2, 7, 3, 8, 6, 9【答案】B【解析】从1出发可直接到达2、4、5遍历时可按不同顺序将这些点入队此时四个选项的前4项仍然合法。若按2、4、5的顺序将点入队则1出队后遍历2、4、5时会分别将3入队、将7入队且在遍历5时无动作因为7已经入队。此时队列中结点依次有3 7。遍历3、7时会分别将6、8入队最后遍历6时再将9入队。各点的遍历顺序恰为A选项故A选项可以是图的广度优先遍历。若按2、5、4的顺序将点入队则1出队后遍历2、5、4时T会分别将3入队、将7入队且在遍历4时无动作因为7已经入队。此时队列中结点依次有3 7。遍历3、7时会分别将6、8入队从而遍历顺序同出队顺序也应为6 8。但B选项中6和8的顺序颠倒了故B选项不是图的广度优先遍历。若按4、5、2或5、4、2的顺序将点入队则1出队后会依次将7入队、将3入队。从而遍历7、3时再分别将8、6入队遍历顺序同出队顺序。故C、D选项可以是图的广度优先遍历。判断题第1题C语言中表达式 9 12 的结果类型为 int 、值为 8 。A.正确B.错误【答案】A【解析】C中运算符表示个两个操作数进行按位与的运算9和12的二进制表示分别为10011100故9128类型与两个操作数相同都是int类型故答案为正确。第2题C语言中指针变量指向的内存地址不一定都能够合法访问。A.正确B.错误【答案】A【解析】指针被定义后没有正确初始化时它会默认指向一个未知的地址。这些地址可能是垃圾值访问这些地址会导致未定义行为。此外还有很多情形下指针所指的内存地址不一定能合法访问例如指针指向了释放的内存、访问了越界的内存。故答案为正确。第3题对n nn个元素的数组进行快速排序最差情况的时间复杂度为O ( n l o g n ) O(nlogn)O(nlogn)。A.正确B.错误【答案】B【解析】快速排序的最优时间复杂度、平均时间复杂度都为 O(n log n)但最坏时间复杂度为O(n²)故答案为错误。第4题一般情况下 long long 类型占用的字节数比 float 类型多。A.正确B.错误【答案】A【解析】一般情况下 long long 类型占用8字节float类型占用4字节故答案为正确。第5题使用 math.h 或 cmath 头文件中的函数表达式 pow(10, 3) 的结果的值为 1000 、类型为 int 。A.正确B.错误【答案】B【解析】函数 pow(x,n)的作用是返回x n x^nxn的计算结果传入参数和返回值都为double 类型。因此结果的值为1000.0类型为double故答案为错误。第6题二叉排序树的中序遍历序列一定是有序的。A.正确B.错误【答案】A【解析】二叉排序树中任意结点的权值大于其左子树中结点的权值小于其右子树中结点的权值。据此可不断划分中序遍历内元素的大小顺序故答案为正确。第7题无论哈希表采用何种方式解决冲突只要管理的元素足够多都无法避免冲突。A.正确B.错误【答案】A【解析】哈希表的本质是通过哈希函数将范围较大、类型较复杂的值映射到有限的下标范围中。因此哈希冲突只能缓解而无法完全避免故答案为正确。第8题在C语言中类的构造函数和析构函数均可以声明为虚函数。A.正确B.错误【答案】B【解析】C中构造函数不能是虚函数析构函数可以是虚函数故答案为错误。第9题动态规划方法将原问题分解为一个或多个相似的子问题因此必须使用递归实现。A.正确B.错误【答案】B【解析】动态规划的代码既可以递归实现又可以递推实现故答案为错误。第10题如果将城市视作顶点公路视作边将城际公路网络抽象为简单图可以满足城市间的车道级导航需求。A.正确B.错误【答案】B【解析】城市间的车道即使只考虑单一方向也可能不止一条此时多条同方向的车道将成为图上的重边城际公路网络不能抽象为简单图故答案为错误。编程题