LJk57870367
一、课程的性质与设置目的
(一)本课程的性质和特点
作物栽培学是研究作物生长发育规律及其与外界环境条件的关系，以及探讨作物高产、优质、高效、低成本生产理论的一门科学。它所研究的内容极其广泛，而且综合性很强，又密切联系生产实际。
(二)本课程的地位、任务与作用
要提高农作物的产量和品质，降低种植成本，提高种植效益，作物生产必须要良种与良法配套，其中的良法主要为作物栽培学。因此，作物栽培学为农学专业的专业课。自学者只有在掌握作物的生长发育规律和作物高产、优质、高效生产的基本措施和方法，具备作物大田生产管理的基本技能，才能指导农业生产。
(三)本课程的基本要求
设置本课程的目的，是为了有自学能力的学生，通过该课程的学习，掌握作物生长发育规律及其与产量和品质的关系，掌握生态环境条件对作物生长发育和产量品质的影响，掌握作物高产、优质、高效栽培生理与技术措施，明确作物生产的原理，能分析和解决作物生产中存在的问题，指导农业生产。
(四)本课程与相关课程的关系
作物栽培学是综合性的科学。应先修植物生理学、遗传学、土壤学、农业气象、农业生态学、植物保护、农业化学、生物统计等基础课和专业基础课。同时，作物栽培学又是一门实践性很强的科学，因此除了认真学习理论知识外，还需要深入科研、生产第一线，理论联系实际学习，逐步提高发现问题、分析问题和解决问题的能力。
二、课程内容与考核目标
绪 论
(一)学习目的与要求
了解作物的起源与进化条件和主要作物的起源中心。
理解作物起源地的生态条件与作物生长发育特性的关系。
掌握作物演变与进化的和作物的主要分类方法与类型。
- 1 -
熟练掌握作物栽培学在农业生产中的地位和发展趋势。
(二)课程内容
1、作物的概念与分类
2、作物栽培学的性质、任务与研究内容
3、作物的起源与进化
4、作物栽培学在农业生产中的战略地位
5、作物栽培学发展的趋势
(三)考核知识点
1、作物的概念与分类。
2、作物的起源与进化。
3、作物栽培学的性质、任务与研究内容。
4、作物栽培学在农业生产中的地位和发展趋势。
(四)考核要求
1、识记:作物的主要分类方法、类型和代表作物、各起源中心起源的主要作物、作物栽培学的概念。
2、领会:作物、喜温作物、耐寒作物、长日照作物、短日照作物、中性作物等概念、生态条件的变化对作物的演变与进化的影响;杂交对作物的演变和进化的影响。
3、简单应用:作物栽培学性质及与其他相关学科的关系。
4、综合应用:作物栽培学的发展趋势。
第一章 农作物器官建成
(一)学习目的与要求
本章是作物栽培学的重点和难点之一。根、茎、果实器官的简称是本章的重点，农作物各器官之间生长的相关性是本章的难点。
了解主要农作物的各器官的形态结构和解剖结构。
理解农作物种子萌发出苗与环境条件的关系、主茎叶片的功能分组及各器官之间生长的相关性。
掌握影响主要农作物产量、品质形成的因素及各器官的变态。 重点掌握农作物根、茎、叶、花、果实等器官的功能及建成过程和生长发育规律;
(二)课程内容
- 2 -
第一节 农作物种子萌发与出苗
第二节 农作物根系的建成
第三节 农作物茎和分枝的生长
第四节 农作物叶的生长
第五节 农作物花芽的分化与形成
第六节 农作物果实、种子的形成
第七节 农作物各器官之间生长的相关性
(三)考核知识点
1、农作物种子形态结构及萌发与出苗过程。
2、农作物种子萌发与出苗的条件。
3、农作物根的形态结构及建成。
4、作物茎的形态与结构及茎的变态与作用。
5、茎的生长过程及倒伏与徒长现象。
6、禾本科作物分蘖的发生及其作用。
7、双子叶作物分枝的形成过程。
8、农作物叶的形态特征及叶的生存时期和功能分组。
9、农作物花的形态结构及双子叶作物花芽和禾本科作物花序分化时期。 10、禾本科作物子粒的发育与形成。
11、禾本科作物子粒发育的不均衡现象及花而不实和空壳秕粒现象。 12、棉铃和纤维的形成过程。
13、豆类作物种子的生长发育。
14、油菜角果的生长和种子的发育。
15、作物地下部和地上部生长的相关性。
16、作物主茎和分枝间生长的相关性。
17、禾本科作物根、叶、蘖间的同伸关系。
18、营养器官生长和生殖器官生长之间的数量关系，
19、作物茎、叶生长与花芽分化的时间关系。
20、作物源、库、流之间的关系。
(四)考核要求
1、识记:禾本科作物种子和双子叶作物种子的基本结构、作物根系结构中各
部位的名称;禾本科作物次生根的发生和建成与叶片发生的关系、作物的形态与结
构各部位的名称、叶的类型;叶片结构及各部位名称;主要作物的叶片数等、花的
形态结构;禾本科小穗结构等、棉花纤维的构造、油菜角果的构造等、根、茎、蘖
等器官的同伸关系、出叶与花芽分化进程的关系;叶龄指数与穗分化进程的关系;
- 3 -
叶龄余数与穗分化进程的关系;叶枕距与穗分化进程的关系;茎节间伸长与穗分化进程的关系等。
2、领会:水稻糠、小麦麸皮等概念、鸡爪根、根瘤等概念、苎麻龙头根、苎麻扁担根、苎麻跑马根、马铃薯块茎等概念、分蘖节、分蘖盛期、有效分蘖等概念、棉花果枝、棉花叶枝等概念、叶的伸展定型期、叶的功能期、叶的生存期(寿命)、作物生长中心、供长中心叶等概念、花芽分化、棉花现蕾期等概念、强势花、弱势花等的概念、棉铃的发育及与环境条件的关系;棉花纤维的发育及与环境条件的关系、冠/根比、T/R值、顶端生长优势等概念、叶龄指数、叶龄余数、叶枕距等概念。
3、简单应用:农作物种子萌发过程;农作物种子出苗过程;农作物种子的形态结构与萌发出苗的关系、作物变态根的作用;豆类作物根瘤的形成过程;油菜根系的生长时期、农作物茎的倒伏与徒长产生的原因及其防治;油菜茎的生长时期及其物质的动态变化、棉花叶枝和果枝的发生及其主要区别;棉花、油菜、大豆的株型与分枝的关系、禾本科作物和双子叶作物叶片形态特征区别;叶片生长经历的时期及各主要作物叶的生存期;高产栽培应如何调节作物生长中心、供长中心叶的关系;稻、麦作物的叶片分组及各组叶片的功能;棉花主茎叶、果枝叶光合产物运输特点;甘蓝型油菜各组叶片的功能时期和功能、水稻、小麦的幼穗分化时期;棉花的花芽分化时期、禾本科作物子粒的发育过程、禾本科作物子粒发育的不均衡现象及原因、豆类作物种子的形成过程、油菜种子的生长发育及其重量和含油量变化、主茎生长和分枝生长之间的关系。
4、综合应用:农作物种子萌发与出苗的条件及各条件对种子萌发与出苗的生理影响、小麦根系的生长过程;棉花根系的生长时期及各时期的功能特点、禾本科作物分蘖发生的顺序及其规律、禾本科作物子粒形成过程及与栽培和环境条件的关系、禾本科作物空壳和秕粒产生的原因、作物地上部和地下部生长的关系及影响因素和调节措施、作物营养器官生长和生殖器官生长之间的关系、作物生产的源、库、流之间的关系。
第二章 水 稻
(一)学习目的与要求
本章的重点是水稻温光反应特性及其在生产上的应用和水稻的育秧技术，难点是水稻的水分管理和施肥技术。
了解水稻的积温与品种类型及在生产上的应用;栽培稻种的起源;世界和我国的水稻生产概况;不育系的繁殖技术等。
理解水稻栽培品种的分类与利用特点;水稻土壤的特性以及高产稻田土壤的基- 4 -
本特征。
掌握秧苗的类型及壮秧指标;播种期、播种量和秧龄的确定;水稻合理的动态群体结构;水稻杂种优势的利用途径;再生稻的优点及产量潜力。 熟练掌握我国的稻作分区及栽培稻的类型及各类型的特点;水稻温光反应特性及其在生产上的应用;水稻产量构成因素及各因素的决定时期;水稻的需肥规律与施肥技术;水稻的灌溉技术、育秧技术、秧苗移栽技术及各生育期的田间管理措施等;水稻杂种优势的表现和高产制种技术;再生稻的生长发育特性及其与环境条件的关系和栽培技术。
(二)课程内容
第一节 概述
第二节 稻种起源、演变及类型
第三节 水稻生长发育及产量形成
第四节 水稻高产栽培技术
第五节 杂交水稻栽培技术
第六节 再生稻栽培技术
(三)考核知识点
1、世界及我国水稻生产概况及其发展。
2、我国水稻生产的分布与区划。
3、栽培稻种的起源、类型与利用及栽培品种的分类与利用。 4、水稻的生长时期和产量构成因素。
5、水稻品种的库源关系及产量潜力。
6、水稻的温光反应特性及其在生产上的应用。
7、水稻积温与品种类型及在生产上的应用。
8、水稻土的氧化还原状态、有机质的分解和氮素存在状态。 9、高产稻田土壤的基本特征。
10、秧苗的类型及壮秧指标。
11、育秧技术及合理的动态群体结构与秧苗移栽。
12、水稻的需肥规律与施肥技术。
13、水稻的水分生理与灌溉技术。
14、水稻各生育期的苗情诊断、田间管理措施及原理。 15、水稻杂种优势的表现和杂种优势的利用途径。
16、三系杂交稻及两系杂交稻高产制种技术及原理。 17、不育系繁殖技术及原理。
18、再生稻的优点及产量潜力。
- 5 -
19、再生稻的生育特性与稻栽培技术。
(四)考核要求
1、识记:世界各大洲和我国的水稻生产概况、栽培稻的起源及学名:水稻栽培品种分类的类型与利用等、华中稻区水稻生育期，水稻的产量构成因素等、水稻的播种期、播种量和秧龄;水稻不同主茎与分蘖、主茎穗与分蘖穗比重;不同高产途径中的单位面积基本苗数、最高苗数、成穗数和每穗实粒数等、水稻不同生育期对养分的需要量等、我国不同稻区稻田的需水量等。
2、领会:水稻、陆稻、粘稻、糯稻等概念、幼苗期、分蘖期、返青期等概念、感温性、感光性、基本营养生长性概念、活动积温、有效积温、低效积温、无效高温等概念、断奶肥、烂种、烂芽等概念、杂种优势、三系、不育系、保持系、恢复系、两系等概念、再生稻的概念。
3、简单应用:我国水稻生产经历的发展时期、籼稻和粳稻的形态特征及生理特征比较;水稻和陆稻的主要差异;粘稻和糯稻的淀粉结构差异、水稻的产量构成因素及其相互关系、水稻的理想株型与提高产量的途径、积温在水稻生产上的应用、水稻土的氧化还原状态;水稻土中的有机质分解情况;水稻中的氮素存在状态、秧苗类型及壮秧指标、水稻种子的催芽过程;温室育秧技术及原理;两段育秧技术及原理;水稻烂秧的原因及防治、稻田的主要灌溉类型、各生育期对环境条件的要求;水稻各生育期的田间管理措施及原理;水稻各生育期的苗情诊断指标、三系的来源及各自的功能和相互关系;两系法中不育系的特点和功能;两系法中不育系的类型及育性控制机理、三系杂交稻不育系繁殖技术及原理;两系杂交稻不育系繁殖技术及原理、再生稻的优点和产量潜力。
4、综合应用:我国水稻生产的分区及各区的自然条件和在水稻生产中的地位、水稻各产量构成因素在产量中的作用及形成和决定时期、水稻品种的库源关系及类型、水稻的温、光反应特性及其在生产上的应用、高产稻田土壤的基本特征、露地湿润育秧技术及原理;薄膜保温育秧技术及原理;旱育秧的特点和优势;肥床旱育秧技术及原理;塑料软盘旱育秧技术及原理、水稻生育前期重点施肥方法及依据;水稻生育中期重点施肥方法及依据、水稻各生育期对水分的要求及灌溉原则;水稻晒田的作用与技术、水稻返青分蘖期僵苗生理障碍的类型、症状、发生原因及防治措施;高产水稻的叶色变化规律及其与内部生理变化的关系、水稻杂种优势的表现、三系杂交稻高产制种技术及原理;两系杂交稻制种高产技术及原理、再生稻的生长发育特性及与环境条件的关系;再生稻的高产栽培技术。
第三章 小 麦
(一)学习目的与要求
- 6 -
小麦的阶段发育理论及其在生产上的应用以及营养特点和施肥技术是本章的重点，各生育阶段的苗情诊断是本章的难点。
了解小麦的生产概况和生长发育过程;小麦对土壤条件的要求及整地技术及小麦的收获时期及收获方法。
理解小麦的种与变种和我国小麦的分区。
掌握小麦的播种技术、追肥在小麦器官调控中的作用;小麦防倒伏、冻害技术及原理;小麦的产量形成。
熟练掌握小麦的阶段发育理论及其在生产上的应用;小麦的种植密度、营养特性和需水特性及灌排技术;小麦各生育阶段的生育特点、苗情诊断和追肥技术及原理。
(二)课程内容
第一节 概述
第二节 小麦基本生物学特性
第三节 小麦栽培技术
第四节 小麦的田间管理
第五节 收获、贮藏与利用
(三)考核知识点
1、小麦生产概况及我国小麦分区。
2、小麦的种与变种。
3、小麦的生长发育过程和阶段发育。
4、小麦产量的形成。
5、小麦对土壤条件的要求。
6、小麦的营养特性和施肥技术及原理。
7、小麦的种植密度。
8、小麦的播种技术及原理。
9、小麦的需水特性及灌排技术。
10、小麦各生长发育阶段的生育特点及田间管理。
11、小麦的收获与贮藏。
(四)考核要求
1、识记:小麦的生产概况、小麦的种与变种、小麦的生长发育过程、小麦对氮、磷、钾的吸收量;经验施肥法;施肥量的计算公式、播种适期;播种量的计算公式、不同生育阶段的耗水量等、小麦各生育阶段苗情诊断指标。
2、领会:春化阶段、光照阶段、阶段发育等概念、小麦渍害、小麦湿害等概念、腊肥、干热风等概念。
- 7 -
3、简单应用:黄淮平原小麦产区的自然条件特点和小麦的生育期;长江流域小麦产区的自然条件特点和小麦的生育期、根据小麦品种春化阶段中对温度的要求所分的类型及各类型的特点、小麦的源、库、流与产量形成关系、小麦高产稳产对土壤条件的要求、小麦的营养特性;追肥在小麦器官调控中的作用、小麦不同高产途径对种植密度的要求;确定小麦适宜种植密度的依据、麦田灌溉及湿害、渍害的危害与防治、小麦出苗分蘖阶段的合理追肥技术及原理;冻害对小麦的影响及防御措施;小麦拔节孕穗期的生育特点及栽培管理目标、小麦的收获适期与收获方法;小麦在贮藏过程中的生理变化及贮藏技术。
4、综合应用:小麦的阶段发育特性及其在生产上的应用、小麦的产量构成因素及各因素形成过程、小麦出苗分蘖阶段的生育特点和栽培技术及原理;小麦各生育阶段的苗情诊断技术;小麦拔节孕穗期追肥技术及原理;小麦倒伏产生的原因及防治;干热风对小麦的危害及防御措施
第四章 大 麦
(一)学习目的与要求
大麦生长发育对环境条件的要求及需肥特性和施肥技术是本章的重点和难点。
了解大麦的生产概况和发展大麦生产的意义。
理解大麦亚种和各亚种的主要用途及不同生态地区大麦亚种的分布情况;大麦的综合利用途径。
掌握大麦的阶段发育理论及不同类型的分布和大麦的生育期;大麦的播种技术和田间管理技术及原理。
熟练掌握大麦生长发育对环境条件的要求;大麦的营养特性与施肥技术。
(二)课程内容
第一节 概述
第二节 大麦的分类
第三节 大麦生长发育特点
第四节 大麦主要栽培技术
第五节 大麦的综合利用
(三)考核知识点
1、发展大麦生产的意义及大麦的生产概况和分区。
2、大麦栽培种、亚种及变种。
3、大麦的阶段发育和生育期。
4、大麦生长发育对环境条件的要求。
- 8 -
5、大麦的营养特性与施肥技术。
6、大麦的播种技术。
7、大麦的田间管理技术。
8、大麦的综合利用。
(四)考核要求
1、识记:目前我国大麦生产概况;大麦的主要营养成份含量、根据大麦阶段发育中对温度和光照的反应所分各类型对低温和光照时间的具体要求;我国主要的大麦优良品种;我国不同地区大麦的生育期、大麦不同产量和不同生育期对氮、磷、钾的吸收量等、不同地区大麦的实际播种期等。
2、领会:皮大麦、裸大麦的概念、六棱大麦、四棱大麦、二棱大麦的概念。
3、简单应用:我国大麦的分区、大麦各亚种的主要用途、根据大麦品种春化阶段对低温的要求划分的类型及特性;跟据大麦光照阶段对光照条件的要求划分的类型及特性;大麦品种阶段发育特点与原产地生态条件的关系及各类型的分布、啤酒大麦的施肥特点及原理、大麦种子处理技术;确定大麦播种量的方法、大麦的综合利用途径。
4、综合应用:大麦生长发育对环境条件的要求、大麦的施肥原则和方法、大麦的田间管理技术。
第五章 玉 米
(一)学习目的与要求
玉米的生长发育与环境条件的关系及施肥技术是本章的重点和难点。
了解玉米的生产概况、玉米的主要用途及玉米的分类与我国玉米产区分布。
理解玉米的生长发育阶段和源库与产量形成。
掌握玉米的田间管理技术、播种技术、种植密度。
熟练掌握玉米的生长发育与环境条件的关系和玉米的光合作用与产量形成以及玉米的施肥技术、地膜覆盖栽培技术、育苗移栽技术。
(二)课程内容
第一节 概述
第二节 生长发育与产量形成
第三节 玉米栽培技术
(三)考核知识点
1、玉米的主要用途、生产概况及起源与分类。
2、玉米的生长发育阶段及生长发育与环境条件的关系。
- 9 -
3、玉米的产量形成。
4、玉米的播种技术与种植密度。
5、玉米的施肥技术。
6、玉米的育苗移栽技术。
7、玉米地膜覆盖栽培技术。
8、玉米田间管理技术及原理。
(四)考核要求
1、识记:世界和我国玉米生产概况、玉米的光合能力与经济系数、玉米的播种期、播种量、种植密度和种植方式。
2、领会:特用玉米、高赖氨酸玉米、高油玉米、普通甜玉米、超甜玉米、爆裂玉米等概念、玉米蹲苗的概念。
3、简单应用:玉米的主要用途;我国玉米种植分区;玉米的发展趋势;玉米按生育期分类的类型;玉米按耔粒形态与结构分类的类型、玉米的生长发育阶段;玉米缺氮的症状;玉米缺磷的症状;玉米缺钾的症状;玉米缺锌的症状;玉米生长发育对温度条件的要求;玉米生长发育对水分条件的要求、玉米的种子处理技术、玉米育苗移栽增产的原因;玉米育苗方法;玉米育苗的移栽和田间管理、玉米的收获与贮藏技术。
4、综合应用:玉米的光合作用特性、玉米的施肥原则与施肥技术、玉米地膜覆盖栽培技术、玉米苗期田间管理技术及原理;玉米穗期田间管理技术及原理;玉米花粒期田间管理技术及原理。
第六章 大 豆
(一)学习目的与要求
大豆的生长发育特性和需肥规律与施肥技术是本章的重点。大豆的产量形成过程是本章的难点。
了解大豆的生产概况及其起源与分类。
理解大豆的生长发育阶段及各阶段的生长发育特性。
掌握大豆的产量形成过程和大豆的轮作特性、播种技术、需水规律和田间管理技术。
熟练掌握大豆的需肥规律与施肥技术。
(二)课程内容
第一节 概述
第二节 大豆的生长发育与产量形成
- 10 -
第三节 大豆的栽培技术
(三)考核知识点
1、大豆的主要用途、生产概况及起源与分类。
2、大豆的生长发育阶段及各阶段的特性。
3、大豆的产量形成。
4、大豆的光周期特性。
5、大豆的轮作特性。
6、大豆的播种技术。
7、大豆的营养特性与施肥技术。
8、大豆需水规律及灌溉与排水。
9、大豆的田间管理技术。
(四)考核要求
1、识记:世界和我国大豆生产概况、大豆的生长发育阶段、产量构成因素;株高与茎粗的比值等、大豆的播种时期、播种量与种植方式等、大豆不同生育期对氮、磷、钾的吸收量等、大豆的耗水系数与耗水量。
2、简单应用:大豆的主要用途;大豆的分类和类型、大豆的产量形成过程;大豆分枝数目与产量的关系、大豆品种生育期与光周期特性的关系在引种上的应用、大豆的轮作特性和轮作方式、施用钼肥使大豆增产的原因、大豆的灌溉与排水技术、大豆摘心的作用与技术;生长调节剂在大豆上的应用;大豆的收获、留种与贮藏技术。
3、综合应用:大豆各生育阶段的生长发育特性、大豆的施肥技术及原理。
第七章 甘 薯
(一)学习目的与要求
甘薯幼苗生长与环境条件的关系以及育苗技术是奔章的重点，甘薯块根形成与膨大机制是本章的难点。
了解甘薯的用途及起源与分布情况。
理解甘薯垄作增产的原因。
掌握甘薯的抗逆性与适应性;甘薯育苗的方法与技术地膜覆盖栽培技术;合理密植技术和田间管理技术;甘薯适宜收获期及贮藏期间的管理措施。
熟练掌握甘薯块根形成与膨大机制;甘薯茎叶的生长与产量形成的关系;甘薯的萌芽习性及萌芽和幼苗生长与外界环境条件的关系;施肥技术。
(二)课程内容
- 11 -
第一节 概述
第二节 甘薯栽培特性与产量形成
第三节 甘薯的育苗
第四节 大田栽培技术
第五节 甘薯的收获与贮藏
(三)考核知识点
1、甘薯的主要用途与分布。
2、甘薯的抗逆性与适应性。
3、甘薯产量形成。
4、甘薯块根的萌芽习性与育苗技术。
5、整地与施肥。
6、插期与合理密植。
7、田间管理技术及原理。
8、甘薯的收获期与.贮藏。
(四)、考核要求
1、识记:甘薯育苗的排种量、时间与密度等、耕地深度，高产底肥施用量等、合理密植范围等、
2、领会:块根阴面、块根阳面、高热能酿热物、低热能酿热物等概念。
3、简单应用:甘薯的主要用途、甘薯的抗逆性特点;甘薯的适应性特点、甘薯块根形成过程与机制、甘薯温床育苗技术及原理;塑料薄膜育苗技术及原理;露地育苗技术及原理;苗床管理措施、甘薯垄作增产的原因、甘薯适时早插的原则、甘薯中耕除草及培土技术及原理、甘薯适宜收获期的确定方法;甘薯旧窖的消毒方法;甘薯贮藏期间的管理措施。
4、综合应用:甘薯茎叶的生长与产量形成的关系、甘薯块根的萌芽习性;甘薯块根萌发与幼苗生长与外界环境条件的关系、甘薯追肥技术及原理。
第八章 棉 花
(一)学习目的与要求
棉花的营养生理、水分生理、光合生理、育苗移栽的效应、地膜覆盖栽培的增产原理是本章的重点。高产棉田实现营养生长与生殖生长协调，个体发育与群体相适应的合理生育动态是本章的难点。
了解棉花的生产概况及用途;棉花的整地、中耕与培土技术;种子处理技术;短季棉的栽培技术要点;我国主要棉区的气候特点。
- 12 -
理解各生育期的苗情诊断原理。
掌握棉花的产量结构及其主要影响因素;棉花的整枝与化学调节技术;短季棉的生长发育特点;各生育阶段的栽培技术要点;棉花的直播技术。
熟练掌握棉花个体发育与群体生长、营养生长与生殖生长的关系及如何协调;棉花的营养生理与施肥技术;水分生理与灌排技术;光合生理与群体结构;育苗移栽的效应与方法;地膜覆盖栽培的增产原理与技术;各生育期的生长发育特点。
(二)课程内容
第一节 概述
第二节 棉花的生育进程与产量形成
第三节 棉花的栽培技术
(三)考核知识点
1、棉花的用途。
2、棉花的生产概况及我国棉花种植分区和各区的条件。
3、棉花的产量结构及其主要影响因素。
4、棉花个体与群体，营养生长与生殖生长的关系。
5、棉田中耕、培土的作用。
6、棉花的营养生理与施肥。
7、棉花的水分生理与灌排技术。
8、棉花的光合性能、群体结构与合理密植。
9、棉花的种子处理与直播技术。
10、棉花育苗移栽的效应与方法。
11、棉花地膜覆盖栽培的增产原理与技术。
12、棉花整枝与化学调节。
13、棉花各生育期的生长发育特点、苗情诊断和栽培技术要点。
14、短季棉的生长发育特点与栽培技术要点。
(四)考核要求
1、识记:棉花的主、副产品的数量与比例、棉花的生产概况、丰产优质棉花的产量结构;棉花三桃比例等、棉花的需肥数量与比例、棉花的合理密植范围等、各生育期的诊断指标等。
2、领会:五苗等概念、生育期、全生育期、铃重、衣分、籽指、衣指、伏前桃、伏桃、秋桃等概念、三湿三消毒等概念、当家肥等概念、短季棉等概念。
3、简单应用:棉花的综合利用途径、长江流域棉区的生态条件;黄河流域棉区的生态条件;西北内陆棉区的生态条件、棉花的产量构成因素;营养条件与铃重的关系、营养生长与生殖生长协调，个体发育与群体相适应的合理生育动态、棉田
- 13 -
中耕的作用;棉田杂草及其防除技术;棉花培土的作用、棉花不同生育期对养分的吸收动态;棉花合理施肥原则、棉花的需水规律;旱涝对棉花的危害;棉花合理灌溉排水原则、棉花的光合性能;确定棉花种植密度的原则、棉花种衣剂的作用、塑料薄膜覆盖育苗的苗床管理技术及原理、棉花的打顶与去叶枝;延缓型生长调节剂的使用、棉花苗期的生育特点;棉花蕾期的生育特点;棉花蕾肥和当家肥施用技术;棉花吐絮期的生育特点、短季棉的生育特点;短季棉的栽培技术要点。
4、综合应用:棉花产量构成因素与外界条件的关系、协调营养生长与生殖生长，个体与群体的意义、棉花种子准备与处理技术;棉花直播技术、棉花育苗移栽的效应;营养钵育苗方法;育苗移栽棉花的生长发育特点及高产栽培关键、地膜覆盖栽培的增产原理;地膜棉栽培技术要点、棉花各生育期的化学调节技术、棉花花铃期的生长发育特点;花铃肥和盖顶肥的作用和施用技术。
第九章 苎 麻
(一)学习目的与要求
影响产量构成因素的条件及冬季培管的技术是本章的重点，难点是苎麻的繁殖技术。
了解苎麻的用途及生产概况;苎麻的脱胶技术;苎麻的剥制技术及原理。
理解苎麻的收获时间对产量和品质的影响。
掌握苎麻的生长发育进程;新麻园的建立、管理与收获技术;苎麻的需肥特点与施肥技术;水分生理与抗旱排涝技术;防风防霜冻的生理基础;苎麻高产的产量结构。
熟练掌握影响苎麻产量构成因素的内外条件;苎麻的繁殖方法的原理与技术;苎麻的冬季培管的作用、技术;苎麻的类型及各类型的生长发育特点。
(二)课程内容
第一节 概述
第二节 苎麻的生育进程与产量形成
第三节 新麻园的建立及管理
第四节 常年麻园的栽培管理
第五节 收获与剥制
(三)考核知识点
1、苎麻的用途与生产概况。
2、苎麻的类型与品种。
3、苎麻的生长发育进程与产量形成。
- 14 -
4、苎麻繁殖技术。
5、新麻园的建立与管理。
6、苎麻的营养生理与追肥技术。
7、苎麻的水分生理与抗旱排涝。
8、苎麻冬季培管的作用、技术及原理。
9、苎麻防风防霜冻的生理基础。
10、收获时间对产量和品质的影响。
11、剥制原麻技术及原理。
(四)考核要求
1、识记:苎麻的生产概况、高产苎麻的产量结构;苎麻的生育时期及所经历的时间、麻园种植密度、苎麻吸收营养元素的数量与比例。
2、领会:幼龄期、壮龄期、衰老期、鲜茎出麻率、鲜茎出麻率等概念、破秆、蓄蔸、挽蔸的概念、冬培、败蔸等概念、风斑等概念。
3、简单应用:苎麻的综合利用途径、按苎麻地上部和地下部生长状况所分类型及各类型的生长发育特点、每季麻的生长时期及特点;一年中苎麻的生长发育过程、苎麻有性繁殖和无性繁殖的特点比较;苎麻的有性繁殖技术及其原理、栽植密度对产量和品质的影响、苎麻的需肥特点;苎麻的追肥技术及原理、苎麻的抗旱排涝技术及原理、苎麻的防风防冻技术及原理、苎麻的工艺成熟标准;苎麻的收获时间对产量和品质的影响、苎麻剥制技术及原理。
4、综合应用:影响苎麻产量构成因素的内外条件、苎麻无性繁殖方法与技术、苎麻“三当”栽培技术的内涵、原理与技术、苎麻冬季培管的作用、技术及其原理。
第十章 红 麻
(一)学习目的与要求
红麻的营养生理及施肥技术、产量形成为本章的重点，红麻纤维细胞的发育是本章的难点。
了解红麻的用途、起源与生产概况及红麻的轮作技术原理。
理解红麻的沤洗技术及原理。
掌握红麻品种的分类方法及各种类型与品种分布、识别的关系;红麻的产量构成因素及与产量的关系;红麻的收获时期及其与外界条件和红麻生长发育的关系。
熟练掌握红麻的生长发育时期及与环境条件的关系;红麻纤维细胞的发育及纤维形态;红麻的营养生理及施肥技术;红麻的苗期管理技术、播种技术、灌排技术、麦茬红麻和低洼易涝地红麻的栽培技术及原理。
- 15 -
(二)课程内容
第一节 概述
第二节 红麻的生长发育与产量形成
第三节 红麻的栽培技术
第四节 红麻的收剥与沤洗
(三)考核知识点
1、红麻的类型、起源和生产概况。
2、红麻的生长发育及纤维细胞的发育和形态。
3、红麻产量构成因素及与产量之间的关系。
4、红麻轮作与播种技术。
5、红麻苗期管理技术。
6、红麻的营养生理及施肥技术。
7、红麻的灌排技术。
8、麦茬红麻的栽培管理技术。
9、低洼易涝地红麻的栽培管理技术。
10、红麻的收获与沤洗。
(四)考核要求
1、识记:红麻的起源和生产概况、红麻各产量构成因素的范围、红麻对主要营养元素的吸收量。
2、领会:纤维细胞束、纤维细胞群、纤维细胞层等概念、笨麻、生麻、熟麻等概念。
3、简单应用:红麻品种按叶型分类的主要类型及与品种识别的关系;按生育期分类的类型及与品种分布的关系、红麻纤维细胞的发育过程、不同地区红麻品种花芽分化与日照长度的关系及在引种上的应用;红麻产量构成因素与产量之间的关系、红麻轮作的原理与技术;红麻播种期与温度的关系、红麻苗期管理技术、红麻的吸肥规律、红麻的需水特点与灌溉技术、低洼易涝地红麻的栽培管理技术与原理、确定红麻收获时期的原则及收获时期;红麻的收获方法与技术;红麻的沤洗方法、技术和原理。
4、综合应用:红麻的施肥原则和技术及其与生长发育的关系、麦茬红麻的栽培管理技术及其原理。
第十一章 油 菜
(一)学习目的与要求
- 16 -
油菜的温光反应理论和高产途径及油菜的营养特性与施肥技术是本章的重点，环境条件对油菜生长发育的影响是本章的难点。
了解油菜的用途、生产概况、类型与品种及我国油菜的分布与分区。
理解油菜早花和冻害产生的生理原因及防治技术。
掌握环境条件对油菜生长发育的影响;油菜的产量构成因素及其影响条件;油菜的营养生理特性;施肥技术;壮苗的形态和生理指标;确定油菜播种期和收获期的原则。
熟练掌握油菜的温光反应理论和高产途径;直播和育苗移栽油菜的特性;免耕油菜的栽培技术;油菜的需水特性与灌排技术;
(二)课程内容
第一节 概述
第二节 油菜的生育进程与产量形成
第三节 油菜的栽培技术
(三)考核知识点
1、油菜的生产概况及我国油菜的分布与分区。
2、油菜的类型与品种。
3、油菜的生长发育。
4、油菜的产量形成及高产途径。
5、油菜的种植方式和方法
6、油菜的营养生理与施肥技术。
7、油菜的需水特性与灌排技术。
8、油菜早花、冻害的原因、危害及防治措施。
9、油菜的收获。
(四)考核要求
1、识记:油菜生产概况、油菜的产量构成因素、油菜的播种时期。
2、领会:春油菜、冬油菜、双低油菜的概念、冬养油菜、冬壮油菜、冬发油菜、秋发油菜等概念、油菜根颈、免耕油菜等概念、根拔等概念。
3、简单应用:油菜迅速发展的原因;油菜继续发展的潜力;我国油菜的分区及各区油菜的种植制度、优质油菜的类型;油菜三大类型的植物学特征、油菜产量构成因素的形成过程;油菜冬发高产途径及原理;油菜秋发高产途径及原理、油菜播种期与其内在和外部条件的关系;育苗移栽油菜和直播油菜的生长发育特性比较;油菜壮苗的形态和生理特性指标;育苗移栽油菜苗床管理技术与原理;免耕油菜的特点、配套栽培技术及原理、油菜的需水特性与灌排技术、油菜早花产生的原因与防治措施;油菜冻害种类、产生的原因与防治措施、确定油菜适宜收获期的原
- 17 -
则。
4、综合应用:油菜的温光反应特性及其在生产上的应用 ;油菜的生长发育时期及环境条件对生长发育的影响、油菜的营养特性与缺素表现;油菜的施肥技术与原理。
第十二章 芝 麻
(一)学习目的与要求
芝麻的营养生理、水分生理特性及打顶的生理作用是本章的重点，芝麻种子发育过程中的生理变化是本章的难点。
了解芝麻的用途和生产概况;生长调节剂对芝麻生长发育的影响;芝麻的收获与贮藏。
理解芝麻种子发育过程中的生理变化。
掌握芝麻播种期确定原则和播种方式;芝麻连作减产的原因。芝麻的产量构成因素及因素之间的相互关系;芝麻的分类方法与芝麻的主要类型。
熟练掌握芝麻的生长发育过程及与环境条件的关系;芝麻的营养生理特性与施肥技术;水分生理特性与抗旱排涝技术;合理密植的生物学基础;打顶的生理作用与技术。
(二)课程内容
第一节 概述
第二节 芝麻的生长发育与产量形成
第三节 芝麻的栽培技术
(三)考核知识点
1、芝麻的用途、起源、类型及生产概况。
2、芝麻的生长发育与产量形成。
3、芝麻轮作技术及原理。
4、芝麻的播种与种植密度。
5、芝麻的营养生理特性与施肥。
6、芝麻的水分生理特性与水分管理。
7、芝麻的田间管理技术及原理。
(四)考核要求
1、 识记:芝麻的生产概况和用途、芝麻的产量构成因素及因素时间的相
互关系、芝麻的合理密植范围等。
2、 领会:芝麻的腿、芝麻黄梢尖、果轴系数等概念。
- 18 -
3、 简单应用:芝麻类型划分的依据和主要类型、芝麻的生长发育过程;芝麻种子发育过程及脂肪、蛋白质含量的变化、芝麻连作减产的原因、夏芝麻播种过晚对其生长发育和产量的影响;芝麻的播种方式及其优缺点;芝麻播种后如遇雨应及时松土破壳的生理作用、渍害对芝麻生长发育的影响、芝麻打顶的技术及其原理;芝麻生产上常用的几种植物生长调节剂对芝麻生长发育的影响;芝麻成熟的标志。
4、 综合应用:芝麻合理密植的生物学基础、芝麻的需肥特性与施肥技术。
第十三章 花 生
(一)学习目的与要求
花生生长发育对环境条件的要求和地膜覆盖栽培技术是本章的重点，花生的营养生理特性与施肥技术是本章的难点。
了解花生的生产概况和花生的主要用途;花生的脂肪酸组成及对人体健康的影响及花生的收获与贮藏技术。
理解花生的分类方法及四大类型的生长发育特性。
掌握花生的需水规律与水分管理;花生的播种技术;花生的田间管理技术;花生对土壤条件的要求;高产花生的产量结构;花生的生长发育过程。
熟练掌握花生的各产量因素形成过程及各生长发育时期对环境条件的要求;花生的营养生理特性与施肥技术;花生的地膜覆盖栽培技术。
(二)课程内容
第一节 概述
第二节 花生的生长发育与产量形成
第三节 花生的栽培技术。
(三)考核知识点
1、花生的用途、类型和生产概况。
2、花生的生长发育与产量形成。
3、花生的播种技术及原理。
4、花生的地膜覆盖栽培技术及原理。
5、花生的营养生理特性与施肥技术。
6、花生的需水规律与水分管理。
7、花生的田间管理技术及原理。
(四)考核要求
1、识记:花生的脂肪酸组成;花生的生产概况、花生的生长发育时期及划分
- 19 -
标准;高产花生的产量结构等、花生的播种适期、播种量和种植方式、花生对营养三要素的吸收量等、花生适时收获时期。
2、领会:交替开花型、连续开花型的概念、果针、双仁果率等概念、花生清棵等概念。
3、简单应用:花生的营养价值;花生四大类型的生长发育特性、花生各生育时期的生长发育特点;花生荚果发育对环境条件的要求;花生根瘤菌的形成、固氮能力变化与花生生长发育时期的关系;花生“花多果少，秕多实少”现象;高产花生的产量构成、花生经浸种催芽播种遇低温多雨后造成的影响、花生地膜覆盖栽培对产量和品质的影响、花生的营养特性、花生较耐旱的形态和生理基础、花生清棵蹲苗的技术及原理;花生成熟的标志;花生安全贮藏所需条件及原因;化学调节技术在花生上的应用。
4、综合应用:花生各生长发育时期对环境条件的要求;花生各产量构成因素的形成过程、地膜覆盖花生的栽培技术及原理、花生的施肥技术及原理、花生培土的作用;花生连作对土壤微生物、酶、速效养分的影响。
第十四章 烟 草
(一)学习目的与要求
环境条件对烟草生长发育及产量和品质的影响及施肥技术是本章的重点，烟草的品质因素和各营养元素对烟草产量和品质的影响是本章的难点。
了解烟草在国民经济中的作用与生产概况及分布与分区及烟叶的烘烤技术。
理解烟草的主要类型及品质特点。
掌握烟草的生长发育时期和产量构成;育苗移栽和田间管理技术;烟叶的分组与采收。
熟练掌握环境条件对烟草生长发育及产量和品质的影响;烟草的品质因素;烟草的营养生理与施肥技术;烟叶的成熟过程和成熟指标。
(二)课程内容
第一节 概述
第二节 烟草栽培的生物学基础
第三节 烟草的栽培技术
第四节 烟草成熟、采收和烘烤
(三)考核知识点
1、烟草的用途、类型及品质和分布与分区。
2、烟草的生长发育时期和产量构成。
- 20 -
3、烟草的品质因素。
4、烟草的育苗技术及原理。
5、烟草的营养生理基础与施肥技术。
6、烟草的田间管理技术及原理。
7、烟叶的成熟过程和成熟标准。
8、烟叶的分组与采收。
9、烟叶的烘烤。
(四)考核要求
1、识记:烟草的生产概况和主要产区、烟草的产量构成因素及优质适产栽培的产量范围、烟草的播种时期等、烟草对主要营养元素的吸收量。
2、领会:烤烟、晒烟、晾烟、马里兰烟、白肋烟、香料烟等概念、施木克值、评吸、焦油等概念、早花、底烘等概念。
3、简单应用:烟草主要类型的植物学特点;烟草主要类型的加工特点;烟草主要类型的品质特点;黄花烟的植物学特点、品质特点和在我国的主要种植区域;烤烟最适宜种植区域的环境条件、烟草在苗床的生长发育时期及各时期的特点;烟草移栽至大田后的生长发育时期及各时期的特点;烟草产量构成因素间的相互关系、烟草种子处理技术及原理;烟草苗期的管理技术及原理、烟草的施肥原则;烟草追肥及与品质的关系、烟草早花和底烘产生的原因与防止技术;烟草打顶、抹杈的生理基础、烟叶的成熟过程;烟叶成熟的标准、烟叶的分组及各组叶片的品质特点、烟叶烘烤经历的阶段及各阶段对温度的要求。
4、综合应用:环境条件对烟草生长发育及产量和品质的影响、烟草的品质因素及各因素的主要指标、营养元素对烟草产量和品质的影响;烟草施肥的生理基础。 三、有关说明与考核实施要求
(一)编制大纲的目的和作用
本课程自学考试大纲是根据专业自学考试计划的要求，结合自学考试的特点而编写的。其目的是对个人自学、社会助学和本课程考试命题进行知道和规定。
本课程自学考试大纲明确了课程学习的内容以及深广度，规定了课程自学考试的范围和标准。因此，它是选用或编写自学考试教材和辅导书的依据，是社会助学组纪念品进行自学辅导的依据。是自学者学习教材、掌握课程内容知识范围和程度的依据，也是进行本课程自学考试命题的依据。
(二)本大纲与教材的关系
本大纲与所选用教材的基本内容完全一致。教材的内容只是大纲所规定的课程
- 21 -
知识和内容的扩展与发挥。因此，自学、助学、命题应以大纲为依据，教材为范围。 选用的参考教材为自学教材同类，内容基本一致，是在自学教材的基础上修订完成的，有顶替自学教材的作用。
(三)自学教材与参考教材
1、自学教材
作物栽培学 (上、下册) 王维金主编 华中农业大学 1995
2、参考教材
作物栽培学 王维金主编 科学技术文献出版社 1998
3、参考书
作物栽培学各论 杨文钰主编 中国农业出版社 2003
(四)自学要求与自学方法
本大纲的基本要求是依据专业计划和专业培养目标而确定的，明确了鞥的基本内容以及应掌握的程度。知识点是课程内容的主体。因此，课程基本内容掌握程度、课程考核知识点是自学考试考核的主要内容。
本大纲对自学教材各章内容掌握的程度要求由低到高分为四个层次，依次是了解、理解、掌握、熟练掌握。
为有效地指导个人自学和社会助学，本大纲已指明了各章内容的重点和难点。
本课程为6学分，不含实验学分。
自学方法:作物栽培学的特点是密切联系生产实际，实践性强。自学者应在识记作物栽培学内容的基础上，到田间系统地观察2,3种不同类型作物的形态、生长发育状况以及田间管理措施，在观察的同时，应用所学知识分析生产实际中存在的问题，并提出解决办法，以便加深对书本知识的理解，并培养观察问题、分析问题和解决问题的能力。
(五)对社会助学的要求
要在自学并已了解基本内容的基础上进行社会助学。45学时。助学中主要辅导基本要求中的重点和难点，并注重实践能力的培养。对一些重点内容应辅之于标本或影像资料加以说明，以加深对知识内容的深入理解与记忆。
(六)对考核内容和考核目标的说明
本课程要求自学者学习和掌握的知识点内容都作为考核的内容，具体体现在各章的考核知识点中。由于各知识点在课程中的地位、作用以及知识自身特点不同，分别按四个能力层次确定其考核要求，其由低到高依次为
识记:要求应考者能够对大纲中的知识点，如定义、规律、公式、性质、作物栽培的季节特征等有清晰准确的认识，并能做出正确的判断和选择。
领会:要求应考者对大纲中的概念、规律、公式、性质等有一定的理解，清楚- 22 -
它与有关部门知识点的联系与区别，并能做出正确的表述和解释。
简单应用:要求应考者能够运用大纲中各部分的少数几个知识点，解决生产实际中的一些较简单的问题。
综合应用:要求应考者能够运用多个知识点，理论联系实际地分析、解决生产实践中一些稍复杂的问题。
(七)关于试卷结构及考试的有关说明
1( 本大纲各章所规定的考核要求中各知点都是考试的内容。试题覆盖到章，适当突出重点章节，加大重点内容的覆盖密度。
2( 命题不应有超出大纲中考核知识点范围的试题，考核目标不得高于大纲中所规定的相应最高能力层次要求。
3(“识记”、“领会”、“简单应用”、“综合应用”四个认知层次的试题在试卷中所占的分数比例依次约为:20%、30%、30%、20%。
4(试题的难度可分为:容易，中等偏易，中等偏难，难;它们在试卷中所占分数比例依次大致为:20%、30%、30%、20%。
5(试题的题型有:单项选择题、多项选择题、名词解释、简答题、论述题。
6(考试方式为笔试、闭卷;考试时间为150分钟;60分为及格线。考试时只允许带钢笔或圆珠笔、2B铅笔和橡皮。
附录:题型举例
一、单项选择题:
( )1、小麦进入减数分裂期时，叶耳距多为
A. ,6,,4cm B. ,4,,2cm C.,2~0cm D 0~2cm
二、多项选择题:
( )2、移栽油菜的壮苗特征中有
A.绿叶6-7片 B.叶片宽15,20? C.根颈粗6-7mm
D.苗高20-23? E.根长10,15?
三、名词解释:
3、叶龄指数
四、简答题:
4、水稻壮秧的生理特性是什么,
五、论述题:
5、论述作物营养器官和生殖器官生长之间的相互影响及数量关系。
- 23 -
自学考试数据结构重点总结02331(2014整理)
自考数据结构重点（2014整理）
第一章 概论
1. 瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
2. 数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。
3. 数据结构指的是数据元素之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算
①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。
数据的逻辑结构分类: 线性结构和非线性结构
②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算。最常用的检索、插入、删除、更新、排序等。
4. 数据的四种基本存储方法: 顺序存储、链接存储、索引存储、散列存储
（1）顺序存储：通常借助程序设计语言的数组描述。
（2）链接存储：通常借助于程序语言的指针来描述。
（3）索引存储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。
（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。
5. 算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。
算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal 和类C 。
6. 评价算法的优劣：算法的" 正确性" 是首先要考虑的。此外，主要考虑如下三点：
① 执行算法所耗费的时间，即时间复杂性；
② 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；
③ 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。
7. 算法求解问题的输入量称为问题的规模, 用一个正整数n 表示。
8. 常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(log2n) 、线性阶0(n)、线性对数阶0(nlog2n) 、
23k n 平方阶0(n) 立方阶0(n) 、…、k 次方阶0(n) 、指数阶0(2) 和阶乘阶0(n!)。
9. 一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n 的函数, 它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。
第二章 线性表
1. 数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。
2. 只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。
3. 常见的线性表的基本运算:
(1)置空表InitList （L ） 构造一个空的线性表L 。
(2)求表长ListLength （L ）求线性表L 中的结点个数，即求表长。
(3)GetNode（L ，i ） 取线性表L 中的第i 个元素。
(4)LocateNode（L ，x ）在L 中查找第一个值为x 的元素，并返回该元素在L 中的位置。若L 中没有元素的值为x ，则返回0值。
(5)InsertList（L ，i ，x ）在线性表L 的第i 个元素之前插入一个值为x 的新元素，表L 的长度加1。
(6)DeleteList（L ，i ）删除线性表L 的第i 个元素，删除后表L 的长度减1。
4. 顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。
顺序表（Sequential List ）：用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构, 顺序表的特
点是逻辑上相邻的结点其物理位置亦相邻。
5. 顺序表上实现的基本运算：
（1）插入：该算法的平均时间复杂度是O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
（2）删除：顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O(n)。
6. 采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指针的名字来命名。①生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc 分配一个类型为ListNode 的结点变量的空间, 并将其首地址放入指针变量p 中②释放结点变量空间的标准函数 free(p)；//释放p 所指的结点变量空间 ③结点分量的访问 方法二：p-﹥data 和p-﹥next
④指针变量p 和结点变量*p的关系: 指针变量p 的值——结点地址, 结点变量*p的值——结点内容
7. 建立单链表:
（1） 头插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode));①//生成新结点
p->data=ch; ② //将读入的数据放入新结点的数据域中
p->next=head;③
head=p;④
（2） 尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode)); ①//生成新结点
p->data=ch; ② //将读入的数据放入新结点的数据域中
if (head==NULL)
head=p;//新结点插入空表
else
rear->next=p;③//将新结点插到*r之后
rear=p;④//尾指针指向新表尾
（3） 尾插法建带头结点的单链表：
头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:
⒈由于开始结点的位置被存放在头结点的指针域中, 所以在链表的第一个位置上的操作就和在表的其它位置上操作一致, 无须进行特殊处理;
⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
头结点数据域的阴影表示该部分不存储信息。在有的应用
中可用于存放表长等附加信息。
具体算法：r=head; // 尾指针初值也指向头结点
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data=ch; //将读入的数据放入新结点的数据域中
r->next=s;
r=s;
}
r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空
以上三个算法的时间复杂度均为O(n)。
8. 单链表上的查找：（带头结点）
（1）按结点序号查找：序号为0的是头结点。
算法：p=head;j=0;//从头结点开始扫描
while(p->next&&j p=p->next; j++; } if(i==j) return p;//找到了第i 个结点 else return NULL;//当i<0或i>0时，找不到第i 个结点 时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n) （2）按结点值查找： 具体算法：ListNode *p=head->next;//从开始结点比较。表非空，p 初始值指向开始结点 while(p&&p->data!=key)//直到p 为NULL 或p->data为key 为止 p=p->next;//扫描下一结点 return p;//若p=NULL，则查找失败，否则p 指向值为key 的结点 时间复杂度为：O(n) 9. 插入运算：插入运算是将值为x 的新结点插入到表的第i 个结点的位置上，即插入到a i-1与a i 之间。 s=(ListNode *)malloc(sizeof(ListNode)); ② s->data=x;③s->next=p->next④;p->next=s;⑤ 算法的时间主要耗费在查找结点上，故时间复杂度亦为O(n)。 10. 删除运算 r=p->next;②//使r 指向被删除的结点a i p->next=r->next③;//将a i 从链上摘下 free(r);④//释放结点a i 的空间给存储池 算法的时间复杂度也是O （n ）。 p指向被删除的前一个结点。 链表上实现的插入和删除运算，无须移动结点，仅需修改指针。 11. 单循环链表—在单链表中，将终端结点的指针域NULL 改为指向表头结点或开始结点即可。判断空链表的条件是head==head->next; 12. 仅设尾指针的单循环链表: 用尾指针rear 表示的单循环链表对开始结点a 1和终端结点a n 查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为 rear==rear->next; 13. 循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。 具体算法： LinkList Connect(LinkList A,LinkList B) {//假设A ，B 为非空循环链表的尾指针 LinkList p=A->next;//①保存A 表的头结点位置 A->next=B->next->next;//②B 表的开始结点链接到A 表尾 free(B->next);//③释放B 表的头结点 B->next=p;//④ return B;//返回新循环链表的尾指针 循环链表中没有NULL 指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p 或p-＞next 是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。 在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。 14. 双向链表: 双（向）链表中有两条方向不同的链，即每个结点中除next 域存放后继结点地址外，还增加一个指 向其直接前趋的指针域prior 。 ①双链表由头指针head 惟一确定的。 ②带头结点的双链表的某些运算变得方便。 ③将头结点和尾结点链接起来，为双（向）循环链表。 15. 双向链表的前插和删除本结点操作 ①双链表的前插操作 void DInsertBefore(DListNode *p,DataType x){//在带头结点的双链表中，将值为x 的新结点插入*p之前，设p≠NULL DListNode *s=malloc(sizeof(DListNode));//① s->data=x;//② s->prior=p->prior;//③ s->next=p;//④ p->prior->next=s;//⑤ p->prior=s;//⑥ } ②双链表上删除结点*p自身的操作 void DDeleteNode(DListNode *p) {//在带头结点的双链表中，删除结点*p，设*p为非终端结点 p->prior->next=p->next;//① p->next->prior=p->prior;//② free(p);//③ } 与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。 16. 顺序表和链表比较 时间性能：a 、线性表：经常性的查找； b、链式存储结构：经常插入删除操作； 空间性能：a 、对数据量大小事先能够知道的用线性表； b、数据量变化较大的用链式存储结构。 存储密度越大，存储空间的利用率越高。显然，顺序表的存储密度是1，链表的存储密度肯定小于1。 第三章 栈和队列 1. 栈称为后进先出（Last In First Out）的线性表，简称为LIFO 表。 栈是运算受限的线性表，顺序栈也是用数组表示的。 进栈操作：进栈时，需要将S-＞top 加1， ①S-＞top==StackSize-1表示栈满 ②" 上溢" 现象--当栈满时，再做进栈运算产生空间溢出的现象。 退栈操作：退栈时，需将S-＞top 减1， ①S-＞top<> ②" 下溢" 现象--当栈空时，做退栈运算产生的溢出现象。 下溢是正常现象，常用作程序控制转移的条件。 空栈时栈顶指针不能是0，只能是-1。 当程序中同时使用两个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端，让两个栈顶各自向中间延伸。当一个栈中的元素较多而栈使用的空间超过共享空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者 的部分存储空间。 当Top1=Top2-1时，栈满 2. 为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题。可采用链式存储结构来存储栈。链栈是没有附加 头结点的运算受限的单链表。栈顶指针就是链表的头指针。 链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull 运算 栈的一个重要应用是实现递归，直接调用自己或间接调用自己的函数。 3. 允许删除的一端称为队头（Front ），允许插入的一端称为队尾（Rear ），当队列中没有元素时称为空队列，队列亦 称作先进先出（First In First Out）的线性表，简称为FIFO 表。 队列的顺序存储结构称为顺序队列，顺序队列实际上是一个受限的 线性表。 顺序队列的基本操作 ①入队时：将新元素插入rear 所指的位置，然后将rear 加1。 ②出队时：删去front 所指的元素，然后将front 加1并返回被删元素。 当头尾指针相等时，队列为空。 在非空队列里，头指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。而栈顶指针指向栈顶元素。 4. 循环队列：为充分利用数组空间，克服上溢，可将数组空间想象为一个环状空间，并称这种环状数组表示的队列为循环队列。 循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： ① 方法一： if(i+1==QueueSize) //i表示front 或rear i=0; else i++; ② 方法二--利用" 模运算" i=(i+1)%QueueSize； 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件Q.front==Q.rear来判别队列是" 空" 还是" 满" 。 解决这个问题的方法至少有三种： ① 另设一个标志位以区别队列是空还是满； ② 设置一个计数器记录队列中元素的总数（即队列长度）。 ③ 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队列满即尾指针Q.rear 所指的单元始终为空。 5. 循环队列的基本运算: ① 置队空: Q->front=Q->rear=0; ② 判队空: return Q->rear==Q->front; ③ 判队满: return (Q->rear+1)%QueueSize==Q->front; ④ 入队 Q->data[Q->rear]=x; //新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize; ⑤ 出队 temp=Q->data[Q->front]; Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1 return temp; ⑥取队头元素 return Q->data[Q->front]; 6. 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。 为了简化处理，在队头结点之前附加一个头结点，并设队头指针指向此结点。 链队列的基本运算:（带头结点） （1） 构造空队：Q->rear=Q->front；Q->rear->next=NULL; （2） 判队空：return Q->rear==Q->front; （3） 入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点 p->data=x; p->next=NULL; Q->rear->next=p; //*p链到原队尾结点后 Q->rear=p; //队尾指针指向新的尾 （4） 出队：当队列长度大于1时，只需修改头结点指针，尾指针不变 s=Q->front->next; Q->front->next=s->next; x=s->data; free(s); return x; 当队列长度等于1时，不仅要修改头结点指针，还要修改尾指针 s=Q->front->next; Q->front->next=NULL; Q->rear==Q->front; x=s->data; free(s); return x; （5） 取队头元素：return Q->front->next->data; 因为有头结点，所以用了next ①和链栈类似，无须考虑判队满的运算及上溢。 ②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。 7. 用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。 第四章 多维数组和广义表 1. 数组的顺序存储方式:一般采用顺序存储方法表示数组。 （1）行优先顺序 a11,a 12,…,a1n ,a 21,a 22,…,a2n ,……，a m1,a m2,…，a mn （2）列优先顺序 a11,a 21,…,am1,a 12,a 22,…,am2,……，a 1n ,a 2n ,…，a mn Pascal 和C 语言是按行优先顺序存储的，而Fortran 语言是按列优先顺序存储的。 2. 为了节省存储空间，可以对矩阵中有许多值相同或值为零的元素的矩阵，采用压缩存储。 特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。 （1）对称矩阵 在一个n 阶方阵A 中，若元素满足下述性质： aij =aji 0≤i，j≤n-1 称为n 阶对称矩阵，它的元素是关于主对角线对称的，所以只需要存储矩阵上三角或下三角元素即可，让两个对称的元素共享一个存储空间。 矩阵元素a ij 和数组元素sa 【k 】之间的关系是 k=i×(i+1)/2+j i≥j 0≤k k=j×(j+1)/2+i i＜j 0≤k （2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角(不包括主角线) 中的元素均为常数c 或零；下三角矩阵的主对角线上方均为常数c 或零。一般情况，三角矩阵的常数c 均为零。 三角矩阵的压缩存储：三角矩阵中的重复元素c 可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储在一维数组sa[n(n+1)/2+1]中，其中c 存放在数组的最后一个元素中。 三角矩阵的压缩存储结构是随机存取结构。 3. 稀疏矩阵:设矩阵A mn 中有s 个非零元素，若s 远远小于矩阵元素的总数，则称A 为稀疏矩阵。为了节省存储单元，可用压缩存储方法只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行、列位置，所以可用三元组(i，j ，a ij ) 来确定非零元素。 稀疏矩阵进行压缩存储通常有两类方法：顺序存储(三元组表) 和链式存储(十字链表) 。稀疏矩阵的压缩存储会失去随机存取功能。 4. 广义表是线性表的推广, 又称列表。 广义表是n(n≥0)个元素a 1，a 2，…，a i ，…，a n 的有限序列。其中a i 或者是原子或者是一个广义表。 ①广义表通常用圆括号括起来，用逗号分隔其中的元素。 ②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 ③若广义表Ls 非空(n≥1)，则a l 是LS 的表头，其余元素组成的表(a1，a 2，…，a n ) 称为Ls 的表尾。 ④广义表具有递归和共享的性质 广义表的深度：一个表展开后所含括号的层数称为广义表的深度。 19. 广义表是一种多层次的线性结构，实际上这就是一种树形结构。 任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。 head=(a，b)=a，tail(a，b)=(b) 对非空表A 和(y)，也可继续分解。 注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l 的由空表作元素的广义表，可以分解得到的表头和表尾均是空表()。 广义表是一种有层次的非线性结构，通常采用链式存储结构，每个元素用一个结点表示，结点由3个域构成，其中一个是tag 标志位，用来区分结点是原子还是子表，当tag 为零时结点是子表，第二个域为slink ，用以存放子表的地址；当tag 为1时结点是原子，第二个域为data ，用以存放元素值。 第五章 树和二叉树 1. 树的表示法：最常用的是树形图表示法；还有3种嵌套集合、凹形、广义表。 树结构的基本术语 （1）结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的度(Degree)。一棵树的度是指该树中结点的最大度数。 度为零的结点称为叶子(Leaf)或终端结点。度不为零的结点称分支结点或非终端结点。 除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。 （2）①路径（path ）若树中存在一个结点序列k 1，k 2，…，k i ，使得k i 是k i+1的双亲(1≤i 一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。 结点的层数(Level)从根起算：根的层数为1，其余结点的层数等于其双亲结点的层数加1。 双亲在同一层的结点互为堂兄弟。 树中结点的最大层数称为树的高度(Height)或深度(Depth)。 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换) ，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。若不特别指明，一般讨论的树都是有序树。 森林(Forest)是m(m≥0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。 3. 二叉树与度数为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 二叉树的性质： i-14性质1 二叉树第i 层上的结点数目最多为2(i≥1)。例如5层的二叉树，第5层上的结点数目最多为2=16 k 5性质2 深度为k 的二叉树至多有2-1个结点(k≥1)。例如深度为5的二叉树，至多有2-1=31个结点 性质3 在任意-棵二叉树中，若终端结点的个数为n 0，度为2的结点数为n 2，则n o =n2+1。例如一棵深度为4的二叉树（a ），其终端结点数n 0为8, 度为2的结点树为7，则8=7+1，n o =n2+1成立 （b ）其终端结点数n 0为6, 度为2的结点树为5， 则6=5+1，n o =n2+1成立 k 满二叉树：一棵深度为k 且有2-1个结点的二又树称为满二叉树。满二叉树的特点： （1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 （2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 完全二叉树：若一棵深度为k 的二叉树，其前k-1层是一棵满二叉树，而最下面一层上的结点都集中在该层最左边 的若干位置上，则此二叉树称为完全二叉树。特点： （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 性质4 具有n 个结点的完全二叉树的深度为。?logn ?+1 或?log(n+1)? 例，具有100个结点的完全二叉树的深度为:?lg100?+1=7,2=64 2=128所以?lg100?=6 , ?lg(100+1)?=7 4. 完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结 点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子等结点的编号。编号从0开始 ①若i=0，则q i 为根结点，无双亲；否则，q i 的双亲编号为?(i-1)/2?。 ②若2i+1 ③若2i+2 对于完全二叉树而言，使用顺序存储结构既简单又节省存储空间。但对于一般二叉树来说，采用顺序存储时，为了使用结点在数组中的相对位置来表示结点之间的逻辑关系，就必须增加一些虚结点使其成为完全二叉树的形式。 5. 链式存储结构: 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild 和rchild ，分别指向该结点的左孩子和右孩子。结点的结构为： 二叉链表是一种常用的二叉树存储结构。 建立二叉链表方法：a 、按广义表方法，靠近左括号的结点是在左子树上，而逗号右边结点是在右子树上。 b 、按完全二叉树的层次顺序建立结点。 具有n 个结点的二叉链表中，共有2n 个指针域。其中有n-1个用来指示结点的左、右孩子，其余的n+1个为空。 二叉树遍历算法中的递归终止条件是二叉树为空。 递归工作栈中包括两项：一项是递归调用的语句编号，另一项则是指向根结点的指针。 已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列，可唯一确定一棵二叉树。具体方法如下： 首先根据前序或后序遍历序列确定二叉树的各子树的的根，然后根据中序遍历序列确定各子树根的左右子树。 67 6. 线索二叉树：n 个结点的二叉链表必定存在n+1个空指针域，可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种指向前驱和后继结点的指针称为" 线索" ，这种加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。 线索链表的结点结构： 其中:ltag和rtag 是增加的两个标志域，用来区分结点的左、右指针 域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。 图中的实线表示指针，虚线表示线索。 线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。 7. 二叉树的线索化: 把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。 和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n 个结点的二叉树，线索化的算法时间复杂度为O(n)。 8. 树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子(长子) 和一个右邻的兄弟。 将树转换成二叉树：①在所有兄弟结点之间加一道连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 将一个森林转换为二叉树: 将森林中的每棵树转化成二叉树，然后再将二叉树的根节点看做兄弟连在一起，形成一棵二叉树 9. 二叉树到树、森林的转换: 方式是：若二叉树中结点x 是双亲y 的左孩子，则把x 的 右孩子，右孩子的右孩子，…，都与y 用连线连起来，最后去掉所有双亲到右孩子的连线。 10. 树的存储结构： 1. 双亲表示法：双亲链表表示法利用树中每个结点的双亲唯一性， 在存储结点信息的同时，为每个结点附设一个指向其双亲的指针 parent ，惟一地表示任何-棵树。 （1）双亲链表表示法的实现 分析：E 和F 所在结点的双亲域是1，它们的双亲结点在向量中的位 置是1，即B 是它们的双亲。 注意：① 根无双亲，其parent 域为-1。 ② 双亲链表表示法中指针parent 向上链接，适合求指定结 点的双亲或祖先(包括根) ；求指定结点的孩子或其它后代时，可能 要遍历整个数组。 2. 孩子链表法：孩子链表表示法是为树中每个结点设置一个孩子链 表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 注意：① 孩子结点的数据域仅存放了它们在向量空间的序号。 ② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 ③ 将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。 3. 孩子兄弟表示法：在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域，即可得树的 孩子兄弟链表表示。 注意： 这种存储结构的最大优点是：它和二叉树的二叉链 表表示完全一样。可利用二叉树的算法来实现对树的操 作。 11. 树的遍历： 一般都只给出两种次序遍历树的方法：前序(先根次序) 遍历和后序(后根次序) 遍历。 ① 前序遍历一棵树等价于前序遍历该树对应的二叉树 ② 后序遍历一棵树等价于中序遍历该树对应的二叉树。 对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFIGJH 和BDCAIFJGHE 。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH 和BDCAIFJGHE 。 ① 前序遍历森林等同于前序遍历该森林对应的二叉树 ② 后序遍历森林等同于中序遍历该森林对应的二叉树 12. 从根结点到某结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度，树种所有叶子结点的带权路径长度之和称为树的带权路径长度。 带权路径长度WPL 最小的二叉树称为哈夫曼树或最优二叉树。 哈夫曼树不一定是二叉树。 哈夫曼树又称为最优树，是一类带权路径长度最短的树。完全二叉树就是这种路径长度最短的二叉树。 ① 只有叶结点上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 ② 最优二叉树中，权越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，WPL 最小。 13. 哈夫曼算法: 注意：① 初始森林中的n 棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 ② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。 ③ 哈夫曼树是严格的二叉树，没有度数为1的分支结点。 14. 哈夫曼编码： 数据压缩过程称为编码, 反之，解压缩的过程称为解码。 设计一种长短不等的编码，则必须保证任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 可以利用二叉树来设计二进制的前缀编码，其左分支表示字符0，右分支表示字符1，则以根结点到叶结点路径上的分支字符组成的串作为该叶节点的字符编码。 因此设计电文总长最短的二进制前缀编码，就是以n 种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。 译码过程是从树根结点出发，逐个读入电文中的二进制码。 第六章 1. 图G 由两个集合构成，顶点集合和边集合，也可以图G 只有顶点而没有边。用尖括号表示图的有向边 在无向图中，称v i 和v j 相邻接，在有向图中称顶点v i 邻接到v j ，顶点v j 邻接于v i 在无向图中，n 的取值范围是0-n(n-1)/2，将具有n(n-1)/2条边的无向图称为无向完全图。 在有向图中，n 的取值范围是0-n(n-1)，将具有n(n-1)条边的有向图称为有向完全图。 无向图中，顶点的度定义为以该顶点为一个端点的边的数目，有向图的度等于出度和入度之和。 在无向图中，任意两顶点都有路径，则称两顶点连通。若图G 中的任意两个顶点都连通，称G 为连通图。无向图的极大连通子图称为连通分量，显然，任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通分量。 在有向图中，图G 中任意两顶点连通，称为强连通图，极大连通子图称为强连通分量。 若在一个图的每条边上标上某种数值，该数值称为该边的权。边上带权的图称为带权图，带权的连通图称为网络。 2. 图的存储结构：邻接矩阵和邻接表表示法。图的顶点编号从0开始。 邻接矩阵表示法： 无向图的邻接矩阵是按主对角线对称的。若G 是带权图，只要把1换成相应边上的权值即可，0的位置上可以不动 2或将其换成无穷大表示。无向图的邻接矩阵表示法可以仅存储主对角线以下的元素，时间复杂度为O(n) 邻接表表示法：邻接表是图的一种链式存储结构。将无向图的邻接表称为边表，将有向图的邻接表称为出边表，将邻接表的表头向量称为顶点表。若无向图有n 个顶点和e 条边，则它的邻接表共有n 个头结点和2e 个表结点。 建立邻接表的时间复杂度是O(n+e)。图的邻接表表示不是唯一的, 这是因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。 3. 图的遍历：遍历图的算法是求解图的连通性、图的拓扑排序等算法的基础。 图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。 深度优先搜索遍历(DFS)类似于前序(先根) 遍历。按访问顶点的先后次序得到的顶点序列称为图的深度优先遍历序 22列，或简称为DFS 序列。共需要搜索n 个矩阵元素，时间复杂度为邻接矩阵O(n) 或邻接表O(n+e)。 广度优先搜索遍历(BFS)类似于树的按层次遍历，先被访问的顶点，其邻接点也先被访问，就是先进先出。 2时间复杂度为邻接矩阵O(n) 或邻接表O(n+e)，空间复杂度都是O(n)。 4. 生成树是连通图的包含图中所有顶点的一个极小连通子图，一个图的极小连通子图恰为一个无回路的连通图，也就是说，若图中任意添加一条边，就会出现回路，若去掉任意一条边，都会使之成为非连通图。 因此，一个具有n 个顶点的生成树有且仅有n-1条边，但有n-1条边的图不一定是生成树，同一个图可以有不同的生成树。 生成树定义为：若从图的某顶点出发，可以系统的访问到图的所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称为该图的生成树。 最小生成树：图的生成树不唯一，把权值最小的生成树称为最小生成树（MST ）。 2 构造最小生成树的算法：普里姆Prim 算法的时间复杂度为O （n ）与网中边数无关适于稠密图。 克鲁斯卡尔Kruskal 算法的时间复杂度为O （eloge ），主要取决于边数，较适合于稀疏图。 5. 最短路径：Dijkstra 迪杰斯特拉算法，提出了按路径长度递增的顺序产生诸顶点的最短路径算法。 拓扑排序：子工程称为活动，顶点代表活动，有向边代表活动的先后关系。这样的有向无环图DAG 称为顶点活动网，简称为AOV 网。 将有向无环图G 中所有顶点排成一个线性序列，若 检测的方法是：对有向图构造其顶点的拓扑序列，若网中所有顶点都在他的拓扑序列中，则AOV 网必定不存在环。 AOV网的拓扑序列不是唯一的。 拓扑排序的描述思想：a 、在有向图中选一个没有前趋(入度为零) 的顶点，且输出之。b 、从有向图中删除该顶点及其与该顶点有关的所有边。c 、重复上述步骤，直到全部顶点都已输出或图中剩余的顶点中没有前趋顶点为止。 d 、输出剩余的无前趋结点。 拓扑排序实际上是对邻接表表示的图G 进行遍历的过程。时间复杂度是O(n+e)。 第七章 排序 1. 如果待排序文件中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；反之，则是不稳定的。 排序在内存中处理，不涉及数据的内外存交换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、选择、交换、归并和分配排序。 在排序过程中需进行两种操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身，而待排序记录的存储形式一般有三种：顺序结构、链式结构和辅助表。 评价排序算法的标准：执行算法需要的时间，以及算法所需要的附加空间。还有算法本身的复杂度。 排序的时间开销，一般情况下可用算法中关键字的比较次数和记录的移动次数来衡量。 2. 插入排序：每次将一个待排序记录按其关键字大小插入到前面已排好序的文件中的适当位置。 直接插入排序：每次从无序区取出第一个元素把它插入到有序区的适当位置，使之成为新的有序区，经过n-1次插入后完成。算法中R[0]作用：保存R[i]副本，监视数组下标变量j 是否越界。所以R[0]称为哨兵。每次的比较是从后往前比较的。 22时间复杂度最好是O(n)，最坏是O(n) ，所以是O(n) 。空间复杂度O(1)，所以是就地排序。 是稳定的算法。 初始情况是有序区中只有一个元素R[1]，无序区中R[2..n]。 希尔排序(缩小增量排序) ：算法不稳定。记录的总比较次数和总移动次数都要比直接插入排序少得多，特别是当 n 越大越明显。希尔排序的时间依赖于增量序列，最后一个增量必须是1，尽量避免增量互为倍数的情况。 3. 交换排序：两两比较待排序记录的关键字，如果发现两个记录的次序相反时即进行交换，直到没有反序位置。 冒泡排序(起泡排序) ：通过相邻元素之间比较和交换，使较小移向顶部，从后往前两两比较。 22时间复杂度最好是O(n)，最坏是O(n) ，所以是O(n) 。是稳定的排序算法。 快速排序(划分交换排序) ：是冒泡排序的改进。比较和交换从两端向中间进行。 一趟快速排序步骤：设两个指针i 和j ，初值分别为low 和high ，基准为x=R[i]，首先从j 位置开始向前搜索第一个小于基准x.key 的记录存入i 所指位置上，i 自增1，然后从i 所指位置向后搜索找到第一个大于基准x.key 的记录存入j 所指位置上，j 自减1，重复直至i=j为止。 快速排序是不稳定的。有非常好的时间复杂度，优于其他各种排序算法，O(nlog2n) ，但是当记录关键字有序或基本 2有序时复杂度反而大了使之转变成冒泡排序为O(n) 。快速排序是递归的，需要一个栈空间，空间复杂度O(log2n) 。 4. 选择排序：每一趟在待排序的记录中选出关键字最小的记录，依次存放在已排序好的记录序列的最后。 直接选择排序：初始时，R[1..n]为无序区，R[1]为空；第一趟是在R[1..n]中选出最小的记录与R[1]交换，R[1] 2为有序区；第二趟是在R[2..n]中选出最小的记录与R[2]交换，R[1..2]为有序区。时间复杂度O(n) ，是不稳定的。 初始情况是有序区为空，无序区中R[1..n]，第一趟从R[1..n]选择最小记录与R[1]交换。 堆排序：是对直接选择排序的改进，是一种树形选择排序。基本思想：在排序过程中，将记录数组R[1..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大或最小记录。 每一趟排序：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将他和无序区中最后一个记录交换。 堆排序是一个不断建堆的过程。构造堆的过程：R[1]作为二叉树的根，R[2..n]依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R ?i/2?，此称为筛选法。从?n/2?开始。 每一趟的时间复杂度是O(log2n) ，整个堆排序的时间复杂度是O(nlog2n) 。 5. 归并排序：首先将待排序文件看成n 个长度为1的有序子文件，把这些子文件两两归并，得到?n/2?个长度为2的有序子文件，然后再将他们两两归并，如此反复，直到得到一个长度为n 的有序文件，此称为二路归并排序。 每一趟归并排序的时间复杂度是O(n)，所以总的时间复杂度是O(nlog2n) 。 6. 分配排序：前面方法都至少需要进行?nlogn ?次比较，而分配排序将时间复杂度降为O(n)。 箱排序(桶排序) ： 基数排序：是对箱排序的改进和推广。箱排序只适用于关键字取值范围较小的情况，否则所需箱子数目太多。 每个分量可能取值的个数rd 称为基数，基数的选择和关键字的分解因关键字的类型而异。d 趟箱排序。 基数排序中，没有进行关键字的比较和记录的移动，而只是扫描链表和进行指针赋值，所以排序的时间主要用在修改指针上，初始化链表时间为O(n)。 选取排序方法时需要考虑的主要因素：a 、待排序的记录个数，b 、记录本身的大小和存储结构，c 、关键字的分布情况，d 、对排序稳定性的要求，e 、时间和空间复杂度要等 排序方法的选取： a 、若待排序的一组记录数目n 较小(如n ≤50) 时，可采用插入排序或选择排序；b 、n 较大时，则应采用快速排序、堆排序或归并排序；c 、若待排序记录按关键字基本有序时，则宜选用直接插入排序或冒泡排序；d 、当n 很大，而且关键字位数较少时，采用链式基数排序较好；e 、关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。 一般的排序方法都可以在顺序结构上实现，当记录本身信息量较大时，可采用链式存储结构。 插入、归并、基数排序易于在链表上实现；快速排序和堆排序可以提取关键字建立索引表，然后对索引表进行排序。 第八章：查找 1. 查找又称检索，是数据处理中经常使用的一种重要运算。 查找也分为内查找和外查找。 运算查找的主要操作是关键字的比较，因此把查找过程中的平均比较次数(也称为平均查找长度) 作为衡量算法效率优劣的标准。 2. 顺序表的查找：顺序查找和二分查找 顺序查找又称线性查找：查找成功的平均查找长度(n+1)/2，即约为表长的一半。 如果查找成功和不成功机会相等，那么平均查找长度3(n+1)/4。 优点是简单，对表的结构无任何要求，无论是顺序存储和链式存储、无论是否有序，都同样适用，缺点是效率低。 对于有序表来说，该算法的平均查找长度是(n+1)/2。 二分查找(折半查找) ：要求查找对象的线性表必须是顺序存储结构的有序表。查找过程是递归的。 树中每个子树的根节点对应当前查找区间的中位记录R[mid]，它的左子树和右子树分别对应区间的左子表和右子 表，通常将此树称为二叉判定树。由于二分查找是在有序表上进行的，所以其对应的判定树必定是一棵二叉排序树。 二叉判定树一定是二叉排序树，二叉排序树又称为二叉查找树。 从判定树上可见，关键字比较的次数恰好为该结点在树中的层数。因此，二分查找算法在查找成功时进行关键字比较的次数最多不超过判定树的深度。查找成功时的平均查找长度 (n+1)/nlog2(n+1)-1，当n 很大时，可近似用log 2(n+1)-1表示。因为判定树度数小于2的结点只可能在最下面的两层，所以n 个结点的判定树的深度和n 个结点的完全二叉树的深度相同，即为?log 2(n+1)?。可见，二分查找的最坏性能和平均性能相当接近。 二叉判定树的输出：每次以?(low+high)/2?为根建树。 3. 索引顺序查找(分块查找) ：是一种介于顺序查找和二分查找之间的查找方法。要求分块有序，前一块的最大关键字小于后一块的最小关键字，抽取各块中的最大关键字及其起始位置构成索引表。 分块查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。 2平均查找长度：二分查找log(n/s+1)+s/2， 顺序查找(s+2s+n)/2s。 4. 三种查找方法比较 顺序查找缺点是n 较大时，查找成功约为(n+1)/2，失败需要比较n+1次。 二分查找成功时约为log 2(n+1)-1，但是他要求表以顺序存储且按关键字有序，适用于表不易变动且又经常查找的情况。 分块查找的优点是，在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入或删除操作，因为块内记录是无序的，所以插入或删除比较容易，无需移动大量记录。主要缺点是需要增加一个辅助数组的存储空间和将初始表块排序的运算，它也不适用于链式存储结构。 上述三种查找的时间复杂度分别是O(n)、O(log2n) 和O(n的平方根) 5. 二叉排序树(二叉查找树) ：或者是一棵空树，或者具有下面性质：a 、若右子树非空，则右子树上所有结点的值均大于根节点的值。b 、若左子树非空，则左子树上所有结点的值均小于根节点的值。c 、左右子树本身又各是一棵二叉排序树。 由此可得，按中序遍历二叉排序树所得到的遍历序列是一个递增有序序列。 同样一组关键字序列，由于其输入顺序不同，所得到的二叉排序树也有所不同，含有n 个结点的二叉排序树不是唯一的。 构造二叉排序树的真正目的并不是为了排序，而是为了更好地查找，又称为二叉查找树。 二叉排序树的查找与给定值的比较次数不会超过树的深度。若二叉排序树是一颗理想的平衡树或接近理想的平衡树，则时间复杂度为O(log2n) ，若退化为一棵单支树，则时间复杂度为O(n)。 二叉排序树的删除：被删除结点为p ，其父结点为f 。具体操作为： a 、若p 是叶子结点，直接删除p ； b 、若p 只有一棵子树(左子树或右子树) ，直接用p 的左子树(或右子树) 取代p 的位置而成为f 的一棵子树。即p 是左子树则p 的子树变为f 的左子树； c 、若p 既有左子树又有右子树，任选一种方法： (1)、用p 的直接前驱结点代替p ，即从p 的左子树中选择值最大的结点s 放在p 的位置(用结点s 的内容替换结点p 内容) ，然后删除结点s 。s 是p 的左子树中最右边的结点且没有右子树； (2)、用p 的直接后继结点代替p ，即从p 的右子树中选择值最小的结点s 放在p 的位置(用结点s 的内容替换结点p 内容) ，然后删除结点s 。s 是p 的右子树中最左边的结点且没有左子树。 在二叉排序树上实现插入和查找操作的平均时间复杂度为O(log2n) ，但在最坏得情况下，会变成O(n)。 平衡二叉树：既能满足BST 性质又能保证二叉排序树的深度在任何情况下均为O(log2n) 。 6.B 树是一种平衡的多路查找树。 一棵m(m≥3) 阶的B 树，或为空树，或为满足下列性质的m 叉树 a、每个结点至少包含下列信息域；b 、每个结点至多有m 棵子树；c 、若树为非空，则根结点至少有1个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两颗子树。d 、每个非根结点中所含的关键字个数满足： ?m/2?-1≤n ≤m-1，因为每个内部结点的度数正好是关键字总数加1，所以处根结点之外的所有非终端结点至少有?m/2?棵子树，至多有m 棵子树。 在B 树上插入和删除元素的运算比较复杂，它要求进行运算后的结点中关键字个数≥?m/2?-1， 在B 树进行查找包括两种基本操作：在B 树中查找结点、在结点中查找关键字。 7.B 树是一种文件组织的B 树的变形树，通常有两个头指针root 和sqt ，前者指向根结点，后者指向关键字最小的 +叶子结点。因此可对B 树进行两种查找运算：一种是从最小关键字起进行顺序查找，一种是从根结点开始进行随机 查找。 8. 散列表查找是通过对记录的关键字值进行某种运算直接求出记录的地址，是一种由关键字到地址的直接转换方法。 散列存储中使用的函数称为散列函数或哈希函数，散列地址或哈希地址，散列表或哈希表。 具有相同散列地址的关键字称为同义词。冲突的频度除了与散列函数H 相关外，还与散列表的填满程度相关。 如何尽量避免冲突和冲突发生后如何解决冲突，就成了散列存储的两个关键问题。 散列函数的目标是使散列地址尽可能均匀的分布在散列空间上，同时使计算尽可能简单。 直接地址法：计算简单，并且没有冲突。适合于关键字的分布基本连续的情况。 数字分析法：从中提取数字分布比较均匀的若干位作为散列地址。 + 除余数法：p 最好取小于或等于表长m 的最大素数。这是一种最简单也最常用的方法。 平方取中法： 折叠法：把关键字分割成位数相同的几段，分为移位叠加和边界叠加。 9. 处理冲突的方法：开放定址法和拉链法。 开放定址法：线性探查法、二次探查法和双重散列法(几种方法中最好的方法) 。 2222二次探查法：d+1，d-1，d+2，d-2 拉链法：存储结构是链表时常用。把具有相同散列地址的关键字值放在同一个单链表中，称为同义词链表。有m 个散列地址就有m 个链表。用拉链法处理冲突比开放定址法多占用一些存储空间用作链表指针，但它可以减少在插入和查找过程中关键字的平均比较次数(平均查找长度) 。 10. 查找不成功时，顺序查找和二分查找所需要进行的关键字仅取决于表长，而散列表查找所需要进行的比较次数和待查结点有关。 散列表查找，计算查找成功的平均查找长度时，除数是结点的个数，而在计算查找不成功的平均查找长度时，除数却是表长。 开放定址法：装填因子α≤1，实用中一般取0.65-0.9之间的某个值。 拉链法：α可以大于1，但一般取α≤1。 绝密?考试结束前 全国2014年4月高等教育自学考试 数据结构导论试题 课程代码:02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项: 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是 A.O(logn) B.O(n) 2 2C.O(n) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有 A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为 A.O(1) B.O(logn) 2 2C.O(n) D.O(n) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为 A.O(1) B.O(logn) 2 2C.O(n) D.O(n) 浙02142# 数据结构导论试题 第1页 共5页 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为 A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为 A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为 A.31个 B.32个 C.63个 D.64个 8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为 A.1 B.3 C.4 D.5 9.将题9图所示的一棵树转换为二叉树，结点C是 A.A的左孩子 B.A的右孩子 C.B的右孩子 D.E的右孩子 10.n为图的顶点个数，e为图中弧的数目，则图的拓扑排序算法的时间复杂度为 A.O(n) B.O(e) C.O(n-e) D.O(n+e) 11.无向图的邻接矩阵是 A.对角矩阵 B.稀疏矩阵 C.上三角矩阵 D.对称矩阵 12.在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为 A.50 B.51 C.100 D.101 13.构造散列函数的方法很多，常用的构造方法有 A.数字分析法、除留余数法、平方取中法 B.线性探测法、二次探测法、除留余数法 C.线性探测法、除留余数法、链地址法 D.线性探测法、二次探测法、链地址法 浙02142# 数据结构导论试题 第2页 共5页 14.就平均时间性能而言，快速排序方法最佳，其时间复杂度为 n) A.O(n) B.O(nlog2 2C.O(n) D.O(1ogn) 2 15.下述算法中，不稳定的排序算法是 A.直接插入排序 B.冒泡排序 C.堆排序 D.归并排序 非选择题部分 注意事项: 用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。 二、填空题(本大题共13小题，每小题2分，共26分) 16.数据的基本单位是_________。 17.双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为 t->prior=P;t->next=p->next;_________;p->next=t;。 18.在带有头结点的循环链表中，尾指针为rear，判断指针P所指结点为首结点的条件是_________。 19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是_________。 20.不含任何数据元素的栈称为_________。 21.稀疏矩阵一般采用的压缩存储方法是_________。 22.100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有_________个。 23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有_________个结点。 24.n个顶点的有向图G用邻接矩阵A[1..n，1..n]存储，其第i列的所有元素之和等于顶点 V的_________。 i 25.具有10个顶点的有向完全图的弧数为_________。 26.要完全避免散列所产生的“堆积’’现象，通常采用_________解决冲突。 27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为_________。 浙02142# 数据结构导论试题 第3页 共5页 28.归并排序算法的时间复杂度是_________。 三、应用题(本大题共5小题，每小题6分，共30分) 29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。 30.设二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，试画出该二叉树。 31.写出题31图所示无向图的邻接矩阵，并写出每个顶点的度。 题31图 32.已知散列表的地址空间为0至13，散列函数H(k)=kmod11，(mod为求余运算)，待散列序列为(26，61，38，84，49)，用二次探测法解决冲突，构造该序列的散列表，要求写出处理冲突的过程。 33.将一组键值(80，50，65，13，86，35，96，57，39，79，59，15)应用二路归并排序算法从小到大排序，试写出各趟的结果。 四、算法设计题(本大题共2小题，每小题7分，共14分) 34.设单链表及链栈S的结构定义如下: 浙02142# 数据结构导论试题 第4页 共5页 typedef struct node { Data Type data; struct node*next; ,linkstack; 编写一个算法void ReverseList(1inkstack *head)，借助于栈S将带头结点单链表head中序号 ，a，a，为奇数的结点逆置，序号为偶数的结点保持不变。(例如:单链表的逻辑结构为(a123a)，逆置后变为(a，a，a，a，a，a))。 ，a，a456523416 说明:栈的初始化运算用InitStack(S);进栈运算用Push(S，x);判栈空运算用EmptyStack(S);出栈运算用Pop(S);取栈顶元素运算用Gettop(S)。 35.以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。 浙02142# 数据结构导论试题 第5页 共5页 第 一 章 概论 第 二 章 线 性 表 第 三 章 栈 和 队 列 第 四 章 串 第 五 章 多 维 数 组 第 六 章 树 第 七 章 图 第 八 章 排序 第 九 章 查找 第 一 章 概 论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括： 1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。 常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。 分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。 优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题； 类：是在实现层上描述问题； 在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点， 并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的质量： 1正确性；算法应能正确地事先预定的功能。 2易读性；算法应易于阅读和理解，以便于调试和扩充。 3健壮性；当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。 4高效率；即达到所需的时间和空间性能。 11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。 时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2?)、线性阶O(n)、线性对数阶O(nlog2?)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。 13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。 12.算法的特征：有穷性；确定性；可行性；输入；输出 。 13. 决定算法运行时间的因素：（1）问题的规模；（2）编译时间；（3）指令执行速度；（4）重复执行指令的速度。 第 二 章 线 性 表 1.线性表：是由n(n≥0)个数据元素组成的有穷序列。 2.线性表的基本运算有： 1）Initiate(L),加工型运算，作用是构造空表，即表的初始化； 2）Length(L),引用型运算，其结果是表的结点个数，即表长； 3）Get (L,i), 引用型运算，若1≤i≤Length(L)，其结果是表中的第i个结点；否则，为一特殊值。 4）Locate (L,x) ，引用型运算，查找L中值为x的结点并返回结点在L中的位置，若有多个x则返回首个；否则返回特殊值表示查找失败。 5）Insert (L,x,i)，加工型运算，在表的第i个位置插入值为x的新结点，要求1≤i≤Length(L)+1； 6）Delete (L,i)，加工型运算，删除表的第i个位置的结点，要求1≤i≤Length(L)； 3.顺序表：是线性表的顺序存储结构，即按顺序存储方式构造的线性表的存储结构。 4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n （其中Loc(a1)是顺序表的第一个结点，C每个变量占用的内存单元）。 5.顺序表上的基本运算 （1）插入 Void insert_sqlist(sqlist L,datatype x,int i) /*将X插入到顺序表L的第i-1个位置*/ { if(L.last==maxsize) error(“overflow”); /*溢出*/ if((i<1)||(i>L.last+1)) error (“position error”); /*非法位置*/ for(j=L.last;j=i;j--) L.data[j]=L.data[j-1]; /*结点依次后移*/ L.data[i-1]=x; /*置入X*/ L.last=L.last+1 /*修改表长*/ } 在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。 （2）删除 Void delete_sqlist(sqlist L,int i); /*删除顺序表L中的第i个位置上的结点*/ { if ((i<1)||(i>L.last)) error (“position error”)； /*非法位置*/ for(j=i+1;j=L.last;j++) L.data[j-2]=L.data[j-1]; /*依次前移，注意第一个L.data[j-2]存放ai*/ L.last=L.last-1 /*修改表长*/ } 在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。 （3）定位 Void locate_sqlist(sqlist L,datatype X) /*在顺序表中从前往后查找第一个值等于X的结点。若找到则传回该节点的序号；否则传回0*/ { i=1; /*i指示顺序表L中结点序号*/ while ((i≤L.last)&&(L.data[i-1]!=x)) /*注意：a1在L.data[i-1]中*/ i++； /*从前往后找*/ if (i≤L.last) return (i) else return (0) } 6. .单链表：只有一个链域的链表称单链表。 （单链表表示法的基本思想是用指针表示结点间的逻辑关系） 单链表的一个结点包含两个部分，结点形式如下： 数据域 指针域（链域） （1） 建立单链表。时间复杂度为O(n)。 在单链表中加头结点的作用：操作统一；无论链表是否为空，链表的指针不变。 （2） 定位（按值查找） Int locate_lklist(lklist head,datatype x) /*求表head 中第一个值等于X的结点的序号。不存在这种结点时结果为0*/ { P=head;j=0; /*置初值*/ While((p->next!=NULL)&&(p->data!=x)) { p=p->next;j++; } If p->data==x return(j); Else return(0); } (3)删除 时间复杂度为O(n) Void delete_lklist(lklist head;int i) /*删除表head的第i个结点*/ { p=find_lklist(head,i-1); /*先找待删结点的直接前驱*/ q=p->next; /*q指向待删结点*/ p->next=q->next; /*摘除待删结点*/ free(q); /*释放已摘除结点q*/ } Else error(“不存在第i个结点”) /*否则给出相关信息*/ } （3） 插入 时间复杂度为O(n) Void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ { P=find_lklist (head,i-1); /*先找第i-1个结点*/ if(p==NULL) /*若第i-1个结点不存在*/ error(“不存在第i个位置”) /*退出并给出出错信息*/ else { S=malloc(size); s->data=x; /*否则生成新结点*/ S->next=p->next; /*结点*p的链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } } 7..循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。 主要优点：从表中任一结点出发都能通过后移做而扫描整个循环链表。 8.空循环链表仅由一个自成循环的头结点表示。 prior data next ，形成的链表中有两条不同方向的链称为双链表。 10.双链表的特点是找结点的前驱和后继都很容易。 11.顺序表和链表的比较 1） 基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。 2） 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。 第 三 章 栈 和 队 列 1. 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。 插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。 2. 栈的基本运算有： （1） 初始化 Initstack(s),加工型运算，构造一个空栈。 （2） 进栈 Push(S,X)，加工型运算，将元素X插入栈S中，是X成为栈S的栈顶元素。 （3） 退栈 Pop(s),加工型运算， 当栈不为空时，将栈顶元素赋给X，并从栈中删除当前栈顶。 （4） 读栈顶 Top(s),引用型运算，若栈S不空，由X返回栈顶元素；当栈S为空时，结果为一个特殊标志。 （5） 判栈空 Empty(s ), 引用型运算，若栈S为空栈，则结果为1，否则结果为0. 3. 顺序栈：栈的顺序存储结构称顺序栈。 4. .当栈满时，做进栈运算必定产生空间溢出，称“上溢”。 当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。 5. 在顺序栈上的基本运算： 1） 置空栈。 Void initstack(seqstack *s) { s->top=-1; } 2)判栈空。 int stackempty(seqstack *s) { return s->top==-1; } 3)判栈满。 int stackfull(seqstack *s) { return s->top==stacksize-1; } 4)进栈。 Void push(seqstack *s,datatype x) { if(stackfull(s)) error(“stack overflow”); s->data[++s->top]=x; } 5)退栈。 Datatype pop(seqstack *s) { if(stackempty(s)) error(“stack underflow”); return S->data[s->top--]; } 6)取栈顶元素。 Dtatatype stacktop(seqstack *s) { if(stackempty(s)) error(“stack underflow”); return S->data[s->top]; } 6. 链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。 7.链栈上的基本运算： 1） 建栈。 Void initstack(linkstack *s) { s->top=NULL; } 2)判栈空。 Int stackempty (linkstack *s) { return s->top==NULL; } 3) 进栈。 Void push(linkstack *s,datatype x) { stacknode *p=(stacknode *)malloc(sizeof(stacknode)); p->data=x; p->next=s->top; s->top=p; } 4) 退栈。 Datatype pop(linksatck *s) { datatype x; stacknode *p=s->top; if(stackempty(s)) error(“stack underflow”); x=p->data; s->top=p->next; free(p); return x; } 5) 取栈顶元素。 Datatype stacktop(linkstack *s) { if(stackempty(s)) error(“stack is empty”); return s->top->data; } 8. 队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。 队列又称为先进先出线性表，FIFO表。 9. 队列的基本运算： 1）初始化 InitQueue(Q),加工型运算，设置一个空队列Q。 2）入队列 EnQueue(Q,X),加工型运算，将X插入到队列Q的队尾。 3）出队 OutQueue(Q,X)，加工型运算，若队列Q不为空，则将队头元素赋给X，并删除队头结点，而该结点的后继成为新的队头结点。 4）判队列空 EmptyQueue(Q),引用型运算，若队列Q为空，则返回的值为1，否则为0。 5）读队头 GetHead(Q,x),引用型运算，Q不空时由参数X返回队头结点的值，否则给一特殊标志。 10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。 11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。 12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环 向量，存储在其中的队列称循环队列。i=(i+1)%queuesize 13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。 解决的方法有： 1） 另设一个布尔变量以区别队列的空和满； 2） 少用一个元素，在入队前测试rear在循环意义下加1是否等于front； 3） 使用一个记数器记录元素总数 14. 链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。 15. .链队列的基本运算： 1）入队。 Void enqueue(linkqueue *q,datatype x) { queuenode *p=(queuenode *)malloc(sizeof(queuenode)); p->data=x; p->next=NULL; if(queueempty(q)) q-front=q->rear=p; else { q->rear->next=p; q->rear=p; } } 2）出队。 Datatype dequeue(linkqueue *q) { datatype x; queuenode *p; if(queueempty(q)) error(“queue is underflow”); p=q->front; x=p->data; q->front=p->next; if(q->rear==p) q->rear=NULL; free(p); return x; } 第 四 章 串 1. 串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度； 2. 空串：长度为零的串称空串； 空白串：由一个或多个空格组成的串称空白串； 子串：串中任意个连续字符组成的子序列称该串的子串； 主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置； 3. 空串是任意串的子串； 任意串是自身的子串； 串常量在程序中只能引用但不能改变其值； 串变量取值可以改变； 4. 串的基本运算 （1） 赋值 ASSIGN(S,T),加工型运算，将串T的值传给串变量S。 （2） 判等 EQUAL(S,T),引用型运算，若S和T 的值相等则返回值为1，否则返回值为0. （3） 求长 LENGTH(S),引用型运算，求串的长度。 （4） 联接 CONCAT(S,T),引用型运算，运算结果为由S和T联接在一起形成的新串。 （5） 求子串SUBSTR(S,i,j),引用型运算，其结果是串S中从第i个字符开始的，由连续j个字符组成的子串。 （6） 插入 INSERT(S1,i,S2),加工型运算，作用是将串S2整个插入到串S1的第i个字符之后从而产生的一个新串。 （7） 删除 DELETE(S,I,j),加工新运算，作用是从串S中删去从第i个字符开始的长度为j的子串。 （8） 定位INDEX(S,T)，引用型运算，若在串S中存在一个于T相等的子串，则本运算的结果为S中第一个这样的子串中的第一个字符在S中的位置；否则，结果为0. （9） 替换 REPLACE(S,T,R)，加工型运算，结果是在串S中处处同时以串R置换串T的所有出现所得的新串。 5. 串的存储结构： （1） 串的顺序存储 （2） 串的链接存储 第 五 章 多 维 数 组 1. 多维数组：一般用顺序存储的方式表示数组。 2. 数组的逻辑结构是线性结构的推广。 3. 数组的基本运算是： （1） 读：给定一组下标，读取相应的数据元素； （2） 写：给定一组下标，修改相应的数据元素。 4. 矩阵的压缩存储：值相同的多个元素只分配一个存储空间，零元素不分配空间。 （1） 特殊矩阵：值相同的元素或零元素在矩阵中分布有一定的规律的矩阵。 1） 对称矩阵：：在一个n阶的方阵A中，元素满足Aij=Aji 1<><=n;称为对称矩阵。 元素的总数为：n(n+1)/2;=""> 2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c。 元素总数为：(n(n+1)/2)+1; （2） 稀疏矩阵：矩阵中零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵。 第 六 章 树 1.树：是n个结点的有限集T，T为空时称空树，否则满足： 1）有且仅有一个特定的称为根的结点； 2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。 2. 树上任一个结点拥有的子树数称为该结点的度； 3.一棵树的度是指树中结点最大的度数。 4. 度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点 5.根结点称开始结点，根结点外的分支结点称内部结点； 6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲； 7. 结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；一棵树中所有结点层数的最大值称为树的高度或深度； 8.树中的每个结点的子树不能更改其位置，称为有序树；反之称为无序树。 9.二叉树是结点的有穷集合，它或者是空集，或者同时满足下面两个条件： （1）有且只有一个称为根的结点； （2）其余结点分为两个互不相交的集合T1,T2，T1和T2都是二叉树，并且T1,T2有顺序关系（T1在T2前面），它们分别称为根的左子树和右子树。 10.二叉树的特征：1 度不大于2; 2 分左，右分支。 11.度为2的有序树与二叉树的区别是：前者的子树次序是相对的，而后者是绝对的。 12.二叉树的物种形态： 13.二叉树的基本运算： 1）.初始化 2）.求根 3）求双亲 4）求左孩子和右孩子 5）建树 6）剪枝 14.二叉树的性质： 1）二叉树第i(i≥1)层上至多有2i-1个结点。 2）深度为k(k≥1)的二叉树至多有2k-1个结点。 3）对任何二叉树，若2度结点数为n2，则叶子数为n0=n2+1。 15. 满二叉树是一棵深度为k的且有2k-1个结点的二叉树； 16.完全二叉树是在一棵深度为k(k≥1)的满二叉树上删去第k层上最右边的连续j(0≤j≤2k-1)个结点。 17 .具有N个结点的完全二叉树的深度为log2N取整加1；（二叉树的第四个 性质） 18.如果将一棵有n个结点的完全二叉树按层编号，则对任意编号i(1≤i≤n)的结点X有： 1）.若i=1，则结点X是根；若i>1,则X的双亲的编号为∣i/2∣. 2).若2i>n,则结点X无左孩子（且无右孩子）；否则，X的左孩子的编号为2i。 3）.若2i+1>n,则结点X无右孩子；否则，X的右孩子编号为2i+1。 19.二叉树中某一结点的左子树深度减去右子树的深度，称为该结点的平衡因子。 20.二叉树的存储结构 （1）链式存储结构： 二叉链表结点的结构为：l lchild | data | rchild ∣ ； 二叉链表由根指针唯一确定。 （2）顺序存储结构： 把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个一维数组b[0~n]中，b[1~n]存放结点，b[0]存放结点总数。 各个结点编号间的关系： 1） i=1是根结点；i>1则双亲结点是i/2取整； 2） 左孩子是2i, 右孩子是2i+1；（要小于n） 3） i>（n/2取整）的结点是叶子； 4） 奇数没有右兄弟，左兄弟是i-1； 5） 偶数没有左兄弟，右兄弟是i+1； 21.二叉树的遍历：就是按某种次序系统的“访问”二叉树上的所有结点，是每个结点恰好被“访问”一次。 22. 二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。 23.树的存储结构： （1）孩子链表表示法是树的一种链式存储结构。 1）孩子链表表示法的思想是：树上的一个结点的内容以及指向该结点所有的孩子的指针存储在一起以便于运算的实现。 2）一个孩子链表是一个带头结点的单链表，单链表的头结点含有两个域：数据域和指针域。 （以图1为例） 数据域指针域 孩子域 指针域 （2）孩子兄弟链表表示法： （3）.双亲表示法： 24.森林通常定义为树的集合。 25. 树、森林与二叉树的转换 （1）树与二叉树的转换： 1）所有兄弟间连线； 2）保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空 （2）森林与二叉树的转换： 1）将所有树转换成二叉树； 2）将所有树根连线。 26. 树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树； 后序遍历等价于中序遍历对应二叉树。 27.从树中一个结点到另一个结点之间的分支，构成这两个节点之间的路径； 路径上的分支的数目称为路径的长度。 28.结点上赋一个有实际意义的实数，称此实数为根结点的权。 29.从根结点到根结点之间的路径长度于根结点上权的积称为结点的带权路径长度。 30.树中所有叶子结点的带权路径长度之和记做树的带权路径长度。 31.n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树称 为哈夫曼树（HuFFman），又叫最优二叉树。 32.对字符集进行编码时，字符集中任一个编码都不是其他字符的编码的前缀，称为前缀码。 第 七 章 图 1. 图：图G由两个集合V和E组成，记作G=(V,E)，其中V是顶点的有穷非空集合，E是边的集合，而边是V中顶点的偶对。 2. 若定点的偶对是有序的，则称此图为有向图，有序偶对用<>括起来； 若顶点偶对是无序的，则称此图为无向图，无序偶对用（）括起来。 3. 端点和邻接点：图中若存在有一条边（Vi,Vj），则称Vi,Vj为此边的两个端点，并称他们为邻接点。 4. 顶点的度，入度，出度：无向图中顶点的度定义为无向图中以该顶点为一个端点的边的数目；有向图顶点的出度是以该顶点为起始点的边的数目；入度是以该顶点为终点的边的数目。 5. 顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图； 6. 子图：设G,H是图，若V(H)包含于V(G)，E(H)包含于E(G)，则称H是G的子图，G是H的母图；如果H是G的子图且V(H)= V(G)，则称H为G的支撑子图。 7. 可及和连通分量：从顶点Vi到顶点Vj若存在路径，则称Vi和Vj可及；在无向图的顶点集中任意两个顶点都可及，则称此无向图为连通图；；极大连通子图称连通分量。 8. 在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量。 9. 权和网：为边赋一个具有某种意义的数值，成这个数值为该边的权；带权的图称为网。 10. 一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。 11. 图的存储结构：（P109） （1） 邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。 无向图是对称矩阵；有向图行是出度，列是入度。 （2） 邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstarc,并顺序存储在一个向量中；vertex保存顶点信息，firstarc保存邻接表头指针。 12. 邻接矩阵表示法与邻接表表示法的比较： 1） 邻接矩阵是唯一的，邻接表不唯一； 2） 存储稀疏图用邻接表，存储稠密图用邻接矩阵； 3） 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便； 4） 判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)； 5） 求边数e，邻接矩阵耗时为O(n^2)，与e无关，邻接表的耗时为O(e+n)； 13.图的遍历： （1）.图的深度优先搜索：假定图中某个顶点Vi为出发点，首先访问出发点 ，然后任选一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索，直到图中所有结点都被访问过。 （2）.图的广度优先搜索：从图中某个顶点Vi出发，在访问了Vi之后依次访问Vi的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。 14.生成树中各边的权值和称为该树的树值。 15.权值最小的生成树称为图的最小生成树。 16.求最小生成树的方法：（书P118） （1）.普里姆（PRIM）算法： （2）克鲁斯卡尔（kruskal）算法： 17.在有向图中，顶点表示活动，有向边表示活动之间的先后关系，称这种关系为A.O.V网。 18.拓扑序列：A.O.V网中的所有顶点排成一个顺序序列，使每个活动的所有前驱活动都排在该活动的前面。 19.构造A.O.V网拓扑序列的过程称为拓扑排序。 第 八 章 排 序 1. 文件：由一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字； 2. 排序是将文件按关键字的递增（减）顺序排列； 3. 排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序； 4. 在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序，反之称外排序； 5. 内排序的方法主要有：插入排序，交换排序，选择排序，归并排序等四类。 6. 常用的插入排序有：直接插入排序，折半插入排序，表插入排序和希尔排序。 7. 直接插入排序：依次将每个记录插入到一个有序的子序列中去。 算法中引入监视哨R[0]的作用是： 1） 保存R[i]的副本； 2） 简化边界条件，防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2； 算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； 8. 交换排序：将键值较大的记录向序列尾部移动，键值较小的记录向序列的前部移动。 （1）.冒泡排序： 实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2； 算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； （2）.快速排序： 实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2； 算法的最好时间是O(nlog2n)；最坏时间是O(n^2)；平均时间是O(nlog2n)；辅助空 间为O(log2n)；是一种不稳定排序； 9.选择排序： （1）直接选择排序 实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。 关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)； 算法的最好时间是O(n^2)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的不稳定的排序； （2） 堆排序 实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。 算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序； 9. 归并排序：要求待排序列部分有序 （1）.部分有序的含义是待排序列由若干个有序的子序列组成。 （2）.基本是想：将这些有序的子序列进行合并，从而得到有序的序列。 （3）.方法：比较各子序列的第一个记录的键值，最小的一个就是排列后序列的第一个记录的键值。取出这些记录，继续比较各子序列现在的第一个记录的键值，便可以找出排序后的第二个记录。如此继续下去，最终得到排序结果。 因此，归并的基础是合并。 10. 二路归并排序： 实现过程：如果序列中有n个记录，可以把它看成n个子序列，每个子序列中只包含一个记录。先将每相邻的两个子序列合并，得到（n/2）个较大的有序子序列，每个子序列包含2个记录。再将这些子序列两两合并，得到（（n/2）/2）个有序子序列。如此反复，直到最后合并成一个有序序列。 第 九 章 查 找 1. 查找表是一种以集合为逻辑结构，以查找为“核心”运算，同时包括其他运算的数据结构。 2. 由任意一些可辨认的对象构成的整体称为集合。 3. 集合与其他逻辑结构（线性结构，树状结构，图状结构）的根本区别：在集合这种逻辑结构中，任何结点之间都不存在逻辑关系。这也是集合这种逻辑结构的基本特点。 4. .查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。 5. 二分查找(又称折半查找)，它的算法思想：是对一有序表中的元素，从初始的查找区间开始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，则查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。 二分查找在等概率的情况下查找成功的平均查找长度ASL为lg(n+1)-1,在查找失败时所需比较的关键字个数不超过判定树的深度，最坏情况下查找成功的比较次数也不超过判定树的深度 lg(n+1)(不小于lg(n+1)的最小整数) 2）二分查找只适用于顺序存储结构而不能用链式存储结构实现。因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 6. 二叉排序树(BST)又称二叉查找树，其定义是：二叉排序树要或者是空树或者满足如下性质的二叉树： 1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 3)左、右子树本身又是一棵二叉排序树。 2009年自学考试《数据结构》各章要点 第一章 概 论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位, 可以由若干个数据项组成。 数据项是具有独立含义的最小 标识单位。 数据结构的定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机。 ·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:是逻辑结构用计算机语言的实现。 ·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项。 ·散列存储结构:如散列表。 ·对数据的操作:定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用的有:检索、插入、删除、更新、排序。 ·数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。 ·原子类型:由语言提供。 ·结构类型:由用户借助于描述机制定义,是导出类型。 抽象数据类型 ADT : ·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构, 设计一个好的算法。 算法取决于 数据结构。 算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。 评价算法的好坏的因素: ·算法是正确的 ; ·执行算法的时间 ; ·执行算法的存储空间 (主要是辅助存储空间 ); ·算法易于理解、编码、调试。 时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模 n 的函数。 渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为:常数阶 O(1)、对数阶 O(log2n)、线性阶 O(n)、 线性对数阶 O(nlog2n)、 平方阶 O(n^2)、 立方阶 O(n^3)、 ?? k 次方阶 O(n^k)、 指数阶 O(2^n)。 空间复杂度:是某个算法的空间耗费,它是该算法所求解问题规模 n 的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。 第二章 线性表 线性表是由 n ≥ 0个数据元素组成的有限序列。 n=0是空表 ; 非空表,只能有一个开始结 点,有且只能有一个终端结点。 线性表上定义的基本运算: ·构造空表:Initlist(L) ·求表长:Listlength(L) ·取结点:GetNode(L, i) ·查找:LocateNode(L, x) ·插入:InsertList(L, x , i) ·删除:Delete(L, i) 顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。 在存储单元 中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算: LOCa(i)=LOCa(1)+(i-1)*d;(首地址为 1) /考试 大收集整理 / 在顺序表中实现的基本运算: ·插入:平均移动结点次数为 n/2;平均时间复杂度均为 O(n)。 ·删除:平均移动结点次数为 (n-1)/2;平均时间复杂度均为 O(n)。 线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同, 为了能正确表示结点 间的逻辑关系,在存储每个结点值的同时,还存储了其后继结点的地址信息 (即指针或链 ) 。 这两部分信息组成链表中的结点结构。 一个单链表由头指针的名字来命名。 单链表运算: ·建立单链表 ·头插法:s->next=head;head=s;生成的顺序与输入顺序相反。平均时间复杂度均为 O(n)。 ·尾插法:head=rear=null;if(head=null) head=s;else r->next=s;r=s; 平均时间复 杂度均为 O(n) ·加头结点的算法:对开始结点的操作无需特殊处理,统一了空表和非空表。 ·查找 ·按序号:与查找位置有关,平均时间复杂度均为 O(n)。 ·按值:与输入实例有关,平均时间复杂度均为 O(n)。 ·插入运算:p=GetNode(L, i-1);s->next=p->next;p->next=s;平均时间复杂度均为 O(n) ·删除运算:p=GetNode(L, i-1);r=p->next;p->next=r->next;free(r);平均时间复杂 度均为 O(n) 单循环链表是一种首尾相接的单链表, 终端结点的指针域指向开始结点或头结点。 链表 终止条件是以指针等于头指针或尾指针。 采用单循环链表在实用中多采用尾指针表示单循环链表。 优点是查找头指针和尾指针的 时间都是 O(1),不用遍历整个链表。 双链表就是双向链表, 就是在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior ,形成两条不同方向的链。由头指针 head 惟一确定。 双链表也可以头尾相链接构成双 (向 ) 循环链表。 双链表上的插入和删除时间复杂度均为 O (1)。 顺序表和链表的比较: ·基于空间: ·顺序表的存储空间是静态分配,存储密度为 1; 适于线性表事先确定其大小时采用。 ·链表的存储空间是动态分配,存储密度 <> ·基于时间: ·顺序表是随机存储结构,当线性表的操作主要是查找时,宜采用。 ·以插入和删除操作为主的线性表宜采用链表做存储结构。 ·若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。 第三章 栈和队列 栈 (Stack)是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为 栈顶, 另一端称为栈底。 表中无元素时为空栈。 栈的修改是按后进先出的原则进行的, 我们 又称栈为 LIFO 表 (Last In First Out)。通常栈有顺序栈和链栈两种存储结构。 栈的基本运算有六种: ·构造空栈:InitStack(S) ·判栈空:StackEmpty(S) ·判栈满:StackFull(S) ·进栈:Push(S, x) ·退栈:Pop(S) ·取栈顶元素:StackTop(S) 在顺序栈中有“上溢”和“下溢”的现象。 ·“上溢”是栈顶指针指出栈的外面是出错状态。 ·“下溢”可以表示栈为空栈,因此用来作为控制转移的条件。 顺序栈中的基本操作有六种: ·构造空栈 ·判栈空 ·判栈满 ·进栈 ·退栈 ·取栈顶元素 链栈则没有上溢的限制, 因此进栈不要判栈满。 链栈不需要在头部附加头结点, 只要有 链表的头指针就可以了。 链栈中的基本操作有五种: ·构造空栈 ·判栈空 ·进栈 ·退栈 ·取栈顶元素 队列 (Queue)是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进 行,允许删除的一端称为队头 (front),允许插入的一端称为队尾 (rear) ,队列的操作原则是 先进先出的, 又称作 FIFO 表 (First In First Out) .队列也有顺序存储和链式存储两种存储结构。 队列的基本运算有六种: ·置空队:InitQueue(Q) ·判队空:QueueEmpty(Q) ·判队满:QueueFull(Q) ·入队:EnQueue(Q, x) ·出队:DeQueue(Q) ·取队头元素:QueueFront(Q) 顺序队列的“假上溢”现象:由于头尾指针不断前移,超出向量空间。这时整个向量空 间及队列是空的却产生了“上溢”现象。 为了克服 “假上溢” 现象引入循环向量的概念, 是把向量空间形成一个头尾相接的环形, 这时队列称循环队列。 判定循环队列是空还是满,方法有三种: ·一种是另设一个布尔变量来判断 ; ·第二种是少用一个元素空间,入队时先测试 ((rear+1)%m = front)? 满:空 ; ·第三种就是用一个计数器记录队列中的元素的总数。 队列的链式存储结构称为链队列, 一个链队列就是一个操作受限的单链表。 为了便于在 表尾进行插入 (入队 ) 的操作,在表尾增加一个尾指针,一个链队列就由一个头指针和一个尾 指针唯一地确定。 链队列不存在队满和上溢的问题。 在链队列的出队算法中, 要注意当原队 中只有一个结点时,出队后要同进修改头尾指针并使队列变空。 第四章 串 串是零个或多个字符组成的有限序列。 ·空串:是指长度为零的串,也就是串中不包含任何字符 (结点 ) 。 ·空白串:指串中包含一个或多个空格字符的串。 ·在一个串中任意个连续字符组成的子序列称为该串的子串, 包含子串的串就称为主串。 ·子串在主串中的序号就是指子串在主串中首次出现的位置。 ·空串是任意串的子串,任意串是自身的子串。 串分为两种: ·串常量在程序中只能引用不能改变 ; ·串变量的值可以改变。 串的基本运算有: ·求串长 strlen(char*s) ·串复制 strcpy(char*to, char*from) ·串联接 strcat(char*to, char*from) ·串比较 charcmp(char*s1, char*s2) ·字符定位 strchr(char*s, charc) 。串是特殊的线性表 (结点是字符 ) ,所以串的存储结构与线性表的存储结构类似。串的 顺序存储结构简称为顺序串。 顺序串又可按存储分配的不同分为: ·静态存储分配:直接用定长的字符数组来定义。 优点是涉及串长的操作速度快, 但不 适合插入、链接操作。 ·动态存储分配:是在定义串时不分配存储空间, 需要使用时按所需串的长度分配存储 单元。 串的链式存储就是用单链表的方式存储串值, 串的这种链式存储结构简称为链串。 链串 与单链表的差异只是它的结点数据域为单个字符。 为了解决“存储密度”低的状况,可以让一个结点存储多个字符,即结点的大小。 顺序串上子串定位的运算:又称串的“模式匹配”或“串匹配” ,是在主串中查找出子 串出现的位置。在串匹配中,将主串称为目标 (串 ) ,子串称为模式 (串 ) 。这是比较容易理解 的,串匹配问题就是找出给定模式串 P 在给定目标串 T 中首次出现的有效位移或者是全部 有效位移。最坏的情况下时间复杂度是 O((n-m+1)m),假如 m 与 n 同阶的话则它是 O(n^2)。 链串上的子串定位运算位移是结点地址而不是整数。 第五章 多维数组和广义表 数组一般用顺序存储的方式表示。存储的方式有: ·行优先顺序,也就是把数组逐行依次排列。 PASCAL 、 C ·列优先顺序,就是把数组逐列依次排列。 FORTRAN 地址的计算方法: ·按行优先顺序排列的数组:LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d. ·按列优先顺序排列的数组:LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d. 矩阵的压缩存储: 为多个相同的非零元素分配一个存储空间 ; 对零元素不分配空间。 特殊矩阵的概念:所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 稀疏矩阵的概念:一个矩阵中若其非零元素的个数远远小于零元素的个数, 则该矩阵称 为稀疏矩阵。 特殊矩阵的类型: ·对称矩阵:满足 a(ij)=a(ji)。元素总数 n(n+1)/2.I=max(i, j) , J=min(i, j) , LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d. ·三角矩阵: ·上三角阵:k=i*(2n-i+1)/2+j-i, LOCa(ij)=LOC(sa[0])+k*d. ·下三角阵:k=i*(i+1)/2+j, LOCa(ij)=LOC(sa[0])+k*d. ·对角矩阵:k=2i+j, LOCa(ij)=LOC(sa[0])+k*d. 稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结 点存放在一起, 用这些结点组成的一个线性表来表示。 但这种压缩存储方式将失去随机存储 功能。加入行表记录每行的非零元素在三元组表中的起始位置,即带行表的三元组表。 广义表是 n(n≥ 0) 个元素的有限序列,其中的元素是原子或者是一个广义表。 广义表表头和表尾的概念: ·若广义表 LS 非空 (n≥ 1) ,则这个广义表的第一个元素就是表头。 ·其余的元素组成的表称为 LS 的表尾,所以表尾必是一个子表。 广义表有两种表示法,一种是括号表示法,一种是图形表示法。 广义表与树 (形结构 ) 相对应,这个广义表就是纯表。 如果一个广义表的结点又可以被其他结点所共享,则这个表称为再入表。 允许递归的表称为递归表。 线性表∈纯表 (树 ) ∈再入表∈递归表。可见,广义表是对线性表和树的推广。 广义表有两个特殊的基本运算: ·取表头 head(LS):取表中的第一个数据元素,不能对空表操作。 ·取表尾 tail(LS);取除表头外,其余数据元素构成的子表,不能对空表操作。 转载请注明出处范文大全网 » 数据结构自学考试大纲2014年4月自学考试试卷数据结构
数据结构导论_自学考试_概念整理1
2009年自学考试《数据结构》各章要点
