《2022年全国计算机等级考试二级公共基础知识总结 .pdf》由会员分享，可在线阅读，更多相关《2022年全国计算机等级考试二级公共基础知识总结 .pdf（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国计算机等级考试二级公共基础知识总结第一章数据结构与算法 1.1 算法1算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。，2确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；3算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。4归纳法：通过观察一些简单而特殊的情况，最后总结出一般性的结论的算法的设计方法。5算法时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。6算法时间复杂度取决于问题的规模和待处理的数据的初态。7如果算法 P调用另一个算法 Q ，而算法 Q又调用算法 P，则称为间
2、接递归调用8工程上常用的分治法是减半递推技术9算法空间复杂度是指执行这个算法所需要的内存空间。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;in;i+) for(int j=1;jtop= -1 是判断顺序栈为空的条件。 ST-top=MaxSiz
3、e-1 是判断顺序栈为满的条件。4栈的基本运算： （1）插入元素称为入栈运算；（ 2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。栈的基本运算有： 入栈，出栈（删除栈顶元素） ，初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。5通常元素出栈的顺序是先取出栈顶元素再移动栈顶指针，使之指向新的栈顶元素。6从一个循环队列中删除一个元素，通常是先取出元素再移动栈顶指针7队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。 Rear 指针指向队尾， front指针指向队头。8在一个容量为 25 的循环队列中，若头
4、指针front=6 ，尾指针 rear=9 ，则该循环队列中共有 3 个元素9队列是“先进行出”（ FIFO）或“后进后出”（ LILO）的线性表。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 27 页 - - - - - - - - - 10队列运算包括（ 1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列： s=0表示队列空， s=1 且 front=rear表示队列满11当循环队列为空（ S=0）时，不能进行退队运算，这种情况称为下溢1
5、2栈的基本操作。一个栈的入栈序列是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）选项的出栈序列是错误
6、的，应选（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。15 线性链表1数据结构分为逻辑结构与存储结构，线性链表属于存储结构。2数据结构中的每一个结点对应于一个存储单元，这种存储单元（一个一个小块）称为存储结点，简称结点。3结点由两部分组成：（ 1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，
7、用于指向前一个或后一个结点。4在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。因此，链式存储结构是散列存储5带头结点的双向循环链表L 为空的条件是： 只有该头结点， 即 L-next=L 或者 L-prior=L 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 27 页 - - - - - - - - - 6对于链式队列结构，插入元素是在队尾进行的，只需修改队尾指针，不
8、需修改队头指针。 向链式队列中插入一个结点就是在单链表表尾插入一个结点，同时新插入的结点成为表尾结点。 例：在一个链式队列中， 假设 f 和 r 分别为队头和队尾指针，则插入s 所指结点的运算是r-next=s;r=s; 7向链式栈中插入一个结点，就是在单链表的表头插入一个结点，同时将新结点的位置赋予栈顶指针。例：向一个栈顶指针为HS的链式栈中插入一个s 所指的结点时，则执行s-next=HS;HS=s; 8线性链表的基本操作：插入、删除、查找、排序。9双向链表每个结点有两个指针域，这两个指针分别指向它的前驱结点和后继结点。10单链表中，每个结点都含有一个指针域，这个指针指向它的下一个结点。因
9、此访问单链表中的结点时，必须沿着它的指针逐个进行。11由于双向链表比单链表结构复杂，所以在插入和删除元素时， 要修改更多的指针域，相对比较复杂， 单向链表和双向链表在空间存储上的不连续性决定了两者都不可以随机访问， 在双向链表中由于每个结点包括两个指针域，其中一个指向该结点的前驱结点， 另一个指向该结点的后继结点， 因此它既可以直接访问前驱结点，又可以直接访问后继结点， 而单链表每个结点只有一个指针域，指向它的后继结点， 所以它只能直接访问它的下一个结点，而无法直接访问它的前一个结点。所以双向链表顺序访问相邻结点更加灵活。12链表的特点： 顺序表可以随机访问任意一个结点，而链表必须从第一个数据
10、结点出发， 逐一查找每个结点。 链表结构是一些逻辑上相邻，而空间上并不一定相邻的数据元素的集合， 相邻的结点之间通过指针相互联系，在插入和删除元素时，只需修改结点指针即可，不需要移动数据元素。当存储空间不足时，可以动态为其分配内存空间， 所以不必事先估计存储空间的大小。所需空间与其长度成正比。13用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。当往空链表插入元素时， 只要把待插入元素的指针域指向头结点的指针域，把头结点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置，执行同样的操作即可完成插入。 当链表只有一个元素时， 删除操作只要修改指针名师资料总结 - -
11、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 27 页 - - - - - - - - - 指向下一个元素的指针所指的元素即可，跟一般的链表删除操作是一样的。带头结点的链表并不能加快对链表的遍历，带头结点的链表反而要增加一个用于存储头结点的空间，并不能节省存储空间， 用带头结点的链表跟存取元素的速度无关。14忽略了最后结点或头结点的指针，在 n 个结点的单向链表 （无表头结点） 中，每个结点都有一个指针单元（即指针域），加上头指针，至少需要n+1个指针单元。16 树与二叉树1树是一种简单的
12、非线性结构，所有元素之间具有明显的层次特性。栈和队列都是线性结构。在树结构中，每一个结点只有一个前件， 称为父结点，没有前件的结点只有一个，称为树的根结点， 简称树的根。 每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中， 一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。2树的结点不能为空，结点最少的树为只有一个结点的树；二叉树的结点数可以为 0，结点最少的二叉树为空的二叉树。3设树 T 的度为
13、 4，其中度为 1，2，3 和 4 的结点的个数分别为4、2、1、1，则 T 中叶子结点的个数为8（根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和为1。因此树的结点数为1*4+2*2+3*1+4*1+1=16。叶子结点数目等于树结点总数减去度不为0 的结点数之和，即16-(4+2+1+1)=8 。）4设二叉树根结点的层次为0，对含有 100 个结点的二叉树，可能的最大树深和最小树深分别是99 和 6（要使二叉树在规定结点下有最大树深，这时二叉树退化成一个线性链表，如果对应二叉树的根结点的层次为0，那么对应二叉树的树深为结点个数减1，即 99；要使二叉树有最小树深，则此二叉树为
14、满二叉树，当满二叉树的根结点的层次为1时， 结点个数 n和树深 h之间的关系为：n=2h-1，所以当二叉树的根结点层次为0 时，对应关系为 n=2(h+1)-1 。）二叉树的基本性质：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 27 页 - - - - - - - - - （1）在二叉树的第 k 层上，最多有 2k-1(k 1)个结点；（2）深度为 m的二叉树最多有 2 的 m次方-1 个结点；5例：深度为 5 的二叉树至多有 2*2*2*2*2-1=31个结点。6具
15、有 3 个结点的二叉树有5 种，7（3）度为 0 的结点（即叶子结点）总是比度为2 的结点多一个；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
16、 给结点进行编号（ k=1,2, .n ），有以下结论：若 k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为 INT(k/2) ；若 2kn， 则编号为 k 的结点的左子结点编号为2k； 否则该结点无左子结点 （也无右子结点）；若 2k+1n，则编号为 k 的结点的右子结点编号为2k+1；否则该结点无右子结点。9对于深度等于其结点数的二叉树，每层只有一个结点，假设从上向下分别为a1,a2,.,an,则先序遍历序列为a1,a2,.,an。后序遍历序列为an,an-1,.a1。遍历序列正好相反。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k 层上有2k-1 个
17、结点深度为 m的满二叉树有 2m-1个结点。10由满二叉树的树深和结点的关系知，对于深度为h 的满二叉树， m个树叶 ,n个结点 , 则 n=2h-1 即n=20+21+22+.+2(h-1)=2h-1。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 27 页 - - - - - - - - - 完全二叉树是指除最后一层外， 每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。11例：设一棵叉树中有 3 个叶子结点，有 8 个度为 1 的结点，则该二叉树中总的
18、结点数为 13 12例：假定根结点的层次是0，含有 15 个结点的二叉树的最小树深是3（要使二叉树在规定结点数下的深度最小，这样的二叉树只能是完全二叉树。当根结点的层次为 1 时，二叉树的结点 n 和深度 h 之间的关系是 n=2h-1，所以当二叉树的根结点的层次为0 时，结点和树深的关系是n=2(h+1)-1 ，所以 h=3，n=15）13在在深度为 5 的完全二叉树中，度为2 的结点数最多为 15 14 树的度是指树内各结点的度的最大值, 一棵树中除根结点之外 , 每个结点都有一个前驱结点 , 结点拥有子树的个数称为结点的度, 所以结点的度数之和即为除根结点外所有结点的个数, 即每个结点的
19、度数之和等于结点总数减1, 结点的度即是拥有子树的个数 , 而结点与子树之间是以边连接的, 所以一棵树中每个结点的度数之和与边的条数相等, 15由二叉树的性质知二叉树叶子的个数n(0) 和度为 2 的结点个数 n(2) 的关系为 n(0)=n(2)+1 。二叉树的结点个数可以等于0，二叉树中有些不是叶子的结点只有一个子女，二叉树存储结构采用链式存储结构， 对于满二叉树与完全二叉树可以按层序进行顺序存储。16二叉树的遍历：前序遍历 DLR先根结点，后遍历左子树，最后遍历右子树；abdgcefh EFHIGJK EDBAC DBEAFC 中序遍历 LDR先左子树，后访问根结点，最后遍历右子树；dg
20、baechf HFIEJKG DEBAC ABDECF 后序遍历 LRD先左子树，后遍历右子树，最后访问根结点 gdbehfca 右子树为G DACBE DEBFCA 17在先序、中序、后序遍历序列中叶子结点总是从左向右的。相对次序是不发生改变的。是完全相同的。 （任意两种方法遍历同一棵二叉树，可以确保唯一一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 27 页 - - - - - - - - - 棵二叉树，无论是用前序遍历、中序遍历、后序遍历二叉树，其区别都在于访问根
21、的先后次序不同，而叶子结点的顺序是一样的。）18例：对树的三大部分：树根、左子树、右子树，存在树根结点大于左子树各个结点，小于右子树各个结点，因此要得到各个结点值的递增序列，应按“左子树-根结点 - 右子树”的顺序进行访问，这就是中序遍历的遍历过程。19例：设 n，m为一棵二叉树上的两个结点，在中序遍历中，n 在 m后的条件是 n 在 m的右子树上， 如果 n 在 m的右子树上， 根据中序遍历算法， 先访问根结点 m ，然后再访问右子树上的结点，所以n 必然要在 m后。如果 n 是 m的祖先，则 m可能在 n 的左子树上， 也可能在 n 的右子树上， 如果 m在 n 的左子树上， 根据中序遍历
22、算法，先访问n 的左子树，然后访问n 结点，所以 n 必然要在 m后，对如果 n 是 m的子孙，则 n 可能在 m的左子树上， 也可能在 m的右子树上。 中序遍历时，先访问左子树，再访问根结点。n 在 m前，则 n 必须在 m的左子树中。20在中序遍历序列中，根结点将左右子树分开，左边为左子树中的所有结点，右边为右子树中的所有结点。21现有按中序遍历二叉树的结果为abc，问有 5 种不同形态的二叉树可以得到这样的遍历结果22在一棵二叉树中，度为0 的结点个数为 m ，度为 2 的结点个数为 n，则二者之间的关系是 m=n+1 23设一棵完全二叉树共有700 个结点，则在该二叉树中有350 个叶
23、子结点17 查找技术顺序查找的使用情况：（1）线性表为无序表；（ 2）表采用链式存储结构。1顺序查找法适合于线性表，不论采用顺序存储还是链式存储。散列存储于顺序查找无关，同样压缩存储、索引存储也与顺序查找无关2二分法查找也称折半查找，只适用于顺序存储结构的且数据元素按关键字有序的有序表，对于长度为 n 的有序线性表进行二分查找， 最坏情况只需比较 log2n次。3例：有一个有序表为 1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找为 82 的结点时， 4 次比校后查找成功。（此有序表的长度为13，按名师资料总结 - - -精品资料欢迎下载 - - - - -
24、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 27 页 - - - - - - - - - 比较次数 log2n 计算应该是 4。或先找中间结点 45，再找 77，95，最后找到 82，经过 4 次比较，）4例：对有 18 个元素的有序表用二分法查找，则查找A3 的比较序列的下标为 9、4、2、3 第一次 (1+18)/2=9, 第二次 (1+8)/2=4, 第三次 (1+3)/2=2, 第四次 (3+3)/2=3 。5例：设有一个已按元素的值排好序的线性表（长度大于2），对给定的值 k，分别用顺序查找法和二分查找法查找一个与
25、k 相等的元素， 比较的次数分别是s和 b，在查找不成功的情况下，s 和 b 的关系是 sb 。 ( 对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较次数为 log2n+1即最大比较次数。当n=2时，显然 n+1log2n+1 。) 6例：在顺序表（ 3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值 11，所需的关键码比较次数为4 （二分查找是用要查找的关键码与线性表的中间元素比较，根据比较结果是结束查找，还是在左边或者右边子表按相同的方法继续查找。与11 比较的关键码分别为 15、8、10、12。比较的次数为 4。）
26、7例：在顺序表（ 8，12，16，20，26，27，31，34，43，49，51）中，用二分法查找关键值为 21，需做的比较次数为4（首先与 27 比较，由于 21 比 27 小，根据二分法比较的方法， 所以接着与 27 左边的 16 比较，由于 21 比 16 大，所以与 16 右边的 20 比较，最后一次与 26 比较。所以总共比较了4 次。）8例：对一个长度为 10 的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是 3 （分查找的值小于表中所有元素和大于表中所有元素两种情况进行分析），9例：在长度为 n 的线性表中查找一个表中不存在的元素，需要的比较次数为n 10例：设线性表
27、（ a1，a2，。，a500）元素的值由小到大排列，对一个给定的 k 值用二分法查找线性表，在查找不成功的情况下至多需比较9 次（二分法查找在查找不成功的情况下至多需要比较log2n+1=9(n=500)。）11例：已知有序表为（ 12，18，24，35，47，50，62，83，90，115，134），当用二分法查找 100 时，需进行 3 次比较可确定成功 （画出二叉树判定树， 当查名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 27 页 - - - - - - -
28、- - 找 100 时，需要和 50、90、110 比较，由于 110 的左子树为空，查找结束，比较了 3 次。）12如果要求一个线性表既能较快的查找，又能适应动态变化的要求， 可以采用分块查找方法13顺序查找法查找长度为n 的线性表时， 每个元素的平均查找长度为(n+1)/2 。18 排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。1交换类排序法： （1）冒泡排序法，需要比较的次数（在最坏情况下的时间复杂度）为 n(n-1)/2 ；（2）快速排序法。2插入类排序法： （1）简单插入排序法， 最坏情况需要 n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O(n1.5)
29、次比较。3选择类排序法：（ 1）简单选择排序法 , 最坏情况需要 n(n-1)/2次比较；选择排序的思想为： 扫描整个线性表， 从中选出最小的元素， 将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。 第一个元素需要比较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) ，最坏情况为O(nlog2n)
30、 5在插入选择排序中，若初始数据基本正序，则选用插入排序；若初始数据基本反序，则选用选择排序。因为插入排序在初始数据基本正序时时间复杂度为O(n)，而选择排序在初始数据基本反序时时间复杂度为O(n) 6插入排序的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素， 把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。7例：设关键码序列（ 16，9，4，25，15，2，13，18，17，5，8，24），要按关键码值递增的次序排列， 采用简单选
31、择排序法， 一趟扫描后的结果是 2 ，9，4，25，15，16，13，18，17，5，8，24 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 27 页 - - - - - - - - - （简单选择排序法的思想是： 以无序表的第一个元素作为比较标准，依次同后面的元素进行比较， 如果有一个元素比第一个元素小则记录这个元素的下标，然后以新的最小元素继续往下比较，有更小的元素再记录该下标，再比较 .，当对整个数组扫描一趟后就可以等到最小元素的下标，然后与无序表的第一个元素交
32、换位置。本题很明显第一趟扫描结果最小元素是2，与第一个元素交换位置后得到2 ，9，4，25，15，16，13，18，17，5，8，24 选项的结果。）8简单插入排序的过程是，每一趟将一个待排序的记录，按其关键字的大小插入到已经排序的子文件中适当位置上，直到全部记录插入完成为止。当文件“局部有序”或文件长度较小的情况下， 每趟的比较次数大为降低， 也即 n-1 趟比较的时间复杂度由 O(n2)降至 O(n)。所以最佳内排序方法是它9在简单插入排序过程中，当待排序列中记录按关键字非递减有序排序时，所需进行关键字比较的次数最小，为n-1，即记录不需移动；反之，当待排序列中记录按关键字非递增有序排序时
33、， 总的比较次数达到最大值(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 插入到有序表时，为寻找插入位置需比较3 次（当要插入 60 时，前 6 个元素已有序，即为： 15，23，38，54，72，96，需从后
34、向前比较到 54 为止，故要比较 3 次）11插入排序是将待排序的记录插入到前面已排好序的子文件中，即考虑已排好序的子文件。 所以是在待排序的元素序列基本有序的前提下，效率最高的排序方法12在堆排序和快速排序中，当原始记录接近正序或反序时，则选用堆排序，若原始记录无序，则使用快速排序。13快速排序基本思想是： 任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码， 右子表的排序码则大于基准元素的排序码，然后名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
35、 - - - 名师精心整理 - - - - - - - 第 13 页，共 27 页 - - - - - - - - - 分别对两个子表继续进行排序，直至整个表有序。 只有左子表排好序， 右子表还没排好序；左子表的长度在排序过程中可能大于、等于或小于右子表的长度；14由于选择排序每趟从待排序的记录中选中关键字最小的记录，每个记录都要比较，不考虑已排好序的子文件， 因此，关键字比较的次数与记录的初始排列次序无关。快速排序不考虑已排好序的子记录，15例：设有 1000 个无序的元素， 希望用最快的速度挑选出其中前10 个最大的元素，由于堆排序每扫描一趟就排好一个记录，只挑选出其中的前10 个最大的元
36、素时，使用堆排序为好。16希尔排序的基本思想是： 先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。17简单选择排序每趟从n-i+1 个记录中选取关键字最小的记录，其时间复杂度为 O(n)。18例：已知序列， 请给出采用插入排序法对该序列作升序排序时的第五趟结果是(10,32,65,70,83,100),7,9或 10,32,65,70,83,100,7,9 19 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是快速排序，需要
37、内存容量最多的是基数排序第二章程序设计基础21 程序设计设计方法和风格如何形成良好的程序设计风格1、源程序文档化； 2 、数据说明的方法； 3 、语句的结构； 4 、输入和输出。1程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的2注释分序言性注释和功能性注释，语句结构清晰第一、效率第二（已成为当今主导的程序设计风格）。3编制程序在选择标识符的名字时应考虑选择含义明确的名字，以正确提示所代表的实体。4编制程序在书写功能性注解时应考虑为程序段作注解，以帮助读者理解程序。5程序设计中语句结构的要求：（1）在一行内只写一条语句；名师资料总结 - - -精品资料欢迎下载 - - - - -
38、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 27 页 - - - - - - - - - （2）程序编写应优先考虑清晰性，程序编写要做到清晰第一、效率第二；（3）在保证程序正确的基础上再要求提高效率；（4）避免使用临时变量而使程序的可读性下降；避免不必要的转移；6程序的语句结构要从数据出发构造程序，利用信息隐蔽确保每一个模块的独立性。7序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，主要描述内容可以包括：程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等。不包
39、括数据的状态8功能性注释的位置一般嵌在源程序体之中，主要描述其后的语句或者程序做什么。包括数据的状态，语句的功能，程序段的功能，不包括模块的功能9源程序的文档化应考虑如下几点：（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。（2）程序注释：正确的注释能够帮助读者理解程序，注释一般分为序言性注释和功能性注释。（3）视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。不包括正确的文档格式10程序设计方法和技术的发展经过了结构化程序设计、面向对象的程序设计两个阶段11程序文档化应注意以下几点：（1）符号名的命名。符号名的命名具有一定的
40、实际含义，以便于对程序功能的理解；（2）程序注释。正确的注释可以帮助读者理解程序；12输入和输出信息是用户直接关心的。输入、输出方式和格式，应尽可能方便用户的使用，在设计和编程时，对所有的输入数据都要检验数据的合法性13影响输入输出风格的因素包括通信环境，用户经验，输入/ 输出设备，不包括数据状态。22 结构化程序设计名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 27 页 - - - - - - - - - 1结构化程序设计方法的四条原则是：1. 自顶向下； 2. 逐
41、步求精； 3. 模块化；4. 限制使用 goto 语句。2结构化程序的基本结构和特点：（1）顺序结构：一种简单的程序设计，最基本、最常用的结构；顺序结构是顺序执行的结构，就是按照语句的自然顺序，一条一条地执行程序（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；（3）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。3在程序设计中，重复结构对应两类循环语句：（1）对先判断后执行循环体的称为当型循环结构；（2）对先执行循环体后判断的称为直到型循环语句。4结构化程序设计方法是程序设计的先进方法工具。采用结构
42、化程序设计方法编写程序，可使程序结构良好、易读（主要强调程序的易读性）、易理解、易维护。其中最关键的是提高程序清晰性。5结构化程序设计的主要特点是程序语句组成容易识别的模块，每块只有一个入口和一个出口。620 世纪 70年代提出了“结构化程序设计（structured programming）”的思想和方法。7结构化程序设计是一种面向过程的设计方法。8结构化程序设计减少了程序出错的机会、提高了程序的可靠性、保证了程序的质量。9结构化程序设计具有方便理解和阅读、便于维护、便于修改等优点。没有移植性好10将现实生活中的实体抽象成类是面向对象程序设计方法考虑的问题。11结构化程序是由一些为数不多的基
43、本结构模块组成，这些模块甚至可以由机器自动生成，从而极大地减轻了编程工作量23 面向对象的程序设计名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 27 页 - - - - - - - - - 1对象是现实世界中一个实际存在的事物，它可以是有形的也可以是无形的，如狗，桌子，飞机是对象，而苹果的颜色不是对象。2属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。4类是指具有共同属性、共同方法的对象的集合（即一组具在相同的数据结构和相同的行为特征的对象的集
44、合）。包括属性和行为两部分。 所以类是对象的抽象，对象是对应类的一个实例。5多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。6面向对象技术具有多态性、封装性和继承性。7在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送消息8继承是面向对象的方法的一个主要特征，但不是任何对象都必须有继承性。9在面向对象的程序设计中，各个对象之间相对独立，相互依赖性小。10继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。是类之间共享忏悔和操作的机制。3对象具有如下的基本特点：（1）标识唯一性。对象是可区分的，并且由对象的内在
45、本质来区分。（2）分类性。可以将具有相同属性和操作的对象抽象成类；（3）多态性。同一个操作可以是不同对象的行为。（4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法。（5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。第三章软件工程基础31 软件工程基本概念1计算机软件是包括程序、数据及相关文档的完整集合。2软件是一种逻辑实体（逻辑产品）；3软件按功能分为（文档）应用软件、系统软件、支撑软件（或工具软件）。4软件工程包括 3 个要素：方法、工具和过程。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -
46、- - - - - 名师精心整理 - - - - - - - 第 17 页，共 27 页 - - - - - - - - - 5软件工程过程包含4 种基本活动：（1）P- 软件规格说明；（ 2）D- 软件开发；（ 3）C- 软件确认；（ 4）A- 软件演进。6软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。7软件生命周期三个阶段 : 软件定义、软件开发、运行维护，主要活动阶段是：（问题定义）（ 1）可行性研究与计划制定；（2）需求分析；（ 3）软件设计；（4）软件实现（编码）；（5）软件测试；（ 6）运行和维护。8软件工程的目标：在给定成本、进度的前提下，开发出具有有效性、可
47、靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。9软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。10软件开发环境是全面支持软件开发全过程的软件工具的集合11软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。12在软件生命周期中， 能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是需求分析13软件交付使用后， 需要不断地进行维护， 根据新提出的需求进行必要而且可能的扩充和删除。14需求分析主要工作包括4 个方面：需求获取、需求分析、编写说明书、需求评审。15SRS 是软件需求规格说明书
48、的英文简称。32 结构化分析方法1数据字典是结构化分析方法的核心2在结构化分析方法中，用于描述系统中所用到的全部数据和文件的文档称为数据字典3结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具, 建立系统的逻辑模型。4Jackson 方法是一种面向数据流的结构化方法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 27 页 - - - - - - - - - 5结构化分析的常用工具（1）数据流图；（ 2）数据字典；（
49、 3）判定树；（ 4）判定表。6数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。7数据流图由一些特定的图符构成，包括：加工（转换）、数据流、存储文件（数据源）、源和潭，不包括控制流。8程序流程图（ PFD ）中的箭头代表的是控制流。9常见的需求分析方法有：结构化分析方法和面向对象的分析方法（OOA ）。结构化分析方法中， 数据流图（DFD ）是需求分析最常用的工具。 在数据流图（DFD ）中，带有名字的箭头表示数据的流向。10数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。11判定表 4 部分组成：左上部是基本条件、左下部是基本动作、右上
50、部是条件项、右下部是动作项。33 结构化设计方法1合性与内聚性是模块独立性的两个定性标准，其中内聚反映了模块内各万分之间的联系在程序结构中各模块的内聚性越强，则耦合性越弱。 优秀软件应高内聚，低耦合。依据降低耦合提高内聚的原则，通过把一些模块取消或合并来来修改程序结构2软件概要设计的基本任务是：（1）设计软件系统结构；（2）数据结构及数据库设计；（3）编写概要设计文档；（4）概要设计文档评审。模块用一个矩形表示，箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据。3典型的数据流类型有两种