北航历年机试题目集锦：素数、旋转矩阵、字符串匹配等

这篇资源主要包含了历年北航计算机科学与技术专业机试的编程题目，涵盖了算法、数值计算、字符串处理等多个方面。以下是这些题目涉及的知识点详解： 1. **素数**： - 素数是大于1的自然数，除了1和它本身外，不能被其他自然数整除的数。题目要求找到所有个位为1的素数，这涉及到素数判定算法。通常使用的方法是埃拉托斯特尼筛法（Sieve of Eratosthenes），但这里可以简化为只检查个位是1的数，同时避免对2和5进行特殊处理。 2. **旋转矩阵**： - 旋转矩阵是线性代数中的概念，表示二维或三维空间中的旋转操作。判断两个矩阵是否为旋转关系，可以通过比较它们的特征值和特征向量，或者直接计算旋转角度。对于9阶以下的矩阵，可以使用直接计算的方法，例如逐行比较，检查是否可以通过旋转90度、180度、270度得到另一个矩阵。 3. **字符串匹配**： - 字符串匹配是计算机科学中常见问题，涉及到字符串处理和算法设计。题目要求不区分大小写，并支持模式匹配，可以使用KMP算法或者Boyer-Moore算法，同时考虑中括号表示的模式匹配，需要实现相应的扩展。 4. **立方根逼近**： - 这是一个数值计算问题，使用立方根的牛顿迭代法求解。牛顿迭代法是一种寻找函数零点的迭代方法，此处是求立方根，需要通过迭代公式不断逼近目标值，直到满足精度要求。 5. **数组排序**： - 对数组进行排序是常见的编程任务，可以采用各种排序算法，如冒泡排序、插入排序、快速排序、归并排序等。题目要求输出排序后的顺序，而不是实际排序后的数组，这需要维护一个映射表记录每个元素的位置。 6. **字符串查找删除**： - 需要实现字符串的搜索和替换功能，同时不区分大小写。可以使用哈希表或Trie树存储小写字符的出现位置，然后进行删除操作。此外，还需要处理行首空格的整理。 7. **泰勒公式**： - 泰勒公式用于近似复杂函数，它将函数表示为无穷级数。题目要求使用泰勒公式求cos(x)，通常使用麦克劳林展开式，该公式可以将cos(x)表示为x的幂次的和。 这些题目覆盖了基础算法、数据结构、数值计算和文件处理等多方面的计算机科学知识，是检验编程能力和算法理解的良好练习。