2010年北邮计算机学院复试上机测试题及参考答案

这些题目是针对计算机科学基础的编程测试，涵盖了数据结构、算法和基本的逻辑判断。下面是对每个题目涉及知识点的详细解释： 题目A：这个题目主要考察的是对整数的奇偶性判断。输入是一个整数n，然后是n个整数。程序需要统计奇数和偶数的数量，并根据奇数是否多于偶数来输出"YES"或"NO"。这个题目涉及到的基本概念是整数的模运算（%），通过判断数字除以2的余数来确定它是奇数还是偶数。参考答案中使用了for循环遍历所有输入的数字，用变量even和odd分别记录偶数和奇数的数量，最后比较这两个变量的大小来决定输出。 题目B：这个题目考察的是二维数组的处理和排序。输入是n个点的坐标，需要找出横坐标最小的点，如果横坐标相同则选择纵坐标最小的点。这个问题可以通过使用结构体（如C++中的struct）存储点的坐标，并定义两个比较函数cmpx和cmpy分别按横坐标和纵坐标进行排序。在main函数中，先读取n，然后创建一个结构体指针的向量，填入所有点的信息，然后按横坐标排序，最后找出纵坐标最小的点。 题目C：这是一个关于矩阵操作的问题，涉及到了2x2或3x3子矩阵的旋转。根据输入的a、b、c、d四个参数，程序需要执行相应的顺时针或逆时针旋转操作。对于矩阵的处理，可以使用二维数组来实现。参考答案中未提供，但实现时可以先将子矩阵提取出来，执行旋转操作（通过临时数组或原地旋转），然后再替换回原矩阵相应的位置。 题目D：这个题目涉及到赫夫曼编码（Huffman Coding），是一种用于数据压缩的位编码方法。给定n个带权重的节点，构建赫夫曼树并计算所有节点的权重与编码长度（即节点深度）的乘积之和。赫夫曼树是一种特殊的二叉树，其特点是叶子节点代表字符，内部节点的权重是其子节点的权重之和，且路径从根到叶子节点的权值最小。构建赫夫曼树通常采用优先队列（堆）的数据结构，然后根据树的结构生成赫夫曼编码。最后计算每个节点的权重与编码长度的乘积，求和得到结果。 这些题目反映了计算机科学基础课程中常见的问题，包括基本的输入输出处理、条件判断、排序算法、数组操作、数据结构（如二叉树）以及编码理论。解决这些问题需要扎实的编程基础和对数据结构的理解。