[c计算机二级公共基础知识]【计算机二级考试】公共基础知识

算法与数据

1.算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。

2.算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术。

3.数据元素：数据元素是数据的基本单位。

4.数据对象：数据对象是性质相同的数据元素的集合。

5.数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。

6.数据的逻辑结构包括数据对象和数据对象之间的关系。

7.数据的存储结构包括数据元素的存储方式和关系的存储方式。

8.一种数据的逻辑结构可以表示成多种存储结构。

线性结构

1.线性结构的条件（一个非空数据结构)：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。

2.栈、队列、双向链表是线性结构；树、二叉树为非线性结构。

3.线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

4.线性表的存储结构：顺序存储结构和链式存储结构

5.线性表的顺序存储结构有两个特点：
（1）线性表中所有元素所占的存储空间连续；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

6.线性表的链式存储结构存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。结点包含：数据域、指针域。（注：链式存储方式既可用于表示线性结构，也可用于表示非线性结构）。

栈

1.栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。

2.栈具有记忆功能，队列没有记忆功能。栈的特点是先进后出,后进先出,所以对一个栈进行出栈操作,出来的元素肯定是最后存入栈中的元素,所以栈有记忆功能。而队列是先进先出,取队列的第一个元素,得到的是最先存入队列的元素,而不是上一个存入队列的元素,所以没有记忆功能。

3.栈、队列的存储结构：
（1）顺序存储结构：用一组地址连续的存储单元即一维数组来存储；
（2）链式存储：线性链表。

4.计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。

树

1.树是n（n>0）个结点的有限集合，是一种非线性结构。

2.结点的度：结点所拥有的子树的个数。

3.叶子结点：度为0的结点。

4.分支结点：除叶子结点以外的结点。

5.结点的层次：根结点在第一层。

6.树的深度：所处层次最大的那个结点的层次。

7.树的度：树中所有结点的度的最大值。

8.二叉树每个结点最多只有两棵子树，且有左右之分，不能互换，二叉树有五种不同的形态。

9.在二叉树的第k层上，最多有2k-1(k>1)个结点。

10.深度为m的二叉树最多有2m-1个结点。

11.在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。

12.具有n个结点的二叉树，其深度不小于[log2n]+1，其中[log2n]表示为的log2n整数部分。

13.满二叉树：每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点。

14.完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

15.具有n个结点的完全二叉树的深度为[log2n]+1。

16.完全二叉树中度为1的结点数为0或1。

17.前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

18.中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

19.后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

20.顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。

只能采用顺序查找：
（1）线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。（2）    有序线性表，如果采用链式存储结构，也只能用顺序查找。

21.二分查找的条件：
（1）用顺序存储结构，
（2）线性表是有序表。

22.对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。

排序算法

1、交换类排序
（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为n(n-1)/2。
（2）快速排序法 ，在最坏的情况下，快速排序需要比较次数为n(n-1)/2。
2、插入类排序：
（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；
（2）希尔排序法，最坏情况需要O(n1.5)次比较。
3、选择类排序：
（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；
（2）堆排序法，最坏情况需要O(nlog2n)次比较。相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。

例题分析

以下数据结构中不属于线性数据结构的是______。　　

A. 队列　　B. 线性表　　C. 二叉树　　D. 栈　

2. 在一棵二叉树上第5层的结点数最多是______。　　

A. 8　　B. 16　　C. 32　　D. 15　　

3. 下面描述中，符合结构化程序设计风格的是______。　

A. 使用顺序、选择和重复(循环)三种基本控制结构表示程序的控制逻辑　　

B. 模块只有一个入口，可以有多个出口　　

C. 注重提高程序的执行效率　　

D. 不使用goto语句

下面概念中，不属于面向对象方法的是______。　　

A. 对象　　B. 继承　　

C. 类　　D. 过程调用　

在软件开发中，下面任务不属于设计阶段的是______。　　

A. 数据结构设计　　

B. 给出系统模块结构　　

C. 定义模块算法　　

D. 定义需求并建立系统模型　

 数据库系统的核心是______。　　

A. 数据模型　　B. 数据库管理系统　　

C. 软件工具　　D. 数据库