2019 CSP-S1 模拟赛解析：函数式编程、图论与算法时间复杂度

"这份资源是2019 CSP-S1模拟赛3的主办方模拟测试题，包含单项选择题，主要涉及编程语言、计算机科学竞赛规则、数据表示、图论、位图存储、算法时间复杂度、数学期望以及排序算法等相关知识。" 1. 函数式编程语言：题目中提到Haskell是一种纯函数式编程语言。函数式编程语言强调程序是由纯函数构成，不含有副作用，例如状态变化或可变数据。 2. CSP-JS认证规则：CSP-JS认证是中国计算机学会举办的一项计算机编程能力认证，第一轮通常为纸质试卷，第二轮为电子版。认证开始15分钟后，不允许迟到者入场，认证者必须在2小时后才能离开，除非有特殊原因。违规行为可能导致参赛资格取消及禁赛。 3. 二进制表示：-1234在计算机中的二进制表示需要转换，题目中提供了四个选项，但未给出正确答案。一般负数在计算机中使用补码表示。 4. 无向图的DFS生成树：DFS生成树是通过深度优先搜索得到的树形结构，不是最小生成树。无向图的DFS生成树中边分为树边和回边，没有横叉边这一概念。 5. 位图存储空间计算：位图存储空间取决于分辨率和颜色深度。题目中给出的900*600分辨率、16位色，可以计算出存储空间。 6. 算法时间复杂度：根据给定的递推关系式T(N)=2T(N/2)+n^2，这是一个典型的Master定理问题，可以判断其时间复杂度为O(n^2logn)。 7. 数学期望问题：当n=10时，期望步数是指随机选择因子k使n变为1所需的平均步数。这个问题涉及到数学期望的计算，具体解答需要数学分析。 8. 插入排序：插入排序按照从大到小排序数组{1,2,3,4,5,6,7,8}，比较次数为28，因为每次插入都需要与已排序部分的所有元素进行比较。 9. 日期计算：根据公历规则，每过一个非闰年的普通星期会向前移动一天，1949年到2019年跨越了70个非闰年，所以1949年9月30日比2019年10月1日往前推70天。需要考虑1952年、1984年等闰年对星期的影响。 这些题目覆盖了编程语言基础、计算机竞赛规则、数值表示、图论、位图存储、算法效率、数学期望和排序算法等多个IT领域的知识点。