南宫28ng2023年CSP-JS 第一轮初赛真题及参考答案！2023年9月16日上午11:30，CSP-J/S 2023第一轮认证结束，以下为本次比赛真题及参考答案（仅供参考，以官方发布为准）

　　2. 0,1,2,3,4 中选取4个数字，能组成个不同四位数。(注: 最小的四位数是 1000最大的四位数是9999)

　　3.假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法南宫28ng。对于 m=O(n)的稀疏图而言，下面的四个选项，哪一项的渐进时间复杂度最小

　　4.假设有n 根柱子，需要按照以下规则依次放置编号为 1,2,3..的圆柱:每根柱子的底部固定，顶部可以放入圆环:每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4个根子时，最多可以放置个圆环。

　　7.最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下，给定两个序列X=(x1,x2x3....xm)和 Y=(y1,y2,y3,..yn)，最长公共子序列(LCS)问题的目标是找到一个最长的新序列 Z=(z1,z2,z3....zk)，使得序列Z 既是序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。(注: 序列A是序列B 的子序列，当且仅当再保持序列 B 元素顺序的情况下，从序列 B 中删除若干个元素，可以使得剩余的元素构成序列 A。则序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为 。

　　8.一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下: 玩家第一次掷出x点，得到2x元第二次掷出y点，当y=x 时玩家会失去之前的得到2x元。而当y≠x 时玩家能保住第一次获得的2x元。上述x,y∈{1，2，3，4，5，6}。例如: 玩家第一次掷出3点得到6元后，但第二次再次掷出3点,会失去之前得到的6元，玩家最终受益为0元:如果玩家第一次掷出3 点，第二次掷出4点，则最终受益是6元。假设骰子挑出任意一点的概率为 1/6，玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少?

　　请问 res 的值是什么?(提示:在 c++中，逻辑运算的优先级从高到低依次为: 逻辑非(!)，逻辑与(&&)，逻辑或位运算的优先级从高到低依次为: 位非 (~)，位与(&)，位异或，位或)。同时，双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同，且高于所有双目运算符

　　10.假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

　　11.以下哪个命令，能将一个名为main.cpp”的 C++源文件，编译并生成一个名为“main的可执行文件?

　　12.在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数量最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?( )

　　13.如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边?

　　假设输入总是合法的且a[i]≤10、n≤10000和1≤k≤n(n-1)/2，完成下面的判断题和单选题。

　　现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）

　　6. 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。

　　B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。

　　10. 假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）

　　11. 给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）

　　12. 考虑一个有向无环图，该图包括4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)南宫28ng。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）

　　14. 一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）

　　二、 阅读程序（程序输入不超过数组成字符串定义的范围：判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

　　17. （2分）将第7行中的（s-b）*（s-c）改为（s-c）*（s-b）不会影响程序运行的结果（T）

　　28. 第13~14行的作用是避免n的平方根因子i（或n/i）进入第16行而被计算两次（T）

　　(1)(寻找被移除的元素)问题:原有长度为 n+1公差为1等升数列，将数列输到程序的数组时移除了一个元素，导致长度为 n 的开序数组可能不再连续，除非被移除的是第一个或最后之个元素。需要在数组不连续时南宫28ng，找出被移除的元素。试补全程序。

　　(2) （编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

　　从搜狗CEO王小川（信息学金牌），看这二十几年中国奥赛金牌的去向 揭晓高薪专业排行榜，计算机专业薪资最高！哪些专业最具潜力？