2024年信息学奥赛CSP-S1提高组初赛C++真题及参考答案

1.在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（ ） A.pwd B.cd C.Ls D.echo 2.假设一个长度为n的整数数组中每个元素互不相同，且这个数组是无序的。要找到这个 数组中最大元素的时间复杂度是多少？（ ） A.O(n) B.O(logn) C.O(nlogn) D.O(1) 3.在C++中，以下哪个函数调用会造成栈溢出？（ ） A.intfoo(return0;) B.Intbar(intx=1;returnx) C.Voidbaz(){inta[1000];baz();} D.Voidqux(){return;} 4.在一场比赛中，有10名选手参加，前三名将获得金银铜牌，若不允许并列，且每名选手 只能获得一枚铜牌，则不同的颁奖方式共有多少种？（ ） A.120 B.720 C.504 D.1000 5.下面那个数据结构最适合实现先进先出（FIFO）的功能？（ ） A.栈 B.队列 C.线性表 D.二叉搜索树 6.一直f(1)=1,且对于n>=2有f(n)=f(n−1)+f(n/2),则f(4)的值为：（ ） A.4 B.5 C.6 D.7 7.假设一个包含n个顶点的无向图，且该图是欧拉图。一下关于该图的描述中哪一项不一 定正确？（ ） A.所有顶点的度数均为偶数 B.该图联通 C.该图存在一个欧拉回路 D.该图的边数是奇数 8.对数组进行二分查找的过程中，以下哪个条件必须满足？（ ） A.数组必须是有序的 B.数组必须是无序的 C.数组长度必须是2的幂 D.数组中的元素必须是整数 9.考虑一个自然数n以及一个模数m，你需要计算n的逆元（即n在模m意义下的乘法逆 元）。下列哪种算法最为合适？（ ） A.使用暴力方法依次尝试 B.使用扩展欧几里得解法 C.使用快速幂解法 D.使用线性筛法 10.在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和和冲突解决策略。已 知某哈希表中有n个键值对，表的装载因子为α（0<α<=1）。在使用开放地址法解决冲突的 过程中，最坏情况下查找一个元素的时间复杂度为（ ） A.O(1) B.O(logn) C.O(1/(1-α)) D.O(n) 11.假设有一颗h层的完全二叉树，该树最多包含多少个节点（ ） A.2 ℎ −1 B.2 (ℎ+1) −1 C.2 ℎ D.2 ℎ+1 12.设有一个10个顶点的完全图，每两个顶点之间都有一条边，有多少个长度为4的环？ （ ） A.120 B.210 C.630 D.5040 13.对于一个整数n，定义f(n)为n的各个位数之和，问使f(f(x))=10的最小自然数x是多少？ （ ） A.29 B.199 C.299 D.399 14.设有一个长度为n的01字符串，其中有k个1，每次操作可以交换相邻两个字符。在最 坏的情况下将这k个1移到字符串最右边所需要的交换次数是多少？（ ） A.K B.K*(k-1)/2 C.(n-k)*k D.(2n-k-1)*k/2 15.如图是一张包含7个顶点的有向图。如果