全国计算机等级考试_公共基础.ppt

《全国计算机等级考试_公共基础.ppt》由会员分享，可在线阅读，更多相关《全国计算机等级考试_公共基础.ppt（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主讲：刘祖珉主讲：刘祖珉计算机基础教学部计算机基础教学部20112011年年9 9月月全国计算机等级考试培训全国计算机等级考试培训第一部分第一部分 历年知识点分析及考试技巧历年知识点分析及考试技巧历年笔试知识点分析历年笔试知识点分析二级二级VFPVFP笔试时间为笔试时间为9090分钟，包括分钟，包括3535个选择题、个选择题、1515个填空题，个填空题，每题每题2 2分。分。其中，公共基础知识占其中，公共基础知识占3030分，分别为前分，分别为前1010个选择题和前个选择题和前5 5个填个填空题，其余空题，其余7070分为分为VFPVFP程序设计知识。程序设计知识。2005.9 2006.4

2、2006.9 2007.4 2007.9 2008.4 2008.9 2009.3 2009.9 2010.3 2010.92011.3数据结构121012101010101010101010软件工程10668888881066程序设计基础062462222044数据库基础810108610101210101012SQL语句262424262420222418221826VFP基础知识1216146866488108VFP数据库操作181410241816122210201410VFP可视化设计8121612161822830162222VFP程序设计62624108104462各知识点命题趋

3、势各知识点命题趋势公共基础命题趋势公共基础命题趋势2005.92006.42006.92007.42007.92008.42008.92009.32009.92010.32010.92011.30246810121412101210101010101010101010668888881066062462222044810108610101210101012数据结构软件工程程序设计基础数据库基础VFPVFP程序设计知识命题趋势程序设计知识命题趋势各知识点命题趋势各知识点命题趋势2005.92006.42006.92007.42007.92008.42008.92009.32009.92010.3

4、2010.92011.3051015202530352624242624202224182218261216146866488108181410241816122210201410812161216182283016222262624108104462SQL语句VFP基础知识VFP数据库操作VFP可视化设计工具VFP程序设计笔试知识分析笔试知识分析结论结论对于公共基础知识，近年来，对于公共基础知识，近年来，数据结构与算法数据结构与算法分值比较稳定，分值比较稳定，每次均为每次均为1010分；分；数据库基础数据库基础分值也相对稳定，一般在分值也相对稳定，一般在1010分上下；分上下；软件工程软件工

5、程和和程序设计基础程序设计基础一般共占一般共占1010分，其中以软件工程为重分，其中以软件工程为重点。点。在在VFPVFP部分，部分，VFPVFP基础知识基础知识是是VFPVFP编程基础，近年来，分值有编程基础，近年来，分值有所下降，一般在所下降，一般在8 8分上下；而分上下；而数据库操作数据库操作尽管分值有下降的趋势，尽管分值有下降的趋势，但仍是历年考试的重点；但仍是历年考试的重点；SQLSQL语言语言在所有知识点中所占分值最在所有知识点中所占分值最高，基本上每年均超过高，基本上每年均超过2020分，绝对不容忽视；分，绝对不容忽视；可视化程序设计可视化程序设计所占分值逐渐增加，近三年来分值也

6、基本超过所占分值逐渐增加，近三年来分值也基本超过2020分，应引起重分，应引起重视；视；VFPVFP程序设计程序设计分值一般在分值一般在4 4分左右。分左右。笔试知识分析笔试知识分析复习策略复习策略了解所占分值，复习有侧重了解所占分值，复习有侧重公共基础知识主要考查广度而不是深度，所以应遵循公共基础知识主要考查广度而不是深度，所以应遵循“广撒网广撒网”策策略，达到了解程度即可。略，达到了解程度即可。数据库的基本操作、可视化程序设计要达到理解程度，要看懂主要数据库的基本操作、可视化程序设计要达到理解程度，要看懂主要知识点。知识点。VFPVFP基础知识、基础知识、SQLSQL语言要达到掌握程度，力

7、争看懂所有知识点。语言要达到掌握程度，力争看懂所有知识点。其他章节达到了程度即可。其他章节达到了程度即可。归纳整理，注重实践归纳整理，注重实践尊重教材和大纲，适度模拟尊重教材和大纲，适度模拟建立错题集，及时复习建立错题集，及时复习机试分析机试分析题型及分值题型及分值基本操作题基本操作题3030分，一般分，一般4 4个题个题简单应用题简单应用题4040分，一般分，一般2 2个题个题综合应用题综合应用题3030分，一般一个题分，一般一个题考试方式考试方式上机考试，随机抽题上机考试，随机抽题考试题库一般每次更新考试题库一般每次更新10%10%左右左右第一部分第一部分 历年知识点分析及考试技巧历年知识

8、点分析及考试技巧机试分析机试分析基本操作题：基本操作题：3030分，一般分，一般4 4个题个题题型一（重点）题型一（重点）:文件新建与添加文件新建与添加新建项目、数据库、表新建项目、数据库、表向项目中添加文件向项目中添加文件向数据库中添加表向数据库中添加表题型二（重点）题型二（重点）：数据库基本：数据库基本索引的建立索引的建立数据库表永久关系的建立数据库表永久关系的建立建立参照完整性建立参照完整性题型三：用题型三：用SQLSQL查询查询查询（查询（selectselect）语句的书写）语句的书写第一部分第一部分 历年知识点分析及考试技巧历年知识点分析及考试技巧机试分析机试分析基本操作题：基本操

9、作题：3030分，一般分，一般4 4个题个题题型四：用题型四：用SQL操纵及定义表操纵及定义表要求写出修改表结构（要求写出修改表结构（alter table）、更新表（）、更新表（update）、插入记录）、插入记录（insert into）、建立表）、建立表(create table)等等SQL语句。语句。题型五：视图和查询的建立题型五：视图和查询的建立主要考查通过设计器建立视图和查询主要考查通过设计器建立视图和查询将查询设计器各选项卡与将查询设计器各选项卡与SQL 的的Select语句结合理解语句结合理解题型六：其他类题型六：其他类报表及基本操作报表及基本操作简单菜单建立简单菜单建立简单表

10、单建立简单表单建立第一部分第一部分 历年知识点分析及考试技巧历年知识点分析及考试技巧机试分析机试分析简单应用题：简单应用题：4040分，一般分，一般2 2个题个题题型一（重点）：查询与视图题型一（重点）：查询与视图利用数据库建立查询或视图利用数据库建立查询或视图题型二：菜单应用题型二：菜单应用下拉菜单和快捷菜单设计下拉菜单和快捷菜单设计返回系统菜单：返回系统菜单：SET SYSMENU TO DEFAULTSET SYSMENU TO DEFAULT题型三：表单应用题型三：表单应用常见控件的使用常见控件的使用区别属性区别属性NAMENAME与与CAPTIONCAPTION表单向导的使用表单向导

11、的使用题型四：题型四：SQLSQL查询查询第一部分第一部分 历年知识点分析及考试技巧历年知识点分析及考试技巧机试分析机试分析简单应用题：简单应用题：4040分，一般分，一般2 2个题个题题型五：报表题型五：报表利用报表向导建立报表利用报表向导建立报表快速报表快速报表报表带区及常见控件的使用报表带区及常见控件的使用预览预览预览预览:report form:report form 报表名报表名报表名报表名 previewpreview打印打印打印打印:report form:report form 报表名报表名报表名报表名 to printerto printer题型六：数据库操作题型六：数据库操

12、作数据库建立与表的添加数据库建立与表的添加索引的建立索引的建立数据库表属性的设置数据库表属性的设置题型七：程序改错题型七：程序改错第一部分第一部分 历年知识点分析及考试技巧历年知识点分析及考试技巧机试分析机试分析综合应用题：综合应用题：3030分，一般分，一般1 1个题个题题型一：表单题型一：表单常见表单控件的使用常见表单控件的使用控件常见的属性与方法控件常见的属性与方法控件事件响应程序设计控件事件响应程序设计题型二：菜单题型二：菜单下拉菜单和快捷菜单设计下拉菜单和快捷菜单设计顶层表单设计顶层表单设计响应菜单的程序设计响应菜单的程序设计题型三：其他类题型三：其他类编程题编程题报表题报表题第一部

13、分第一部分 历年知识点分析及考试技巧历年知识点分析及考试技巧第二部分第二部分 公共基础知识公共基础知识复习与答题技巧复习与答题技巧6060分万岁分万岁遵循遵循“广撒网广撒网”策略，达到了解程度即可策略，达到了解程度即可把把80%80%的时间用在的时间用在20%20%的重点知识点上，争取用的重点知识点上，争取用20%20%的重点知的重点知识点来答对识点来答对80%80%的考题的考题学会把学会把“知识点知识点”连成连成“知识链知识链”，并把，并把 “知识链知识链”织成织成“知知识网识网”。避免题海战术，更不能为了应付考试记住一大堆错误答案，只避免题海战术，更不能为了应付考试记住一大堆错误答案，只记

14、住正确答案就可以了。记住正确答案就可以了。先死后活、熟能生巧先死后活、熟能生巧会就会，不会就不会会就会，不会就不会2.1 2.1 数据结构和算法数据结构和算法一、算法一、算法重点考查重点考查对象，基本每次必考，但近两次未考对象，基本每次必考，但近两次未考1 1、定义定义是对解题方案的准确而完整的描述。算法不等于程序，也不等计算是对解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，它是指令的有限序列。机方法，它是指令的有限序列。2 2、主要特征主要特征可行性可行性：能够用已经实现的基本运算执行有限次来实现：能够用已经实现的基本运算执行有限次来实现确定性确定性：算法中每一步骤都必须有明

15、确定义，不充许有模棱两可的：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多解释，不允许有多 义性义性有穷性有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理后终止，包括合理 的执行时间的含义的执行时间的含义拥有足够的情报拥有足够的情报：有：有0 0个或多个输入、至少有一个输出个或多个输入、至少有一个输出2.1 2.1 数据结构和算法数据结构和算法一、算法一、算法3 3、算法的要素算法的要素对数据对象的运算和操作、算法的控制结构对数据对象的运算和操作、算法的控制结构4 4、算法复杂度算法复杂度时间复杂

16、度时间复杂度：是指执行算法所需要的计算工作量：是指执行算法所需要的计算工作量空间复杂度空间复杂度：是指执行这个算法所需要的内存空间。：是指执行这个算法所需要的内存空间。典型实例典型实例（1 1）问题处理方案的正确而完整的描述称为（问题处理方案的正确而完整的描述称为（）（2 2）下列叙述中正确的是下列叙述中正确的是 （）A A）程序执行的效率与数据的存储结构密切相关）程序执行的效率与数据的存储结构密切相关 B B）程序执行的效率只取决于程序的控制结构）程序执行的效率只取决于程序的控制结构 C C）程序执行的效率只取决于所处理的数据量）程序执行的效率只取决于所处理的数据量 D D）以上三种说法都不

17、对）以上三种说法都不对算法算法A2.1 2.1 数据结构和算法数据结构和算法一、算法一、算法典型实例典型实例（3 3）算法的时间复杂度是指（算法的时间复杂度是指（）A A）算法的执行时间）算法的执行时间B B）算法所处理的数据量）算法所处理的数据量C C）算法程序中的语句或指令条数）算法程序中的语句或指令条数DD）算法在执行过程中所需要的基本运算次数）算法在执行过程中所需要的基本运算次数（4 4）算法的空间复杂度是指（算法的空间复杂度是指（）A A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间 B B）算法所处理的数据量）算法所处理的数据量 C C）算法程序中

18、的语句或指令条数）算法程序中的语句或指令条数 DD）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数 DA2.1 2.1 数据结构和算法数据结构和算法一、算法一、算法典型实例典型实例（5 5）下列叙述中正确的是（下列叙述中正确的是（）A A）算法的效率只与问题的规模有关，而与数据的存储结构无关）算法的效率只与问题的规模有关，而与数据的存储结构无关B B）算法的时间复杂度是指执行算法所需要的计算工作量）算法的时间复杂度是指执行算法所需要的计算工作量C C）数据的逻辑结构与存储结构是一一对应的）数据的逻辑结构与存储结构是一一对应的D D）算法的时间复杂度与空间复杂度一

19、定相关）算法的时间复杂度与空间复杂度一定相关（6 6）算法的有穷性是指算法的有穷性是指（）A A算法程序的运行时间是有限的算法程序的运行时间是有限的 B B算法程序所处理的数据量是有限的算法程序所处理的数据量是有限的 C C算法程序的长度是有限的算法程序的长度是有限的 D D算法只能被有限的用户使用算法只能被有限的用户使用 BA2.1 2.1 数据结构和算法数据结构和算法二、数据结构的基本概念二、数据结构的基本概念重点考查对象，几乎每次必考重点考查对象，几乎每次必考1 1、定义定义数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。2 2、研究内容研究内容（1 1）

20、数据集合中各数据元素之间所固有的逻辑关系，即数据的逻）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；辑结构；（2 2）在对数据进行处理时，各数据元素在计算机中的存储关系，）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；即数据的存储结构；（3 3）对各种数据结构进行的运算）对各种数据结构进行的运算3 3、数据的逻辑结构数据的逻辑结构（1 1）表示数据元素的信息）表示数据元素的信息（2 2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。2.1 2.1 数据结构和算法数据结构和算法二、数据结构的基本概念二、数据结构的基本概念4 4、两类逻辑结

21、构两类逻辑结构线性结构：如线性表线性结构：如线性表（1 1）有且只有一个根结点）有且只有一个根结点（2 2）每一个结点最多有一个前驱，也最多有一个后继）每一个结点最多有一个前驱，也最多有一个后继非线性结构非线性结构不满足线性结构条件的数据结构，如树和图不满足线性结构条件的数据结构，如树和图5 5、数据的存储结构数据的存储结构数据的逻辑结构在计算机中的表示。数据的逻辑结构在计算机中的表示。4 4种存储映射方法种存储映射方法顺序映射：用连续区域来存储结点数据顺序映射：用连续区域来存储结点数据链式映射：存储数据元素和与之有关结点的指针链式映射：存储数据元素和与之有关结点的指针索引映射：顺序映射的推广

22、，增加索引表来存储结点指针索引映射：顺序映射的推广，增加索引表来存储结点指针散列映射：索引映射的推广，用散列函数计算结点索引散列映射：索引映射的推广，用散列函数计算结点索引2.1 2.1 数据结构和算法数据结构和算法二、数据结构的基本概念二、数据结构的基本概念典型实例典型实例下列叙述中正确的是下列叙述中正确的是A A）有一个以上根结点的数据结构不一定是非线性结构）有一个以上根结点的数据结构不一定是非线性结构B B）只有一个根结点的数据结构不一定是线性结构）只有一个根结点的数据结构不一定是线性结构C C）循环链表是非线性结构）循环链表是非线性结构DD）双向链表是非线性结构）双向链表是非线性结构下

23、列叙述中正确的是下列叙述中正确的是 A A）数据的逻辑结构与存储结构必定是一一对应的）数据的逻辑结构与存储结构必定是一一对应的 B B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构构一定是线性结构 C C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构能处理线性结构 DD）以上三种说法都不对）以上三种说法都不对BD2.1 2.1 数据结构和算法数据结构和算法二、数据结构的基本概念二、数据结构的基本概念典型实例典型实例数据的存储结

24、构是指数据的存储结构是指_。A A）存储在外存中的数据）存储在外存中的数据 B B）数据所占的存储空间量）数据所占的存储空间量C C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D D）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示下列叙述中正确的是下列叙述中正确的是A A）一个逻辑数据结构只能有一种存储结构）一个逻辑数据结构只能有一种存储结构 B B）数据的逻辑结构属于线性结构，存储结构属于非线性结构）数据的逻辑结构属于线性结构，存储结构属于非线性结构C C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数）一个逻辑数据结构可以有多种存储结构，且各种存

25、储结构不影响数据处理的效率据处理的效率D D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率处理的效率DD三、线性表三、线性表暂未出过单独试题，但每次考试均涉及线性表暂未出过单独试题，但每次考试均涉及线性表1 1、定义定义线性表是由具有相同类型的数据元素组成的有限序列，数据元素的线性表是由具有相同类型的数据元素组成的有限序列，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，在复杂线性表中，由若

26、干项数据元素组成的数据元素称为记录，而而由多个记录构成的线性表又称为文件。由多个记录构成的线性表又称为文件。结点个数结点个数 n n 称为线性表的长度，当称为线性表的长度，当 n=0 n=0 时，称为空表。时，称为空表。2 2、非空线性表非空线性表（1 1）有且只有一个根结点）有且只有一个根结点 ，它无前驱；，它无前驱；（2 2）有且只有一个终端，它无后继；）有且只有一个终端，它无后继；（3 3）除根结点与终端结点外，其他所有结点有且只有一个前驱，）除根结点与终端结点外，其他所有结点有且只有一个前驱，也有且只有一个后继。也有且只有一个后继。2.1 2.1 数据结构和算法数据结构和算法三、线性表

27、三、线性表暂未出过单独试题，但每次考试均涉及线性表暂未出过单独试题，但每次考试均涉及线性表3 3、线性表的顺序存储结构线性表的顺序存储结构用一组地址连续的存储单元来存储线性表的元素用一组地址连续的存储单元来存储线性表的元素基本特点基本特点（1 1）线性表中所有元素的所占的存储空间是线性表中所有元素的所占的存储空间是 连续的；连续的；（2 2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。a ai i 的存储地址为：的存储地址为：ADRADR（a ai i）=ADR=ADR（a a1 1）+（i-1i-1）k k，ADRADR（a

28、a1 1）为第一个元素的地址，）为第一个元素的地址，k k 代表每个元代表每个元 素占的字节数。素占的字节数。4 4、线性表的运算线性表的运算插入：在第插入：在第i i个元素与第个元素与第i+1i+1个元素之间插入一个新数据元素个元素之间插入一个新数据元素删除：删除一个元素删除：删除一个元素a ai i2.1 2.1 数据结构和算法数据结构和算法四、栈四、栈重点考查对象，基本上每次必考，但近年有所下降重点考查对象，基本上每次必考，但近年有所下降1 1、定义定义栈是限定在一端进行插入与删除的线性表，栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与允许插入与删除的一

29、端称为栈顶，不允许插入与 删除的另一端称为删除的另一端称为栈底。栈底。栈按照栈按照“先进后出先进后出”（FILOFILO）或）或“后进先出后进先出”（LIFOLIFO）组织数据，）组织数据，栈具有记忆作用。用栈具有记忆作用。用toptop表示栈顶，用表示栈顶，用bottombottom表示栈底。表示栈底。2 2、栈的顺序存储结构栈的顺序存储结构利用一组连续地址的存储单元来存储从栈底到栈顶的数据元素，利用一组连续地址的存储单元来存储从栈底到栈顶的数据元素，附设一个指针附设一个指针toptop表示栈顶，一个指针表示栈顶，一个指针bottombottom表示栈底。表示栈底。bottombottom的

30、值为的值为NULLNULL时表示栈不存在时表示栈不存在top top 和和bottombottom相等时表示空栈相等时表示空栈2.1 2.1 数据结构和算法数据结构和算法四、栈四、栈3 3、栈的基本运算栈的基本运算（1 1）插入元素称为入栈运算，）插入元素称为入栈运算，top+1 top+1；（2 2）删除元素称为退栈运算，）删除元素称为退栈运算，top-1 top-1；（3 3）读栈顶元素）读栈顶元素 是将栈顶元素赋给一个指定的变量，此时指针无是将栈顶元素赋给一个指定的变量，此时指针无变化。变化。典型实例典型实例下列关于栈叙述正确的是下列关于栈叙述正确的是 A A）栈顶元素最先能被删除栈顶元

31、素最先能被删除 B B）栈顶元素最后才能被删除）栈顶元素最后才能被删除 C C）栈底元素永远不能被删除）栈底元素永远不能被删除 D D）以上三种说法都不对）以上三种说法都不对2.1 2.1 数据结构和算法数据结构和算法A四、栈四、栈典型实例典型实例下列叙述正确的是下列叙述正确的是 A A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B B）在栈中，栈顶指针不变，栈中元素随栈底指针而动态变化）在栈中，栈顶指针不变，栈中元素随栈底指针而动态变化C C）在栈中，栈底指针不变，栈中元素随栈顶指针而动态变化）在栈中，栈底指针不变，栈中元素随栈顶

32、指针而动态变化DD）以上三种说法都不对）以上三种说法都不对假设用一个长度为假设用一个长度为5050的数组（数组元素的下标从的数组（数组元素的下标从0 0到到4949）作为栈的存）作为栈的存储空间，栈底指针储空间，栈底指针bottombottom指向栈底元素，栈顶指针指向栈底元素，栈顶指针toptop指向栈顶元素，指向栈顶元素，如果如果bottom=49bottom=49，top=30top=30（数组下标），则栈中具有（数组下标），则栈中具有_个元个元素。素。栈的基本运算有三种：入栈、退栈与栈的基本运算有三种：入栈、退栈与_一个栈的初始状态为空，首先将元素一个栈的初始状态为空，首先将元素5 5

33、、4 4、3 3、2 2、1 1依次入栈，然后依次入栈，然后退栈一次，再将元素退栈一次，再将元素A A、B B、C C、DD依次入栈，之后将所有元素全部退栈，依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为则所有元素退栈（包括中间退栈的元素）的顺序为_2.1 2.1 数据结构和算法数据结构和算法C19读栈顶元素读栈顶元素1DCBA23451DCBA2345五、队列五、队列一般考查对象，基本上和栈不同时出题，但近年有所上升一般考查对象，基本上和栈不同时出题，但近年有所上升1 1、定义定义队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行队列是指允许在一端（队

34、尾）进入插入，而在另一端（队头）进行删除的线性表。删除的线性表。rearrear指针指向队尾，指针指向队尾，frontfront指针指向队头。指针指向队头。队列是队列是“先进先出先进先出（FIFOFIFO）或）或 后进后出后进后出（LILOLILO）的线）的线 性表。性表。循环队列：循环队列：s=0 s=0 表示队列空，表示队列空，s=1 s=1 且且 front=rear front=rear 表示队列满表示队列满队列运算队列运算（1 1）插入：从队尾插入一个元素称为入队运算，）插入：从队尾插入一个元素称为入队运算，rear+1rear+1；（2 2）删除：从队头删除一个元素称为退队运算，）

35、删除：从队头删除一个元素称为退队运算，front+1front+12.1 2.1 数据结构和算法数据结构和算法五、队列五、队列典型实例典型实例一个队列的初始状态为空。现将元素一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1 A,B,C,D,E,F,5,4,3,2,1 依依次入队，然后再依次退队，则元素退队的顺序为次入队，然后再依次退队，则元素退队的顺序为_ 。设某循环队列的容量为设某循环队列的容量为5050，如果头指针，如果头指针front=45front=45（指向队头元（指向队头元素的前一位置），尾指针素的前一位置），尾指针rear=10rear=10（指向队尾元

36、素），则该循环（指向队尾元素），则该循环队列中共有队列中共有_个元素个元素对于循环队列，下列叙述中正确的是（对于循环队列，下列叙述中正确的是（）。）。A A）队头指针是固定不变的）队头指针是固定不变的 B B）队头指针一定大于队尾指针）队头指针一定大于队尾指针 C C）队头指针一定小于队尾指针）队头指针一定小于队尾指针 D D）队头指针可以大于队尾指针，也可以小于队尾指针）队头指针可以大于队尾指针，也可以小于队尾指针 2.1 2.1 数据结构和算法数据结构和算法ABCDEF54321ABCDEF543211515D D五、队列五、队列典型实例典型实例下列数据结构中，能够按照下列数据结构中，能够

37、按照“先进后出先进后出”原则存取数据的是（原则存取数据的是（）A A）循环队列）循环队列 B B）栈）栈 C C）队列）队列 D D）二叉树）二叉树 线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的一种特殊的线性表，循环队列是队列的_ _ 存储结构。存储结构。下列对队列的叙述正确的是（下列对队列的叙述正确的是（）A A）队列属于非线性表）队列属于非线性表B B）队列按）队列按“先进后出先进后出”原则组织数据原则组织数据C C）队列在队尾删除数据）队列在队尾删除数据D D）队列按）队列按“先进先

38、出先进先出”原则组织数据原则组织数据2.1 2.1 数据结构和算法数据结构和算法B B顺序顺序D D2.1 2.1 数据结构和算法数据结构和算法六、链表六、链表非重点考查对象，主要考查线性单链表、双向链表、循环链表非重点考查对象，主要考查线性单链表、双向链表、循环链表的结构及基本运算的结构及基本运算1 1、顺序结构的缺点顺序结构的缺点:在插入、删除时要移动大量的节点，效率低在插入、删除时要移动大量的节点，效率低表的大小固定。预先指定，无法更改，不便扩充表的大小固定。预先指定，无法更改，不便扩充原因：原因：结构存放的连续性结构存放的连续性突破突破离散存放离散存放用指针来表示元素之间的关系。用指针

39、来表示元素之间的关系。2 2、链接的形式：单链表、双链表、循环链表链接的形式：单链表、双链表、循环链表2.1 2.1 数据结构和算法数据结构和算法六、链表六、链表3 3、结点结点数据结构中的每一个结点对应于一个存储单元，这种存储单元称为数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。存储结点，简称结点。结点由两部分组成：结点由两部分组成：（1 1）用于存储数据元素值，称为数据域；）用于存储数据元素值，称为数据域；（2 2）用于存放指针，称为指针域，用于指向前一个或后一个结点。）用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存

40、储空间可以不连续，各在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的链式存储方式而数据元素之间的逻辑关系是由指针域来确定的链式存储方式即可用于表示线性结构，也可用于表示非线性结构。即可用于表示线性结构，也可用于表示非线性结构。4 4、单链表单链表链表的每个结点只包含一个指针域，用于指向它的后一个结点链表的每个结点只包含一个指针域，用于指向它的后一个结点最后一个结点的指针域为最后一个结点的指针域为“空空”2.1 2.1 数据结构和算法数据结构

41、和算法六、链表六、链表5 5、循环链表循环链表链表的每个结点只包含一个指针域，用于指向它的后一个结点链表的每个结点只包含一个指针域，用于指向它的后一个结点最后一个结点的指针域指向头结点最后一个结点的指针域指向头结点6 6、双向链表双向链表链表的每个结点包含有两个指针域：一个指向直接后继，另一个指链表的每个结点包含有两个指针域：一个指向直接后继，另一个指向直接前驱向直接前驱7 7、链表的基本操作链表的基本操作插入插入删除删除2.1 2.1 数据结构和算法数据结构和算法六、链表六、链表典型实例典型实例下列叙述中正确的是（下列叙述中正确的是（）A)A)线性链表是线性表的链式存储结构线性链表是线性表的

42、链式存储结构 B)B)栈与队列是非线性结构栈与队列是非线性结构C)C)双向链表是非线性结构双向链表是非线性结构 D)D)只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构下列对于线性链表的描述中正确的是下列对于线性链表的描述中正确的是_。A A）存储空间不一定是连续，且各元素的存储顺序是任意的存储空间不一定是连续，且各元素的存储顺序是任意的B B）存储空间不一定是连续，且前件元素一定存储在后件元素的存储空间不一定是连续，且前件元素一定存储在后件元素的前面前面C C）存储空间必须连续，且前件元素一定存储在后件元素的前面存储空间必须连续，且前件元素一定存储在后件元素的前面D D）存储空间必须

43、连续，且各元素的存储顺序是任意的存储空间必须连续，且各元素的存储顺序是任意的A AA A2.1 2.1 数据结构和算法数据结构和算法七、树七、树重中之重重中之重考查对象，必考，主要考查二叉树的定义、存储结构考查对象，必考，主要考查二叉树的定义、存储结构和和3 3种遍历算法种遍历算法1 1、定义定义树是一种简单的非线性结构，所有元素之间具有明显的层次特性。树是一种简单的非线性结构，所有元素之间具有明显的层次特性。每一个结点只有一个前驱，称为父结点，没有前驱的结点只有一每一个结点只有一个前驱，称为父结点，没有前驱的结点只有一个，称为树的根结点，简称树的根。个，称为树的根结点，简称树的根。每一个结点

44、可以有多个后继，称为该结点的子结点。没有后继的每一个结点可以有多个后继，称为该结点的子结点。没有后继的结点称为叶子结点。结点称为叶子结点。结点的度：结点的度：一个结点所拥有的后继的个数一个结点所拥有的后继的个数树的度：树的度：所有结点中最大的度所有结点中最大的度树的深度：树的深度：树的最大层次树的最大层次结点的层次：结点的层次：结点的层次从根开始定义，根为第一层结点的层次从根开始定义，根为第一层2.1 2.1 数据结构和算法数据结构和算法七、树七、树2 2、二叉树的特点二叉树的特点（1 1）非空二叉树只有一个根结点）非空二叉树只有一个根结点（2 2）每一个结点最多有两棵子树，且分别称为该结点的

45、左子树与）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树右子树3 3、满二叉树满二叉树除最后一层外，每一层上的所有结点有两个子结点，则除最后一层外，每一层上的所有结点有两个子结点，则k k层上有层上有2 2k k-1 1个结点。深度为个结点。深度为mm的满二叉树有的满二叉树有2 2mm-1-1个结点。个结点。4 4、完全二叉树完全二叉树深度为深度为k k且有且有n n个结点的二叉树，当且仅当其每一个结点都有与深度个结点的二叉树，当且仅当其每一个结点都有与深度为为k k的满二叉树中编号从的满二叉树中编号从1 1至至n n的结点一一对应的结点一一对应简单说，就是指除最后一层外，每一层上

46、的结点数均达到最大值，简单说，就是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。在最后一层上只缺少右边的若干结点。2.1 2.1 数据结构和算法数据结构和算法七、树七、树4 4、二叉树的性质二叉树的性质1 1）在二叉树的第在二叉树的第k k层上，最多有层上，最多有2 2k-1k-1（k1k1）个结点）个结点2 2）深度为深度为mm的二叉树最多有的二叉树最多有2 2mm-1-1个结点个结点3 3）度为度为0 0的结点（即叶子结点）总是比度为的结点（即叶子结点）总是比度为2 2的结点多一个的结点多一个4 4）具有具有n n个结点的二叉树，其深度至少为个结点的二叉树

47、，其深度至少为loglog2 2n+1n+1，其中，其中loglog2 2nn表示取表示取loglog2 2n n的整数部分的整数部分5 5）具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n+1n+1；6 6）设完全二叉树共有设完全二叉树共有n n个结点。如果从根结点开始，按层序（每一层从左个结点。如果从根结点开始，按层序（每一层从左到右）用自然数到右）用自然数1 1，2 2，n n给结点进行编号（给结点进行编号（k=1k=1，2 2n n），有以下结论：），有以下结论：若若k=1k=1，则该结点为根结点，它没有父结点；若，则该结点为根结点，它没有父结点；

48、若k1k1，则该结点的父，则该结点的父结点编号为结点编号为INTINT（k/2k/2）；）；若若2kn2kn，则编号为，则编号为k k的结点的左子结点编号为的结点的左子结点编号为2k2k；否则该结点无左；否则该结点无左子结点（也无右子结点）；子结点（也无右子结点）；若若2k+1n2k+1n，则编号为，则编号为k k的结点的右子结点编号为的结点的右子结点编号为2k+12k+1；否则该结点；否则该结点无右子结点。无右子结点。2.1 2.1 数据结构和算法数据结构和算法七、树七、树5 5、二叉树的存储结构二叉树的存储结构二叉树存储结构采用链式存储结构，二叉树存储结构采用链式存储结构，满二叉树与完全二

49、叉树可以按层序进行顺序存储。满二叉树与完全二叉树可以按层序进行顺序存储。6 6、二叉树的遍历二叉树的遍历（1 1）前序遍历（）前序遍历（DLRDLR）首先访问根结点，然后遍历左子树，最后遍历右子树；首先访问根结点，然后遍历左子树，最后遍历右子树；（2 2）中序遍历（）中序遍历（LDRLDR）首先遍历左子树，然后访问根结点，最后遍历右子树；首先遍历左子树，然后访问根结点，最后遍历右子树；（3 3）后序遍历（）后序遍历（LRDLRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。首先遍历左子树，然后访问遍历右子树，最后访问根结点。2.1 2.1 数据结构和算法数据结构和算法七、树七、树典型实

50、例典型实例某二叉树共有某二叉树共有7 7个结点，其中叶子结点只有个结点，其中叶子结点只有1 1个，则该二叉树的个，则该二叉树的深度为（假设根结点在第深度为（假设根结点在第1 1层）层）A A）3 3 B B）4 4 C C）6 6 DD）7 7某二叉树中有某二叉树中有n n个度为个度为2 2的结点的结点,则该二叉树中的叶子结点数为则该二叉树中的叶子结点数为A)n+1A)n+1B)n-1B)n-1C)2nC)2nD)n/2D)n/2设一棵完全二叉树共有设一棵完全二叉树共有700700个结点，则有个结点，则有（）个叶子结点个叶子结点在深度为在深度为7 7的满二叉树中，度为的满二叉树中，度为2 2的