c语言公共基础复习重点

《c语言公共基础复习重点》由会员分享，可在线阅读，更多相关《c语言公共基础复习重点（41页珍藏版）》请在装配图网上搜索。

1、精品K第二部分二级公共基础历年试题分布：数据结构与算法（3?5个选择题，一般4题；1?3个填空题，一般2题，约12分）程序设计基础（1-2个选择题，一燉1题；0-2个填空题，一般0-1个，约4分）软件工程基础（2-3个选择题，一燉2题；1-2个填空题，一般2个，约8分）数据库设计基础（2?3个选择题，一般2题:1-2个填空题，一般2个，约8分）第一章数据结构与算法第一部分算法大纲要求：算法的基本概念；算法复杂度的概念和意义（时间与空间复杂度）一、算法的基本概念算法：是指？组有穷的指令集，是解题方案的准确而完整的描述。通俗的说，算法就是计算机解题的过程。注：程序的编制不可能优于算法。二、算法的基

2、本特征（）1、可行性：能够得到满意的结果。2、确定性：算法的每一个步骤都必须有明确的定义。3、有穷性：一个算法必须在执行有穷步后结束，即算法必须能够终止。即必须能在有限的时间内做完。4、拥有足够的情报（有零个输入或多个输入，有一个或多个输出）：算法是否有效，取决于算法提供的情报是否足够。例：1.算法的有穷性是指（）【08年4月】AA）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用三、算法设计基本方法1、列举法2、归纳法3、递推法4、递归法5、减半递推技术6、回溯法四、算法复杂度（时可复杂度和空间复杂度）（）1、时间复杂度：执行

3、算法所需要的计算工作量，也就是耗费的时间量。是对算法时间效率的度量2、空间复杂度：执行这个算法所需要的内存空间，是对算法所需存储空间的度量。例：1.算法的空间3、时间复杂度与空间复杂度是从两个方而对算法的效率进行度量，两者之间没冇必然的联系。复杂度是指（）。【09年9月】AA.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数2. 算法复杂度主要包括3. 下列叙述中正确的是（A）一个算法的空间复杂度大，B）一个算法的空间复杂度大，C）一个算法的时间复杂度4. 算法复杂度主要包括5. 下列叙述中正确的是（A）一个算

4、法的空间复杂度大，B）一个算法的空间复杂度大，C）一个算法的时间复杂度?时间和【05年9月】复杂度。）【06年9月】D则其时间复杂度也必定大则其时间复杂度必定小则英空间复杂必定小第二部分数据结构大纲要求：数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示；线性结构与非线性结构的概o一、数据结构的相关概念1、数据结构是指由某一数据对象及该对象屮所有数据成员之I可的关系组成的集合。通常也指带有结构的数据元素的集合。数据结构可分为数据的逻辑结构和数据的存储结构两种。2、数据的逻辑结构反映数据元素之间逻辑关系的数据结构。（）3、数据的存储结构一一数据的逻辑结构在计算机存储空间中的存放形式称为

5、数据的存储结构，即各数据元素在计算机中的存储关系。（）4、数据存储结构不仅要存放各数据元素的信息，还要存放各数据元素之间的前后件关系的信息。5、逻辑结构与存储结构之间的关系（）一种数据的逻辑结构根据儘要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。用不同的存储结构，其数据处理的效率是不同的。例：1?下列描述中正确的是（）【05年9月】DA）个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，H各种存储结构不影响数据处理的效率D）个逻辑数据结构可以有多种存储结构，冃各种存储结构影响数据处理的效率下列叙

6、述正确的是（）【07年4月】BA）算法的效率只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的（可以一对多）D）算法的吋间复杂度与空间复杂度一定相关（不相关2. 下列叙述中正确的是（）【07年9j】cA）数据的逻辑结构与存储结构必定是一一对应的B）山于计算机存储空间是向量式的存储结构，I月此，数据的存储结构一？定是线性结构C）程序设计语言屮的数组一般是顺序存储结构，因此，利川数组只能处理线性结构D）以上三种说法都不对数据的存储结构是指（）【05年4刀】DA）存储在外存屮的数据B）数据在外存中的数据0数据在计算机中

7、的顺序存储方式D）数据的逻辑结构在计算机屮的表示6、数据结构的符号表示：B=（D,R）B:数据结构，D:数据元素的集合，R:数据元索之间的前后件关系。7、数据结构的图形表示：方框：表示数据元索有向线段：表示数据元索的前后件关系女如:一年四季的数据结构用图形表示为&根据数据结构各数据元索之间前后件关系的复杂程度，将数据结构分为：（按逻辑结构的分类）（）线性结构非线性结构9、线性结构所满足的条件： 有且只有一个根结点；每一个结点最多有二个直接前驱，也最多有一个直接后继；线性结构又称为线性表，如：线性表、栈、队列、循坏对列、线性链表、循环链表等屈线性结构。（10、非线性结构：如果一个数据结构不是线性

8、结构，则称之为非线性结构。如口：树、一叉树等属非线性结构（）例：1?下列叙述中正确的是（）【06年彳月】A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构线性表的正确说法是（）【05年4月】BA）存储空间不一定连续，前件和灰件可以任意排列B）存储空间不一？定连续，前件必须排在后件的前面C）存储空间一定连续，前件和后件可以任意排列D）存储空间一定连续，前件必须排在后件的前而11、空的数据结构既可以是线性结构，也可以是非线性结构，要根据该结构进行的运算而定1、线性表大纲要求：线性表的定义，线性表的顺序存储结构及其插入与删除运算1、线性

9、衣是最简单、最常用的一种线性数据结构。2、非空线性表有以下三个结构特征： 有且只有一个根结点，它无前件；有且只有一个终端结点，它无后件； 除根结点与终端结点外，其他所有结点有且只有一个前件（直接前驱），也有且只有一个后件（直接后继）。3、线性表中结点的个数n称为线性表的长度，当n二0吋，称为空表。4、线性表的顺序存储结构具有以下两个基本特点： 线性表中所有元素所占的亦储空间是连续的线性表中各数据元素在存储空间中是按逻辑顺序依次存放的5、以顺序存储方式存储的线性表称为顺序表，顺序表的基本运算有： 插入运算要在第i（lv=iv=n）个元索之前插入一个新元索时，首先要从最后一个元索开始，立到第i个元

10、素Z间共n-i+1个元素依次向后移动一个位置，移动结朿后，第i个位置就被空iii,然后将新元索插入到第i项。 删除运算在一般情况下，要删除笫i（lv=iv=n）个元素，则原来第i个元素Z后的所有元素都必须依次往前移动一个位置。6、在平均情况下，要在线性表中插入或删除？个元素，需要移动衣中半的元素。?元素经常石要变动的大线性表7、线性表的顺序存储结构适合小线性表或其中元素不常变动的线性表，对丁就不太合适，因为顺序存储的插入与删除的效率比较低。（）三、线性单链表大纲要求：线性单链表、双向链表的结构及其基本运算1、线性链表线性表的链式存储结构称为线性链表。2、在线性链表中，用一个专门的指针HEAD指

11、向线性链表中第一个数据元素的结点，线性链表小最后一个元索没有后件，因此最后一个结点的指针域为空（用NULL或0表示），表示链表终止。3、线性链表中的每一个元素，一方面要存储数据元素的值：另一方血要存储各数据元素之间的前后件关系。即是将存储空间的每一个存储结点分为两部分：一部分川丁-存储数据元素的值，称为数据域；另一部分用于存放卜？一个数据元索的存储序号，即指向后件结点，称为指针域。359HEAD_A_B_?1DNUL4、线性单链表的基本运算：插入运算和删除运算插入运算：首先给要插入的元索分配一个新结点，以便用于存储该元素的值，新结点可以从可利用栈中収得，然后将存放新元素值的结点链接到线性链表中

12、指定的位置。删除运算：首先要在线性链表中找到要删除的结点，然后将要删除结点放回到可利川栈。注：线性四、双向链表1、双向链表对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前駆结点另一个称为右指针（Rlink），用以指向其后继结点，这样的链表称为双向链表。链表中插入和删除元索时，不需要移动数据元索，因此插入和删除的效率比较高。（）HEAD?0A：注：双向链表的突出特点是从某一结点出发能够找到它的前件。（）五、循环链表大纲要求：循环链表的结构及其基本运算1、循环链表与线性单链表相比，循环链表具有以下特点： 循环链表中最后一个结点的指针域不是空，而是指向表头结点，即在循环

13、链表屮，所冇结点的指针构成了一个环状链。 在循环链表中增加了个衣头结点，在任何情况下，农中至少有个结点存在，从而使空农与非空表的运算得至0统一。 存循环链表中，只要指岀表中任何？个结点的位直，就町以从它出发访问到表中其他所冇的结点，而线性单链表就不行。D1六、栈（它是一种特殊的线性表）大纲要求：栈的定义，栈的顺序存储结构及其基本运算。1、栈一一是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶（TOP）,而不允许插入与删除的另一？端称为栈底（BOTTOM）o（）2、栈是按照“先进后出”或“后进先出”的原则来组织数据的。（3、栈具有记忆功能，因此可用于函数或过程调用。（）7

14、654D3IC2B1A（m表示栈的最大容量，top=0表示栈空，top二m表示栈满）4、关于栈的进出和计算（）例：1?下列关丁栈的描述正确的是（A）B）C）D）2.（A）例：1?下列关丁栈的描述正确的是（A）B）C）D）2.（A）【05年9刀】C在栈中只能插入元素而不能删除元素在栈中只能删除元素不能插入元素栈是特殊的线性表，只能在一端插入或删除元素栈是特姝的线性表，只能在一端插入元素，而在另一端删除元索按照”后进先出”原则组织数据的数据结构是【06年4月】13队列B）栈C）双向链表队列B）栈C）双向链表3. 下列关于栈的叙述止确的是（A）栈按“先进先出”组织数据C）只能在栈底插入数据4. 一个

15、栈的初始状态为空。现将元索元索出栈的顺序是【08年9月】B二叉树【08年4月】BB）栈按“先进后出”组织数据D）不能删除数据1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA5?支持了程序调丿IJ的数据结构是（A）【09年4月】A栈B）树C）队列D）二叉树6.假设川一个长度为50的数组（数组元索的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素,栈顶指针top指向栈顶元素，如果bottom=49,top=30（数组下标），则栈中具右【09年4月】个元索。204、栈的

16、基本运算有三种：入栈、退栈、读栈顶元素。 入栈：首先将栈顶指针进一（top加1）撚后将新元素插入到栈顶指针指向的位置。 退栈：指取出栈顶元索并赋给一个指定的变量。 读栈顶元素：指将栈顶元素赋给一个指定的变量。 “上溢”：当栈顶指针已经指向存储空r可的最后一个位置时，说明栈空间已满，若再进行入栈操作此种情况称为栈“上溢”“下溢”：当栈顶指针为0时，说明栈空，不可能进行退栈操作，此种情况称为栈“下溢”七、带链的栈带链的栈可以用于收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。八、队列（是一种特殊的线性表）大纲要求：队列的定义，队列的顺序存储结构及其基本运算1、队列一一是指允许在一

17、端进行插入、而在另一端进行删除的线性表。（）2、允许插入的一-端称为队尾，用尾指针（rear）指向队尾元索，re如总是指向最后被插入的元素；允许删除的一端称为队头，用队头指针（front）扌旨向排头元素的前？个位置。（）3、队列是按照“先进先出”或“后进后出”的原则来组织数据的。（）1234567891011ABCDEFfrdnlrcl4、队列的基本运算有：入队运算和退队运算两种 入队：往队列的队尾插入一个元素称为入队运算。 退队：从队列的排头删除一个元素称为退队运算。九、循环队列（）1、循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。2、循坏队列中

18、，用队尾指针rear指向队列中的队尾元索，用排头指针front指向排头元索的前一个位置。3、从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元索均为队列中的元索,设队列的容量为mf为当前队头元素的前一位置，I?为队尾元素的位置，假定队列中元索的个数总小于m求队列中元素的个数的公式为：（n+r-f）%n,如下图三，队列的容量n=7,队首所指的位置仁4,队尾所指的位置r二2,则队中元素个数为（7+2-4）%7=5o图二：队列满图二：队列满FrontRear4、循环队列的运算主要有：入队运算和退队运算两种入队：每进行一次入队运算，队尾指针就进一，当队尾指针rear=m+1

19、时，贝lj?rear=l,然后将新元素插入到队尾指针指向的位置追队：每进行一次退队运算，排头指针就进一，当排头指针front=m+llit，则置front然后将排头指针指向的元素赋给指定的变量A)B)C)D)例：1.下列叙述中正确的是【08年9月】D循环队列有队头和队尾两个指针，因此，循环队列是非线性结构在循环队列中，只需要队头指针就能反应队列中元素的动态变化情况在循环队列中，只需要队尾指针就能反应队列屮元素的动态变化情况循环队列中元素的个数是山队头和队尾指针共同决定2.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循坏队列是队列的【07年9月】存储结构。链式设某

20、循环队列的容量为50,头指针front二5（指向队头元素的前一位置），尾指针rear=29（指向队尾元索，则该循环队列屮共有【08年4月】个元素。242. 设某循环队列的容量为50,如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有【2】个元素。【10年3月】15【小结】链式存储结构与顺序存储结构的区别： 链式存储结构的存储空间可以不连续，而顺序存储结构耍求存储空间必须是连续的;序存储结构的存储线性结构；或其元素不常变动序存储结构的存储线性结构；或其元素不常变动 链式存储结构的各数据结点的存储顺序与数据元索之间的逻辑关系可以不一致，顺

21、顺序与数据元素的逻辑顺序是一致的；链式存储既可用于表示线性结构，也可以用于表示非线性结构：顺序存储用于表示 链式存储适合大的线性表或插入和删除很频繁的线性表；顺序存储适合小的线性表的线性表用链式存储便于插入和删除操作。 链式存储不能随机存取元素，而顺序存储叮以随机存取元素。 顺序存储结构不便于对存储空间的动态分配；链式存储能很方便的实现存储空间的动态分配顺序存储结构的存储空间不便于扩充。 顺序存储结构的插入与删除运算的效率很低。 只要可利用栈不空，链式存储结构不会发生“上溢”的情况。十、树（非线性结构）大纲要求：树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序、后序遍历1、树是一种简

22、单的非线性结构。2、父结点：在树结构中，每一个结点只有一个前件。如：下图B是D和E的父结点3、根结点：没有前件的结点只有一个，称为树的根结点。如：下图A是根结点4、子结点：每一个结点可以有多个后件，它们称为该结点的子结点如：D和E是B的子结点5、叶子结点：没有后件的结点称为叶子结点。如：下图结点D、E、F、G是叶子结点（）6、度：一个结点拥有的后件个数称为该结点的度。女口：下图结点B的度为2,结点C的度为1（）7、树的度：所有结点中最人的度称为树的度。如：下图屮树的度为3（）&树的深度：树具有明显的层次结构，树的最大层次称为树的深度。如：下图中树的深度为3（）9、树在计算机中通常用多重链表农示

23、。卜一、二叉树大纲要求：二叉树的定义1、二叉树的两个特点（二叉树如下图）（） 非空二叉树只有一个根结点 每一个结点最多有两棵子树，冃分别称为该结点的左子树与右子树大为2。卜一、二叉树大纲要求：二叉树的定义1、二叉树的两个特点（二叉树如下图）（） 非空二叉树只有一个根结点 每一个结点最多有两棵子树，冃分别称为该结点的左子树与右子树大为2。注：在二叉树中，每一个结点的度故2、在二叉树的第K层上，最多有2k(K=1)个结点()3、深度为m的二叉树最多有2m-l个结点()4、在任意一棵二叉树中，度为0的结点(叶子结点)总是比度为2的结点多一个()5、有n个结点的二叉树，其深度至少为10g2r，+l,其

24、中10g2n表示収log/的整数部分()例：1?在下列关于二叉树的叙述，选出正确的一项()DA.在二叉树中，任何一个结点的度都是2B.二叉树的度为2C.在二叉树中至少有一个结点的度是2D.一棵二叉树的度可以小于2一棵二叉树第六层(根结点为第一层)的结点数最务为【05年9刀】个。322. 某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有个结点。【09年9月】3. -?棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为()【07年9no219B)221C)229D)231十二、满二叉树1、满二叉树除最后一层外，每一层的所有结点都有两个子结点(满二叉树如下图)

25、ADEFG2、满二叉树的每一层上的结点数都达到最大值。3、满二叉树的第K层上有2戸个结点。如：上图第3层有4个结点()4、深度为m的满二叉树有2,n-l个结点。如：上图深度为3共有7个结点()例：1.在深度为7的满二叉树中，叶子结点的个数为()【06年4刀】CA) 32B)31C)64D)63在深度为7的满二叉树中，度为2的结点个数为【07年4月】。2. 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为()【07年4刀】n+1B)n-1C)2nD)n/23. -棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为()【07年9月】。A) 219B)221C)229

26、D)231十三、完全二叉树1、完全二叉树除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。(b)完全二叉树(c)非完全二叉树(a)完全二叉树2、在完全二叉树中，叶子结点只可能在层次最大的两层上出现。(d)非完全二叉树3、右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次为p或p+14、满一叉树也是完全一叉树，而完全一叉树一般不是满一叉树。5、具有n个结点的完全二叉树的深度为log2n+l()6、设完全二叉树共有N个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1到N给结点进行编号，贝I对编号为K(K=l,2,N)的结点有以下结论：若K=l,

27、则该结点为根结点，它没有父结点；若Kl,则该结点的父结点编号为1NT(K/2)o若2K=N,则编号为K的结点的左子结点编号为2K;否则该结点无左子结点，也没有右子结点 若2K+1UN,则编号为K的结点的右子结点编号为2K+1,否则该结点无右子结点。例如:1例：上图编号为2的结点（即K二2）,那么该结点的左子结点的编号应为4（2*2二4）例：上图编号为2的结点（即K二2）,那么该结点的左子结点的编号应为4（2*2二4）|?四、二叉树的遍历（指不垂复地访问二叉树屮的所右结点）（）序遍历大纲要求：二叉树的前序、中序、后1、前序遍历（根左右或DLR）方法：首先访问根结点，然后遍历左子树，最后遍历右子树

28、。2、中序扁历（左根右或LDR）方法：首先遍历左子树，然斤访问根结点，最后遍历右子树。3人后序扁历（左右根或LRD方法：首先遍历左子树，然后遍历右子树，最后访问根结点。例：1.对如下二叉树如上图前序遍历的结果是：ABDECF如上图中序遍历遍历的结果是：DBEAFC如上图后序遍历遍历的结果是：DEBFCALpJELpJE进行后序遍历的结果为（A）ABCDEFB）DBEAFC【06年4月】DD)DEBFCC) ABDECFA十五、查找技术大纲要求：顺序查找与二分法查找算法（1）顺序查找1、查找方法：从线性表的第一个元素开始，依次将线性中的元素与被查元素进行比较，若相等则表示找至0;若所有的元素都与

29、被查元素进行了比较但都不相等，则表示查找失败。（2、若在长度为N的线性表中查找，在最坏情况下需要比较N次，记为O（N）。（）3、如果线性表为无序表（即未按升序或降序排列），则不管是顺序存储结构还是链式存储结构，都只能川顺序查找.（4、即使是有序线表，如杲釆用链式存储结构，也只能用顺序查找.（）（2）二分法查找1、查找方法：将待查找元索X与线性表的屮间项值进行比较，若中间项的值等于X,则找到；若X小于中间项的值，则在线性表的前半部分以和同的方法进行查找；若X大于中间项的值，则在线性衣的后半部分以相同的方法进行查找，直到杏找成功或子表长度为0为止。（）2、若在长度为N的线性表中进行二分查找，在最坏

30、情况下，需要比较10g2N（*）3、二分法查找只适川丁？顺序存储的冇序表。（）例：1.对t度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）【05年4刀】BA）Log2nB）nC）n+1D）n/22. 下列叙述中正确的是【10年3月】CA）对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n/2）C）对长度为n的有序链衣进行对分杏找，最坏情况下需要的比较次数为（Iog2n）D）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nIog2n）3?下列数据结构中，能用二分法进行查找的是（）【05年9刀

31、】A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序性链表十六、排序技术大纲要求：基本排序算法（交换类排序、选择类排序、插入类排序）（-）交换类排序法（1）冒泡排序法1、排序方法：首先，从衣头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大丁？后面的元素，则将它们互换；然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元索的大小，若相邻两个元索中，后而的元索小于前而的元索，则将它们互换；重复上述过程，立到剩F的线性表变空为止。（*2、最坏情况比较次数为：N（N-I）/2（*）注：目泡排序法是-种最简单的交换类排序方法，它是通过相邻

32、数据元索的交换逐步将线性表变（2）、-快速排序法1、排序方法：从线性表屮选取一个元索，设为T,将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割；对分割后的各子表再按上述原则进行分割，直到所有子表为空为止，则此时的线性表就变成了有序表.（）2、最坏情况比较次数为：N（N-l）/2（*）3、快速排序方法在被排序数据已基本有序的情况下最不利于发挥其长处。（）注:快速排序法的关键是对线性表进行分割，以及対各分割出的子表再进行分割。（二）插入类排序法（1）简单插入排序法插入排序一一将无序序列中的各

33、元素依次插入到已经有序的线性表中。1、方法：在线性表中，只包含第1个元索的子表显然可以看成是有序表。然后，从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中。伙*2、最坏情况比较次数为：N（N-1）（）注：简单插入排序的效率与冒泡排序法的效率相同。（）（2）希尔排序法1、方法：将整个无序序列分割成若干个小的子序列分别进行插入排序。分割方法：将相隔某个增量II的元素构成一个子序列，在排序过程中，逐次减小这个增量，最后当H减到1时，进行一次插入排序，排序就完成了。（）152、最坏情况比较次数为：N，（）（三）选择类排序法（1）简单选择排序法1、方法：扫描整个

34、线性表，从中选出绘小的元素，将它交换到表的最前血；然后对剩下的子表采川同样的方法，直到子表空为止。（）2、最坏情况比较次数为：N（N-I）/2（*）（2）堆排序法1、方法：首先将？个无序序列建成堆，然后将堆顶元索与堆中最片？个元索交换不考虑己经换到最后的那个元素，只考虑前n-1个元索构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆，反复做前一步，直到剩下的子序列为空为止。2、最坏情况比较次数为：nL0G2x（AAA）注：堆排序方法不适合规模较小的线性表，対较大规模的线性表是很有效的。例：1?冒泡排序在最坏情况下的比较次数是（）【07年9月】。A）n（n+1）/2

35、B）nIog2nC）n（nI）/2D）n/2对长度为n的线性表排序，在最坏情况下，比较次数不是n（n-l）/2的排序方法雄（）【08年4刀】A）快速排序B）冒泡排序C）直接插入排序D）堆排序第二章程序设计基础第一部分程序设计方法与风格大纲要求：程序设计方法与风格（一）程序设计方法就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。（二）程序设计风格程序设计的总体风格是：强调简单和清晰，程序必须是可以理解的（可读性好），即“清晰第一，效率第二”（形成良好程序设计风格应考虑以下儿个因索：（,不需要背，但要熟悉）（1）源程序文档化（要有必要的注释1、注释一般分为序言性注

36、释和功能性注释。序言性注释：位于每个程序的开头部分，它给出程序的整体说明。功能性注释：一般嵌在程序体之中，主要描述其后的语句或程序做什么。（2）数据说明的方法注意数据说明的风格，以便使程序中的数据说明更易于理解和维护（3）语句的结构（优先考虑清晰性程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复朵化，一般应注意以下儿八、？1、程序编写应优先考虑清晰性；2、避免采川复杂的条件语句；3、尽量减少使川“否定”条件的条件语句；4、要模块化，使模块功能尽可能单一化；5、利川信息隐蔽，确保每一个模块的独立性；6、从数据出发去构造程序；7、不要修补不好的程序，要重新编写；&尽可能使川库函数

37、；9、避免使用临时变量而使程序的可读性下降；（4）输入和输出（输入数据前后要有提示信息输入和输出方式和格式应尽可能方便川户的使川，因为系统能否被川户接受，往往取决于输入和输出的风格。例：1?下列叙述中，不符合良好程序设计风格要求的是（）【07年9月。A）程序的效率第一，清晰第二B）程序的可读性好C）程序中要有必要的注释D）输入数据前要有提示信息第二部分结构化程序设计大纲要求：结构化程序设计（一）结构化程序设计方法的主要原则（背）自顶向下，逐步求精（细化），模块化，限制使用goto语句。（二）结构化程序的三种基本结构（背）顺序结构.选择结构（分支结构）.循环结构（重复结构）（三）在结构化程序设计

38、的具体实施中，要注意把握以下要素：1、使用顺序.选择.循坏等控制结构2、控制结构只准许有一个入口和一个出口3、复杂结构应该用嵌套的基木控制结构进行组合嵌套4、严格控制GOTO语句的使用例：1?下列选项屮不属于结构化程序设计方法的是（）【06年4月】A）自顶向下B）逐步求精C）模块化D）可复用第三部分面向对象的程序设计大纲要求：面向对象的程序设计方法，对象、方法、属性及继承与多态性（-）面向对彖方法有以下主要优点：1、与人类习惯的思维方法一致2、稳定性好3、可重用性好4、易于开发大型软件产品5、可维护性好注：面向对象方法为面向过程的方法的本质区别在于一一面向对象方法是使用现实I比界的概念抽彖地思

39、考问题从而自然地解决问题，它强调模拟现实世界中的概念而不强调算法。（二）而向对象方法的基本概念（1）对象1、对象一一是山描述该対象属性的数据以及可以对这些数据施加的所有操作所纽？成的统一体。对象可以用来表示客观世界中的任何实体，在应用领域中有意义的、与所要解决的问题有关系的任何事件都町以作为对彖，它既可以是具休的物理实休的抽象，也可以是人为的概念，或者是任何明确边界和意义的东西。2、展性对象所包含的信息，它是在设计对彖时确定，一般只能通过执行対彖的操作来改变。2. 操作一一描述对象执行的功能，若通过消息传递，还可以为其它对象使用。通常把对象的操作也称为方法或服务。4、对彖的基本特点：（背标识唯

40、？性:指对象是可区分的，并H由对象的内在本质来区分。 分类性:可以将具有和同属性和操作的对象抽象成类。 多态性:指同一个操作可以是不同对象的行为。 圭寸装性:从外血看只能看到对彖的外部特性，即只需知道数据的取值范用和町以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法；信息隐蔽就是通过封装性來实现的。（记） 楔块独立性好:对象内部各种元索彼此结合得很紧密，内聚性强。4. 面向对象程序设计的三大特征：继承、封装.多态（背）（2）类类具有共同属性共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。（背）2、类是关于对象性质

41、的描述，它同对象-?样，包括一组数据属性和在数据上的一组合法操作。例：1.在血向对彖方法中，【06年4月】描述的是具有相似属性与操作的一组对彖。2.在面向对象方法中，类的实例称为【05年4月】。（3）消息1、消息一一指対象间的相互合作需要一个机制协助进行，这样的机制称为“消息S2、消息是？个实例少另？个实例Z间传递的信息，它请求对彖执行某?处理或冋答某？耍求的信息,它统?了数据流和控制流。_记不同不同3、一个对象能够接受不同形式、不同内容的多个消息；相同形式的消息可以送往不同的对象；的对象对于形式相同的消息可以有不同的解释，能够做出不同的反映；一个对象可以同时往多个对彖传递信息，两个对彖也可以

42、同时向某个对彖传递消息。4、消息山三部分组成：接收消息的对象的名称；消息标识符（也称消息名）；零个或多个参数如：MYFORM.BOX（10,20）其屮MYFORM是接收消息的对彖名，BOX是消息名，10和20是消息的参数。（4）继承1、继承类之间共享属性和操作的机制称为继承。广义地说，即是指能够直接获得已有的性质和牲征，而不必重复定义它们。2、继承是面向对象的方法的一个主要特征。提高了软件的可重用性和扩充性。（记）3、继承分为单继承和多車继承。单继承-个类只允许有一个父类。多重继承一一一个类允许有多个父类。（5）多态性心1、多态性一一同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为

43、多态性。（记）2、多态性不仅增加了血向对彖软件系统的灵活性，进一步减少了信息兀余，而且显著地提高了软件的可重用性和可扩充性。第三章软件工程基础第一部分软件工程基本概念大纲要求：软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。（一）软件的定义及其特点1、计算机软件是计算机系统中与硬件相互依存的另一?部分，是包括程序、数据及相关文档的完整集合。（背）例:1?软件是指（【07年9月】A）程序B）程序和文档C）算法加数据结构2、软件的特点D）稈序、数据少相关文档的完整集合 软件是一种逻辑实体，而不是物理实体，具有抽象性C软件的生产与碾件不同，它没有明显的制作过程。 软件在运行.使用期间不存

44、在磨损、老化问题。 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题。 软件复朵性高，成本昂贵。（是人类有史以来生产的复杂度最高的工业产品）软件开发涉及诸多的社会因索。3. 软件分类：应用软件.系统软件.支撑软件（或工具软件）（理解各种软件属于哪一类）应用软件包括：事务处理软件，工程与科学让算软件，实时处理软件，械入式软件，人工智能软件等。例如:办公自动化软件、成绩管理系统等。 系统软件包括：操作系统，编译程序，汇编程序，网络软件，数据库管理系统等。 支撑软件包括：需求分析工具软件，设计工具软件，编码工具软件，测试工具软件，维护工具软件等（二）软件工程1、软件

45、工程：是应用于计算机软件的定义、开发和维护的一幣套方法、工具、文档、实践标准和工序。2、软件工程包括三个要素：方法、工具和过程.（背）3、1968年衣北人西洋公约纽.织会议（NATO会议）上，软件工程作为一个概念旨次被提出，这在软件技术发展史上是一件大事。注：软件工稈概念的岀现源口软件危机。（记）例：1?下列描述中正确的是（C）05年9月】A）软件工程只是解决软件项目的管理问题B）软件工程只是解决软件产品的生产率问题C）软件工程的主耍思想是强调在软件开发丄程中需耍应用工程化原则D）软件工程只是解决软件开发过程中的技术问题（三）软件工程过程软件工程过程一一是把输入转化为输出的一纽彼此和关的资源和

46、活动。2、软件工程过程的4种基本活动： P（Plan）软件规格说明。规定软件的功能及其运行时的限制。 D（Do）软件开发。产生满足规格说明的软件。 C（Check）软件确认。确认软件能够满足客八提出的要求。 A（Action）软件演进。为满足客户的变更耍求，软件必须在使用的过程中演进（四）软件生命周期测试也用开发阶段錐护退役维护阶段（软件生命周期）1、软件牛命周期-软件产品从提出、实现、使用维护到停II?使用退役的过程称为软件牛命周期.（背）2、软件牛命周期的二个阶段：软件定义.软件开发、软件运行维护（费用放多的阶段）（背,知道上图中每个活动属丁？哪个阶段）注：软件开发阶段包括一一设让（包括概

47、要设计和详细设让）、实现（编码）和测试 软件运行维护阶段包括使川、维护和退役例：1?下列叙述中正确的是（）【05年9刀】A）软件交付使川后还需要进行维护B）软件一旦交付使川就不需要再进行维护C）软件交付使用后期牛命周期就结束D）软件维护是指修复程序中被破坏的指令1. 软件牛命周期可分为定义阶段，开发阶段和维护阶段。详细设计属T10年3刀】A）定义阶段B）开发阶段C）维护阶段D）上述三个阶段（五）软件工程的目标与原则1、软件工程的基本日标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能按时完成开发，及时交付使用。2、软件工程的理论和技术性研

48、究的内容主要包括：软件开发技术和软件工程筲理。3、软件工程的基木原则：抽象、信息隐蔽、模块化、局部化、确定性、一？致性、完备性和可验证性。（六）软件开发工具与软件开发环境1、软件开发环境是全面支持软件开发全过程的软件工具集合。2、工具和环境的使用进一步提高了软件的开发效率、维护效率和软件质量。3、计算机辅助软件工程（CASE）是当前软件开发坏境中富有特色的研究工作和发展方向。第二部分结构化分析方法大纲要求：结构分析方法，数据流图.数据字典.软件需求规格说明书一、需求分析阶段可以概括为四个方面:K需求获取2、需求分析3、编勇需求规格说明书（是需求分析的阶段成果）4、需求评审注：需求分析阶段能够准

49、确确定软件该做什么，即确定软件的功能。（）二、需求分析方法1、结构化分析方法面向数据流的结构化分析（SA） 血向数据结构的Jackson方法（JSD）面向数据结构的结构化数据系统开发方法（DSSD）2、面向对象的分析方法（00A）三、结构化分析的常用工具（1）数据流图（RER）数据流图一一是描述数据处理过稈的工具，是需求理解的逻辑模型的图形表示，它真接支持系统的功能建模。丄要川于概要设计阶段。（,记）数砸图的主要图形元素:（，记）1、C）加工（转换）一输入数据经加工变换产生输出。2、数据流沿箭头方向传送数据的通道，一般在旁边标注数据流名o3、；存储文件（数据源）表示处理过程中存放各种数据的文件

50、。4、源，潭表示系统和环境的接口，屈系统Z外的实体。例：1.FW流图中带有箭头的线段表示的是（）【08年9月】A）控制流B）爭件驱动C）模块调用D）数据流注：典型的数据流类型有两种：变换型和事务丿股（2）数据字典（堕数据字典一一是结构化分析力法的核心。数据字典的作川是对DFD屮出现的被命名的图形元素的确切解释。通常数据字典包含的信息有：名称、别名何处使用/如何使用.内容描述、补充信息等。数据字典中出现的符号：符号含义二表示“等于”，“定义为”，“山什么构成”丨？?？表示“或”即选择括号中用“丨”号分隔的各项中的某一项+表示“与”和”nm表示“重复”，即括号中的项要重复若干次，n,m是車复次数的

51、上下限（.）表示“可选”，即括号屮的项可以没有*表示“注释”.表示“连接符”（3）判定树（4）判定衣四、软件需求规格说明书软件石求规格说明卩（SRS）是需求分析阶段的得出的最主要的文档，也是主要成果，是软件开发中的車要文档Z-o（,记）例：1.在软件开发中，需求分析阶段产牛的主要文档是（）【08年4月】A）可行性分析报告B）软件需求规格说明书C）概要设计说明书D）做成测试计划软件开发过程主要分为需求分析、设计、编码与测试以个阶段，其中一阶段产生“软件需求规格说明书J软件需要规格说明书的作用：1、便于用户、开发人员进行理解和交流。2、反映出用户问题的结构，可以作为软件开发工作的基础和依据。3、作

52、为确认测喩和验收的依据注：软件需求规格说明书应具令完整性，无岐义性、正确性、可验证性、可修改性等特征，其屮最重要的是无岐义性。第三部分结构化设计方法大纲要求：结构化设计方法，总体设计与详细设计一、软件设计的基础1、软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。2、从技术观点來看，软件设计包括软件结构设计、数据设计、接口设计.过程设计。（,背）软件结构设计一一是定义软件系统主要部件之间的关系。 数据设计一一是将分析时创建的模型转化为数据结构的定义。 接口设计一一是描述软件内部、软件和I办作系统Z间以及软件与人Z间如何通信。 过程设计一一是把系统结构部件转换成软件的过程性描述

53、。3、从工程管理允度来看，软件设计分两步完成：概要设计和详细设计。（,背）概要设计：又称结构设计，是将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库檢式。 详细设计：确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。例：1.从工程管理角度，软件设计一般分为两步完成，它们是（）【06年9刀】A）概要设计与详细设让B）数据设让与接口设计C）软件结构设计与数据设计D）过程设计与数据设计】、软件设i?白勺基本原刊！、（1）竝一矗把事物木质的共同特性提取出来而不考虑其他细节。（2）模块化指解决一个复杂问题时口顶向下逐层把软件系统划分成若干模块的过程。（3）伫息隐

54、蔽-在一个模块内包含的信息，对于不需要这些信息的其他模块来说是不能访问的，一般采用封装技术来实现。（4）模块独立性-每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单（即高内聚低耦合）.（,背）衡量软件的模块独立性：使用耦合性和内聚性两个定性的度童标准。（,背）山聚性-扌1个模块内就各不元素间彼此结谷的緊密程斥的应量,内聚由弱到强分别为：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚和功能内聚（,记）耦合性一指模块间互相连接的紧密程度的度暈，耦合由高到低分别为：内容耦合、公共耦合.外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合.（,记）例：1.为了使模块尽

55、可能独立，耍求（）【05年4月】A）模块的内聚程度要尽量高,且各模块间的耦合程度要尽量强B）模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱C）模块的内聚程度要尽最低，且各模块间的耦合程度要尽量弱D）模块的内聚程度要尽量低，冃各模块间的耦合程度要尽量强2. 在结构化程序设计中，模块划分的原则是（）【07年4月】A）各模块应包括尽呈多的功能B）各模块的规模应尽量人C）各模块之间的联系应尽量紧密D）模块内具有高内聚度、模块间具冇低耦合度软件设计中模块划分应遵循的准则是（）【08年4月】A）低内聚低耦合B）咼内聚低耦合C）低内聚I冷耦合D）|Vrj内聚間耦合耦合性和内聚性是对模块独立性度量的两个

56、标准，下列叙述中正确的是（）【09年4月】A）提高耦合性降低内聚性有利于提高模块的独立性B）降低耦合性提高内聚性有利于提高模块的独立性C）耦合性是指一个模块内部各个元索间彼此结合的紧密程序D）内聚性是指模块间互相连接的紧密程序5?两个或两个以上模块之间关联的紧密程度称为（）【06年4月】A）耦合度B）内聚度C）复杂度D）数据传输特性二、概要设计（也称总体设计或结构设计）1、概要设计的基本任务是：（1）设计软件系统结构在需求分析阶段，已经把系统分解成层次结构，而在概要设计阶段，需要进一步分解，划分为模块以及模块的层次结构。（2）数据结构及数据库设计数据设计是实现需求定义和规格说明过程屮提出的数据

57、对象的逻辑表示。（3）编写概耍设计文档在概要设计阶段，需要编写的文档有：概要设计说明书、数据库设计说明书、集成测试计划等。（4）概要设计文档评审2、常用的概要设计工具是：结构图（SCStnicmreChart）,也称程序结构图。（1）使川结构图描述软件系统的层次和分块结构关系，它反映了整个系统的功能实现以及模块与模块之间的联系与通讯，是未來程序中的控制层次体系。（2）结构图中图形符号表示的意思： 用矩形衣示模块（矩形内注明模块的功能和名字）川箭头表示模块间的调川关系。 川带实心圆的箭头表示传递的是控制信息。 用带空心圆的箭头衣示传递的是数据。（3）扇入：调川一个给定模块的模块个数。（,理解）（

58、4）扇出：一个模块宜接调川的其他模块数。（，理解）（5）深度：表示控制的层数。（,理解）（6）宽度：整体控制跨度（最大模块数的层）的表示（,理解）例：1?下列软件系统结构图的宽度为【06年9月】。3、概要设计的准则： 提咼模块独立性（模块咼内聚，低耦合）。 模块规模适中。 深度、宽度、扇出和扇入适当：顶层高扇出，屮间扇出较少，底层高扇入。 使模块的作用域在该模块的控制域内。 应减少模块的接口和界面的复杂性。 设计成单入口、单出口的模块。 设计功能可预测的模块。三、详细设计详细设计的任务:是为软件结构图中的每一?个模块确定实现算法和局部数据结构;用某种选定的农达工具衣示算法和数据结构的细节。常见

59、的过程设计工具有（*，记）：图形I?具一一程序流程图，NSPAD,HIPO。表格工具一判定表濡芒丁翼.PDL（伪码）1、程序流程图一一是二活传靈的、应川广榜山软件过程设计表示工具,通常也称为程序框图。一:控制流IL加工步骤O:逻辑条件（*,记住各符号的意思）例：1?程序流程图屮带箭头的线段表示的是（）【（）8年4月】A）图兀关系B）数据流C）控制流D）调川关系软件设计中，不属于过程设计工具的是（）【05年9月】A）PAL（过程设计语言）B）PAD图C）N-S图D）DFD图2、N?S图一一川方框图来代替传统的程序流程图,把这种图称为N?S图。 母个构件具仃明确的功能域控制转移必须遵导结构化设计要

60、求 易于确定局部数据和全局数据的作川域易于表达嵌套关系和模块的层次结构3、PAD图问题分析图（ProblemAnalysisDiagram）的英文缩写。 结构淸晰，结构化程度高，易于阅读最左端的纵线是程序主干线，每增加一层PAD图向右扩展一？条纵线。4、PDL也称为结构化的英语和伪码。 有为结构化构成元素、数据说明和模块化特征提供的关键词语法处理部分的描述采川H然语音语法 可以说明简单和复杂的数据结构第四部分软件测试大纲要求：软件测试的方法，白盒测试与黑盒法测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试（一）软件测试的目的1、为了发现错误血执行程序的过程。（,背）2、-个好的

61、测试川例是指很可能找到迄今为止尚未发现的错谋的川例3、一个成功的测试是发现了至今尚未发现的错误的测试例：L下列对于软件测试的描述中止确的是（）【05年4月】A）软件测试的H的证明程序是否正确B）软件测试的目的是使程序运行结果止确C）软件测试的I的是尽可能多地发现程序中的错课D）软件测试的廿的是使程序符合结构化原则2?卞列叙述正确的是（）【07年4月】A）软件测试的主要目的是发现程序中的错误B）软件测试的主要H的是确定程序中错误的位置C）为了提高软件测试的效率，最好市程序编制者自己来完成软件测试的工作D）软件测试是证明软件没有错误2. 下面叙述中错误的是（）【09年4月】A）软件测试的目的是发现错误并改止错误B）对被调试的程序进行“错误定位”是程序调试的必耍步骤C）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性（二）软件测试的基本准则（,记）1、所有测试都应追溯到需求2、严格执行测试计划，排除测试的随意性3、充分注意测试中的群集现彖（为了提高测试效率，测试人员应该集中对付那些错误群集的程序）4、程序员应避免检查自己的程序（为了达到好的测试效果，应该山独立的第三方來测试5、穷举测试不可能（在实际测试过程中不可能穷尽每一种组合。这说