当前位置：文档之家› 全国计算机等级考试二级公共基础知识总结

全国计算机等级考试二级公共基础知识总结

第一章数据结构与算法

1.1 算法

1．算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。，

2．确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；

3．算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

的设计方法。

5．算法时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

6．算法时间复杂度取决于问题的规模和待处理的数据的初态。

7．如果算法P调用另一个算法Q，而算法Q又调用算法P，

8．工程上常用的分治法是减半递推技术

10．如果查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。也就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。如果已知需要查找的x有一半机会在数组中，此时q=1/2。则A(n)=[(n+1)/4]+n/2=3n/4。x不在数组中时，A(n)=n。. 11．下面程序段的时间复杂度是

for(int i=0;i

for(int j=1;j<=m;j++)

A[i][j]=0;

语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频度之和构成了该算法的运行时间。本例中语句:A[i][j]=0;的频度是n*m，所以该程序段的时间复杂度是：O(m*n).

13．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程较慢。

1.2 数据结构的基本基本概念

1．数据结构研究的三个方面：；

数据运算。

2．逻辑结构是数据元素间关系的描述，与所用的计算机无关

3．数据的逻辑关系是指数据元素的关联。

4．数据的不可分割的基本单位是数据项。

6．一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、7。索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。

8．数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式，与所使用的计算机密切相关

9．根据数据结构中各数据元素之间前后件关系的复杂度，一般将数据结构分为

10．在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元

11．插入和删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。

12．在数据结构中，用一组地址连续的存储单元依次存储数据元素的方式是线性结构。

1．3 线性表及其顺序存储结构

2．线性表是由n个数据元素组成的一个有限序列。删除一个元素，平均移动的元素的个数为(n-1+n-2+......+0)/n=(n-1)/2；插入一个元素，平均移动元素个

数为(n+n-1+n-2+......+1)/n=(n+1)/2

4．线性表可以是空表。

5．非空线性表的结构特征：

（1）且只有一个根结点a1，它无前件；

（2）有且只有一个终端结点an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。

6．线性表的顺序存储结构具有以下两个基本特点：

7．ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。

例：一个矢量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是108

数据元素的存储位置均取决于第一个数据元素的存储位置，即：。

ADR(ai)=ADR(a1)+(i-1)k

第5个元素的地址：ADR(a5)=100+(5-1)X2=108

8．在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有：

线性表的合并、线性表的复制、线性表的逆转等

合适的，因为顺序存储的结构比较简单。

10．采用顺序存储的线性表，顺序存储结构必须占用一片连续的存储单元，当对其进行插入和删除操作时需要移动大量的元素，优点是存储密度大，由于数组的存储方式是采用顺序存储的，即占用连续的存储空间，所以可以用数组的下标直接存取。

11．查找第i-1个结点和第i个结点，在顺序表中查找的时间复杂度为O(1)速度最快。由于链表结构在空间存储上的不连续性，在查找某个结点时，需要从当前结点开始向前或者向后逐个比较查找，浪费时间，查找结果的时间复杂度均为O(n)，

12．链接存储不是占用一片连续的存储空间，所以便于进行插入和删除操作。13．线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点，此类存储方式属于顺序存储。

1．4 栈和队列

1．栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。

2FILO LIFO

top表示栈顶位置，用bottom表示栈底。

3．当一个栈ST （最多元素为MaxSize）时，ST->top= -1是判断顺序栈为空的条件。ST->top=MaxSize-1是判断顺序栈为满的条件。

4．栈的基本运算：（12

（3

本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。

元素。

7．队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。

8．在一个容量为25的循环队列中，若头指针front=6，尾指针rear=9，则该循

环队列中共有

9FIFO LILO）的线性表。

10．队列运算包括（12

队头删除一个元素。

循环队列：s=0表示队列空，s=1且front=rear表示队列满

12．栈的基本操作。一个栈的入栈序列是1,2,3,...,n,其输出序列为P1，P2，P3，。。。，Pn，若P1=n，则Pi为n-i+1

当p1=n，即n是最先出栈的，根据栈的运算原理，n必定是最后入栈的，那么输入顺序必定是1,2,3,...,n,则出栈的序列是n,n-1,n-2,...,1

13．设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列B序列是不可能通过栈产生的

由于栈的压入和退出只能在栈顶进行，所以要使出栈的第一个数是序列的最后一个数5，只能先把序列所有元素都压入栈，但这时出栈序列只能是（A 5，4，3，2，1），所以（B 5，3，4，1，2）选项的出栈序列是错误的，应选（B）。当初始序列压入一个时，就退出一个元素，这样就得到（A）选项的出栈序列1，2，3，4，5；先压入1，2，3，4四个元素，再退出所有元素，最后压入5，并退栈这时得到（C）选项的出栈序列4，3，2，1，5；压入1，2后对后面的元素3，4，5分别压入一个退出一个，这时便得到（D）选项的出栈序列3，4，5，2，1。

1．5 线性链表

2．数据结构中的每一个结点对应于一个存储单元，这种存储单元（一个一个小

3．结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存

4．在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。因此，链式存储结构是散列存储

5．带头结点的双向循环链表L为空的条件是：只有该头结点，即L->next==L 或者 L->prior==L

6．对于链式队列结构，插入元素是在队尾进行的，只需修改队尾指针，不需修改队头指针。向链式队列中插入一个结点就是在单链表表尾插入一个结点，同时新插入的结点成为表尾结点。例：在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是r->next=s;r=s;

7．向链式栈中插入一个结点，就是在单链表的表头插入一个结点，同时将新结点的位置赋予栈顶指针。例：向一个栈顶指针为HS的链式栈中插入一个s所指的结点时，则执行s->next=HS;HS=s;

8．线性链表的基本操作

9．双向链表每个结点有两个指针域，这两个指针分别指向它的

10．单链表中，每个结点都含有一个指针域，这个指针指向它的下一个结点。因

11．由于双向链表比单链表结构复杂，所以在插入和删除元素时，要修改更多的指针域，相对比较复杂，单向链表和双向链表在空间存储上的不连续性决定了两者都不可以随机访问，在双向链表中由于每个结点包括两个指针域，其中一个指向该结点的前驱结点，另一个指向该结点的后继结点，因此它既可以直接访问前驱结点，又可以直接访问后继结点，而单链表每个结点只有一个指针域，指向它的后继结点，所以它只能直接访问它的下一个结点，而无法直接访问它的前一个结点。所以双向链表顺序访问相邻结点更加灵活。

12．链表的特点：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。链表结构是一些逻辑上相邻，而空间上并不一定相邻的数据元素的集合，相邻的结点之间通过指针相互联系，在插入和删除元素时，只需修改结点指针即可，不需要移动数据元素。当存储空间不足时，可以动态为其分配内存空间，所以不必事先估计存储空间的大小。所需空间与其长度成正比。

13．用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。当往空链表插入元素时，只要把待插入元素的指针域指向头结点的指针域，把头结点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置，执行同样的操作即可完成插入。当链表只有一个元素时，删除操作只要修改指针指向下一个元素的指针所指的元素即可，跟一般的链表删除操作是一样的。带头结点的链表并不能加快对链表的遍历，带头结点的链表反而要增加一个用于存储头结点的空间，并不能节省存储空间，用带头结点的链表跟存取元素的速度无关。14．忽略了最后结点或头结点的指针，在n个结点的单向链表（无表头结点）中，每个结点都有一个指针单元（即指针域），加上头指针，至少需要n+1个指针单元。

1．6 树与二叉树

1．树是一种简单的非线性结构，所有元素之间具有明显的层次特性。栈和队列都是线性结构。

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

2．树的结点不能为空，结点最少的树为只有一个结点的树；二叉树的结点数可

以为0

3．设树T的度为4，其中度为1，2，3和4的结点的个数分别为4、2、1、1，

则T中叶子结点的个数为

应的结点个数乘积之和为1。因此树的结点数为1*4+2*2+3*1+4*1+1=16。叶子结点数目等于树结点总数减去度不为0的结点数之和，即16-(4+2+1+1)=8。）4．设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深

和最小树深分别是

退化成一个线性链表，如果对应二叉树的根结点的层次为0，那么对应二叉树的树深为结点个数减1，即99；要使二叉树有最小树深，则此二叉树为满二叉树，当满二叉树的根结点的层次为1时，结点个数n和树深h之间的关系为：n=2^h-1，所以当二叉树的根结点层次为0时，对应关系为n=2^(h+1)-1。）

二叉树的基本性质：

（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；

（2）深度为m的二叉树最多有2的m次方-1个结点；

（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；

例：深度为5的二叉树至多有2*2*2*2*2-1=31个结点。

具有3个结点的二叉树有5种，

8．例：设深度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少2h-1

为结点最少的情况，除根结点层只有1个结点外，其余h-1层均有两个结点，结点总数=2(h-1)+1=2h-1。

（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n 的整数部分；

（5）具有n个结点的完全二叉树的深度为[log2n]+1；

（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：

①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；

②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；

③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。

9．对于深度等于其结点数的二叉树，每层只有一个结点，假设从上向下分别为a1,a2,...,an,则先序遍历序列为a1,a2,...,an。后序遍历序列为

an,an-1,...a1。遍历序列正好相反。

满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有

2k-1个结点深度为m的满二叉树有2m-1个结点。

10．由满二叉树的树深和结点的关系知，对于深度为h的满二叉树，m个树叶,n 个结点,则n=2^h-1即

n=2^0+2^1+2^2+......+2^(h-1)=2^h-1。

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

11．例：设一棵叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为13

12．例：假定根结点的层次是0，含有15个结点的二叉树的最小树深是3（要使二叉树在规定结点数下的深度最小，这样的二叉树只能是完全二叉树。当根结点的层次为1时，二叉树的结点n和深度h之间的关系是n=2^h-1，所以当二叉树的根结点的层次为0时，结点和树深的关系是n=2^(h+1)-1，所以h=3，n=15）

13．在在深度为5的完全二叉树中，度为2的结点数最多为

14．树的度是指树内各结点的度的最大值,一棵树中除根结点之外,每个结点都有一个前驱结点,结点拥有子树的个数称为结点的度,所以结点的度数之和即为除

根结点外所有结点的个数,即每个结点的度数之和等于结点总数减1,结点的度

即是拥有子树的个数,而结点与子树之间是以边连接的,所以一棵树中每个结点

的度数之和与边的条数相等,

15．由二叉树的性质知二叉树叶子的个数n(0)和度为2的结点个数n(2)的关系为n(0)=n(2)+1。二叉树的结点个数可以等于0，二叉树中有些不是叶子的结点只有一个子女，

二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。

16．二叉树的遍历：

前序遍历DLR先根结点，后遍历左子树，最后遍历右子树；abdgcefh EFHIGJK EDBAC DBEAFC

中序遍历LDR先左子树，后访问根结点，最后遍历右子树；dgbaechf HFIEJKG DEBAC ABDECF

后序遍历LRD先左子树，后遍历右子树，最后访问根结点 gdbehfca 右子树为

G DACBE DEBFCA

17．在先序、中序、后序遍历序列中叶子结点总是从左向右的。相对次序是不发生改变的。是完全相同的。（任意两种方法遍历同一棵二叉树，可以确保唯一一棵二叉树，无论是用前序遍历、中序遍历、后序遍历二叉树，其区别都在于访问根的先后次序不同，而叶子结点的顺序是一样的。）

18．例：对树的三大部分：树根、左子树、右子树，存在树根结点大于左子树各个结点，小于右子树各个结点，因此要得到各个结点值的递增序列，应按“左子树-根结点-右子树”的顺序进行访问，这就是中序遍历的遍历过程。

19．例：设n，m为一棵二叉树上的两个结点，在中序遍历中，n在m后的条件

是n在m的右子树上，如果n在m的右子树上，根据中序遍历算法，先访问根结点m，然后再访问右子树上的结点，所以n必然要在m后。如果n是m的祖先，则m可能在n的左子树上，也可能在n的右子树上，如果m在n的左子树上，根据中序遍历算法，先访问n的左子树，然后访问n结点，所以n必然要在m后，

对如果n是m的子孙，则n可能在m的左子树上，也可能在m的右子树上。中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。20．在中序遍历序列中，根结点将左右子树分开，左边为左子树中的所有结点，右边为右子树中的所有结点。

21．现有按中序遍历二叉树的结果为abc，问有

这样的遍历结果

22．在一棵二叉树中，度为0的结点个数为m，度为2的结点个数为n，则二者

之间的关系是

23．设一棵完全二叉树共有700个结点，则在该二叉树中有

1．7 查找技术

顺序查找的使用情况：（1）线性表为无序表；（2）表采用链式存储结构。1．顺序查找法适合于线性表，不论采用顺序存储还是链式存储。散列存储于顺序查找无关，同样压缩存储、索引存储也与顺序查找无关

序的有序表，对于长度为n的有序线性表进行二分查找，

次。

3．例：有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找为82的结点时，4次比校后查找成功。（此有序表的长度为13，按比较次数log2n计算应该是4。或先找中间结点45，再找77，95，最后找到82，经过4次比较，）

4．例：对有18个元素的有序表用二分法查找，则查找A[3]的比较序列的下标为9、4、2、3

第一次(1+18)/2=9,第二次(1+8)/2=4,第三次(1+3)/2=2,第四次(3+3)/2=3。5．例：设有一个已按元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s 和b，在查找不成功的情况下，s和b的关系是s>b 。 (对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较

n>=2时，显然n+1>[log2n]+1。)

6．例：在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值11，所需的关键码比较次数为4

（二分查找是用要查找的关键码与线性表的中间元素比较，根据比较结果是结束查找，还是在左边或者右边子表按相同的方法继续查找。与11比较的关键码分别为15、8、10、12。比较的次数为4。）

7．例：在顺序表（8，12，16，20，26，27，31，34，43，49，51）中，用二分

法查找关键值为21，需做的比较次数为27比较，由于21比27小，

根据二分法比较的方法，所以接着与27左边的16比较，由于21比16大，所以与16右边的20比较，最后一次与26比较。所以总共比较了4次。）

8．例：对一个长度为10的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是3

（分查找的值小于表中所有元素和大于表中所有元素两种情况进行分析），9．例：在长度为n的线性表中查找一个表中不存在的元素，需要的比较次数为

10．例：设线性表（a1，a2，。。。，a500）元素的值由小到大排列，对一个给

定的k值用二分法查找线性表，在查找不成功的情况下至多需比较

（二分法查找在查找不成功的情况下至多需要比较[log2n]+1=9(n=500)。）11．例：已知有序表为（12，18，24，35，47，50，62，83，90，115，134），

当用二分法查找100时，需进行（画出二叉树判定树，当查

找100时，需要和50、90、110比较，由于110的左子树为空，查找结束，比较了3次。）

12．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用分块查找方法

13．顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为(n+1)/2。

1．8 排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

1．交换类排序法：（1）冒泡排序法，需要比较的次数（在最坏情况下的时间复

杂度）为2）快速排序法。

2．插入类排序法：（1）简单插入排序法，最坏情况需要（2）

希尔排序法，最坏情况需要

3．选择类排序法：（1）简单选择排序法, 最坏情况需要

择排序的思想为：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。第一个元素需要比较n-1次，第二个元素需要比较n-2次，依次类推，倒数第二个元素只须比较1次即可，所以总的比较次数为：(n-1)+(n-2)+...+2+1=n(n-1)/2。

4．（2）堆排序法，最坏情况需要O(nlog2n)次比较。堆排序的空间复杂度为O(1)；时间复杂度在最好情况为O(nlog2n)，平均情况为O(nlog2n)，最坏情况为

5．在插入选择排序中，若初始数据基本正序，则选用插入排序；若初始数据基

O(n)，而选择排序在初始数据基本反序时时间复杂度为O(n)

6：把n个待排序的元素看成为一个有序表和一个无序

表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中

每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

7．例：设关键码序列（16，9，4，25，15，2，13，18，17，5，8，24），要按关键码值递增的次序排列，采用简单选择排序法，一趟扫描后的结果是[2，9，4，25，15，16，13，18，17，5，8，24]

（简单选择排序法的思想是：以无序表的第一个元素作为比较标准，依次同后面的元素进行比较，如果有一个元素比第一个元素小则记录这个元素的下标，然后以新的最小元素继续往下比较，有更小的元素再记录该下标，再比较......，当对整个数组扫描一趟后就可以等到最小元素的下标，然后与无序表的第一个元素交换位置。本题很明显第一趟扫描结果最小元素是2，与第一个元素交换位置后得到[2，9，4，25，15，16，13，18，17，5，8，24]选项的结果。）

8．简单插入排序的过程是，每一趟将一个待排序的记录，按其关键字的大小插入到已经排序的子文件中适当位置上，直到全部记录插入完成为止。当文件“局部有序”或文件长度较小的情况下，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n^2)降至O(n)。所以最佳内排序方法是它

9．在简单插入排序过程中，当待排序列中记录按关键字非递减有序排序时，所需进行关键字比较的次数最小，为n-1，即记录不需移动；反之，当待排序列中记录按关键字非递增有序排序时，总的比较次数达到最大值(n+2)(n-1)/2。由（A：94，32，40，90，80，46，21，69）、（B：21，32，46，40，80，69，90，94）、（C：32，40，21，46，69，94，90，80）、（D：90，69，80，46，21，32，94，40）四个答案中知（B）选项已经基本有序，需要比较的次数最少。

10．例：在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入

排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较

要插入60时，前6个元素已有序，即为：15，23，38，54，72，96，需从后向前比较到54为止，故要比较3次）

11．插入排序是将待排序的记录插入到前面已排好序的子文件中，即考虑已排好序的子文件。所以是在待排序的元素序列基本有序的前提下，效率最高的排序方法

12．在堆排序和快速排序中，当原始记录接近正序或反序时，则选用堆排序，若

13．快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。只有左子表排好序，右子表还没排好序；左子表的长度在排序过程中可能大于、等于或小于右子表的长度；14．由于选择排序每趟从待排序的记录中选中关键字最小的记录，每个记录都要比较，不考虑已排好序的子文件，因此，关键字比较的次数与记录的初始排列次序无关。快速排序不考虑已排好序的子记录，

15．例：设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，由于堆排序每扫描一趟就排好一个记录，只挑选出其中的前10个最大的元素时，使用堆排序为好。

16．希尔排序的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

17．简单选择排序每趟从n-i+1个记录中选取关键字最小的记录，其时间复杂度为O(n)。

18．例：已知序列，请给出采用插入排序法对该序列作升序排序时的第五趟结果

19．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数

第二章程序设计基础

2．1 程序设计设计方法和风格

如何形成良好的程序设计风格

1、源程序文档化；

2、数据说明的方法；

3、语句的结构；

4、输入和输出。1．程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的

今主导的程序设计风格）。

3．编制程序在选择标识符的名字时应考虑选择含义明确的名字，以正确提示所代表的实体。

4．编制程序在书写功能性注解时应考虑为程序段作注解，以帮助读者理解程序。5．程序设计中语句结构的要求：

（1）在一行内只写一条语句；

（2）程序编写应优先考虑清晰性，程序编写要做到清晰第一、效率第二；（3）在保证程序正确的基础上再要求提高效率；

（4）避免使用临时变量而使程序的可读性下降；避免不必要的转移；

立性。

7．序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，主要描述内容可以包括：程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等。不包括数据的状态8．功能性注释的位置一般嵌在源程序体之中，主要描述其后的语句或者程序做什么。包括数据的状态，语句的功能，程序段的功能，不包括模块的功能

9．源程序的文档化应考虑如下几点：

（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。

（2）程序注释：正确的注释能够帮助读者理解程序，注释一般分为序言性注释

（3）视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。不包括正确的文档格式

10．

个阶段

11．程序文档化应注意以下几点：

（1

理解；

（2

12．输入和输出信息是用户直接关心的。输入、输出方式和格式，应尽可能方便

用户的使用，

13．影响输入输出风格的因素包括通信环境，用户经验，输入/输出设备，不包括数据状态。

2．2 结构化程序设计

1．结构化程序设计方法的四条原则是：

2．结构化程序的基本结构和特点：

（1）顺序结构

序执行的结构，就是按照语句的自然顺序，一条一条地执行程序

（2又称分支结构，包括简单选择和多分支选择结构，可根据条件，

判断应该选择哪一条分支来执行相应的语句序列；

（3又称循环结构，可根据给定条件，判断是否需要重复执行某一

相同程序段。

3．在程序设计中，重复结构对应两类循环语句：

（1

（2）对先执行循环体后判断的称为直到型循环语句。

4．结构化程序设计方法是程序设计的先进方法工具。采用结构化程序设计方法

编写程序，可使程序结构良好、易读（主要强调程序的易读性）、易理解、

提高程序清晰性。

5．结构化程序设计的主要特点是程序语句组成容易识别的模块，每块只有一个入口和一个出口。

6．20世纪70年代提出了“结构化程序设计（structured programming）”的思想和方法。

8．结构化程序设计减少了程序出错的机会、提高了程序的可靠性、保证了程序的质量。

9．结构化程序设计具有方便理解和阅读、便于维护、便于修改等优点。没有移植性好

10．将现实生活中的实体抽象成类是面向对象程序设计方法考虑的问题。

11．这些模块甚至可以由机

器自动生成，从而极大地减轻了编程工作量

2．3 面向对象的程序设计

1．对象是现实世界中一个实际存在的事物，它可以是有形的也可以是无形的，如狗，桌子，飞机是对象，而苹果的颜色不是对象。

2．属性即对象所包含的信息，操作描述了对象执行的功能，

4．类是指具有共同属性、共同方法的对象的集合（即一组具在相同的数据结构

和相同的行为特征的对象的集合）。所以类是对象的抽

象，对象是对应类的

6．面向对象技术具有多态性、封装性和继承性。

7．在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送消息8．继承是面向对象的方法的一个主要特征，但不是任何对象都必须有继承性。9．在面向对象的程序设计中，各个对象之间相对独立，相互依赖性小。

10已有的类可当作基

类来引用，则新类相应地可当作派生类来引用。是类之间共享忏悔和操作的机制。

3．对象具有如下的基本特点：

（1

（2）分类性。可以将具有相同属性和操作的对象抽象成类；

（3）多态性。同一个操作可以是不同对象的行为。

（4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法。

（5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。

第三章软件工程基础

3．1 软件工程基本概念

1．计算机软件是包括程序、数据及相关文档的完整集合。

2．软件是一种逻辑实体（逻辑产品）；

3或工具软件）。

4．软件工程包括3

5．软件工程过程包含4种基本活动：

（1）P--软件规格说明；（2）D--软件开发；（3）C--软件确认；（4）A--软件演进。

6软件产品从提出、实现、使用维护到停止使用退役的过程。

7个阶段:主要活动阶段是：

（问题定义）（1）可行性研究与计划制定；（23

（4）软件实现（编码）；（56）运行和维护。

8．软件工程的

可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。

理。

11．软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。

12．在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是需求分析

13．软件交付使用后，需要不断地进行维护，根据新提出的需求进行必要而且可能的扩充和删除。

14．需求分析主要工作包括4个方面：需求获取、需求分析、编写说明书、需求评审。

15．SRS

3．2 结构化分析方法

2．在结构化分析方法中，用于描述系统中所用到的全部数据和文件的文档称为

处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。

4．Jackson

5．结构化分析的常用工具

它直接支持系统功能建模。

7．数据流图由一些特定的图符构成，包括：加工（转换）、数据流、存储文件

（数据源）、源和潭，不包括控制流。

8．程序流程图（PFD）中的箭头代表的是控制流。

9．常见的需求分析方法有：结构化分析方法和面向对象的分析方法（OOA）。结构化分析方法中，数据流图（DFD）是需求分析最常用的工具。在数据流图（DFD）中，带有名字的箭头表示数据的流向。

11．判定表4部分组成：左上部是基本条件、左下部是基本动作、右上部是条件项、右下部是动作项。

3．3 结构化设计方法

1．合性与内聚性是模块独立性的两个定性标准，其映了模块内各万分之间的联系在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。依据降低耦合提高内聚的原则，

改程序结构

2．软件概要设计的基本任务是：

（1）设计软件系统结构；（2）数据结构及数据库设计；

（3）编写概要设计文档；（4）概要设计文档评审。

模块用一个矩形表示，箭头表示模块间的调用关系。

在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据。

4．变换型系统结构图由输入、中心变换、输出三部分组成。

5．在结构化设计方法中生成的结构图（SD）中，带有箭头的连线表示模块之间的调用关系

6．常见设计工具.N-S的重要特征是：每个构件具有明确的作用域；控制转移必须遵守结构化设计要求；易于确定局部数据和（或）全局数据的作用域；易于表达嵌套关系和模块的层次结构。

7．PAD有5种结构，通常把程序流程图的5种基本控制结构组合或嵌套，可以构成任何复杂的程序流程图。

8．常见设计工具：图形工具（程序流程图，N-S，PAD，HIPO），表格工具（判定表），语言工具（PDL）。

9．程序流程图构成的控制结构的含义如下：

（1）顺序型：几个连续的加工步骤依次排列构成；

（2）选择型：由某个逻辑判断式的取值决定选择两个加工中的一个；

（3）先判断重复型：先判断条件是否成立，成立则执行循环体语句；

（4）后判断重复型：重复执行某些特定的加工，直到控制条件成立；

（5）多分支选择型：列举多种加工情况，根据控制变量的取值，选择执行其中之一。

11提出的又一种用于描述软件详细

设计的图形表示工具

3．4 软件测试

1。（尽可能多地发现软件系统

中的错误和缺陷）

3．从功能角度划分，试软件测试方法：静态测试和动态测试。

4．静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行（人工检测）。

5．动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法（从功能角度划分）。

6是基于计算机的测试，是为了发现错误而执行程序的

过程。

7．白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法

8．黑盒测试：用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。黑盒测试方法也称功能测试或数据驱动测试，是对软件已经实现的功能是否满足需求进行测试和验证

9．软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认

10．单元测试的技术可以采用静态分析和动态测试。

测试为主，辅之以黑盒测试。

11．集成测试所设计的内容包括：

12．检查软件产品是否符合需求定义的过程称为确认测试

13．，

14．白盒测试主要考虑程序内部的逻辑结构，主要用于完成软件内部操作的验证。黑盒测试方法完全不考虑程序的内部结构和内部特征，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。

15．集成测试时要进行软件单元的接口测试、

和非法输入的测试等

16．测试准则：

（1）所有测试都应追溯到需求；

（2）严格执行测试计划，排除测试的随意性；

（3）充分注意测试中的群体现象；

（4）程序员应避免检查自己的程序；

（5）穷举测试不可能；

（6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。

17．系统测试的目的是在真实的系统工作环境下，检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。包括：功能测试、性能测试、操作测试、配置测试、外部接口测试和安全测试等。

18．软件测试是保证软件质量的重要手段，包括需求定义阶段的需求测试、编码

19．代码检查，包括代码审查、代码走查、桌面检查、静态分析等具体方式。

3．5 程序的调试

1．程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。的关键

2．程序调试的基本步骤：

（1

（2）修改设计和代码，以排除错误；

（3）进行回归测试，防止引进新的错误。

3．软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分

析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：

（1）强行排错法；其过程可概括为设置断点、程序暂停、观察程序状态、继续运行程序。

1）通过内存全部打印来排错；2）在程序特定部位设置打印语句-即断点法；3）自动调试工具。

（2）回溯法；

（3）原因排除法。原因排除法是通过演绎和归纳，以及二分法来实现

4．修改错误原则：

（1）在出现错误的地方，很可能有别的错误；

（2）修改错误的一个常见失误是修改了这个错误的征兆或这个错误的表现，而没有修改错误本身；

（3）注意修正一个错误的同时有可能会引入新的错误；

（4）修改错误的过程将迫使人们暂时回到程序设计阶段；

（5）修改源代码程序，不要改变目标代码。

5．为了修改程序中错误，往往采用来实现，但这种做法会引起整体程序质量的下降。

6。

置并改正错误

存在别的错误

9．程序调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性；二是对程序进行修改，排除这个错误。目的是改正错误

第四章数据库设计基础

4．1 数据库系统的基本概念

1．数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是数据库系统阶段。

2．数据库系统由数据库、数据库管理系统、数据库管理员、硬件和软件平台组成。其核心是数据库。

3．数据库技术的根本目的是要解决数据的共享问题

5．数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。

6．数据操纵：为用户使用数据库的数据提供方便，如查询、插入、修改、删除等以及简单的算术运算及统计；

7．数据控制语言：负责数据完整性、安全性（和一致性）的定义与检查以及并发控制、故障恢复等。

8．DBMS提供了以下几个方面的数据控制功能：

（1（2）数据完整性控制。（3）故障恢复。（4）并发控制。

的运行实体。

10．数据库系统的基本特点：

独立性（物理独立性与逻辑独立性）、数据统一管理与控制。

11．数据的独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。

12．数据独立性是指应用程序和数据之间相互独立，即数据结构的修改不会引起

应用程序的修改。物理独立性两个方面。数据的物

理独立性是指数据的存储结构或存取方法的修改不会引起应用程序的修改。基于

13．数据共享是数据库的主要特点之一，它体现在以下几个方面：

（1）多个应用程序可以使用同一个数据文件的记录；

（2）在同一时刻多个用户可存取同一数据；

（3）当应用需求改变或增加时，只需重新选取不同的子集或增加一部分数据便可以满足新的需求。

14．数据库系统的三级模式：其中的外模式/模式映射保证了数据库系统具有较

高的逻辑独立性，模式/

（1称为DBA视图, 也称逻辑模式,模式 , 数据库系统中全局数据

逻辑结构的描述，全体用户公共数据视图；

（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；

（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。在这三层数据库中,只有物理数据库(即内模式)才真正存在，它是数据物理结构

和存储结构的描述。

15．数据库系统的两级映射：

（1）概念模式到内模式的映射；是“模式/内模式”间的映射，定义了数据库的

（2）外模式到概念模式的映射,是“外模式

/模式”间的映射，

数据库管理系统提供的数据控制功能是指在数据库建立、运行和维护时，由DBMS 统一管理、统一控制，以保证数据的安全性、完整性和一致性。

完整性规则是给定的数据模型中数据及其联系所具有的制约和依存规则，用以限定符合数据模型的数据库状态及其状态的变化，以保证数据的正确性、有效性和相容性。

16．DBMS的完整性控制机制包括如下三方面：

（1）定义功能，提供定义完整性约束；

（2）检查功能，检查用户发出的操作请求是否违背了完整性约束的条件；（3）如果发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性。

DDL）和数据操纵语言（DML）组成

4.2 数据模型

1．数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述

)具有描述数据和数据联系两方面的

功能，是记录及其联系的集合。

4．将E-R图转换为关系模型：将实体、实体的属性和实体之间的联系转化为关

系模式

5．例：在数据库逻辑结构的设计中，将E-R模型转换为关系模型应遵循相关原

则。对于三个不同实体集和它们之间的多对多联系m：n：p，最少可转换为

关系模式

6．在E-R图中，实体集用矩形框表示

7．关系表中的每一横行称为一个元组

8．用树形结构来表示实体之间联系的模型称为层次模型。

框架及表的元组组成。一个关系对应一个二维表，但

是一个二维表不一定都能成为一个关系，

10．在关系数据库中，用来表示实体之间联系的是二维表

11．实体集之间的联系包括一对一、一对多、多对多。数据模型包括层次模型、网状模型、关系模型三种。层次模型的基本结构是树形结构，关系模型采用二维表来表示。

12．关系中的数据约束：

（1实体完整性约束：约束关系的主键中属性值不能为空值；

（2

（3）用户定义的完整性约束：它反映了具体应用中数据的语义要求。不要由应用程序担负这一功能。

13．数据模型分为格式化模型与非格式化模型，

4.3关系代数

1．关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算(常用的关系运算)。

2011全国计算机等级考试二级公共基础知识教程

目录二级公共基础知识考纲 (1) 第一章数据结构与算法 (2) 第二章程序设计基础 (19) 第三章软件工程基础 (23) 第四章数据库设计基础 (32) 全国计算机等级考试二级公共基础知识考纲考试内容一、基本数据结构与算法 1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。三、软件工程基础 1.软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3.结构化设计方法，总体设计与详细设计。 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5.程序的调试，静态调试与动态调试。四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统。 2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。考试方式公共基础的考试方式为笔试，与C语言（V isualBASIC、V isual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。第一章数据结构与算法一、内容要点（一）算法 1．算法的基本概念算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。 1）算法的基本特征（1）可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。

全国计算机等级考试二级公共基础知识要点汇总

全国计算机等级考试二级公共基础知识要点汇总第一章数据结构与算法 1.1 算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。指令系统：一个计算机系统能执行的所有指令的集合。基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；

教育公共基础知识总结归纳

2010年教师招聘考试公共基础知识总结归纳填空： 1、制度化教育阶段开始于：近代。 2、各国的学校教育系统基本形成于：19世纪末。 3、现在世界上大多数国家的义务教育年限在：9年或9年以上。 4、“不愤不启，不悱不发”启发教学法的最早倡导者是：孔子。 5、“建国君民，教学为先”提示了教育的重要性和：教育与政治的关系。 6、建国初期，对我国教育理论体系影响较大的苏联教育家是：凯洛夫。 7、狭义的教育主要是指：学校教育。产生于奴隶社会初期 8、古代中国学校教育的主要内容是六艺，它包括：礼、乐、射、御、书、数。 9、在古代印度，能够享受最好教育的是当时的最高种姓：婆罗门。 10、制度化教育或正规教育形成的主要标志是形成近代的：学校教育系统。 11、中国的科举制度开始于：隋唐时期。 12、战国后期，我国出现的具有世界影响的教育文献是：《学记》。 13、在古希腊，最早提出发现法的大教育家是：苏格拉底。 14、古希腊着名思想家柏拉图的教育代表作是：《理想国》。 15、在人类教育史上首次提出“教育遵循自然”学说的教育思想家是古希腊的：亚里士多德。 16、教育学作为一门独立的学科萌芽于：资本主义社会初期夸美纽斯的《大教育学论》。（首先提出普及教育思想的教育家及其着作） 17、强调教育学的心理学和伦理学基础，奠定了科学教育学基础的教育家是：赫尔巴特。 18、资产阶级传统教育学的代表人物是：赫尔巴特。 19、20世纪初实用主义教育学的代表人物和作品是：杜威《民本主义与教育》。 20、主张教师应以学生的发展为目的，以儿童中心主义着称的美国教育家是：杜威。实用主义 21、制度化的教育是指具有：层次结构和年龄分级的教育制度。 22、普通教育主要是指以升学为目标，以（基础科学知识）为主要教学内容的学校教育。 23、职业教育是以生产劳动的知识和技能为主要教学内容，以（就业）为主要目标的学校教育。 24、英国教育家洛克将那种既有贵族气派，又有资产阶级创业精神和才干，还有强健的体魄的人称之为（绅士）。 25、教育区别于其他事物和现象的根本特征，教育的质的规定性是指教育是一种（培养人）的社会活动。 26、规定着一个国家各级各类学校教育的系统，包括各级各类学校的性质、任务、入学条件、企业年限以及它们之间关系的制度中（学校教育制度）。27、西欧中世纪早期的教会学校主要学习神学和七艺，七艺包括（修词、音乐、算术、几何、文法、天文、辨证法） 28、中国近代制度化教育兴起的标志是清朝末年的（“废科举，兴学校”）。 29、中国近代完备的学制系统产生于1902年的“壬寅学制”以及1903年的（“癸卯学制”）。

计算机二级公共基础知识题库及答案

第一章数据结构一、选择题（1）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表【答案】A 【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大．但允许相邻元素值相等)的。选项A正确。（2）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素【答案】C 【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项C。（3）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】D 【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。 (4)算法执行过程中所需要的存储空间称为算法的 A）时间复杂度B）计算工作量C）空间复杂度D）工作空间【答案】c 【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。 (5)下列关于队列的叙述中正确的是 A）在队列中只能插入数据B）在队列中只能删除数据 C）队列是先进先出的线性表D）队列是先进后出的线性表【答案】c 【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。 (6)设有下列二叉树： A

全国计算机二级考试公共基础知识总结

全国计算机二级考试公共基础知识总结第一章数据结构与算法 1.1 算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。指令系统：一个计算机系统能执行的所有指令的集合。基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由

计算机二级公共基础知识(全)

1.1 算法考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2)归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

全国计算机等级考试二级公共基础知识总结

公共基础知识总结第一章数据结构与算法 1.1 算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。指令系统：一个计算机系统能执行的所有指令的集合。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：插入、删除。（详见14--16页） 1．4 栈和队列栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 1．5 线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。

全国计算机等级考试二级公共基础知识

全国计算机等级考试二级公共基础知识复习资料全国计算机等级考试二级公共基础知识复习资料第一章数据结构与算法 1.1 算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。指令系统：一个计算机系统能执行的所有指令的集合。基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

计算机二级公共基础知识高频考点归纳总结

第一章数据结构与算法算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的,此顺序将在有限的次数下终止。特征包括：（1）可行性;（2)确定性(3）有穷性（4）拥有足够的情报。３、算法的基本要素:一是对数据对象的运算和操作；二是算法的控制结构。４、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。６、算法的控制结构：顺序结构、选择结构、循环结构。 7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。数据结构的基本基本概念 1、数据结构研究的三个方面: (1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; （2）在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构;（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。２、数据的逻辑结构包含:(1）表示数据元素的信息;(2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。３、线性结构条件：(1）有且只有一个根结点;(２）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。线性表及其顺序存储结构１、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1）且只有一个根结点ａ1，它无前件；(2)有且只有一个终端结点an，它无后件; （3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当ｎ=0时，称为空表。 3、线性表的顺序存储结构具有以下两个基本特点：(１）线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO)或“后进先出”(LＩFO）组织数据,栈具有记忆作用。用ｔop表示栈顶位置，用ｂottoｍ表示栈底。 2、栈的基本运算：(1）插入元素称为入栈运算；（2)删除元素称为退栈运算;（３）读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端（队尾）进入插入,而在另一端(队头）进行删除的线性表。Ｒear指针指向队尾,frｏnt 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。线性链表

全国计算机等级考试二级公共基础知识考纲

全国计算机等级考试二级公共基础知识考纲考试内容一、基本数据结构与算法 1、算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2、数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3、线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5、线性单链表、双向链表与循环链表的结构及其基本运算。 6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7、顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。二、程序设计基础 1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。三、软件工程基础 1、软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3、结构化设计方法，总体设计与详细设计。 4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5、程序的调试，静态调试与动态调试。四、数据库设计基础 1、数据库的基本概念：数据库，数据库管理系统，数据库系统。 2、数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4、数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。考试方式：公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。第一章数据结构与算法一、内容要点（一）算法 1．算法的基本概念：算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且

教育公共基础知识点总结.

教育公共基础知识点总结 1、教育学的研究对象是学校教育现象。 2、教育现象包括学校教育、家庭教育、社会教育。 3、教育学是一种综合性的学科,既是理论学科也是应用学科。 4、完备的教师知识结构是学科基础知识、教育学科基础知识和广泛的文化科学知识。 5、孔子对我国教育的贡献有三个方面:创立私学、创立儒学、删订六经。 6、福禄贝尔被称为“幼儿园之父”。 7、杜威是“进步主义教育学派”的代表。 8、历史研究法的工作是:史料真伪的鉴别,鉴别包括:外部考证和内部考证。 9、调查研究法可分为确定课题、搜集资料、做出结论。 10、调查研究法包括:调查、研究、访问。 11、在个体早期生命中有一个比较短暂的时期,在此时期,个体对某种刺激特别敏感,过了这一时期,同样的刺激对之影响很小或没有影响。心理学者把此时期称之为关键期。 12、智力测验中的一个重要概念是智商,简称IQ=(智力年龄MA÷实际年龄 CA×100。 13、我国教育心理学家主张学生的学习分为知识的学习、技能的学习和行为规范的学习。 14、桑代克认为尝试——错误学习的基本规律有:效果律、练习律

和准备律。 15、心理辅导的一般目标可归纳为两个方面,第一是学会调适,第二是寻求发展。 16、教师合理的知识结构应包括扎实的事业知识、广泛的文化科学知识、娴熟的教育科学知识等方面;教师的能力结构主要有组织管理人员能力、语言表达能力、教育机智等方面。 17、教师良好的心理素质至少应包括良好的意志品质,稳定的情绪,良好的性格特征,清晰的自我意识等方面。 18、我国的师生关系是以培养全面发展的新人为根本目标的。其明显的特征是教育民主,尊师爱生,教学相长。 19、师生关系与一般社会关系的最大不同就在于它是因教育_而生,又为教育而存,其最大的功能就是教育功能。 20、一般来说,在师生关系中有几种典型的模式,它们分别是放任型,专制型,民主型。 21、17世纪捷克教育家夸美纽斯说:教师是太阳底下最光荣的职业。 22、俄国教育家乌伸斯基说:教师职业是历史上最伟大的事业。 23、“古之学者必有师”出自韩愈的师说《师说》。 24、前苏联教育理论家加里宁说:"教师是人类灵魂的工程师"。 25、1985年开始我国确定每年的9月10日为教师节。 26、文化对教育的制约作用表现在:教育思想和教育观点、教育内容。 27、教育通过对文化的传递、选择、融合、创造来促进文化的发展。

2017计算机二级公共基础知识完整

第一章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。详细重点学习知识点： 1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义 3．栈的定义及其运算、线性链表的存储方式 4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5．二分查找法 6．冒泡排序法 1.1 算法考点1 算法的基本概念考试链接：考点1在笔试考试中考核的几率为30% ，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：

（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。考点2 算法复杂度考试链接：考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70% ，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法" 运行工作量" 的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。即算法的工作量=f（n） 2.算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存

二级公共基础知识分类模拟题43

二级公共基础知识分类模拟题43 单项选择题 1、下列叙述中正确的是______。 A．所谓算法就是计算方法 B．程序可以作为算法的一种描述方法 C．算法设计只需考虑得到计算结果 D．算法设计可以忽略算法的运算时间 2、下列叙述中正确的是______。 A．算法的复杂度包括时间复杂度与空间复杂度 B．算法的复杂度是指算法控制结构的复杂程度 C．算法的复杂度是指算法程序中指令的数量 D．算法的复杂度是指算法所处理的数据量 3、下列叙述中正确的是______。 A．算法的时间复杂度与计算机的运行速度有关 B．算法的时间复杂度与运行算法时特定的输入有关 C．算法的时间复杂度与算法程序中的语句条数成正比 D．算法的时间复杂度与算法程序编制者的水平有关 4、下列叙述中正确的是______。 A．非线性结构可以为空 B．只有一个根结点和一个叶子结点的必定是线性结构 C．只有一个根结点的必定是线性结构或二叉树 D．没有根结点的一定是非线性结构 5、设数据结构B=(D，R)，其中 D={a,b,c,d,e,f} R={(f,a),(d,b),(e,d),(c,e),(a,c)} 该数据结构为______。 A．线性结构 B．循环队列 C．循环链表 D．非线性结构 6、下列叙述中正确的是______。 A．矩阵是非线性结构 B．数组是长度固定的线性表 C．对线性表只能作插入与删除运算 D．线性表中各元素的数据类型可以不同 7、在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。 A．不同，但元素的存储顺序与逻辑顺序一致 B．不同，且其元素的存储顺序可以与逻辑顺序不一致 C．相同，元素的存储顺序与逻辑顺序一致 D．相同，但其元素的存储顺序可以与逻辑顺序不一致 8、下列叙述中正确的是______。 A．能采用顺序存储的必定是线性结构 B．所有的线性结构都可以采用顺序存储结构 C．具有两个以上指针的链表必定是非线性结构 D．循环队列是队列的链式存储结构 9、下列叙述中正确的是______。 A．在栈中，栈顶指针的动态变化决定栈中元素的个数

计算机二级公共基础知识要点总结

计算机二级公共基础知识要点总结 1.栈按先进后出的原则组织数据，所以入栈最早的最后出栈，而队列是先进先出的线性表。 2.循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的线性表。在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。 3.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性表，在最坏的情况下二分法查找只需要比较log2n次，而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间。顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流，即沿箭头方向传送数据的通道一般在旁边标注数据流名。程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中，需求分析阶段可以使用的工具有数据流图DFD图，数据字典DD，判定树与判定表。 7.“对象”有如下一些基本特点：标识唯一性，分类型，多态性，封装性，模块独立性好。 8.数据管理发展至今已经历了三个阶段：人工管理阶段，文件系统阶段和数据库系统阶段。其中最后一个阶段结构简单，使用方便，逻辑性强，物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。 10.内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言，机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活，直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是：网络接口层，网络层，传输层和应用层。 14.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个。例如:某二叉树有五个度为2的结点，则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次，而堆排序在最坏的情况下需要比较的次数是nlog2n，即在排序方法中，最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为：应用软件，系统软件和支撑软件（或工具软件）。 19.软件测试的目的是为了发现错误而执行程序的过程，并不涉及改正错误。程序调试的基本步骤有：错误定位，修改设计和代码，以排除错误进行回归测试，防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有：所有测试都应追溯到需求，严格执行测试计划，排除测试的随意性，充分注意测试中的群集现象，程序员应避免检查自己的程序，穷举测试不可能，

全国计算机二级考试公共基础知识

全国计算机二级考试公共基础知识（全） (2010-01-13 17:13:54) 转载标签：it 分类：天下快报(热点聚焦) 第一章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。详细重点学习知识点： 1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义 3．栈的定义及其运算、线性链表的存储方式 4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5．二分查找法 6．冒泡排序法 1.1算法考点1 算法的基本概念考试链接：考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。考点2 算法复杂度考试链接：考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。即算法的工作量=f（n） 2.算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。疑难解答：算法的工作量用什么来计算？算法的工作量用算法所执行的基本运算次数来计算，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f（n），其中n 是问题的规模。 1.2数据结构的基本概念考点3 数据结构的定义考试链接：考点3在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为识记内容，读者还应该识记数据的逻辑结构和存储结构的概念。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

文档之家

全国计算机等级考试二级公共基础知识总结

2011全国计算机等级考试二级公共基础知识教程

全国计算机等级考试二级公共基础知识要点汇总

教育公共基础知识总结归纳

计算机二级公共基础知识题库及答案

全国计算机二级考试公共基础知识总结

最新《公共基础知识》重点归纳

计算机二级公共基础知识(全)

全国计算机等级考试二级公共基础知识总结

全国计算机等级考试二级公共基础知识

计算机二级公共基础知识高频考点归纳总结

全国计算机等级考试二级公共基础知识考纲

教育公共基础知识点总结.

2017计算机二级公共基础知识完整

二级公共基础知识分类模拟题43

计算机二级公共基础知识要点总结

全国计算机二级考试公共基础知识

最新《公共基础知识》重点归纳

文档之家

全国计算机等级考试二级公共基础知识总结

2011全国计算机等级考试二级公共基础知识教程

全国计算机等级考试二级公共基础知识要点汇总

教育公共基础知识总结归纳

计算机二级公共基础知识题库及答案

全国计算机二级考试公共基础知识总结

最新《公共基础知识》重点归纳

计算机二级公共基础知识(全)

全国计算机等级考试二级公共基础知识总结

全国计算机等级考试二级公共基础知识

计算机二级公共基础知识高频考点归纳总结

全国计算机等级考试二级公共基础知识考纲

教育公共基础 知识点总结.

2017计算机二级公共基础知识完整

二级公共基础知识分类模拟题43

计算机二级公共基础知识要点总结

全国计算机二级考试公共基础知识

最新《公共基础知识》重点归纳

教育公共基础知识点总结.