二级Web程序设计专用教材.docx
- 文档编号:14534186
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:350
- 大小:1.47MB
二级Web程序设计专用教材.docx
《二级Web程序设计专用教材.docx》由会员分享,可在线阅读,更多相关《二级Web程序设计专用教材.docx(350页珍藏版)》请在冰点文库上搜索。
二级Web程序设计专用教材
目 录
第一部分 公共基础知识
第1章 数据结构与算法
考纲分析
1.算法的基本概念,算法复杂度的概念和意义(时间复杂度与空间复杂度)。
2.数据结构的定义,数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。
3.线性表的定义,线性表的顺序存储结构及其插入与删除运算。
4.栈和队列的定义,栈和队列的顺序存储结构及其基本运算。
5.线性单链表、双向链表与循环链表的结构及其基本运算。
6.树的基本概念,二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。
7.顺序查找与二分法查找算法,基本排序算法(交换类排序,选择类排序,插入类排序)。
考点精讲
1.1 算 法
考点1算法的基本概念
(1)算法的定义
算法是指解题方案的准确而完整的描述,即算法是对特定问题求解步骤的一种描述。
它是一组严谨定义运算顺序的规则,且每个规则都是明确有效的,此顺序将在有限的次数下终止。
需要注意的是:
算法不等于程序,也不等于计算方法。
(2)算法的基本特征
①可行性
a.算法中的每一步骤都必须能够实现;
b.算法执行的结果要能够达到预期的目的。
②确定性
确定性是指算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释,也不允许有多义性。
③有穷性
有穷性是指算法必须能在有限的时间内做完,即必须能在执行有限个步骤之后终止,且必须有合理的执行时间。
④拥有足够的情报
算法是否有效,取决于为算法所提供的情报是否足够。
一般而言,当算法有足够的情报时,此算法有效,而当提供的情报不够时,算法可能无效。
【真题演练】
算法的有穷性是指()。
[2013年9月真题]
A.算法程序的运行时间是有限的
B.算法程序所处理的数据量是有限的
C.算法程序的长度是有限的
D.算法只能被有限的用户使用
【答案】A
【解析】算法设计有穷性要求操作步骤有限且必须在有限时间内完成,耗费太长时间得到的正确结果是没有意义的。
考点2算法设计基本方法
(1)列举法
①基本思想
根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。
常用于解决“是否存在”或“有多少种可能”等类型的问题。
②主要特点
算法比较简单,但列举情况较多时,算法工作量很大。
③注意事项
例举算法时,通过对实际问题进行详细分析,将与问题有关的知识条理化、完备化、系统化,并从中找出规律,或对所有可能的情况进行分类,从而引出一些有用的信息,减少列举量。
(2)归纳法
①基本思想
通过列举少量的特殊情况,经过分析,最后找出一般的关系。
②主要特点
a.比列举法更能反映问题的本质,可解决列举量为无限的问题;
b.可操作性低,不易归纳出一个具体数学模型;
c.归纳得出的结论只是一种猜测,须对这种猜测加以必要的证明。
(3)递推
①基本思想
从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。
②主要特点
a.初始条件或问题本身已给定,或通过对问题的分析化简得到;
b.递推本质上属于归纳法,递推关系式往往是归纳的结果;
c.数值型递推算法计算过程中必须注意数值计算的稳定性问题。
(4)递归
①基本思想
将复杂问题逐层分解,归结为一些简单的问题,将简单问题解决掉,再沿着原来分解的逆过程逐步进行综合。
②主要特点
a.递归的基础是归纳,对问题逐层分解的过程实际上并没有对问题进行求解;
b.在可计算性理论和算法设计中占有重要地位;
c.递归算法比递推算法清晰易读,结构简练;
d.设计递归算法比递推算法容易,但是其执行效率较低。
③分类
a.直接递归。
一个算法P显式地调用自己。
b.间接递归。
算法P调用另一个算法Q,而算法Q又调用算法P。
④递归与递推的区别
递归与递推的区别主要在于二者实现方法的不同,表现为:
a.递归是从算法本身到达递归的边界的;
b.递推是从初始条件出发,逐次推出所需求的结果。
(5)减半递推技术
减半递推技术是工程上常用的分治法,其中,“减半”指将问题的规模减半,而问题的性质不变;“递推”指重复“减半”的过程。
(6)回溯法
回溯法是指通过对问题的分析,找出一个解决问题的线索,然后沿着这个线索逐步试探,若试探成功,则问题得到解决,若试探失败,则逐步回退换别的路线再进行试探。
【真题演练】
1.下列叙述中正确的是()。
[2013年9月真题]
A.所谓算法就是计算方法
B.程序可以作为算法的一种描述方法
C.算法设计只需考虑得到计算结果
D.算法设计可以忽略算法的运算时间
【答案】B
【解析】程序可以作为算法的一种描述方法,算法在实现时需要用具体的程序设计语言描述。
A项错误,算法并不等同于计算方法,是指对解题方案的准确而完整的描述;C项错误,算法设计需要考虑可行性、确定性、有穷性与足够的情报;D项错误,算法设计有穷性要求操作步骤有限且必须在有限时间内完成,耗费太长时间得到的正确结果是没有意义的。
2.下列关于算法的描述中错误的是()。
[2014年3月真题]
A.算法强调动态的执行过程,不同于静态的计算公式
B.算法必须能在有限个步骤之后终止
C.算法设计必须考虑算法的复杂度
D.算法的优劣取决于运行算法程序的环境
【答案】D
【解析】算法是指对解题方案的准确而完整的描述。
A项正确,算法强调实现,不同于数学上的计算方法;B项正确,算法的有穷性是指,算法中的操作步骤为有限个,且每个步骤都能在有限时间内完成;C项正确,算法设计必须考虑执行算法所需要的资源,即时间复杂度与空间复杂度;D项错误,算法的优劣取决于算法复杂度,只有当算法被编程实现运行时才会受到运行环境影响。
考点3算法复杂度
(1)时间复杂度
①定义
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即
算法的工作量=f(n)
其中,n是问题的规模。
②在同一问题规模下,若算法的基本运算次数取决于某一特定输入,可用以下两种方法来分析算法的工作量:
a.平均性态
平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
算法的平均性态定义为:
其中,x是所有可能输入中的某个特定输入,p(x)是x出现的概率,即输入为x的概率,t(x)是算法在输入为x时所执行的基本运算次数,Dn表示当规模为n时,算法执行时所有可能输入的集合。
b.最坏情况复杂性
最坏情况分析是指规模为n时,算法所执行的基本运算的最大次数。
其定义为:
(2)空间复杂度
①定义
算法的空间复杂度一般是指执行这个算法所需要的内存空间。
②存储空间组成
一个算法的存储空间包括以下几种:
a.算法程序占用的空间;
b.输入的初始数据占用的存储空间;
c.算法执行过程中所需要的额外空间。
额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间,若额外空间相对于问题规模来说是常数,则称该算法是原地工作的。
【真题演练】
1.下列叙述中正确的是()。
[2015年3月真题]
A.算法的效率只与问题的规模有关,而与数据的存储结构无关
B.算法的时间复杂度是指执行算法所需要的计算工作量
C.数据的逻辑结构与存储结构是一一对应的
D.算法的时间复杂度与空间复杂度一定相关
【答案】B
【解析】算法的时间复杂度是指算法在计算机内执行时所需时间的度量;与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。
2.算法的空间复杂度是指()。
[2013年9月真题]
A.算法在执行过程中所需要的计算机存储空间
B.算法所处理的数据量
C.算法程序中的语句或指令条数
D.算法在执行过程中所需要的临时工作单元数
【答案】A
【解析】空间复杂度是是对一个算法在运行过程中临时占用存储空间大小的量度。
3.算法空间复杂度的度量方法是()。
[2014年9月真题]
A.算法程序的长度
B.算法所处理的数据量
C.执行算法所需要的工作单元
D.执行算法所需要的存储空间
【答案】D
【解析】算法的空间复杂度包括:
①输入数据所占的存储空间;②程序本身所占的存储空间;③算法执行过程中所需要的额外空间,是指执行这个算法所需要的内存空间,
1.2 数据结构的基本概念
考点1概述
(1)数据处理概述
①定义
数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。
②关键问题
大量数据元素在计算机中如何组织,以便提高数据处理的效率,从而节省计算机的存储空间,这是进行数据结构处理的关键问题。
(2)数据结构研究概述
①研究问题
a.数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
b.在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
c.对各种数据结构进行的运算。
②研究目的
数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率,包括:
a.提高数据处理的速度;b.尽量节省在数据处理过程中所占用的计算机存储空间。
考点2数据结构的概念
(1)数据结构的定义
数据结构是指相互有关联的数据元素的集合,即它是反映数据元素之间关系的数据元素集合的表示。
简言之,数据结构是指带有结构的数据元素的集合,这里的“结构”指数据元素之间的前后件关系。
一个数据结构应包含以下两方面内容:
①表述数据元素的信息;
②表示各数据元素之间的前后件关系。
(2)数据的逻辑结构
①定义
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
②要素:
a.数据元素的集合,通常记为D;
b.D上的关系,通常记为R,它反映了D中各数据元素之间的前后件关系。
③表示
一个数据结构B可表示为:
B=(D,R)
为反映D中个数据元素之间的前后件关系,一般用二元组来表示。
(3)数据的存储结构
①定义
数据的存储结构,也称数据的物理结构,是指数据逻辑结构在计算机存储空间中的存放形式。
在数据的存储结构中,不仅要存放各数据元素的信息,而且要存放各数据元素之间的前后件信息。
②常用的存储结构:
a.顺序;b.链接;c.索引。
采用不同的存储结构,数据处理的效率是不同的。
【真题演练】
下列叙述中正确的是()。
[2014年3月真题]
A.有且只有一个根结点的数据结构一定是线性结构
B.每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构
C.有且只有一个根结点的数据结构一定是非线性结构
D.有且只有一个根结点的数据结构可能是线性结构,也可能是非线性结构
【答案】D
【解析】逻辑结构分为线性结构和非线性结构,线性结构的特征有:
①集合中必存在唯一的一个“第一个元素”;②集合中必存在唯一的一个“最后的元素”;③除第一元素之外,其它数据元素均有唯一的“前驱”;④除最后元素之外,其它数据元素均有唯一的“后继”。
D项正确,如树形结构只有一个根结点,为非线性结构。
考点3数据结构的图形表示
(1)在数据结构的图形表示中,数据集合D中每个元素用中间标有元素值的方框表示,称为数据结点(简称结点);对关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点。
(2)在数据结构中,没有前件的结点称为根结点,没有后件的结点称为终端结点(也称叶子结点),其余结点都称为内部结点。
(3)数据结构中的元素结点可能是在动态变化的,这种变化体现在结点数量的增减以及各结点之间的前后件关系的动态变化上。
考点4线性结构与非线性结构
根据数据结构中各数据元素之间的前后件关系的复杂程度,可将数据结构分为:
(1)线性结构(线性表)
一个非空的数据结构满足下列两个条件时,称其为线性结构:
①有且只有一个根结点;
②每个结点最多只有一个前件,也最多只有一个后件。
线性结构中插入或删除任何一个结点还应是线性结构,如果不满足这个条件就不能称之为线性结构。
(2)非线性结构
如果一个数据结构不是线性结构,则称之为非线性结构。
注:
线性结构与非线性结构都可以是空的数据结构。
一个空的数据结构属于线性结构还是非线性结构,需要根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。
1.3 线性表及其顺序存储结构
考点1线性表的基本概念
(1)线性表是一种最常见最简单的数据结构,由一组数据元素构成。
数据元素在线性表中的位置值只取决于它们自己的序号,即数据元素之间的相对位置是线性的。
(2)非空线性表的结构特征:
①有且只有一个根结点a1,它无前件;
②有且只有一个终端结点an,它无后件;
③除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。
当n=0时,称为空表。
【真题演练】
下列叙述中正确的是()。
[2014年9月真题]
A.结点中具有两个指针域的链表一定是二叉链表
B.结点中具有两个指针域的链表可以是线性结构,也可以是非线性结构
C.二叉树只能采用链式存储结构
D.循环链表是非线性结构
【答案】B
【解析】A项错误,具有两个指针域的链表可能是双向链表;B项正确,如双向链表是线性结构,二叉树为非线性结构,两者结点中均有两个指针域;C项错误,二叉树通常采用链式存储结构,也可采用其他结构;D项错误,循环链表是线性结构,逻辑概念线性非线性与实际存储结构无关。
考点2线性表的顺序存储结构
(1)概述
顺序存储是一种最简单的在计算机中存放线性表的方法,也称顺序分配。
(2)特点:
①线性表中所有元素所占的存储空间是连续的;
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面。
(3)运算
在线性表的顺序存储结构下,可对线性表进行以下运算:
①插入:
在线性表的指定位置处加入一个新的元素;
②删除:
在线性表中删除指定的元素;
③查找:
在线性表中查找某个(或某些)特定的元素;
④排序:
对线性表中的元素进行整序;
⑤分解:
按要求将一个线性表分解成多个线性表;
⑥合并:
按要求将多个线性表合并成一个线性表;
⑦复制:
复制一个线性表;
⑧逆转:
逆转一个线性表等。
【真题演练】
在线性表的顺序存储结构中,其存储空间连续,各个元素所占的字节数()。
[2014年3月真题]
A.相同,元素的存储顺序与逻辑顺序一致
B.相同,但其元素的存储顺序可以与逻辑顺序不一致
C.不同,但元素的存储顺序与逻辑顺序一致
D.不同,且其元素的存储顺序可以与逻辑顺序不一致
【答案】A
【解析】在顺序表中,每个元素占有相同的存储单元。
顺序表具有特征:
①线性表中所有元素所占的存储空间是连续的;②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
考点3顺序表的插入运算
假设线性表的存储空间为V(1:
m),线性表的长度为n(n≤m),插入的位置为i(表示在第i个位置插入元素),则顺序表插入新元素过程如下:
(1)首先处理以下三种异常情况:
①当存储空间已满(即n=m)时为“上溢”错误,不能进行插入,算法结束;
②当i>n时,认为在最后一个元素之后(即第n+1个元素之前)插入;
③当i<1时,认为在第1个元素之前插入。
(2)从最后一个元素开始,直到第i个元素,其中每一个元素均往后移动一个位置。
(3)最后将新元素插入到第i个位置,并且将线性表的长度增加1。
考点4顺序表的删除运算
假设线性表的存储空间为V(1:
m),线性表的长度为n(n≤m),删除的位置为i(表示删除第i个元素),则顺序表删除元素的过程如下:
(1)首先处理以下两种异常情况:
①当线性表为空(即n=0)时为“上溢”错误,不能进行插入,算法结束;
②当i<1或i>n时,认为在最后一个元素之后(即第n+1个元素之前)插入。
(2)然后从第i+1个元素开始,直到最后一个元素,其中每一个元素均依次往前移动一个位置。
(3)最后将线性表的长度减小1。
1.4 栈和队列
考点1栈及其基本运算
(1)栈的定义
栈是限定在一端进行插入与删除的线性表。
(2)栈的特点:
①允许插入和删除的一端称为栈顶,不允许插入与删除的一端称为栈底。
栈顶元素总是最后被插入的元素,也是最先被删除的元素;栈底元素总是最先被插入也是最后被删除的。
②栈遵循“先进后出”或“后进先出”的原则,具有记忆功能。
③通常用指针top来指示栈顶位置,用指针bottom指向栈底,栈顶指针top动态反映了栈中元素的变化情况。
(3)栈的顺序存储及其运算
在栈的顺序存储空间S(1:
m)中,top=0表示栈空;top=m表示栈满。
栈的三种运算:
①入栈运算
人栈运算是指在栈顶位置插入一个新元素。
操作过程如下:
a.首先判断栈顶指针是否已经指向存储空间的最后一个位置。
如果是,则说明栈空间已满,不可能再进行入栈操作(这种情况称为栈“上溢”错误),算法结束。
b.然后将栈顶指针进一(即top加1)。
c.最后将新元素x插入栈顶指针指向的位置。
②退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。
操作过程如下:
a.首先判断栈顶指针是否为0。
如果是,则说明栈空,不可能进行退栈操作(这种情况称为栈“下溢”错误),算法结束。
b.然后将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量。
c.最后将栈顶指针退一(即top减1)。
③读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。
操作过程如下:
a.首先判断栈顶指针是否为0。
如果是,则说明栈空,读不到栈顶元素,算法结束。
b.然后将栈顶元素赋给指定的变量y。
这个运算不删除栈顶元素,只是将它的值赋给一个变量,栈顶指针不会变。
【真题演练】
1.支持子程序调用的数据结构是()。
[2013年9月真题]
A.栈
B.树
C.队列
D.二叉树
【答案】A
【解析】栈和队列都是受限的线性表,其中栈按照“先进后出”的原则组织数据,插入与删除操作被限制在栈顶一端进行。
栈支持子程序调用,在主程序调用子函数时,要首先保存主程序当前的状态,然后转去执行子程序,结束调用后返回到主程序中调用子程序的位置,继续执行,这种调用符合栈的特点。
2.下列与栈结构有关联的是()。
[2013年3月真题]
A.数组的定义域使用
B.操作系统的进程调度
C.函数的递归调用
D.选择结构的执行
【答案】C
【解析】递归调用的本质就是函数调用函数本身,直到满足特定条件时才停止,然后从最后被递归调用处返回。
递归函数是通过栈来实现的,所以调用原则和栈的实现相一致。
3.设栈的顺序存储空间为S(1:
50),初始状态为top=0。
现经过一系列入栈与退栈运算后,top=20,则当前栈中的元素个数为()。
[2014年3月真题]
A.30
B.29
C.20
D.19
【答案】C
【解析】栈按照“先进后出”的原则组织数据,插入与删除操作被限制在栈顶一端进行,入栈使栈顶位置进1,退栈使栈顶退1。
top=0表示栈为空,在运算过程中,指针始终指向栈顶元素。
top=20,说明当前栈中有20个元素。
4.一个栈的初始状态为空。
现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是()。
[2013年9月真题]
A.12345ABCDE
B.EDCBA54321
C.ABCDE12345
D.54321FDCBA
【答案】B
【解析】栈中数据的插入和删除都在栈顶按照“先进后出”的原则进行操作。
考点2队列及其基本运算
(1)什么是队列
队列(Queue)是指允许在一端进行插入、而在另一端进行删除的线性表。
(2)队列的特点
①允许插入的一端称为队尾,用队尾指针指向队尾元素;允许删除的一端称为队头,用排头指针指向排头元素的前一个位置。
②最先插入的元素最先被删除,最后插入的元素最后被删除,遵循“先进先出”或“后进后出”原则。
③队尾指针rear和排头指针front共同反映队列中元素变动情况。
④入队运算指只涉及队尾指针rear变化,退队运算只涉及排头指针front变化。
(3)循环队列及其运算
循环队列是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。
在循环队列中,用队尾指针rear指向队尾元素,用排头指针front指向排头元素的前一个位置,从排头指针front指向的后一个位置到队尾指针rear指向的位置均是队列中元素。
队列空的条件是s=0;队列满的条件是s=1且front=rear。
队列的两种运算
假设循环队列的初始状态为空,即:
s=0,且front=rear=m。
①入队运算
入队运算是指在循环队列的队尾加入一个新元素。
操作过程如下:
a.首先判断循环队列是否满。
当循环队列非空(S=1)且队尾指针等于排头指针时,说明循环队列已满,不能进行入队运算。
这种情况称为“上溢”。
此时算法结束。
b.然后将队尾指针进一(即rear=rear+1),并当rear=m+1时置rear=1。
c.最后将新元素x插入队尾指针指向的位置,并且置循环队列非空标志。
②退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。
操作过程如下:
a.首先判断循环队列是否为空。
当循环队列为空(s=0)时,不能进行退队运算。
这种情况称为“下溢”。
此时算法结束。
b.然后将排头指针进一(即front=front+1),并当front=m+1时置front=1。
c.再将排头指针指向的元素赋给指定的变量。
d.最后判断退队后循环队列是否为空。
当front=rear时置循环队列空标志(即s=0)。
【真题演练】
1.下列叙述中正确的是()。
[2013年9月真题]
A.栈是“先进先出”的线性表
B.队列是“先进后出”的线性表
C.循环队列是非线性结构
D.有序线性表既可以采用顺序存储结构,也可以采用链式存储结构
【答案】D
【解析】栈和队列都是受限的线性表,其中栈按照“先进后出”的原则组织数据,插入与删除操作被限制在栈顶一端进行;队列采用“先进先出”的原则组织数据。
循环队列是队列的一种特殊形式,是线性结构。
2.下列叙述中正确的是()。
[2014年3月真题]
A.循环队列是顺序存储结构
B.循环队列是链式存储结构
C.循环队列是非线性结构
D.循环队列的插入运算不会发生溢出现象
【答案】A
【解析】B项错误,循环队列是一种顺序存储结构的队列;C项错误,线性结构是一个非空序列:
除第一个元素外,每个元素,有且只有一个前件;除最后一个元素外,每个元素有且只有一个后件,所以循环队列是线性结构;D项错误,当循环队列的元素个数等于存储长度后,入队会发生溢出现象,覆盖前面的数据。
3.对于循环队列,下列叙述中正确的是()。
[2013年9月真题]
A.队头指针是固定不变的
B.队头指针一定大于队尾指针
C.队头指针一定小于队尾指针
D.队头指针可以大于队尾指针,也可以小于队尾指针
【答案】D
【解析】循环队列的队头指针与队尾指针都不是固定的,每次入队操作队尾指针要%m进1,每次出队操作队头指针要%m进1。
因为存在%m运算,所以队头指针与队尾指针大小关系不确定。
4.下列叙述中正确的是()。
[2013年9月真题]
A.循环队列有队头和队尾两个指针,因此,循环队列是非线性结构
B.在循环队列中,只需要队头指针就能反映队列中元索的动态变化情况
C.在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况
D.循环
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二级 Web 程序设计 专用 教材