全国计算机二级公共基础知识--复习

1、-1全国计算机二级公共基础知识一、数据结构与算法数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构用来反映一个数据的内部构成，即一个数据由哪些成分构成、以什数据结构有逻辑上的数据结构。么方式构成、呈现什么样的结构和物理上的数据结构之分。逻辑上的数据结构反映数据之间的逻辑关系，而物理上的数据结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式。算法是解题的步骤， 是指令的有限序列。 它们规定了解决某一特定类型问题的一系列运算， 是对解题方案的准确与完整的描述。 一个问题的解决方案要以算法为基础。1.1 概念介绍 算法的时间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量。

2、算法的工作量用算法所执行的基本运算次数来度量， 而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)其中 n 是问题的规模。例如，两个 n 阶矩阵相乘所需要的基本运算(即两个实数的乘法 )次数为 333 。，也就是时间复杂度为，即计算工作量为 n n n-2 算法的空间复杂度：算法的空间复杂度一般是指执行这个算法所需要的内存空间。数据的逻辑结构数据元素相互之间的关系，称为结构。数据的逻辑结构： 是指反映数据元素之间逻辑关系的数据结构。数据的存储结构数据的存储结构： 是数据的逻辑结构在计算机存储空间中的存放形式。 也称数据的物理结构。各数据元素在计算机存储空间中的位置关系与它们的

3、逻辑关系不一定是相同的。 同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构。数据的顺序存储方式：是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里。 也就是将所有存储结点相继存入在一个连续相邻的存储区里。数据的链式存储方式：是在存储每个结点信息的同时，增加一个指针来表示结点间的逻辑关系。 该方式不要求逻辑上相邻结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。因此，链式存储结构中的每数据域 一部分用于存储结点本身的信息，称为个结点都由两部分组成： ；另一指针域 的存储单元地址，称为 )(部分用于存储该结点的后继结点或前驱结点 。指针域可以包含一个或多个指针

4、， 这由结点之间的关系所决定。线性结构和非线性结构如果在一个线性结构中， 一个数据元素都没有，则称该数据结构为空数据结构。线性结构的逻辑特征：在一个非空的数据结构中，除第一个数据元素只有一个后继没有前驱、 最后一个数据元素只有一个前驱没有后继外， 其他的-3线性表 每一个数据元素仅有一个前驱和一个后继。线性结构也称为 。前驱、直接相邻的后一注：某个元素直接相邻的前一个元素称为此元素的后继 。个元素称为此元素的非线性结构的逻辑特征：在一个非空的数据结构中，某数据元素可能有多于一个前驱或后继。如树型结构等。习题：（一）选择题(单选)1. 算法的时间复杂度是指（D）A) 算法的执行时间算法所处理的数

5、据量B)算法程序中的语句或指令条数C)D) 算法在执行过程中所需要的基本运算次数1.2 线性表线性表是由同一类型的数据元素构成的一种线性的数据结构。是一种最基本、最常用的数据结构。线性表常用的存储方式有两种： 顺序存储方式和链接存储方式。线性表的数学定义：L=(a,a,a , ? ,a) n213说明：线性表是具有相同类型的 n(n 0)个数据元素组成的有限序列。L ：为表的名称。a (i=1,2, ?：,n) 为表的元素，也称为线性表中的一个结点。 它可以是一个数、ia 是一个字符、一个字符串，也可以是一条记录，还可以是复杂的数据对象。 1a 的前驱、 a 是 a 的后继，a 是 a 的前驱

6、、 a 是a 的后继，, ，依次类推。 122 2323-4n：为线性表的长度 (元素个数 )，当 n=0 时称线性表为空表。线性表的特点：在非空的线性表中： 存在唯一的一个 “第一个元素”(根结点 )。存在唯一的一个“最后一个元素” (终端结点 )。除第一个元素外，其他的元素均有唯一的前驱。除最后一个元素外，其他的元素均有唯一的后继。1.3 栈和队列栈和队列本质上也是线性表，只是它们的操作受到了限制。栈栈是限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶(top) ，表头称为栈底(bottom) 。栈这种数据结构， 类似于子弹夹， 底端是封闭的，最后压入的子弹总是最先被弹出， 最先压入的

7、子弹只能最后被弹出。栈顶元素总是最后被插入的元素， 从而也是最先能被删除的元素； 栈底元素总是最先被插入的元素， 从而也是最后能被删除的元素。 即栈是按照“先进后出”栈也被称为“先进后出”表或“后进先出”的原则组织数据的。因此，或“后进先出”表。由此可以看出，栈具有记忆作用。队列队列是指只允许在表的一端插入元素、在另一端删除元素的线性表。允许插入的一端称为队尾(rear) ，允许删除的一端称为队头(front)。在队列这种数据结构中，最先插入的元素将最先能够被删除， 反之最后插入的元队列又称为“先进先出”或“后进后素将最后才能被删除。因此，出”的线性表。-51.4 树和二叉树树树形结构是数据结

8、构中一种很重要的非线性结构。在树形结构中，所有数据元素之间的关系具有明显的层次特性。树形结构很像自然界中的树，像一棵倒长的树。在现实生活中，能用树形结构表示的例子很多。参见下面的图形：树形结构的基本特征及基本术语：以下图为例：-6树的根：在树形结构中，没有前驱的结点只有一个，称为树的根结点，简称为树的根。如：上图中的“R”。父结点：在树形结构中，每一个结点 (除了树的根结点 )只有一个前驱，称为父结点。如：上图中的“ R”是 K、 P、Q、D 的父结点； “ N”是 X 、 Y 的父结点。子结点：在树形结构中，每个结点可以有多个后继，称为该结点的子结点。如：上图中的K 、P、Q、D 是“ R”

9、的子结点；X 、Y 是“ N”的子结点。叶子结点：在树形结构中，没有后继的结点称为叶子结点，也称终端结点。如：上图中的C、M、F、E、X、G、S、L、Z、A 均为叶子结点。结点的度：在树形结构中， 一个结点所拥有的后继个数称为该结点的度。如：上图中根结点 R 的度是 4；结点 T 的度是 3；结点 P、 Q、D、O、Y 、W 的度都为1。叶子结点的度为0。-7树的度：在树形结构中，所有结点中的最大的度称为树的度。 如：上图中树的度为4，因为结点R 的度最大，是4。树的深度：在树形结构中，树的最大层数称为树的深度 (或高度 )。如：上图中树的深度是 5。说明：树形结构具有明显的层次关系，即树是一

10、种层次结构。 在树形结构中一般按如下原则分层：1) 根结点在第 1 层。2) 其余结点的层数等于其父结点的层数加1。子树：在树形结中， 以某结点的一个子结点为根构成的树称为该结点的一棵子树。如：上图中，结点 R 有 4 棵子树，它们分别以 K 、P、 Q、D 为根结点；结点 P有 1 棵子树，其根结点为 N；结点 T 有 3 棵子树，它们分别以 W、Z、 A 为根结点。在树形结构中，子树间互不相交，叶子结点没有子树。森林：森林是 M(M 0)棵互不相交的树的集合。 删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。二叉树(1) 二叉树的特点 非空二叉树只有一个根结点。

11、 二叉树中的每个结点，最多有两棵子树，分另称为该结点的 左子树 与右子树。当一个结点即没有左子树也没有右子树时，该结点就是叶子结点。在下面的图中，左面是只有根结点的二叉树，右面是深度为 4 的二叉树：-8(2) 满二叉树与完全二叉树1) 满二叉树：满二叉树是指除最后一层外， 每一层上的所有结点都有两个子结点。就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的i-1 个结点。 1)2k -1(k 的满二叉树有k第 k 层上有 2 (k 1)个结点，且深度为的满二叉树：、 4 在下图中分别是深度为 2、 3满二叉树中不存在度数为 1 的结点，每个分支结点均有两棵深度相同的子树，且叶

12、子结点都在最下一层。2) 完全二叉树：若一棵二叉树最多只有最下面的两层上结点的度数可以小于 2，并且最下一层上的所有结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。-9在下图的 4 棵二叉树中，分别是深度为 3 和 4 的完全二叉树：满二叉树是完全二叉树， 完全二叉树不一定是满二叉树。在满二叉树的最下一层上， 从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。在完全二叉树中， 若某个结点没有左子结点，则它一定没有右子结点， 即该结点必是叶子结点。(3) 二叉树的性质1(注意：有些资料中规定根结点的层数为0)。假设定义根结点的层数为2i-1(i 1)：在二叉树的第 1

13、 层上，最多有i 个结点。性质2k-1(k 1) 个结点。 2：深度为 k 的二叉树最多有性质性质 3：在任意二叉树中，若度为 0 的结点 (即叶子结点 )的个数为 n，度为 2 0n0= n2+1 ，则：的结点的个数为 n 2(对于完全二叉树还有如下属性)log2n+1 。注 个结点的完全二叉树， 其深度为n 性质 4：具有 nlog ：2表示取 logn 的整数部分。性质 5：如果将一棵有 n 个结点的完全二叉树自顶 2向下、同一层自左向右连续给结点编号 1、2、3、, 、n，则对于任意结点 i(1 i n) 有如下结论：1) 如果 i=1 ，此结点为根结点，无前驱 (即无父结点 )；In

14、t(i/2) 。 ，则该结点的父结点编号为如果i1 ，都也可表示成 i/2-10表示取整数。2) 如果 2in ，则结点 i 无左子结点，显然也没有右子结点，是叶子结点。 2i 的结点。n，则结点i 的左子结点是编号为如果2i3) 如果 2i+1n ，则结点 i 无右子结点。2i+1 。的右子结点的编号为i2i+1 n，则结点如果二叉树的遍历(4)二叉树的遍历就是遵从某种次序， 访问二叉树中的所有结点，使得每个结点仅被访问一次。一棵非空二叉树是由根结点、 左子树和右子树三部分组成。 因此遍历一棵非空二叉树的问题就可以分解为三项“子任条” ： 访问根结点(假设用D 表示 )。 遍历左子树(假设用

15、L 表示 )。 遍历右子树(假设用R 表示 )。在遍历二叉树的过程中， 一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可分为三种：前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。以下图中的二叉树为例：前序遍历(DLR)：首先访问根结点， 然后遍历左子树， 最后遍历右子树。 在遍历左、右子树时，-11仍然先访问子树的根结点，然后遍历其左子树，最后遍历其右子树。即，前序遍历是指访问所有的根结点 (包括子树的根结点 )都在遍历其左、右子树之前。前序遍历的操作：若二叉树为空，则结束反返回。否则： 访问根结点 前序遍历左子树 前序遍历右子树如，对上

16、图中的二叉树进行前序遍历的结果是：FCADBEGHP中序遍历(LDR)：首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历其左子树，然后访问子树的根结点，最后遍历其右子树。即，中序遍历是指访问所有的根结点 (包括子树的根结点 )都在遍历其左子树之后、在遍历其右子树之前。中序遍历的操作：若二叉树为空，则结束反返回。否则： 中序遍历左子树 访问根结点 中序遍历右子树如，对上图中的二叉树进行中序遍历的结果是：ACBDFEHGP后序遍历(LRD)：首先遍历左子树， 然后遍历右子树， 最后访问根结点。在遍历左、右子树时，仍然先遍历其左子树，然后遍历其右子树，最后访问子树的根结

17、点。即，后序遍历是指访问所有的根结点 (包括子树的根结点 )都在遍历其左、右子树之后。后序遍历的操作：若二叉树为空，则结束反返回。否则： 后序遍历左子树 后序遍历右子树-12 访问根结点如，对上图中的二叉树进行后序遍历的结果是：ABDCHPGEF1.5 查找查找又称检索。 查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构， 应采用不同的查找方法。顺序查找顺序查找又称顺序搜索或线性查找。 顺序查找一般是指在线性表中查找指定的元素。顺序查找的基本思想：在 n 个结点组成的线性表中， 从线性表的一端开始， 依次将线性表中的元素与被查元素进行比较，若相等则表示找到， 即查找成

18、功； 若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素，即查找失败。在顺序查找中，查找成功时最多需要比较 n 次、最少比较 1 次、平均比较次数约为表长的一半。查找失败时比较n+1次。顺序查找的时间复杂度为O(n) 。) 和链式存储结构的线性表 (有序对于无序表 (即表中的元素的排列是无序的的和无序的)，只能用顺序查找。顺序查找的优点：算法简单而适用范围广。对表中元素的排列次序无要求，既可以是按关键字排列的有序表，也可以是无序表；对表的存储结构也无任何要求，既适用于顺序存储的顺序表，也适用于链接存储的链表。顺序查找的缺点：查找效率低， 平均查找长度较大。 当

19、n 很大时不宜采用顺序查找。-13二分查找二分查找又称折半查找。 它是一种查找效率较高的查找方法。 该方法只适用于顺序存储结构的有序表。 通常是指有序表中的元素按值升序排列 (非递减有序排列 )。二分查找不能用于链式存储结构的线性表。二分查找的基本思想：参见“ C 语言程序设计”或“ VB 程序设计”课件的相应内容动画。对于长度为 n 的有序线性表，查找成功时最多需要比较log2(n+1) 次、最少比较 1 次、平均查找长度近似 log2n 。当查找失败时，比较 log2n 或 log2(n+1)次。不管二分查找成功与否， 其时间复杂度均为。 O(log2n)二分查找的最坏性能和平均性能相当接

20、近。1.6 排序排序就是将文件中的记录进行整理，使之按照关键字进行递增或递减的顺序排列起来，成为一个有序序列的过程。在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表， 在程序设计语言中就是一维数组。这里的排序算法，都是针对升序排序。交换排序交换排序是两两比较待排序记录的关键字，若发现两个记录关键字的次序相反时即进行交换，直到没有反序的记录为止。下面介绍两种常用的交换排序。(1) 冒泡排序冒泡排序的基本思想：参见“ C 语言程序设计”或“ VB 程序设计”课件的-14相应内容动画。对于长度为 n 的线性表，在最坏情况下， 冒泡排序需要经过 n/2 遍的扫描，比较次数为n(n -1

21、)/2 。冒泡排序算法的平均时间复杂度为 O(n2) ，空间复杂度为O(1) 。(2) 快速排序快速排序的基本思想：参见下图：从线性表中选取一个元素， 设为 T，将线性表后面小于 T 的元素移到前面， 将线性表前面大于 T 的元素移到后面，结果就把线性表分成了两部分 (称为两个子表 )，T 插入到其分界线的位置处， 这个过程称为线性表的分割。通过对线性表的一次分割， 就以 T 为分界线， 将线性表分成了前后两个子表， 且前面子表中的所有元素均不大于 T，后面子表中的所有元素均不小于 T。如果对分割后的各子表再按上述原则进行分割，并且这种分割过程可以一直做下去，随着对各子表不断地进行分割，划分出

22、的子表会越来越多 (一次只能对一个子表进行再分割处理 )，直到所有子表中的元素都排好序为止，则此时的线性表就变成了有序表。对于长度为n 的线性表：-15在最坏情况下， 快速排序比较次数为 n(n -1)/2 。算法的时间复杂度为 O(n2) ，空间复杂度为O(n) 。在最好情况下， 快速排序算法的时间复杂度为。 O(log2n) O(nlog2n) ，空间复杂度为快速排序算法的平均时间复杂度是 O(nlog2n) ，平均比较次数不大于 (n+1)log2n插入排序插入排序是每次将一个待排序的记录按其关键字大小， 插入到前面已排好的序列中的适当位置，直到全部记录插入为止。(1) 直接插入排序快速

23、排序的基本思想：请查看相关资料。对于长度为n 的线性表：在最坏情况下， 直接插入排序比较次数为 n(n -1)/2 。算法的时间复杂度为 。O(n2)(2) 希尔排序希尔排序的基本思想：请查看相关资料。对于长度为n 的线性表：在最坏情况下希尔排序比较次数为 O(n1.5) 。选择排序选择排序的基本思想是：每一遍在n-i+1(i=1,2, , ,n -1)个待排序记录中选取关键字最小的记录作为有序序列中第 i 个记录，直到全部记录排完为止。(1) 直接选择排序选择排序的基本思想：参见“ C 语言程序设计”或“ VB 程序设计”课件的-16相应内容动画。在最坏情况下， 直接选择排序比较次数为 n(

24、n -1)/2 。(2) 堆排序希尔排序的基本思想：请查看相关资料。在最坏情况下， 堆排序比较次数为 O(nlog2n) 。习题：（一）选择题(单选)1.下列叙述中正确的是( D )A ）栈是“先进先出”的线性表）队列是“先进后出”的线性表 B）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 D .2( A )下列关于栈的叙述中正确的是 栈顶元素最先被删除 B)A) 栈顶元素最后才能被删除 D)C) 以上三种说法都不对栈底元素永远不能被删除3. 下列叙述中正确的是( B )A) 有一个以上根结点的数据结构不一定是非线性结构只有一个根结点的数据结构不一定是线性结构B)循环链表是非线性结

25、构C)D) 双向链表是非线性结构4.支持子程序调用的数据结构是( A )二叉树 D)B)树 C) 队列栈 A)某二叉树有5 个度为2 的结点，则该二叉树中的叶子结点数是.5( C )4）C） 6D ）A ）10B 8提示：在任意二叉树中，若度为0 的结点(即叶子结点)的个数为 n0 ，度为2 的结点的个数为)=5+1=6 ，则：叶子结点数n0= n2+1即n0(n27 个结点，其中叶子结点只有1 个，则该二叉树的深度为(假设根结点在第某二叉树共有6.)(D) 一层-17C) 6D)7 B) 4A) 3下列排序方法中，最坏情况下比较次数最少的是7.(D)D ）堆排序 ）简单选择排序BA ）冒泡排

26、序 ）直接插入排序 C8. 下列叙述中正确的是( A )A) 对长度为 n 的有序链表进行查找，最坏的情况下需要的比较次数为 nn/2 ）B)对长度为 n 的有序链表进行对分查找，最坏的情况下需要的比较次数为（( log n) 的有序链表进行对分查找，最坏的情况下需要的比较次数为 C)对长度为 n2( nlogn) 的有序链表进行对分查找，最坏的情况下需要的比较次数为对长度为n D)2(二) 填空题1. 假设用一个长度为50 的数组（数组元素的下标从0 到49 ）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top 指向栈顶元素，如果bottom=49,top=30(数组下标)，

27、则个元素。栈中具有_20 答案：2. 一个队列的初始状态为空。 现将元素 一次入队，然 1 、2、 3 F、 5、 4、 EA、B、 C、 D、后再一次退队，则元素退队的顺序为。_答案：A、 B、 C、 D、E、 F、 5、 4、 3、2、 13. 设某循环队列的容量为50 ，如果头指针 front=45( 指向队头元素的前一个位置) ，尾指针rear=10（指向队尾元素），则该循环队列中共有_ 个元素。15 答案：设二叉树如下： 4.ABCDFEGH对该二叉树进行后序遍历的结果为_。答案：E、D、 B、 G、H、 F、 C、 A-18一棵二叉树的中序遍历结果为 DBEAFC ，前序遍历结果为

28、 ABDECF ，则后序遍 5. 历结果为_ 。答案：DEBFCA6. 有序线性表能进行二分查找的前提是该线性表必须是_ 存储。答案：顺序二、软件工程基础计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。软件由两部分组成： 一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。软件的分类软件按功能可以分为：应用软件、系统软件、支撑软件 (或工具软件 )。应用软件： 是为解决特定领域的应用而开发的软件。系统软件：是计算机管理自身资源， 提高计算机使用效率并为计算机用户提供各种服务的软件。支撑软件：是介于系统软件和应用软件之

29、间，协助用户开发软件的工具性软件。软件生命周期通常将软件产品从提出、 实现、使用维护到停止使用退役的过程称为软件生命周期。参见下图：-19结构化分析方法结构化分析的常用工具：是描述数据处理过程的工具，是需求理解的逻辑模型的图数据流图 (DFD)形表示，它直接支持系统的功能建模。：是结构化分析方法的核心。数据字典(DD)判定树判定表-20结构化设计方法常见的过程设计工具：图形工具：程序流程图，N-S 图， PAD 图(问题分析图 )， HIPO表格工具：判定表。语言工具：PDL(伪码 )软件设计的基本原理1) 抽象：是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。2) 模块化：

30、是指把一个待开发的软件分解成若干小的简单的部分。如高级语言中的过程、函数、子程序等。每个模块可以完成一个特定的子功能，各个模块可以按一定的方法组装起来成为一个整体，从而实现整个系统的功能。3) 信息隐蔽：是指在一个模块内包含的信息 (过程或数据 )，对于不需要这些信息的其他模块来说是不能访问的。4) 模块独立性：是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准 。内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。 内聚是从功能角度来度量模块内的联系。内聚性是

31、信息隐蔽和局部化概念的自然扩展。 一个模块的内聚性越强则该模块的模块独立性越强。作为软件结构设计的设计原则， 要求每一个模块的内部都具有很强的内聚性， 它的各个组成部分彼此都密切相关。耦合性：耦合性是模块间相互连接的紧密程度的度量。一个模块与其他模块的耦合性越强则该模块的模块独立性越弱。原则上讲，模块化设计总是希望模块间的耦合表现为非直接耦合方式。但是，由于问题所固-21有的复杂性和结构化设计的原则， 非直接耦合往往是不存在的。耦合性与内聚性是模块独立性的两个定性标准，耦合性与内聚性是相互联系的。在程序结构中，各模块的内聚性越强， 则耦合性越弱。 一般优秀的软件设计，应尽量做到高内聚， 低耦合，即减弱模块之间的耦合性和提高模块内的的内聚性，有利于提高模块的独立性。软件测试软件测试是在软件投入运行前对软件需求、设计、编码的最后审核。 软件测试是为了发现错误而执行程序的过程。 软件测试应当制定明确的测试计划并按计划执行。软件测试的目的：是发现错误。软件测试方法和技术： 若从是否需要执行被测软件的角度， 可以分为静态测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。静态测试：包括代码检查、静态结构分析、代码质量度量等。静态测试不实际运行软件，主要通过人工进行。动态测试：是基于计算机的测试，是为了发现错