2024年计算机等级考试公共基础知识.doc

计算机公共基础知识

1.1大纲规定

1．掌握算法的基本概念。

2．掌握基本数据构造及其操作。

3．掌握基本排序和查找算法。

4．掌握逐渐求精的构造化程序设计措施。

5．掌握软件工程的基本措施，具有初步应用有关技术进行软件开发的能力。

6．掌握数据的基本知识，理解关系数据库的设计。

1.2考试題型及比例分派

比例：30％。一般10个选择題和5个填空題，详细如表1.1所示。

表1.1考试題型及比例分派

年份

題型

分数

年份

題型

分数

4月

选择（1～10）

填空（1～5）

30

4月

选择（1～10）

填空（1～5）

30

9月

选择（1～10）

填空（1～5）

30

括号内為考试題号。

1.3考试重点与经验分析

1.3.1基本数据构造与算法

1．算法的基本概念及特性

算法的概念是考试的重点，是指解題方案的精确而完整的描述，它由两种基本要素构成：一是对数据对象的运算和操作，二是算法的控制构造。

算法具有可行性、确定性、有穷性、拥有足够的情报等特性。其中，确定性和有穷性是考试的重点。

算法确实定性，是指算法中的每一环节都必须有明确定义，不容許有模棱两可的解释，也不容許有多义性。

算法的有穷性，是指算法必须能在有限的時间内做完，既算法必须能在执行有限个环节之后终止。

2．算法复杂度的概念和意义

一种算法质量的好坏可从算法的時间复杂度和空间复杂度两个方面来衡量。算法的复杂度也是每次考试的重点，要注意明确有关概念。

算法的時间复杂度是指算法所需要的计算工作量；算法的空间复杂度是指执行这个算法所需要的内存空间。

3．数据构造的定义

数据构造重要研究和讨论如下三个方面的问題：

①数据集合中各元素之间所固有的逻辑关系，既数据的逻辑构造。

②在对数据进行处理時，各数据元素在计算机中的存储关系，既数据的存储构造。

③对多种数据构造进行的运算。

要注意数据的逻辑构造与存储构造的区别与联络。

4．线性构造与非线性构造

根据数据构造中各元素之间前后件关系的复杂程度，一般数据构造分為两大类型：线性构造与非线性构造。要注意这两种构造的特性、它們之间的区别以及常見的有关构造。

（1）线性构造（或称线性表）有如下重要特性：

①有且只有一种根結点，它无前件。

②有且只有一种终止点，它无后件。

③除根結点与终端結点外，其他所有結点有且只有一种前件，也有且只有一种后件。线性表中結点的个数称為线性表的長度，当結点个数為0時，该线性表為空表。

常見的线性构造有：线性表、栈、队列等。

（2）假如一种数据构造不是线性构造，则称之為非线性构造，常見的非线性构造有：树、二叉树、图等。

5．线性表的次序存储构造（次序表）及其插入与删除运算

线性表既可以采用次序存储构造，又可以采用链式存储构造进行存储。要注意掌握两者在存储数据方面的方式与特点。

（1）线性表的次序存储构造的特点

①线性表中所有元素所占的存储空间是持续的。

②线性表中各数据元素在存储空间中是按逻辑次序依次寄存的。

由此可見，在线性表的次序存储构造中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。

（2）线性表在次序存储构造下的插入与删除运算

线性表在次序存储构造下，若在第i（1?i?n，n為线性表中元素的个数）个位置上插入一种新元素，则首先从最终一种（既第n个）元素开始，直到第i个元素之间共有n–i+1个元素依次向后移动一种位置，移动結束后，第i个位置就被空出，然后将新元素插入到第i个位置。插入結束后，线性表的長度增1。

显然，在最佳的状况下，插入位置在线性表的末尾进行，既在第n个元素之后插入运算，此時，不需要移动表中的元素。而在最坏的状况下，插入位置在第1个元素上，此時需要移动表中所有的元素。在平均状况下，要在线性表中插入一种新元素，需要移动表中二分之一的元素。

同理，线性表在次序存储构造下的删除运算，也需要移动表中的元素，只不过是向前移动，在最佳的状况下，删除运算在线性表的末尾进行，既删除第n个元素，此時，不需要移动表中的元素。而在最坏的状况下，删除位置在第1个元素上，此時需要移动表中所有的元素。在平均状况下，要在线性表中删除一种元素，需要移动表中二分之一的元素。

线性表的次序存储构造的特点，以及在次序存储构造下插入与删除运算的效率是考试的重点。

6．栈与队列

要深刻领会两者的概念，以及对两者进行插入、删除运算的特点，这是考试的重点。

栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。既在这种线性表的构造中，一端是封闭的，不容許进行插入与删除元素；另一端是开口的，容許插入与删除元素。容許插入与删除运算的一端称為栈顶，而不容許插入与