第1章
计算机科学基础

1.1 考点精讲

1.1.1 考纲要求

1.1.1.1 考点导图

计算机科学基础部分的考点如图1-1所示。

1.1.1.2 考点分析

这一章主要是要求考生掌握数制及其转换、数据的表示、算术运算和逻辑运算、数学应用的基本知识，并熟练掌握常用数据结构和常用算法。根据近年来的考试情况分析得出：

●难点

1）数据的3种编码——原码、反码、补码，以及它们之间的变换方法。

2）浮点数的表示法及其规格化。

3）常用数据结构，其中二叉树及其遍历、链表尤为重要。

4）图的存储（矩阵、邻接表）与遍历、算法效率的计算（时间、空间复杂度）、6种常见的排序算法、哈希表（散列表）及其解决冲突的方法。

●考试题型的一般分布

1）数制表示、数据表示、校验码的长度、逻辑表达式（公式、等效变换）、“与”“非”“异或”的运算规则。

2）数学应用的内容虽然在近年的考试中很少涉及，但是会利用数据结构、程序设计的方法来考察，比如基于C语言的二维数组完成矩阵的运算。

3）二维数组及其存储、链表的存储/操作（插入、删除、移动）、二叉树的定义及性质（完全二叉树、满二叉树）、结点与深度的关系、图的概念（有向、无向）及性质。

●考试出现频率较高的内容

1）浮点数规格化、进制转换、求反码和补码。

2）链表操作、队列和栈的性质及对比、二叉树的遍历、二叉树的结点计算、递归算法的设计（退出条件等）。