国家二级C语言公共基础知识要点及历年真题

1、1 算法1.1算法的基本概念1算法的概念(必记)：分析： 要用计算机实现某一任务时， 先应设计出一整套解决问题的指导方案， 然后具体实现。整套的指导方案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。2算法的基本特征(必记)：a.可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。b.确定性：算法中的每一个步骤都必须是有

2、明确定义的，不允许有模棱两可的解释，也不允许有多义性。c.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。d.拥有足够的情报：算法有相应的初始数据。3算法的基本要素：一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。基本运算和操作分为四类：a.算术运算: (加、减、乘、除等运算)b.逻辑运算: (与、或、非等运算)c.关系运算: (大于、小于、等于、不等于等运算)d.数据传输: (赋值、输入、输出等操作)算法的控制结构：算法中各操作之间的执行顺序称之为算法的控制结构。一个算法一般都可以用顺序、 选择、 循环三种基本控制结构组合而成。注

3、意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。4算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。1.2算法的复杂度(必记)算法的复杂度主要包括时间复杂度和空间复杂度。1算法的时间复杂度：是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。可用平均性态和最坏情况两种分析方法。 其中平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。2算法的空间复杂度：一个算法的空间复杂度， 是指执行这个算法所需要的内存空间。包含有三部分所组成： 算法程序所占的空间+

4、输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。历届的考题：1、算法具有五个特性，以下选项中不属于算法特性的是(_) 2005.4a)有穷性b)简洁性c)可行性d)确定性2、问题处理方案的正确而完整的描述称为_。2005.43、下列叙述中正确的是_。2006.9a）一个算法的空间复杂度大，则其时间复杂度也必定大b）一个算法的空间复杂度大，则其时间复杂度必定小c）一个算法的时间复杂度大，则其空间可复杂度必定小d）上述三种说法都不对第1页，共26页第 52 页 共 52 页4、算法复杂度主要包括时间复杂度和_复杂度。2006.91.2 数据结构与算法数据结构作为计算机的一门学科，主要

5、研究以下三个方面的问题：a数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c对各种数据结构进行的运算。注意：讨论以上问题主要目的是为了提高数据处理的效率。 提高效率包括两个方面：一是提高数据处理的速度，二是节省在数据处理过程中所占用的计算机存储空间。2.1什么是数据结构简单地说，数据结构是指相互有关联的数据元素的集合。 而数据元素之间的关联通常是指其前后件关系(即先后顺序关系)，如春、夏、秋、冬之间的先后顺序关系。因此，一个数据结构应包含以下两方面的信息：a.表示数据元素的信息； b.表示各数据元素之间的前后件

6、关系。1数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。注意：这种逻辑关系仅指元素之间的固有的一个先后顺序关系，而与它们在计算机中的存储顺序无关。2数据的存储结构数据的存储结构的概念：数据的逻辑结构在计算机存储空间中的存放形式 (也称数据的物理结构)。注意：a、数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同，也可以不相同。b、数据的存储结构有顺序、链接、索引等。c、数据元素采用不同的存储结构，其数据处理的效率是不同的。2.2数据结构的图形表示一般用一个中间标有元素值的方框表示一个数据元素，用一条有向线段从前件结点指向后件结点。父亲春夏秋冬儿子女儿在数据

7、结构中，没有前件的结点成为根结点(如上图中的春与父亲)；没有后件的结点称为终端结点 (也称为叶子结点，如上图中的冬与儿子和女儿)。注意：在进行处理时， 一个数据结构中的元素结点可能是在动态变化的。 这种变化可能是元素结点的个数发生变化，也可以是元素结点的先后顺序发生变化。2.3 线性结构与非线性结构空的数据结构是：一个数据元素都没有的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分为二大类：线性结构和非线性结构。一个非空的数据结构满足下列两个条件，则为线性结构，线性结构又称为线性表。a.有且只有一个根结点； b.每一个结点最多有一个前件，也最多有一个后件。在上图中，左

8、边的是线性结构，而右边的是非线性结构。注意：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟属于线性结构还是属于非线性结构， 要根据具体情况来确定。 如果对该数据结构的运算是按线性结构的规则来处理的， 则属于线性结构；否则属于非线性结构。历届的考题：1、数据的存储结构是指(_)2005.4a)存储在外存中的数据c)数据在计算机中的顺序存储方式2、下列叙述中正确的是(_)2005.9b)数据所占的存储空间量d)数据的逻辑结构中计算机中的表示a)一个逻辑数据结构只能有一种存储结构第2页，共26页b)数据的逻辑结构属于线性结构，存储结构属于非线性结构c)一个逻辑数据结构可以有多种存储结

9、构，且各种存储结构不影响数据处理的效率d)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率1.3 线性表及其顺序存储结构3.1 线性表的基本概念非空线性表的结构特征如下：a.有且只有一个根结点，它无前件；b.有且只有一个终端结点，它无后件；c.除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。春夏秋冬线性表中结点的个数n 称为线性表的长度。当 n=0 时，称为空表。3.2线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：a.线性表中所有元素所占的存储空间是连续的；b.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。注意： 在线性表的顺

10、序存储结构中， 其前后件两个元素在存储空间中是紧邻的， 且前件元素一定在后件元素的前面。在线性表的顺序存储结构中，如第一个元素的地址为adr(a1)，每个元素占用的存储空间大小为k 个字节，则线性表中第 i 个元素的存储地址为：adr(a1)+(i-1)*k。3.3顺序表的插入运算春1001100210031004夏春夏秋冬秋冬在线性表的顺序存储结构中，当插入元素时，插入点后的元素都要向后移动一位，以让出一个存储空间。在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。3.4顺序表的删除运算在线性表的顺序存储结构中

11、，当删除元素时，删除点后的元素都要向前移动一位，以保证元素都是相邻存储的。在平均情况下， 要在线性表中删除一个元素， 需要移动表中一半的元素。 因此， 在线性表顺序存储的情况下，要删除一个元素，其效率是很低的。1.4 栈和队列4.1栈及其基本运算1什么是栈栈是一种特殊的线性表。 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈按照先进后出 (filo)或后进先出 (lifo)组织数据，栈具有记忆作用。用 top 表示栈顶位置，用 botton表示栈底。第3页，共26页2栈的顺序存储及其运算栈的基本运算有三种：.入栈运算、退栈运算和.读栈顶元

12、素。4.2队列及其基本运算1什么是队列队列是允许在一端进行插入、 而在另一端进行删除的特殊的线性表。允许插入的一端称为队尾， 允许删除的一端称为排头(或队头)。队列又称为先进先出(fifo)或后进后出(lilo)的线性表，它体现了先来先服务的原则。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。2循环队列及其运算所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。队列空和队列满的条件如下：队列空的条件为s=0 ;队列满的条件为s=1 且 front=rear.循环队列主要有两种基本运算：入队运算和退队运算。a.入队运算

13、：在循环队列的队尾加入一个新元素，首先将队尾指针进一(即 rear=rear+1)，并当 rear=m+1 时置rear=1；然后将新元素插入到队尾指针指向的位置。注意：当循环队列非空(s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为上溢。b. 退队运算：指在循环队列的排头位置退出一个元素并赋给指定的变量。首先将排头指针进一front=front+1)，并当 front=m+1 时置 front=1;然后将排头指针指向的元素赋给指定的变量。注意：当循环队列为空(s=0)时，不能进行退队运算，这种情况称为下溢。历届的考题：1、下列关于栈的描述中错误的是(_)20

14、05.4a）栈是先进后出的线性表b）栈只能顺序存储c）栈具有记忆作用d）对栈的插入与删除操作中，不需要改变栈底指针2、按照后进先出原则组织数据的数据结构是(_)2006.4a)队列b)栈c)双向链表d)二叉树3、列关于栈的描述正确的是(_)2005.9a）在栈中只能插入元素而不能删除元素b）在栈中只能删除元素而不能插入元素c）栈是特殊的线性表，只能在一端插入或删除元素d）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素第4页，共26页( 即4、数据结构分为逻辑结构和存储结构，循环队列属于_结构。2005.95、按“先进后出”原则组织数据的数据结构是_。2006.91.5 线性链表5.1

15、 线性链表的基本概念1.链式存储在顺序存储方式中所有的数据元素在内存中是相邻存放的， 从而造成了在插入与删除数据元素时， 需要大量移动相应的数据元素。 为了解决这种问题， 可以将每个数据元素存储在内存中不相邻的不同位置， 并利用上一个数据元素在存有数据的同时，也存放下一个数据元素所在的位置地址(称为一个存储单元，即结点)，以便查找。这就是链式存储方式。在链式存储方式中， 要求每个结点由两部分组成：一部分用于存放数据元素值， 称为数据域； 另一部分用于存放地址，称为指针域。其中指针用于指向该结点的前一个或后一个结点 (即前件或后件)。注意：a、在链式存储结构中，存储数据结构的存储空间可以不连续，

16、各数据结点的存储顺序与数据元素之间的head 头结点 开始结点 a1a2 终端结点 an 逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。b、 链式存储方式既可以用于表示线性结构， 也可以用于表示非线性结构。 在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。2线性链表线性表的链式存储结构称为线性链表。如果结点中有两个指针， 一个用于指向前一个结点， 而另一上用于指向后一个结点，则称之为双向链表。dhead 头结点 开始结点 a1a2 终端结点 an 3带链的栈：栈的链式存储结构称为带链的栈。4带链的队列：队列的链式存储结构称为带链的队列。5.2线性链表的基本运算

17、：查找、插入、删除。历届的考题：1、下列对于线性链表的描述中正确的是(_)2005.4a）存储空间不一定是连续，且各元素的存储顺序是任意的b）存储空间不一定是连续，且前件元素一定存储在后件元素的前面c）存储空间必须连续，且前件元素一定存储在后件元素的前面d）存储空间必须连续，且各元素的存储顺序是任意的2、下列叙述中正确的是(_)2006.4a)线性链表是线性表的链式存储结构c)双向链表是非线性结构b)栈与队列是非线性结构d)只有根结点的二叉树是线性结构3、数据结构分为线性结构和非线性结构，带链的队列属于_。2006.91.6 树与二叉树6.1树的基本概念树是一种简单的非线性结构，所有元素之间具

18、有明显的层次特性。a.在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。b.在树结构中，一个结点所拥有的后件个数称为该结点的度；在树中，所有结点中的最大的度称为树的度。c.树具有明显的层次关系，即树是一种层次结构。d.数的最大层次称为树的深度。第5页，共26页f.在树中，叶子结点没有子树。a 如左图中，1、a 为根结点；e b f c g j h k d i l 2、e、f、j、h、k、l、m 为叶子结点。3、树中a、i 都有 3 个子结点，故树的度为 3。m 4、 整个树中， 总共分为4层，故树的深度为 4。树形表示法6.2 二叉树及其基本

19、性质1什么是二叉树：二叉树是一种很有用的非线性结构。二叉树具有以下两个特点：a.非空二叉树只有一个根结点；b.每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。由以上特点可以看出，在二叉树中，每一个结点的度最大为2。2二叉树的基本性质：(重要)a.在二叉树的第 k 层上，最多有 2k-1(k=1)个结点。二叉树b.深度为 m 的二叉树最多有 2m-1 个结点。深度为 m 的二叉树是指二叉树共有 m 层。c.在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比深度为 2 的结点多一个。d.具有 n 个结点的二叉树，其深度至少为log2n+1，其中log2n表示取 log2n 的整数

20、部分。a、 第四层中，最多有 24-1=23=8 个结点。b、树的深度为 4，最多有 24-1=16-1=15 个结点。c、度为 0 的结点有 8 个， 度为2 的结点有7个。3满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。a.满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k 层上有 2k-1 个结点，且深度为 m 的满二叉树有 2m-1 个结点。b.完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉

21、树。完全二叉树还具有以下性质：a.具有 n 个结点的完全二叉树的深度为log2n +1。完全二叉树6.3二叉树的存储结构满二叉树非满二叉树在计算机中，二叉树通常采用链式存储结构。6.4二叉树的遍历：(重要)在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍第6页，共26页历。a.前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。b.中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。c.后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。c2f1e 62c5f6ec4f9e 8a 3d4b5g7h 8p1 a94 d3b8g7h9

22、pa 1d3b2g7h5p 6前序：fcadbeghp中序：acbdfehgp后序：abdchpgef注意：在树结构中，每一个结点都代表一棵子树。前序遍历中一定以根结点开头，后序遍历一定以根结点结尾，而中序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树。历届的考题：1、在深度为 7 的满二叉树中，叶子结点的个数为()2006.4a)32 b)31 c)64 d)632、对下图 1 所示二叉树图 1图 2进行中序遍历的结果是_。2006.9a)acbdfeg b)acbdfge c)abdcgef d)fcadbeg3、对如下图 2 所示二叉树，进行后序遍历的结果为()2006.4a)

23、abcdef b)dbeafc c)abdecf d)debfca4、某二叉树中，度为 2 的结点有 18 个，则该二叉树中有_个叶子结点。2005.45、一棵二叉树第六层（根结点为第一层）的结点数最多为_个。2005.91.7 查找技术7.1顺序查找：顺序查找的方法是：用被查元素与线性表中的元素逐一比较， 直到找出相等的元素， 则查找成功；或者找遍所有元素都不相等，则查找失败。顺序查找的优点：对线性表的元素的逻辑次序无要求 （不必对元素进行排序） ， 对线性表的存储结构无要求(顺序存储、链接存储皆可)。顺序查找的效率很低，但在以下情况下，只能采用顺序查找：a.如果线性表为无序表，则不管是顺序

24、存储结构还是链式存储结构，都只能用顺序查找。b.即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。7.2 二分法查找：第7页，共26页二分法查找是一种效率较高的线性表查找方法。要进行二分法查找， 则线性表结点必须是排好序的， 且线性表以顺序方式存储。二分法查找的方法：首先用要查找的元素值与线性表中间位置的元素值相比较， 这个中间结点把线性表分成了两个子表， 比较相等则查找完成， 不等则根据比较结果确定下一步的查找应在哪一个子表中进行， 如此进行下去，直到找到满足条件的结点，或者确定表中没有这样的结点。对于二分法查找的缺点是线性表排序需花费时间，顺序方式存储的插入、删除不便。注意：对于长

25、度为 n 的有序线性表，在最坏的情况下，二分查找只需要比较比较log2n次，而顺序查找需要比较 n 次。二分查找的效率要比顺序查找高得多。历届的考题：1、在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为(_)2006.9a)63b)64c)6d)72、下列数据结构中，能用二分法进行查找的是(_)2005.9a)顺序存储的有序线性表c)二叉链表b)线性链表d)有序线性链表3、对长度为 n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为(_)2005.4a)log2nb) n/2c) nd) n+11.8 排序技术(记住每种排序的比较次数)排序是指将一个无序序列整理成按值

26、非递减顺序排列的有序序列。8.1 交换类排序法交换类排序的基本思想:两两比较待排序线性表的元素值 ,并对不满足顺序要求的元素进行位置交换 ,直到全部满足为止.1、冒泡排序法将相邻的元素进行两两比较， 若为逆序则进行交换。 将线性表照此方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将元素值最大的记录交换到了最后的位置， 即该线性表的最终位置。 若某一趟起泡过程中没有发生任何交换，则排序过程结束。在最坏情况下，需要的比较 n(n-1)/2 次。2、快速排序法快速排序又称分区交换排序，是对冒泡排序的一种改进。其基本方法是：在待排序线性表中任取一个元素，以它为基准用交换的方法将所有的元素分成两部分

27、， 元素值比它小的在一个部分， 元素值比它大的在另一个部分。 再分别对两个部分实施上述过程，一直重复到排序完成。在最坏的情况下与冒泡排序相当，然而快速排序的平均执行时间为o(nlog2n)。8.2插入类排序法插入排序的基本思想是：每步将一个待排序元素按其元素值的大小插入到前面已排序的元素中的适当位置上，直到全部记录插入完为止。1、简单插入排序它是指将无序序列中的各元素依次插入到已经有序的线性表中。在最坏情况下比较需要 n(n-1)/2 次。2、希尔排序法希尔排序的基本思想是把元素按下标的一定增量分组， 对每组元素使用插入排序， 随增量的逐渐减小， 所分成的组包含的记录越来越多， 到增量的值减小

28、到1 时， 整个数据合成一组， 构成一组有序元素，故其属于插入排序方法。在最坏情况下需要的比较 o(n1.5)次。8.3选择类排序法选择排序的基本思想是： 每次从待排序的元素中选出元素值最小 （或最大） 的记录，顺序放在已排序的记录第8页，共26页序列的最后，直到全部排完。1、简单选择排序对线性表进行 n-1 趟扫描，第 i 趟扫描从剩下的 n-i+1 个记录中选出元素值最小的记录，与第i 个记录交换。最坏情况下需要比较 n(n-1)/2 次。2、堆排序堆排序的基本思想是：对待排序的线性表，首先把它们按堆的定义排成一个序列（称为建堆） ，这就找到了最小的元素，然后将最小的元素取出，用剩下的元素

29、再建堆，便得到次最小的的元素，如此反复进行，直到将全部元素排好序为止。在最坏怀况下需要比较 o(nlog2n)次。8.4 总结假设线性表的长度为 n，在最坏的情况下进行比较的次数：1、交换类排序法2、插入类排序法3、选择类排序法历届的考题：1、冒泡排序法: n(n-1)/22、快速排序法: n(n-1)/23、简单插入排序法: n(n-1)/24、希尔排序法: o(n1.5)5、简单选择排序法: n(n-1)/26、堆排序法: o(nlog2n)1、对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是(_)2005.4a）冒泡排序为 n/2b）冒泡排序为 nc）快速排

30、序为 nd）快速排序为 n(n-1)/22、对长度为 10 的线性表进行冒泡排序，最坏情况下需要比较的次数为_。2006.4总复习图：定义：是指解题方案的准确而完整的描述算数据结构法特征：是可行性、 确定性、 有穷性和拥有足够的情报复杂度：包括时间复杂度和空间复杂度线性结构顺序存储：栈与队列数据的逻辑结构链式存储： 链表、双向非线性结构与算法数据结构数据的存储结构顺序存储链式存储链表、带链的栈、带链的队列1.9 精典模拟题一选择题数据的运算排序：交换类、插入类和选择类查找：顺序查找、二分查找插入与删除1.算法的时间复杂度是指_。a.执行算法程序所需要的时间b.算法程序的长度c.算法执行过程中所

31、需要的基本运算次数d.算法程序中的指令条数2.算法的空间复杂度是指_。a.算法程序的长度b.算法程序中的指令条数第9页，共26页c.算法程序所占的存储空间3.下面叙述正确的是_。d.算法执行过程中所需要的存储空间a.算法的执行效率与数据的存储结构无关b.算法的空间复杂度是指算法程序中指令（或语句）的条数c.算法的有穷性是指算法必须能在执行有限个步骤之后终止d.以上三种描述都不对4.在计算机中，算法是指_。a.查询方法b.加工方法c.解题方案的准确而完整的描述d.排序方法5.算法一般都可以用哪几种控制结构组合而成_。a.循环、分支、递归b.顺序、循环、嵌套c.循环、递归、选择d.顺序、选择、循环

32、6.算法分析的目的是_。(d)a.找出数据结构的合理性c.分析算法的易懂性和可靠性b.找出算法中输入和输出之间的关系d.分析算法的效率以求改进7.下列列关于算法的叙述中，正确的是_。a. 算法是解决问题的实现程序b. 算法是解决问题的计算方法c. 程序的实现可以优于算法的设计d. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。8下列叙述中正确的是_。a)线性表是线性结构c)线性链表是非线性结构9. 数据的存储结构是指_。a)数据所占的存储空间量b)栈与队列是非线性结构d)二叉树是线性结构b)数据的逻辑结构在计算机中的表示c)数据在计算机中的顺序存储方式d)存储在外存中的数据10下列关

33、于队列的叙述中正确的是_。a)在队列中只能插入数据c)队列是先进先出的线性表b)在队列中只能删除数据d)队列是先进后出的线性表11下列关于栈的叙述中正确的是_。a)在栈中只能插入数据c)栈是先进先出的线性表b)在栈中只能删除数据d)栈是先进后出的线性表12.以下数据结构中不属于线性数据结构的是_。a.队列b.线性表c.二叉树d.栈13.数据的存储结构是指_。a.数据所占的存储空间量b.数据的逻辑结构在计算机中的表示c.数据在计算机中的顺序存储方式d.存储在外存中的数据14.栈和队列的共同点是_。a.都是先进后出b.都是先进先出c.只允许在端点处插入和删除元素d.没有共同点15.用链表表示线性表

34、的优点是_。a.便于插入和删除操作b.数据元素的物理顺序与逻辑顺序相同c.花费的存储空间较顺序存储少d.便于随机存取16.链表不具有的特点是_。a）不必事先估计存储空间c）插入删除不需要移动元素b）可随机访问任一元素d）所需空间与线性表长度成正比17.如果进栈序列为 e1,e2,e3,e4，则可能的出栈序列是_。a）e3,e1,e4,e2b）e2,e4,e3,e1 c）e3,e4,e1,e2d）任意顺序18设有下列二叉树：第10页，共26页dbaefc对此二叉树中序遍历的结果为_。a)abcdefb)dbeafcc)abdecfd)debfca19在深度为 5 的满二叉树中，叶子结点的个数为_

35、。a)32b)31c)16d)1520.设树 t 的度为 4，其中度为 1，2，3，4 的结点个数分别为 4，2，1，1。则 t 树中叶子结点数为_。a)8b)7c)6d)521.在一棵二叉树上第 5 层的结点数最多是_。a. 8b. 16c. 32d. 1522.设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为_。a. 349b. 350c. 255d. 35123.在深度为 5 的满二叉树中，结点的个数为_。a. 32b. 31c. 16d. 1524.已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是_。a. cedbab. acbed

36、c. decabd. deabc25.已知二叉树前序遍历序列 deabc，是后序遍历序列是 dabec，中序遍历序列是 _。a）debacb）decabc）deabcd）cedba26.已知一棵二叉树前序遍历和中序遍历分别为abdegcfh 和 dbgeachf，则该二叉树的后序遍历为_。a）gedhfbcab）dgebhfcac）abcdefghd）acbfedhg27.树是结点的集合，它的根结点数目是_。a）有且只有 1b）1 或多于 1c）0 或 1d）至少 228.线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。a）必须是连续的b）部分地址必须是连续的c）一定是不连续的d）

37、连续不连续都可以29.下列叙述中，错误的是_。a）数据的存储结构与数据处理的效率密切相关b）数据的存储结构与数据处理的效率无关c）数据的存储结构在计算机中所占的空间不一定是连续的d）一种数据的逻辑结构可以有多种存储结构30.对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_。a）冒泡排序为 n/2b）冒泡排序为 nc）快速排序为 nd）快速排序为 n(n-1)/2正确答案：1- 5：c、d、c、c、d6-10：d、d、a、b、c11-15：d、c、b、c、a16-20：b、b、b、c、a21-25：b、b、b、d、a26-30：b、a、d、b、d二填空题1.在计算

38、机中，算法是指解题方案的准确而完整的描述2.算法的时间复杂度是指算法执行过程中所需要的基本运算次数3.算法的空间复杂度是指执行过程中所需要的存储空间4.算法分析的目的是分析算法的效率以求改进5.算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。6. 算法的复杂度主要包括时间复杂度和空间复杂度。7.一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。8. 栈的基本运算有三种：入栈、退栈和读栈顶元素。9. 队列主要有两种基本运算：入队运算与退队运算。第11页，共26页10. 数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。11. 数据的逻辑结构在计算机存储空间中

39、的存放形式称为数据的存储结构或物理结构。12. 顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。13 在一个容量为15 的循环队列中， 若头指针front=6， 尾指针rear=9，则该循环队列中共有_个元素。14设一棵完全二叉树共有 700 个结点，则在该二叉树中有_个叶子结点。15设一棵二叉树的中序遍历结果为 dbeafc，前序遍历结果为 abdecf，则后序遍历结果为_16 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。17在最坏的情况下，冒泡排序的时间复杂度为_18在最坏情况下，堆排序需要比较的次数为_。19在长度为

40、n 的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为_。20对于输入为 n 个数进行快速排序算法的平均时间复杂度是_。2 程序设计基础2.1程序设计设计方法和风格程序的整体风格应该强调简单和清晰，程序必须是可以理解的。著名的”清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重和考虑以下因素：1、源程序文档化3、.语句的结构2.2 结构化程序设计2、数据说明的方法4、输入和输出2.2.1结构化程序设计的原则结构化程序设计方法的主要原则包括：(重要)1自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多

41、追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。2逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。3模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为模块。4限制使用 goto 语句2.2.2 结构化程序的基本结构与特点结构化程序的基本结构为顺序结构、选择结构和重复结构三种。2.3 面向对象的程序设计2.3.1关于面向对象方法面向对象方法的优点：(重要)1与人类习怪的思维方法一致2稳定性好3可重用性好4易于开发大型软件产品5可维护性好2.3.2 面向对象方法的基本概念：用辩证唯物的认识论

42、来认识世界。1对象：对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体， 是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。对象的基本特征如下：a.标识惟一性：可通过内在本质来区分。b.分类性：可以将具有相同属性和操作的对象抽象成类。第12页，共26页c.多态性：指同一个操作可以是不同对象的行为。d.封装性：从外面不能直接使用对象的处理能力，也不能直接修改内部状态，对象的内部状态只能由其自身改变。e.模块独立性好。2类和实例将属性、操作相似的对象归为类。类是具有共同属

43、性、共同方法的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质。而一个对象则是其对应类的一个实例。3消息：对象间的这种相互合作需要一个机制协助进行， 这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息。4继承：继承是指能够直接获得已有的性质和特征， 而不必重复定义他们。继承是使用已有的类定义作为基础建立新类的定义技术，以使新类自动拥有旧类的所有特征。5多态性：多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。历届的考题：1、下列选项不符合良好程序设计风格的是()2006.9a）源程序要文档化b）数据说明的次序要规范化c）避免滥用 goto

44、语句d）模块设主地要保证高耦合、高内聚2、下列选项中不属于结构化程序设计方法的是()2006.4a)自顶向下c)模块化b)逐步求精d)可复用3、在面向对象的方法中，类的实例称为_。2005.44、在面向对象方法中，_描述的是具有相似属性与操作的一组对象。2006.42.4 精典模拟题一选择题1结构化程序设计主要强调的是a)程序的规模b)程序的易读性c)程序的执行效率 d)程序的可移植性2对建立良好的程序设计风格，下列描述正确的是a)程序应简单、清晰、可读性好c)充分考虑程序的执行效率b)符号名的命名只要符合语法d)程序的注释可有可无3在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过

45、发送a)调用语句b)命令c)口令d)消息4信息隐蔽的概念与下述哪一种概念直接相关？a)软件结构定义c)模块类型划分b)模块独立性d)模块耦合度5下面对对象概念描述错误的是a)任何对象都必须有继承性c)对象间的通讯靠消息传递b)对象是属性和方法的封装体d)操作是对象的动态属性6. 下面描述中，符合结构化程序设计风格的是_。a. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑b. 模块只有一个入口，可以有多个出口c. 注重提高程序的执行效率d. 不使用 goto 语句7.下面概念中，不属于面向对象方法的是_(d)第13页，共26页a. 对象b. 继承c. 类d. 过程调用8. 面向

46、对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是_。a. 模拟现实世界中不同事物之间的联系b. 强调模拟现实世界中的算法而不强调概念c. 使用现实世界的概念抽象地思考问题从而自然地解决问题d. 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考9.在设计程序时，应采纳的原则之一是_。a. 程序结构应有助于读者理解b. 不限制 goto 语句的使用c. 减少或取消注解行d. 程序越短越好10.结构化程序设计的 3 种结构是_。a）顺序结构、选择结构、转移结构b）分支结构、等价结构、循环结构c）多分支结构、赋值结构、等价结构 d）顺序结构、选择结构、循环结构正确答案：1-5：

47、b、a、d、b、a 6-10：a、d、c、a、d二填空题1结构化程序设计的三种基本逻辑结构为顺序、选择和_2源程序文档化要求程序应加注释。注释一般分为序言性注释和_3在面向对象方法中，信息隐蔽是通过对象的_性来实现的。4类是一个支持集成的抽象数据类型，而对象是类的_5在面向对象方法中，类之间共享属性和操作的机制称为_6.结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化和限制使用 goto 语句。7.面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体。8.一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的可重用性。9.面向对象的模型中，最

48、基本的概念是对象和类。10.在面向对象的程序设计中，类描述的是具有相似性质的一组_。3 软件工程基础3.1.1 软件定义与软件特点计算机软件：是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。软件的特点：a. 软件是一种逻辑实体，不是物理实体，具有抽象性；b. 软件的生产与硬件不同，它没有明显的制作过程；c. 软件在运行、使用期间不存在磨损、老化问题；d. 软件的开发、运行对计算机系统有依赖性，受计算机系统的限制，这导致软件移植的问题。e. 软件复杂性高，成本昂贵；f. 软件开发涉及诸多的社会因素。3.1.2 软件危机与软件工程软件危机归结为成本、质量、生产率等问题

49、。软件工程的主要思想是强调在软件开发过程中需要应用工程化原则， 即将软件产品看作是一个工程产品来处理。软件工程包括 3 个要素，即方法、工具和过程。3.1.3 软件工程过程与软件生命周期：(重要)1、软件工程过程包含 4 种基本活动：ap(plan)软件规格说明。规定软件的功能及其运行时的限制。bd(do)软件开发。产生满足规格说明的软件。cc(check)软件确认。确认软件能够满足客户提出的要求。da(action)软件演进。为满足客户的变更要求，软件必须在使用的过程中演进。2、软件生命周期：软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。其中软件定义阶段包含有：可行性研究、第14页，共26页需求分析两步；软件开发阶段包含有：概要设计、详细设计、实现和测试；软件运行维护阶段包含有：使用、维护和退役。3.1.4 软件工程的目标与原则1软件工程的目标软件工程的目标是： 考试出现时， 只要是达到用最小的人力、 物力、 财力和时间而得到最好质时产品的都是。基于软件工程的目标，软件工程的理论和技术