2017年9月全国计算机等级考试《二级C语言程序设计》【教材精讲＋真题解析】讲

下载地址:http://free.100xuexi.com/Ebook/126123.html
目录                                                                                        封面
内容简介
视频讲解教师简介
目录
教材精讲部分[视频讲解]
　第一部分　公共基础知识[视频讲解]
　　第1章　数据结构与算法[视频讲解]
　　第2章　程序设计基础[视频讲解]
　　第3章　软件工程基础[视频讲解]
　　第4章　数据库设计基础[视频讲解]
　第二部分　C语言程序设计[视频讲解]
　　第1章　程序设计基本概念[视频讲解]
　　第2章　C程序设计的初步知识[视频讲解]
　　第3章　顺序结构[视频讲解]
　　第4章　选择结构[视频讲解]
　　第5章　循环结构[视频讲解]
　　第6章　字符型数据[视频讲解]
　　第7章　函数[视频讲解]
　　第8章　地址和指针[视频讲解]
　　第9章　数组[视频讲解]
　　第10章　字符串[视频讲解]
　　第11章　对函数的进一步讨论[视频讲解]
　　第12章　用户标识符的作用域和存储类[视频讲解]
　　第13章　编译预处理和动态存储分配[视频讲解]
　　第14章　结构体、共用体和用户定义类型[视频讲解]
　　第15章　位运算[视频讲解]
　　第16章　文件[视频讲解]
　　第17章　考试指导[视频讲解]
真题解析部分[视频讲解]
　2015年9月全国计算机等级考试《二级C语言程序设计》真题及详解
　2015年3月全国计算机等级考试《二级C语言程序设计》真题及详解
　2014年9月全国计算机等级考试《二级C语言程序设计》真题及详解
　2014年3月全国计算机等级考试《二级C语言程序设计》真题[视频讲解]
　2013年9月全国计算机等级考试《二级C语言程序设计》真题及详解
　2013年3月全国计算机等级考试《二级C语言程序设计》真题及详解
　2012年9月全国计算机等级考试《二级C语言程序设计》真题及详解
　2012年3月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
　2011年9月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
　2011年3月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
　2010年9月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
　2010年3月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
　2009年9月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
　2009年3月全国计算机等级考试《二级C语言程序设计》笔试真题[视频讲解]
                                                                                                                                    本书更多内容>>
                                                                                                                                                                                                                    使用说明                                                                                                   
                                                                                    

内容预览
教材精讲部分[视频讲解]
第一部分　公共基础知识[视频讲解]
考试形式
1．公共基础知识不单独考试，与其他二级科目组合在一起,作为二级科目考核内容的一部分。
2．考试方式为上机考试，10道选择题，占10分。
大纲基本要求

1．掌握算法的基本概念。
2．掌握基本数据结构及其操作。
3．掌握基本排序和查找算法。
4．掌握逐步求精的结构化程序设计方法。
5．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。
6．掌握数据库的基本知识，了解关系数据库的设计。
知识点分布
1．数据结构与算法
2．程序设计基础
3．软件工程基础
4．数据库设计基础
第1章　数据结构与算法[视频讲解]
本章考点
1．算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3．线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4．栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5．线性单链表、双向链表与循环链表的结构及其基本运算。
6．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7．顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。
第一节　算　法

一、算法的基本概念
1．算法的定义
算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。
*算法不等于程序，也不等于计算方法。
2．算法的基本特征
（1）可行性（Effectiveness）
①算法中的每一个步骤必须能够实现。
②算法执行的结果要能够达到预期的目的。
（2）确定性（Definiteness）
算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。
（3）有穷性（Finiteness）
算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
*算法的有穷性还应包括合理的执行时间
（4）拥有足够的情报
①输入是否足够并正确，输出是否合理。
②初始状态是否正确。
二、算法设计基本方法
1．列举法
（1）基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
（2）特点
简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。
（3）使用
将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。
例1.1 今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各几何？
假设买母鸡I只、公鸡J只、小鸡K只。根据题意，粗略的列举算法描述如下：
FOR I=0 TO 100 STEP 1 DO
FOR J=0 TO 100 STEP 1 DO
FOR K=0 TO 100 STEP 1 DO
{
IF（（I+J+K==100）AND（　　3*I+2*J+0.5*K==100.0））THEN
PRINT I，J，K
}
END
共有三层循环，每层循环各需要循环101次，大约为100万次。
优化后的算法
FOR I=0 TO 33 STEP 1DO
FOR J=0 TO 50-1.5*I STEP 1 DO
{
K=100-I-J
IF（3*I+2*J+0.5*K==100.0）THEN
PRINT I，J，K
}
END
共有两层循环，循环次数为

2．归纳法
（1）基本思想
通过列举少量的特殊情况，经过分析最后找出一般的关系。
（2）特点
归纳是一种抽象，即从特殊现象中找出一般关系。
（3）使用
由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。
3．递推
（1）基本思想
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
（2）特点
本质上属于归纳法，递推关系式往往是归纳的结果。
（3）使用
递推算法在数值计算中是极为常见的。但
是，对于数值型的递推算法必须要注意数值计算的稳定性问题。
4．递归 *
（1）基本思想
为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。
（2）特点
结构清晰，可读性强。
（3）使用
递归在可计算性理论和算法设计中占有很重要的地位。
（4）分类
直接递归（自己调用自己）和间接递归（P调用Q，Q又调用P）。
例1.2　编写一个过程，对于输入的参数n，依次打印输出自然数1到n。
非递归算法：
wrt（intn）
{
FOR k=1 TO n STEP 1 DO PRINT k
RETURN
}
递归算法：
wrt1（intn）
{
IF（n≠0）THEN
{
wrt1（n-1）PRINT n
}
RETURN
}
5．减半递推技术
所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
例1.3　设方程f（x）=0在区间[a，b]上有实根，且f（a）与f（b）异号。利用二分法求该方程在区间[a，b]上的一个实根。
用二分法求方程实根的减半递推过程如下：
首先取给定区间的中点c=（a+b）／2。
然后判断f（c）是否为0。
若f（c）=0，则说明C即为所求的根，求解过程结束；
如果f（c）≠0，则根据以下原则将原区间减半：
若f（a）f（c）i | l≤i≤n+1}=n
注：当算法的计算工作量与输入无关时，即当规模为n时，在所有可能的输入下，算法所执行的基本运算次数是一定的，此时有A(n)=W(n)。
2．算法的空间复杂度
定义：执行这个算法所需要的内存空间。
（1）算法程序所占的空间；
（2）输入的初始数据所占的存储空间；
（3）算法执行过程中所需要的额外空间。
*如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。
*在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。



第二节　数据结构的基本概念

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
（3）对各种数据结构进行的运算。
讨论以上问题的目的：
（1）提高数据处理的速度；
（2）尽量节省在数据处理过程中所占用的计算机存储空间。
一、什么是数据结构
定义：数据结构是指相互有关联的数据元素的集合。
数据元素具有广泛的含义：
描述一年四季的季节名：春、夏、秋、冬
表示数值的各个数：18、11、35、23、16…
表示家庭成员的各成员名：父亲、儿子、女儿
数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
*作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。
1．数据的逻辑结构
（1）定义
反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：
①表示数据元素的信息；
②表示各数据元素之间的前后件关系。
（2）数据的逻辑结构有两个要素：
一是数据元素的集合，通常记为D；
二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R；
即一个数据结构可以表示成B=（D，R）。
例1.5 一年四季的数据结构可以表示成
B=（D，R）
D={春，夏，秋，冬}
R={（春，夏），（夏，秋），（秋，冬）}
例1.6　家庭成员数据结构可以表示成
B=（D，R）
D={父亲，儿子，女儿}
R={（父亲，儿子），（父亲，女儿）}
例1.7 n维向量X=（x1，x2，…，xn）也是一种数据结构。即X=（D，R），
其中数据元素的集合为：D={x1，x2，…，xn}
关系为：R={（x1，x2），（x2，x3），…，（xn-1，xn）}
*对于一些复杂的数据结构来说，它的数据元素可以是另一种数据结构。
例如，m×n的矩阵

是一个数据结构。在这个数据结构中，矩阵的每一行
Ai=（ai1，ai2，…，ain），i=1，2，…，m
可以看成是它的一个数据元素。即这个数据结构的数据元素的集合为D={A1，A2，…，Am}
D上的一个关系为
R={（A1，A2），（A2，A3），…，（Ai，Ai+1），…，（Am-1，Am）}
显然，数据结构A中的每一个数据元素：
Ai（i=1，2，…，m）
又是另一个数据结构,即数据元素的集合为：
Di={ai1，ai2，…，ain}
Di上的一个关系为：
Ri={（ai1，ai2），（ai2，ai3），…，（aij，ai，j+1），…，（ai，n-1，ain）}
2．数据的存储结构
定义：数据的逻辑结构在计算机存储空间中的存放形式。
*各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
*在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
*常用的存储结构有顺序、链接、索引等存储结构。
*采用不同的存储结构，其数据处理的效率是不同的。
二、数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观地用图形表示。
（1）对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；
（2）对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。

图1-1一年四季数据结构的图形表示图　 　1-2家庭成员间辈分关系数据结构的图形表示
例1.8 用图形表示数据结构B=(D，R)，其中
D={di|1≤i≤7}_{d1，d2，d3，d4，d5，d6，d7}
R={（d1，d3），（d1，d7），（d2，d4），（d3，d6），（d4，d5）}
在数据结构中，没有前件的结点称为根结
点；没有后件的结点称为终端结点（也称为叶子结点）。

图1.3　例1.8数据结构的图形表示
三、线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，线性结构又称线性表。
*在一个线性结构中插入或删除任何一个结点后还应是线性结构。

图1.4　不是线性结构的数据结构特例
如果一个数据结构不是线性结构，则称之为非线性结构。
*线性结构与非线性结构都可以是空的数据结构。
*一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。
*如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。
第三节　线性表及其顺序存储结构

一、线性表的基本概念
线性表（Linear List）是最简单、最常用的一种数据结构。
如：一个n维向量、矩阵，学生情况登记表；
综上所述，线性表是由n（n≥0）个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a1，a2，…，ai，…，an）其中ai（i=1，2，…，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。
非空线性表有如下一些结构特征：
（1）有且只有一个根结点a1它无前件；
（2）有且只有一个终端结点an，它无后件；
（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
*线性表中结点的个数n称为线性表的长度。
*当n=0时，称为空表。
二、线性表的顺序存储结构
1．特点
（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。

图1.5线性表的顺序存储结构
*在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
*在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。
2．在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有以下几种：
（1）在线性表的指定位置处加入一个新的元素（即线性表的插入）；
（2）在线性表中删除指定的元素（即线性表的删除）；
（3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）；
（4）对线性表中的元素进行整序（即线性表的排序）；
（5）按要求将一个线性表分解成多个线性表（即线性表的分解）；
（6）按要求将多个线性表合并成一个线性表（即线性表的合并）；
（7）复制一个线性表（即线性表的复制）；
（8）逆转一个线性表(即线性表的逆转)等。
三、顺序表的插入运算
例1.9　图1.6（a）为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素（即18）之前插入一个新元素87。然后在线性表的第9个元素之前插入一个新元素14。

图1.6　线性表在顺序存储结构下的插入
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（i表示在第i个元素之前插入），插入新元素。则插入的过程如下：
（1）首先处理以下三种异常情况：
*当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结束；
*当i>n时，认为在最后一个元素之后（第n+1个元素之前）插入；
*当in时，错误，不能进行删除，算法结束；
（2）删除线性表中的第i个元素；
（3）然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置；
（4）最后将线性表的长度减小1。
*由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适
的，因为顺序存储的结构比较简单。
*但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。
第四节　栈和队列

一、栈及其基本运算
1．什么是栈
定义：限定在一端进行插入与删除的线性表
*在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。用指针top来指示栈顶的位置，用指针bottom指向栈底。
*栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。
*栈具有记忆作用。
*往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。
计算机系统在处理时要用一个线性表来动态记忆调用过程中的路径，其基本原则如下：
（1）在开始执行程序前，建立一个线性表，初始状态为空；
（2）发生调用时，将当前调用的返回点地址插入到线性表的末尾；
（3）当遇到从某个子程序返回时，其返回点地址从线性表的末尾取出（即删除线性表的最后一个元素）。

图1.9　栈示意图
图1.8中给出了具有嵌套调用关系的五个程序，其中主程序要调用子程序SUB1，SUB1要调用子程序SUB2，SUB2要调用子程序SUB3，SUB3要调用子程序SUB4，SUB4不再调用其他子程序了。

图1.8主程序与子程序之间的调用关系
图1.8中五个程序在执行过程中的调用顺序以及线性表中元素变化的情况如下：
（1）主程序开始执行前，建立一个空线性表。即线性表的状态为（）。
（2）开始执行主程序MAIN。当要调用子程序SUB1时，先将本次调用的返回点地址A插入到线性表的末尾。此时，线性表的状态为（A）。
（3）开始调用执行子程序SUB1。当要调用子程序SUB2时，先将本次调用的返回点地址B插入到线性表的末尾。此时,线性表的状态为（A，B）。
（4）开始调用执行子程序SUB2。当要调用子程序SUB3时，先将本次调用的返回点地址C插入到线性表的末尾。此时，线性表的状态为(A,B,C)。
（5）开始调用执行子程序SUB3。当要调用子程序SUB4时，先将本次调用的返回点地址D插入到线性表的末尾。此时，线性表的状态为（A，B，C，D）。
由上述逐步调用的过程可以看出，每次发生调用时，都需要将当前调用的返回点地址插入到线性表的末尾，而这种对线性表的插入操作是不需要移动线性表中原有元素的。并且，各返回点地址在线性表中的存放顺序恰好是调用顺序。
（6）开始调用执行子程序SUB4。由于子程序SUB4不再调用其他子程序，执行完子程序SUB4后要返回到子程序SUB3的地址D处。其中返回点地址D取自线性表的最后一个元素。取出D后，线性表的状态为（A，B，C）。
（7）返回到子程序SUB3的D处继续执行，执行完子程序SUB3后要返回到子程序SUB2的地址C处。其中返回点地址C取自线性表的最后一个元素。取出C后，线性表的状态为（A，B）。
（8）返回到子程序SUB2的C处继续执行，执行完子程序SUB2后萋返回到子程序SUB1的地址B处。其中返回点地址、取自线性表的最后一个元素。取出B后，线性表的状态为（A）。
（9）返回到子程序SUB1的B处继续执行，执行完子程序SUB1后要返回到主程序MAIN的地址A处。其中返回点地址A取自线性表最后一个元素。取出A后，线性表变空，即线性表的状态为（）。
（10）返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完成。
由上述逐步返回的过程可以看出，当由子程序返回到上一个调用程序时，需要从线性表的末尾取出返回点地址，即从线性表中删除最后一个元素，而这种对线性表的删除操作也是不需要移动线性表中其他数据元素的。
2．栈的顺序存储及其运算
图1.10（a）是容量为10的栈顺序存储空间，栈中已有6个元素；图1.10（b）与图1.10（c）分别为入栈与退栈后的状态。

图1.10　栈在顺序存储结构下的运算
在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素(在栈非空的情况下)，S（top）为栈顶元素。
top=0表示栈空；top=m表示栈满。
栈的基本运算有三种：入栈、退栈与读栈顶元素。
（1）入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程如下：
①首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
②然后将栈顶指针进一（即top加1）。
③最后将新元素x插入栈顶指针指向的位置。
（2）退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
②然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
③最后将栈顶指针退一（即top减1）。
（3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
②然后将栈顶元素赋给指定的变量y。
必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。
二、队列及其基本运算
1．什么是队列
在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：
①初始时线性表为空；
②当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；
③当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。
由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。
定义：队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。
*允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（Front）指向排头元素的前一个位置。
*在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。
*在队列中，队尾指针 rear与排头指针front共同反映了队列中元素动态变化的情况。

图1.11　具有6个元素的队列示意图


图1.12　队列运算示意图
2．循环队列及其运算
定义：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
*在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
*循环队列的初始状态为空，即rear=front=m，如图1.13所示。

图1.13　循环队列存储空间示意图
循环队列主要有两种基本运算：入队运算与退队运算。
每进行一次入队运算，队尾指针就进一。当队尾指针 rear=m+1时，则置rear=1。
每进行一次退队运算，排头指针就进一。当排头指针 front=m+1时，则置front=1。

图1.14　循环队列运算例
*当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满还是队列空。
在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：

由此可以得出队列空与队列满的条件如下：
队列空的条件为s=0；
队列满的条件为s=1且front=rear。
假设循环队列的初始状态为空，即：s=0，且front=rear=m。
（1）入队运算
入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：
①首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。
②然后将队尾指针进一（即rear=rear+1），并当rear=m+1时置rear=1。
③最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。
（2）退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
①首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。
②然后将排头指针进一（即front=front+1），并当front=m+1时置front=1。
③再将排头指针指向的元素赋给指定的变量
④最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（即s=0）。


第五节　线性链表

一、线性链表的基本概念
*线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。
*线性表的顺序存储结构存在的缺点：
（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。
（2）当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。
（3）线性表的顺序存储结构不便于对存储空间的动态分配。
因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。
*假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
*在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。
*在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
*链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。
1．线性链表
定义：线性表的链式存储结构称为线性链表。
为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。

图1.15线性链表的存储空间
为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。

图1.16线性链表的一个存储结点
*在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。

图1.17线性链表的逻辑结构
*在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。
*当HEAD= NULL（或0）时称为空表。

图1.18线性链表例
*在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。
因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。
为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。这样的线性链表称为双向链表。

图1.19双向链表示意图
2．带链的栈
栈也是线性表，也可以采用链式存储结构。

图1.20带链的栈
在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

图1.21可利用栈及其运算
与顺序栈一样，带链栈的基本操作有以下几个：
①栈的初始化。即建立一个空栈的顺序存储空间。
②入栈运算。是指在栈顶位置插入一个新元素。
③退栈运算。是指取出栈顶元素并赋给一个指定的变量。
④读栈顶元素。是指将栈顶元素赋给一个指定的变量。
3．带链的队列
队列也是线性表,也可以采用链式存储结构。

图1.22带链的队列及其运算
与顺序队列一样，带链队列的基本操作有以下几个：
①队列的初始化。即建立一个空队列的顺序存储空间。
②入队运算。是指在循环队列的队尾加入一个新元素。
③退队运算。是指在循环队列的排头位置退出一个元素并赋给指定的变量。
二、线性链表的基本运算
线性链表的运算主要有以下几个：
①在线性链表中包含指定元素的结点之前插入一个新元素。
②在线性链表中删除包含指定元素的结点。
③将两个线性链表按要求合并成一个线性链表
④将一个线性链表按要求进行分解。
⑤逆转线性链表。
⑥复制线性链表。
⑦线性链表的排序。
⑧线性链表的查找。
1．在线性链表中查找指定元素
在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。
因此，由这种方法找到的结点p有两种可能：
*当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；
*当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。
2．线性链表的插入
（1）定义
在链式存储结构下的线性表中插入一个新元素。
（2）插入过程
①从可利用栈取得一个结点，设该结点号为p（即取得结点的存储序号存放在变量p中），并置结点p的数据域为插入的元素值b。
②在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。
③最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：
a．使结点P指向包含元素x的结点（即结点q的后件结点）。
b．使结点q的指针域内容改为指向结点p。

（a）原来的可利用栈与线性链表

（b）从可利用栈取得结点p，在线性链表中找到包含元素x的前一个结点q

（c）p插入到q之后
图1.23　线性链表的插入
*只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。
*可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。
*线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。
3．线性链表的删除
（1）定义：在链式存储结构下的线性表中删除包含指定元素的结点。
（2）删除过程
①在线性链表中寻找包含元素x的前一个结点，设该结点序号为q。
②将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点。
③将包含元素x的结点p送回可利用栈。此时，线性链表的删除运算完成。

（c）将被删除的结点p送回可利用栈后
图1.24　线性链表的删除
*在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。
*当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将该空闲结点送回到可利用栈。
三、循环链表
前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。
1．循环链表的特点
（1）在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
2．循环链表与线性单链表相比主要有以下两个方面的优点：
（1）在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。线性单链表做不到这一点。
（2）由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。

（a）非空循环链表


（b）空循环链表
图1.25　循环链表的逻辑状态
第六节　树与二叉树

一、树的基本概念
定义：树（Tree）是一种简单的非线性结构，树中所有数据元素之间的关系具有明显的层次特性。

图1.26一般的树

图1.27学校行政层次结构树


图1.28书的层次结构树
*在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。
*在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
*在树结构中，一个结点所拥有的后件个数称为该结点的度。
*在树中，所有结点中的最大的度称为树的度。

*树中的结点数=树中所有结点的度之和+1。
*根结点在第1层。同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。
在计算机中，可以用树结构来表示算术表达式。
用树来表示算术表达式的原则如下：
①表达式中的每一个运算符在树中对应一个结点，称为运算符结点。
②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。
③运算对象中的单变量均为叶子结点。
*表示一个表达式的表达式树是不唯一的。
a*（b+e／d）+e*h-g*f（s，t，x+y）

（a）表达式树之一

（b）表达式树之二
树在计算机中通常用多重链表表示。
*多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（指针域）个数将随树中该结点的度而定。

图1.30树链表中的结点结构
二、二叉树及其基本性质
1．什么是二叉树
二叉树具有以下两个特点：
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
*在二叉树中，每一个结点的度最大为2。

图1.31二叉树例
2．二叉树的基本性质
性质1　在二叉树的第k层上，最多有2k-1（k≥1）个结点。
性质2　深度为m的二叉树最多有2m-1个结点。
21-1+22-1+…+2m-1=2m-1
性质3　在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
二叉树中总的结点数为　n=n0+n1+n2（1）
进入分支的总数为m　n=m+1（2）
总的射出分支数应与总的进入分支数相等　　　m=n1+2n2（3）
n=n1+2n2+1（4）
　n0+n1+n2=n1+2n2+1
　n0=n2+1
性质4　具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分。
3．满二叉树与完全二叉树
（1）满二叉树
定义：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
*在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。

（a）深度为2的满二叉树（b）深度为3的满二叉树（c）深度为4的满二叉树
图1.32满二叉树
（2）完全二叉树
定义：所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。
*对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为P，则其左分支下的子孙结点的最大层次或为P，或为P+1。

图1.33完全二叉树
*满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
完全二叉树还具有以下两个性质：
性质5　具有n个结点的完全二叉树的深度为[log2n]+1。
性质6 　设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT（k／2）。
②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
三、二叉树的存储结构
在计算机中,二叉树通常采用链式存储结构。
*用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。
*用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。

图1.34二叉树存储结点的结构


图1.35二叉树的链式存储结构
*对于满二叉树与完全二叉树来说，可以按层序进行顺序存储，这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。
四、二叉树的遍历
定义：二叉树的遍历是指不重复地访问二叉树中的所有结点。
*在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。
1．前序遍历（DLR）
定义：在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
二叉树前序遍历的简单描述：
若二叉树为空，则结束返回。 否则：
①访问根结点；
②前序遍历左子树；
③前序遍历右子树。
2．中序遍历（LDR）
定义：在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
下面是二叉树中序遍历的简单描述：
若二叉树为空，则结束返回。
否则：
①中序遍历左子树；
②访问根结点；
③中序遍历左子树。
3．后序遍历（LRD）
定义：所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
下面是二叉树后序遍历的简单描述：
若二叉树为空，则结束返回。

否则：
①后序遍历左子树；
②后序遍历右子树；
③访问根结点。
前序序列： F，C，A，D，B，E，G，H，P
中序序列： A，C，B，D，F，E，H，G，P
后序序列： A，B，D，C，H，P，G，E，F
*如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树。
*如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。
*但如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。
例如，假设某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG，则二叉树的回复过程如下：

图1.36二叉树的恢复过程



第七节　查找技术

定义：查找是指在一个给定的数据结构中查找某个指定的元素。
一、顺序查找
顺序查找又称顺序搜索。其基本方法如下：
（1）从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；
（2）若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。
比较次数(假设线性表的长度为n)：
最好情况：第一个元素即是要查找的元素，比较一次；
最坏情况：被查找元素是线性表中的最后一个元素或者不在线性表中，比较n次；
平均情况：大约与线性表中的一半元素进行比较。
*虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：
①如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
二、二分法查找
二分法查找（又称对分查找）只适用于顺序存储的有序表。
设有序线性表的长度为n，被查元素为x，则二分查找的方法如下：
（1）将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束。
（2）若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。
（3）若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
（4）这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
*显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。
可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较[log2n]+1次，而顺序查找需要比较n次。

第八节　排序技术

定义：将一个无序序列整理成按值非递减顺序排列的有序序列。
在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。
一、交换类排序法
定义：借助数据元素之间的互相交换进行排序的一种方法。
*冒泡排序法与快速排序法都属于交换类的排序方法。
1．冒泡排序法
（1）定义
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。
（2）排序过程
①首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。
②然后，从后到前扫描剩下的线性表,同样,在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。
③对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有
序。
*在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。

图1.37冒泡排序过程示意图
（3）性能分析
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n（n-1）／2。但这拿工作量不是必需的，一般情况下要小于这个工作量。
2．快速排序法
（1）定义
快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
（2）基本思想
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。
通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。

图1.38快速排序示意图
（3）排序过程
①首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P（k），并将P（k）赋给T，再将表中的第一个元素移到P（k）的位置上。
②然后设置两个指针i和i分别指向表的起始与最后的位置。反复操作以下两步：
a．将j逐渐减小，并逐次比较P（j）与T，直到发现一个P（j）T为止，将P（i）移到P（j）的位置上。
③上述两个操作交替进行，直到指针i与j指向同一个位置（即i=j）为止，此时将T移到P（i）的位置上。
*在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。
*快速排序可以设计成一个递归算法。
（4）性能分析
快速排序在最坏情况下需要进行n（n-1）／2次比较，但实际的排序效率要比冒泡排序高得多。
二 、插入类排序法
1．简单插入排序法
（1）定义
将无序序列中的各元素依次插入到已经有序的线性表中。
一般来说，假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中。
（2）插入过程
首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。

图1.39简单插入排序示意图
（3）性能分析
在最坏情况下，简单插入排序需要n（n-1）／2次比较。
2．希尔排序法
（1）定义
希尔排序法（Shell Sort）属于插入类排序，但它对简单插入排序做了较大的改进。
（2）排序过程
将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：
①将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。
②增量序列一般取ht=n／2k（k=1，2，…，[log2n]），其中n为待排序序列的长度。

图1.40希尔排序法示意图
（3）性能分析
希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为0（n1.5）。
三、选择类排序法
1．简单选择排序法
（1）排序过程
①扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；
②然后对剩下的子表采用同样的方法，直到子表空为止。

　
图1.41简单选择排序法示意图
（2）性能分析
简单选择排序法在最坏情况下需要比较n（n-1）／2次。
2．堆排序法
（1）堆的定义
具有n个元素的序列（h1，h2，…，hn），当且仅当满足

(i=1，2，…，n／2)时称之为堆。本节只讨论满足前者条件的堆。
（2）堆的表示
在实际处理中，可以用一维数组H（1:n）来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。

图1.42　堆顶元素为最大的堆
在一棵具有n个结点的完全二叉树[用一维数组H（1:n）表示]中，假设结点H（m）的左右子树均为堆，现要将以H（m）为根结点的子树也调整为堆。这是调整建堆的问题。

图1.43调整建堆示意图
*在调整建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。
*有了调整建堆的算法后，就可以将一个无序序列建成为堆。
假设无序序列H（1:n）以完全二叉树表示。
从完全二叉树的最后一个非叶子结点（即第n／2个元素）开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆，最后就可以得到与该序列对应的堆。
（3）堆排序的方法
①首先将一个无序序列建成堆。
②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（2）步，直到剩下的子序列为空为止。
习题解析
1．算法的时间复杂度是指（　　）。
A．执行算法程序所需要的时间
B．算法程序的长度
C．算法执行过程中所需要的基本运算次数
D．算法执行过程中所需要的所有运算次数
E．算法程序中的指令条数
【答案】C查看答案
2．算法的空间复杂度是指（　　）。
A．算法程序的长度
B．算法程序中的指令条数
C．算法程序所占的存储空间
D．算法执行过程中所需要的存储空间
E．算法所处理的数据量
【答案】D查看答案
3．下列叙述中正确的是（　　）。
A．线性表是线性结构
B．栈与队列是非线性结构
C．循环链表是非线性结构
D．二叉树是线性结构
【答案】A查看答案
4．数据的存储结构是指（　　）。
A．数据所占的存储空间量
B．数据的逻辑结构在计算机中的表示
C．数据在计算机中的顺序存储方式
D．存储在外存中的数据
【答案】B查看答案
5．下列关于队列的叙述中正确的是（　　）。
A．在队列中只能插入数据
B．在队列中只能删除数据
C．队列是先进先出的线性表
D．队列是先进后出的线性表
【答案】C查看答案
6．下列关于栈的叙述中正确的是（　）。
A．在栈中只能插入数据
B．在栈中只能删除数据
C．栈是先进先出的线性表
D．栈是先进后出的线性表
E．栈是一种非线性结构
【答案】D查看答案
7．设有下列二叉树：

对此二叉树进行中序遍历的结果为(　　)。
A．ABCDEF
B．DBEAFC
C．ABDECF
D．DEBFCA
【答案】B查看答案
8．在深度为5的满二叉树中，叶子结点的个数为（　　）。
A．32
B．31
C．16
D．15
【答案】C查看答案
9．设一棵二叉树的中序序列为DBEAFC，前序序列为ABDECF，则后序序列为（　　）。
A．ABCDEF
B．FEDCBA
C．DEBFCA
【答案】C查看答案
10．设一棵完全二叉树共有700个结点，则该完全二叉树中的叶子结点数为（　　）。
A．351
B．350
C．349
D．348
【答案】B查看答案
n2=n0-1n1=0或1
n0+n1+n2=700　2*n0-1+1=700
11．对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（　　）。
A．n+1
B．n
C．（n+1）／2
D．n／2
【答案】B查看答案
12．在长度为n的线性表中寻找最大项，在最坏情况下所需要的比较次数为（　　）。
A．n+1
B．n-1
C．n
D．n／2
【答案】B查看答案
13．设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则树T中的叶子结点数为（　　）。
A．8
B．7
C．6
D．5
【答案】A查看答案
【解析】结点数为所有结点的度数之和加1 , 同时注意到叶子结点的度数为0 则总结点数(设叶子结点数为X)1*4+2*2+3*1+4*1+X*0+1=16，叶子结点数为X=16-4-2-1-1=8。
14．在长度为n的有序线性表中进行二分查找，在最坏情况下所需要的比较次数为(　　)。
A．n-1
B．n／2
C．（n-1）／2
D．O(log2n)
【答案】D查看答案
15．下列排序法中，在最坏情况下时间复杂度最小的是（　　）。
A．快速排序
B．希尔排序
C．堆排序
【答案】C查看答案
16．设循环队列为Q（1:m），其初始状态为front=rear=m。经过一系列入队与退队运算后，front=30，rear=10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（　　）。
A．19
B．20
C．m-19
D．m-20
【答案】D查看答案
17．设数据集合为D={1，3，5，7，9}，D上的关系为R。下列数据结构B=（D，R）中为非线性结构的是（　　）。
A．R={（5，1），（7，9），（1，7），（9，3）}
B．R={（9，7），（1，3），（7，1），（3，5）}
C．R={（1，9），（9，7），（7，5），（5，3）}
D．R={（1，3），（3，5），（5，9）}
【答案】D查看答案

下载地址:http://free.100xuexi.com/Ebook/126123.html