2022年全国计算机二级公共基础知识--复习 2.pdf

《2022年全国计算机二级公共基础知识--复习 2.pdf》由会员分享，可在线阅读，更多相关《2022年全国计算机二级公共基础知识--复习 2.pdf（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量 =f(n)其中 n 是问题的规模。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 46 页 - - - - - - - - - 2 / 46 例如，两个n 阶矩阵相乘所需要的基本运算( 即两个实数的乘法 ) 次数为 n3，即计算工作量为n3，也就是时间复杂度为n3。 算法的空间复杂度：算法的空间复杂度一般是指执行这个算法所需要的内存空间。数据的逻辑结构数据元素相互

3、之间的关系，称为结构。数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。数据的存储结构数据的存储结构：是数据的逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构。各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。 同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构。数据的顺序存储方式： 是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里。也就是将所有存储结点相继存入在一个连续相邻的存储区里。数据的链式存储方式： 是在存储每个结点信息的同时，增加一个指针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结名师资料总结 - - -精品资料欢迎下载 -

4、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 46 页 - - - - - - - - - 3 / 46 点在物理位置上亦相邻， 结点间的逻辑关系是由附加的指针字段表示的。因此，链式存储结构中的每个结点都由两部分组成：一部分用于存储结点本身的信息，称为数据域； 另一部分用于存储该结点的后继结点 ( 或前驱结点 ) 的存储单元地址，称为指针域。指针域可以包含一个或多个指针，这由结点之间的关系所决定。线性结构和非线性结构如果在一个线性结构中，一个数据元素都没有，则称该数据结构为空数据结构。线性结构的逻辑特征： 在一个

5、非空的数据结构中，除第一个数据元素只有一个后继没有前驱、最后一个数据元素只有一个前驱没有后继外，其他的每一个数据元素仅有一个前驱和一个后继。线性结构也称为线性表。注：某个元素直接相邻的前一个元素称为此元素的前驱、直接相邻的后一个元素称为此元素的后继。非线性结构的逻辑特征：在一个非空的数据结构中，某数据元素可能有多于一个前驱或后继。如树型结构等。习题：（一）选择题 ( 单选)1. 算法的时间复杂度是指（D）A) 算法的执行时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共

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

7、1是 a2的前驱、 a2是 a1的后继， a2是 a3的前驱、 a3是 a2的后继，依次类推。n：为线性表的长度 ( 元素个数 ) ，当 n=0 时称线性表为空表。线性表的特点 ：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 46 页 - - - - - - - - - 5 / 46 在非空的线性表中： 存在唯一的一个 “第一个元素”( 根结点 ) 。存在唯一的一个 “最后一个元素” ( 终端结点 ) 。 除第一个元素外，其他的元素均有唯一的前驱。除最后一个元素外， 其

8、他的元素均有唯一的后继。1.3 栈和队列栈和队列本质上也是线性表，只是它们的操作受到了限制。1.3.1栈栈是限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶 (top) ，表头称为栈底 (bottom) 。栈这种数据结构，类似于子弹夹，底端是封闭的，最后压入的子弹总是最先被弹出，最先压入的子弹只能最后被弹出。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后能被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。1.3.2队列队列是指只允许在表的一端

9、插入元素、在另一端删除元素的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队头名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 46 页 - - - - - - - - - 6 / 46 (front)。在队列这种数据结构中，最先插入的元素将最先能够被删除，反之最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表。1.4 树和二叉树1.4.1树树形结构是数据结构中一种很重要的非线性结构。在树形结构中，所有数据元素之间的关系具有明

10、显的层次特性。树形结构很像自然界中的树，像一棵倒长的树。在现实生活中，能用树形结构表示的例子很多。参见下面的图形：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 46 页 - - - - - - - - - 7 / 46 树形结构的基本特征及基本术语：以下图为例：树的根：在树形结构中， 没有前驱的结点只有一个，称为树的根结点，简称为树的根。如：上图中的“R” 。父结点：在树形结构中， 每一个结点 ( 除了树的根结点 ) 只有一个前驱，称为父结点。如：上图中的“ R”是 K

11、、P、Q、D的父结点；“N”是 X、Y的父结点。子结点：在树形结构中，每个结点可以有多个后继，称为该结点的子结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 46 页 - - - - - - - - - 8 / 46 如：上图中的 K、P、Q 、D是“R”的子结点； X、Y是“N ”的子结点。叶子结点：在树形结构中，没有后继的结点称为叶子结点，也称终端结点。如：上图中的 C、M 、F、E、X、G 、S、L、Z、A均为叶子结点。结点的度：在树形结构中， 一个结点所拥有的

12、后继个数称为该结点的度。如：上图中根结点R的度是 4；结点 T 的度是 3；结点 P、Q、D、O、Y、W的度都为 1。叶子结点的度为0。树的度：在树形结构中，所有结点中的最大的度称为树的度。如：上图中树的度为4，因为结点 R的度最大，是4。树的深度：在树形结构中，树的最大层数称为树的深度( 或高度 ) 。如：上图中树的深度是5。说明：树形结构具有明显的层次关系，即树是一种层次结构。在树形结构中一般按如下原则分层：1) 根结点在第 1 层。2) 其余结点的层数等于其父结点的层数加1。子树：在树形结中，以某结点的一个子结点为根构成的树称为该结名师资料总结 - - -精品资料欢迎下载 - - - -

13、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 46 页 - - - - - - - - - 9 / 46 点的一棵子树。如：上图中，结点R有 4 棵子树，它们分别以K、P、Q 、D为根结点；结点 P有 1 棵子树，其根结点为N ；结点 T 有 3 棵子树，它们分别以 W 、Z、A为根结点。在树形结构中，子树间互不相交，叶子结点没有子树。森林：森林是M(M 0) 棵互不相交的树的集合。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。1.4.2二叉树(1) 二叉树的特点 非空二叉树只有一个根结点。 二

14、叉树中的每个结点， 最多有两棵子树， 分另称为该结点的左子树 与右子树 。当一个结点即没有左子树也没有右子树时，该结点就是叶子结点。在下面的图中， 左面是只有根结点的二叉树，右面是深度为4 的二叉树：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 46 页 - - - - - - - - - 10 / 46 (2) 满二叉树与完全二叉树1) 满二叉树：满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉

15、树的第k 层上有 2i-1(k 1) 个结点，且深度为k 的满二叉树有 2k-1(k 1) 个结点。在下图中分别是深度为2、3、4 的满二叉树：满二叉树中不存在度数为1 的结点，每个分支结点均有两棵深度相同的子树，且叶子结点都在最下一层。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 46 页 - - - - - - - - - 11 / 46 2) 完全二叉树：若一棵二叉树最多只有最下面的两层上结点的度数可以小于2，并且最下一层上的所有结点都集中在该层最左边的若干位置

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

17、 的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 46 页 - - - - - - - - - 12 / 46 个数为 n0，度为 2 的结点的个数为n2，则： n0= n2+1(对于完全二叉树还有如下属性)性质 4：具有 n 个结点的完全二叉树，其深度为log2n+1。注：log2n 表示取 log2n 的整数部分。 性质 5：如果将一棵有n 个结点的完全二叉树自顶向下、同一层自左向右连续给结点编号 1、2、3、n，则对于任意结点i(1 i n)有如下结论：1) 如

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

19、： 访问根结点 (假设用 D表示) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 46 页 - - - - - - - - - 13 / 46 遍历左子树 (假设用 L 表示) 。 遍历右子树 (假设用 R表示) 。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可分为三种：前序遍历(DLR)、中序遍历 (LDR)、后序遍历(LRD)。以下图中的二叉树为例：前序遍历 (DLR)：首先访问根结点，然后遍历

20、左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问子树的根结点，然后遍历其左子树，最后遍历其右子树。即，前序遍历是指访问所有的根结点( 包括子树的根结点 ) 都在遍历其左、右子树之前。前序遍历的操作：若二叉树为空，则结束反返回。否则： 访问根结点 前序遍历左子树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 46 页 - - - - - - - - - 14 / 46 前序遍历右子树如，对上图中的二叉树进行前序遍历的结果是：F C A D B E G H P中序遍历

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

22、包括子树的根结点 ) 都在遍历其左、右子树之后。后序遍历的操作：若二叉树为空，则结束反返回。否则：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 46 页 - - - - - - - - - 15 / 46 后序遍历左子树 后序遍历右子树 访问根结点如，对上图中的二叉树进行后序遍历的结果是：A B D C H P G E F1.5 查找查找又称检索。查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。1.5.1 顺序查找顺序

23、查找又称顺序搜索或线性查找。顺序查找一般是指在线性表中查找指定的元素。顺序查找的基本思想：在 n 个结点组成的线性表中，从线性表的一端开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到， 即查找成功；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素，即查找失败。在顺序查找中，查找成功时最多需要比较n 次、最少比较 1次、平均比较次数约为表长的一半。查找失败时比较n+1 次。顺序查找的时间复杂度为O(n) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

24、- - - 第 15 页，共 46 页 - - - - - - - - - 16 / 46 对于无序表 ( 即表中的元素的排列是无序的) 和链式存储结构的线性表 ( 有序的和无序的 ) ，只能用顺序查找。顺序查找的优点：算法简单而适用范围广。对表中元素的排列次序无要求，既可以是按关键字排列的有序表，也可以是无序表； 对表的存储结构也无任何要求， 既适用于顺序存储的顺序表，也适用于链接存储的链表。顺序查找的缺点：查找效率低， 平均查找长度较大。 当 n 很大时不宜采用顺序查找。1.5.2 二分查找二分查找又称折半查找。 它是一种查找效率较高的查找方法。该方法只适用于顺序存储结构的有序表。通常是指

25、有序表中的元素按值升序排列 ( 非递减有序排列 ) 。 二分查找不能用于链式存储结构的线性表。二分查找的基本思想：参见“C语言程序设计”或“ VB程序设计”课件的相应内容动画。对于长度为n 的有序线性表，查找成功时最多需要比较log2(n+1) 次、最少比较1 次、平均查找长度近似log2n 。当查找失败时，比较log2n 或 log2(n+1) 次。不管二分查找成功与否，其时间复杂度均为O(log2n) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 46 页 -

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

27、表， 在最坏情况下， 冒泡排序需要经过n/2 遍的扫描，比较次数为n(n-1)/2。冒泡排序算法的平均时间复杂度为O(n2) ，空间复杂度为O(1) 。(2) 快速排序快速排序的基本思想：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 46 页 - - - - - - - - - 18 / 46 参见下图：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面， 将线性表前面大于T 的元素移到后面， 结果就把线性表分成了两部分( 称为两个子表 )，T 插入到其

28、分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以 T 为分界线， 将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T。如果对分割后的各子表再按上述原则进行分割，并且这种分割过程可以一直做下去，随着对各子表不断地进行分割，划分出的子表会越来越多 ( 一次只能对一个子表进行再分割处理) ， 直到所有子表中的元素都排好序为止，则此时的线性表就变成了有序表。对于长度为 n 的线性表：在最坏情况下，快速排序比较次数为n(n-1)/2。算法的时间复杂度为 O(n2) ，空间复杂度为O(n)。名师资料总结 - - -精品资料欢迎下载 - - -

29、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 46 页 - - - - - - - - - 19 / 46 在最好情况下，快速排序算法的时间复杂度为O(nlog2n) ，空间复杂度为O(log2n) 。快速排序算法的平均时间复杂度是O(nlog2n) ，平均比较次数不大于 (n+1)log2n1.6.2 插入排序插入排序是每次将一个待排序的记录按其关键字大小，插入到前面已排好的序列中的适当位置，直到全部记录插入为止。(1) 直接插入排序快速排序的基本思想：请查看相关资料。对于长度为 n 的线性表：在最坏情况下，直接插入

30、排序比较次数为n(n-1)/2。算法的时间复杂度为 O(n2) 。(2) 希尔排序希尔排序的基本思想：请查看相关资料。对于长度为 n 的线性表：在最坏情况下希尔排序比较次数为O(n1.5) 。1.6.3 选择排序选择排序的基本思想是：每一遍在n-i+1(i=1,2,n-1) 个待排序记录中选取关键字最小的记录作为有序序列中第i个记录，直到全部记录排完为止。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 46 页 - - - - - - - - - 20 / 46 (1)

31、 直接选择排序选择排序的基本思想：参见“C语言程序设计”或“ VB程序设计”课件的相应内容动画。在最坏情况下，直接选择排序比较次数为n(n-1)/2。(2) 堆排序希尔排序的基本思想：请查看相关资料。在最坏情况下，堆排序比较次数为O(nlog2n) 。习题：（一）选择题 ( 单选) 1. 下列叙述中正确的是( D ) A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构2.下列关于栈的叙述中正确的是( A ) A) 栈顶元素最先被删除 B) 栈顶元素最后才能被删除C) 栈底元素永远不能被删除 D) 以上三

32、种说法都不对名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 46 页 - - - - - - - - - 21 / 46 3. 下列叙述中正确的是( B ) A) 有一个以上根结点的数据结构不一定是非线性结构B) 只有一个根结点的数据结构不一定是线性结构C) 循环链表是非线性结构D) 双向链表是非线性结构4.支持子程序调用的数据结构是( A ) A) 栈 B) 树 C) 队列 D) 二叉树5. 某二叉树有 5 个度为 2 的结点，则该二叉树中的叶子结点数是( C ) A

33、）10 B ）8 C）6 D）4 提示：在任意二叉树中， 若度为 0 的结点 ( 即叶子结点 ) 的个数为n0，度为 2 的结点的个数为n2，则： n0= n2+1 即 n0( 叶子结点数 )=5+1=6 6. 某二叉树共有7 个结点，其中叶子结点只有1 个，则该二叉树的深度为 ( 假设根结点在第一层)( D ) A) 3 B) 4 C) 6 D)7 7. 下列排序方法中，最坏情况下比较次数最少的是( D ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 46 页 -

34、 - - - - - - - - 22 / 46 A）冒泡排序 B ）简单选择排序 C ）直接插入排序 D ）堆排序8. 下列叙述中正确的是( A ) A) 对长度为 n 的有序链表进行查找，最坏的情况下需要的比较次数为 n B) 对长度为 n 的有序链表进行对分查找，最坏的情况下需要的比较次数为（ n/2 ）C) 对长度为 n 的有序链表进行对分查找，最坏的情况下需要的比较次数为 (log2n) D) 对长度为 n 的有序链表进行对分查找，最坏的情况下需要的比较次数为 (nlog2n) ( 二) 填空题1. 假设用一个长度为50 的数组（数组元素的下标从0 到 49）作为栈的存储空间，栈底指

35、针bottom 指向栈底元素，栈顶指针top 指向栈顶元素， 如果 bottom=49,top=30(数组下标 )，则栈中具有 _个元素。答案： 202. 一个队列的初始状态为空。现将元素A、B、C、D、E、F、5、4、3、2、1 一次入队，然后再一次退队，则元素退队的顺序为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 46 页 - - - - - - - - - 23 / 46 _。答案： A、B、C、D 、E、F、5、4、3、2、1 3. 设某循环队列的容量为50

36、，如果头指针front=45(指向队头元素的前一个位置 ) ，尾指针 rear=10 （指向队尾元素） ，则该循环队列中共有 _个元素。答案： 15 4. 设二叉树如下：对该二叉树进行后序遍历的结果为_。答案： E、D 、B、G 、H、F、C、A 5. 一棵二叉树的中序遍历结果为DBEAFC ，前序遍历结果为ABDECF ，则后序遍历结果为_。答案： DEBFCAA B C D E F G H 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 46 页 - - - - -

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

38、软件和应用软件之间，协助用户开发软件的工具性软件。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 46 页 - - - - - - - - - 25 / 46 软件生命周期通常将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。参见下图：结构化分析方法结构化分析的常用工具：数据流图 (DFD)：是描述数据处理过程的工具，是需求理解的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心

39、整理 - - - - - - - 第 25 页，共 46 页 - - - - - - - - - 26 / 46 逻辑模型的图形表示，它直接支持系统的功能建模。数据字典 (DD)：是结构化分析方法的核心。判定树判定表结构化设计方法常见的过程设计工具：图形工具：程序流程图，N-S图，PAD图( 问题分析图 ) ，HIPO表格工具：判定表。语言工具： PDL(伪码)软件设计的基本原理 1) 抽象：是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。 2) 模块化：是指把一个待开发的软件分解成若干小的简单的部分。如高级语言中的过程、函数、子程序等。每个模块可以完成一个特定的子功能， 各

40、个模块可以按一定的方法组装起来成为一个整体，从而实现整个系统的功能。 3) 信息隐蔽：是指在一个模块内包含的信息( 过程或数据 ) ，对于不需要这些信息的其他模块来说是不能访问的。4) 模块独立性： 是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立程度是评价名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 46 页 - - - - - - - - - 27 / 46 设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个

41、定性的度量标准。内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。内聚性是信息隐蔽和局部化概念的自然扩展。一个模块的内聚性越强则该模块的模块独立性越强。作为软件结构设计的设计原则，要求每一个模块的内部都具有很强的内聚性，它的各个组成部分彼此都密切相关。耦合性：耦合性是模块间相互连接的紧密程度的度量。一个模块与其他模块的耦合性越强则该模块的模块独立性越弱。原则上讲， 模块化设计总是希望模块间的耦合表现为非直接耦合方式。但是，由于问题所固有的复杂性和结构化设计的原则，非直接耦合往往是不存在的。耦合性与内聚性是模块独立性的两个定性标准，耦合性与内聚性是相互

42、联系的。在程序结构中，各模块的内聚性越强，则耦合性越弱。一般优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的的内聚性，有利于提高模块的独立性。软件测试软件测试是在软件投入运行前对软件需求、设计、编码的最名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 46 页 - - - - - - - - - 28 / 46 后审核。 软件测试是为了发现错误而执行程序的过程。软件测试应当制定明确的测试计划并按计划执行。软件测试的目的：是发现错误。软件测试方

43、法和技术：若从是否需要执行被测软件的角度，可以分为静态测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。静态测试： 包括代码检查、 静态结构分析、 代码质量度量等。静态测试不实际运行软件，主要通过人工进行。动态测试：是基于计算机的测试，是为了发现错误而执行程序的过程。 需要精心设计一批测试用例，并利用这些测试用例去运行程序，以发现程序错误的过程。测试用例的格式为： (输入值集 ),( 输出值集 )白盒测试：也称结构测试或逻辑驱动测试。它是根据软件产品的内部工作过程， 检查内部成分， 以确认每种内部操作符合设计规格要求。 白盒测试把测试对象看作一个打开的盒子，允许测试人员利用程序

44、内部的逻辑结构及有关信息来设计或选择测试用例，对程序所有的逻辑路径进行测试。通过在不同点检查程序的状态来了解实际的运行状态是否与预期的一致。所以，白盒测试是在程序内部进行，主要用于完成软件内部操作的验证。白盒测试的主要方法有逻辑覆盖、基本路径测试等。黑盒测试：也称功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试完全名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 46 页 - - - - - - - - - 29 / 46 不考虑

45、程序内部的逻辑结构和内部特征，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。所以，黑盒测试是在软件接口处进行，完成功能验证。 黑盒测试只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息，并且保持外部信息( 如数据库或文件 )的完整性。黑盒测试主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错误。黑盒测试方法主要有等价类划分法、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。程序调试在对程序进行了成功的测试之后，将进入程序调试( 通常称Debug，即排错 ) 。程序调试的任

46、务是诊断和改正程序中的错误。它与软件测试不同，软件测试是尽可能多地发现软件中的错误，并找出软件错误的具体位置。软件测试贯穿整个软件生命期，调试主要在开发阶段。习题：（一）选择题 ( 单选) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 46 页 - - - - - - - - - 30 / 46 1. 软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软件的是( C ) A) 编译程序 B) 操作系统 C) 教务管理系统 D) 汇编程序2.

47、软件按功能可分为：应用软件、系统软件、和支撑软件（或工具软件）。下面属于系统软件的是( B ) A) 编辑软件 B) 操作系统 C) 教务管理系统 D) 浏览器、3. 软件( 程序) 调试的任务是 ( A ) A) 诊断和改正程序中的错误 B) 尽可能多的发现程序中的错误C) 发现并改正程序中的所有错误 D) 确定程序中错误的性质4. 下面叙述中错误的是( A ) A) 软件测试的目的是发现错误并改正错误B) 对被调试的程序进行“错误定位”是程序调试的必要步骤C) 程序调试通常也称为Debug D) 软件测试应严格执行测试计划，排除测试的随意性5. 耦合性和内聚性是对模块独立性度量的两个标准。

48、下列叙述名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 30 页，共 46 页 - - - - - - - - - 31 / 46 中正确的是 ( B ) A) 提高耦合性、降低内聚性有利于提高模块的独立性B) 降低耦合性、提高内聚性有利于提高模块的独立性C) 耦合性是指一个模块内部各个元素间彼此结合的紧密程度D) 内聚性是指模块间互相连接的紧密程度6. 数据流图 (DFD图) 是( C ) A) 软件概要设计的工具 B) 软件详细设计的工具C) 结构化方法的需求分析工具 D) 面向

49、对象方法的需求分析工具7. 软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于 ( B ) A) 定义阶段 B) 开发阶段 C) 维护阶段 D) 上述三个阶段8. 在软件开发中，需求分析阶段产生的主要文档是( D ) A) 软件集成测试计划 B) 软件详细设计说明书 C) 用户手册 D) 软件需求规格说明书9. 结构化程序所要求的基本结构不包括( B ) A) 顺序结构 B) GOTO 跳转 C) 选择( 分支) 结构 D) 重名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

50、 31 页，共 46 页 - - - - - - - - - 32 / 46 复( 循环) 结构10. 下面描述中错误的是( A ) A) 系统总体结构图支持软件系统的详细设计B) 软件设计是将软件需求转换为软件表示的过程C) 数据结构与数据库设计是软件设计的任务之一D) PAD 图是软件详细设计的表示工具( 二) 填空题1. 软件测试可分为白盒测试和黑盒测试。基本路径测试属于_测试。答案：白盒2. 符合结构化原则的三种基本控制结构是：选择结构、循环结构和 _。答案：顺序结构3. 软件是 _、数据和文档的集合。答案：程序4. 对软件设计的最小单位( 模块或程序单元 ) 进行的测试通常为_测试。