普通高中教科书·信息技术选择性必修1 数据与数据结构.pdf

普 通 高 中 教 科 书选择性必修信息技术普通高中教科书信息技术1数据与数据结构Shuju yu Shuju Jiegou选择性必修 1数据与数据结构广东教育出版社广东教育出版社定价：10.59元批准文号：粤发改价格2017434号 举报电话:12358ook2020信息技术选择性必修1-6封面.indd 12020/5/28 下午2:31信息技术广东教育出版社普 通 高 中 教 科 书徐福荫 主编广州数据与数据结构Shuju yu Shuju Jiegou1选择性必修 ook2020信息技术-8扉页.indd 32020/5/28 下午2:522 2 图书在版编目(CIP)数据信息技术选择性必修1：数据与数据结构/徐福荫主编广州：广东教育出版社，2019.12（2021.1重印）普通高中教科书ISBN 978-7-5548-3027-7.信.徐.计算机课高中教材.G634.671中国版本图书馆CIP数据核字（2019）第208284号 编写单位 广东教育出版社 主 编 徐福荫 副 主 编 朱光明 黄国洪 本册主编 刘毅婉 严开明 核心编写人员（以姓氏笔画为序）丘韶科 李苑文 周玳珈 黄淑燕 责任编辑 姜树彪 严洪超 责任技编 杨启承 陈 瑾 装帧设计 何 维信息技术 必修1 数据与数据结构XINXI JISHU BIXIU 1 SHUJU YU SHUJU JIEGOU广 东 教 育 出 版 社 出 版（广州市环市东路472号12-15楼）邮政编码：510075网址：http:/广东新华发行集团股份有限公司发行广东新华印刷有限公司南海分公司印刷（佛山市南海区盐步河东中心路）890毫米1240毫米16开本9印张180 000字2019年12月第1版2021年1月第3次印刷ISBN 978-7-5548-3027-7定价：10.59元批准文号：粤发改价格2017434 号 举报电话：12315著作权所有请勿擅用本书制作各类出版物违者必究如有印装质量或内容质量问题，请与我社联系。质量监督电话：020-87613102 邮箱：gjs-购书咨询电话：020-8777243822X2204.indd 22020/12/3 17:15:1511前 言信息技术作为当今先进生产力的代表，已经成为我国经济发展的重要支柱和网络强国的战略支撑。信息技术涵盖了获取、表示、传输、存储和加工信息在内的各种技术。自电子计算机问世以来，信息技术沿着以计算机为核心、到以互联网为核心、再到以数据为核心的发展脉络，深刻影响着社会的经济结构和生产方式，加快了全球范围内的知识更新和技术创新，推动了社会信息化、智能化的建设与发展，催生出现实空间与虚拟空间并存的信息社会，并逐步构建出智慧社会。在数字化时代，数据对科学发现、技术进步、经济发展以及人们的日常生活有着越来越深刻的影响。理解数据的作用及价值，对同学们适应信息社会、学会数字化生存有着重要意义。数据结构是信息技术学科的核心内容之一，对培养同学们的信息意识与计算思维、深入理解及掌握信息技术学科知识与实践方法、形成学科核心素养，具有非常重要的作用。本教科书是针对数据、数据结构及其应用而设置的选择性必修模块。通过本教科书的学习，同学们可以进一步了解数据的作用，在掌握常用数据结构的概念、特点、操作、编程实现方法等内容的基础上，能对简单的数据问题进行分析，选择恰当的数据结构，用一种程序设计语言编程实现，在问题解决过程中对数据抽象、数据结构的思想与方法有初步的认识。本教科书按“数据与数据结构”“数据的组织和存储”“数据结构应用”三部分内容展开，围绕信息技术学科核心素养，设计了“超市数据与社会关系的调查”“超市商品的信息化管理程序设计”“超市服务自动化的模拟实验”“俄罗斯方块游戏的抽象数据类型案例分析”“超市促销商品的选择与查询程序设计”项目范例。教师围绕“情境主题规划探究实施成果评价”的项目范例主线开展教学活动，帮助同学们掌握本教科书的基础知识、方法与技能，增强信息意识，发展计算思维，提高数字化学习与创新能力，树立正确的信息社会价值观和责任感，从而促进同学们的信息素养提升。本教科书要求同学们对现实世界中的真实性问题进行自主、协作、探21X2204.indd 12019/9/26 13:52:512 2 究学习。同学们围绕“项目选题项目规划方案交流探究活动项目实施成果交流活动评价”的项目学习主线开展学习活动，体验“做中学、学中创、创中乐”的项目学习理念和“从实践入手、先学后教、先练后讲”的项目学习策略，将知识建构、技能培养与思维发展融入运用数字化工具解决问题和完成任务的过程中，从而促进信息意识、计算思维、数字化学习与创新、信息社会责任的信息技术学科核心素养达成。本教科书设置了“项目范例”“项目选题”“项目规划”“方案交流”“探究活动”“项目实施”“成果交流”“活动评价”等学习栏目，指导同学们开展项目学习活动。其中，“项目范例”是教师通过“情境”“主题”“规划”“探究”“实施”“成果”“评价”等活动，引导同学们了解开展项目学习活动的全过程；“项目选题”是同学们从真实世界选择自己感兴趣的项目主题；“项目规划”是同学们根据项目选题，制订自己的项目方案；“方案交流”是同学们展示、交流自己设计的项目方案，师生共同探究、完善其方案；“探究活动”是同学们通过“问题”“观察”“分析”“阅读”“思考”“交流”“实践”“实验”“体验”“调查”“讨论”“拓展”等活动，获取知识和技能的过程；“项目实施”是同学们运用在项目学习过程中所获得的知识和技能来完成项目方案；“成果交流”是教师组织同学们展示交流项目成果，共享创造、分享快乐；“活动评价”是教师组织同学们开展项目评价活动。本教科书各章首页的导言，叙述了本章的学习目的与方式、学习目标与内容，让同学们对整章有个总体认识。每章设置了“本章扼要回顾”，通过知识结构图把每章的主要内容及它们之间的关系描述出来，这有助于同学们建立自己的知识结构体系。每章结尾的“本章学业评价”设计了基于学业质量水平的测试题，并通过本章的项目活动评价，让同学们综合评价自己在信息技术知识与技能、解决实际问题的过程与方法，以及相关情感态度与价值观的形成等方面，是否达到了本章的学习目标。此外，本教科书中为同学们提供了配套学习资源包，里面含有超市数据与社会关系的分析调查报告、超市商品的信息化管理程序、超市服务自动化的模拟程序及超市促销商品的选择与查询程序等，还提供了同学们开展学习探究的程序设计示例。当然，同学们还可以自己收集素材，让自己的项目学习作品更有特色。前言21X2204.indd 22019/9/26 13:52:5111目 录目 录CONTENTS 第一章 认识数据和数据结构1项目范例 超市数据与社会关系的调查21.1 数据及其价值4111数字、数值与数据 5112数据与社会的关系 7113数据的价值和意义 91.2对实际问题的数据抽象 11121抽象问题中的数据 11122分析数据之间的关系13123建立数据模型 151.3认识数据结构 17131数据结构 17132数据类型 21133数据结构的重要作用2221X2204.indd 12019/9/26 13:52:512 2 2 目录 第二章 数据的存储方式27项目范例 超市商品的信息化管理程序设计 282.1数据存储的顺序结构与链式结构 30211数据存储的顺序结构 30212数据存储的链式结构322.2数据的顺序存储与组织34221数组 34222数组的基本操作 402.3数据的链式存储与组织43231指针与指针变量 44232链表 46233链表的基本操作 472.4数组与链表及其应用 51241数组与链表 51242数组与链表的应用52 第三章 线性数据的组织和存储58项目范例 超市服务自动化的模拟实验593.1线性表 62311线性表及其运算 62312线性表的应用 633.2用字符串存储数据 64321字符串及其存储 64322字符串的基本操作6821X2204.indd 22019/9/26 13:52:51333.3用队列组织先进先出数据69331队列 69332队列的基本操作 73333队列的实现 743.4用栈组织后进先出数据 79341栈79342栈的基本操作 82343顺序栈的实现 82 第四章 抽象数据类型88项目范例 俄罗斯方块游戏的抽象数据类型案例分析894.1认识抽象数据类型91411抽象数据类型 91412抽象数据类型的应用93413抽象数据类型的实现944.2用抽象数据类型表示队列和栈 96421用抽象数据类型表示队列 96422用抽象数据类型表示栈 974.3用抽象数据类型表示二叉树98431树98432二叉树 100433二叉树的抽象数据类型 101434二叉树的基本操作方法 102目录21X2204.indd 32019/9/26 13:52:514 4 目录 第五章 数据结构的应用107项目范例 超市促销商品的选择与查询程序设计1085.1迭代与递归 111511迭代111512递归 1135.2查找 115521顺序查找 115522二分查找 1165.3排序 120531认识排序 120532冒泡排序 122533快速排序 1245.4算法与数据结构的联系与区别 128541算法与数据结构的联系 128542算法与数据结构的区别 130附录1 部分术语、缩略语中英文对照表134附录2 项目活动评价表13521X2204.indd 42019/9/26 13:52:511 第一章 数据与信息1在数字化时代，数据与大数据对科学发现、技术进步、经济发展以及人们的日常生活有着越来越深刻的影响。人们产生数据、分析数据、使用数据，使数据成为新的原材料、生产资料和基础设施。把握数据的内涵与外延，才能把握时代的脉搏。本章将通过“数据与社会关系的调查”项目，进行自主、协作、探究学习，让同学们理解数字、数值和数据的基本含义，懂得对生活中的实际问题进行数据抽象，认识数据结构在解决问题过程中的重要作用，从而将知识建构、技能培养与思维发展融入运用数字化工具解决问题和完成任务的过程中，促进信息技术学科核心素养达成，完成项目学习目标。数据及其价值 对实际问题的数据抽象 认识数据结构第一章认识数据和数据结构第一章 数据与信息21X2204.indd 12019/9/26 13:52:512 2第一章 认识数据和数据结构超市数据与社会关系的调查项目范例情 境现代超市涉及大量的数据处理，对管理和技术提出了很高的要求。超市商品、客户群、资金流的管理都是数据处理的问题。如超市设置的收银机（如图1-1所示），收银的过程就包含了大量的数据处理工作；对超市客户数据的高效管理也能使经营更有针对性。超市借助计算机管理系统减少人工操作所带来的低效率、易出错等问题，精确适时地反映和处理超市各项经营活动。主 题超市数据与社会关系的调查规 划根据项目范例的主题，在小组中组织讨论，利用思维导图工具，制订项目学习规划，如图1-2所示。图1-2“超市数据与社会关系的调查”项目学习规划图1-1超市收银台21X2204.indd 22019/9/26 13:52:533 第一章 数据与信息3探 究根据项目学习规划的安排，通过调查、案例分析、文献阅读和网上资料搜索，开展“超市数据与社会关系的调查”项目学习探究活动，如表1-1所示。表1-1“超市数据与社会关系的调查”项目学习探究活动探究活动学习内容知识技能超市收银机数据应用调查列举数据应用实例。调查收银机的功能。分析数据与社会各领域的关系。理解数字、数值和数据的基本含义。认识数据在社会应用中的价值和意义。抽取事物中的数据。调查收银机收集的数据。分析数据关系。分析收银机使用的数据之间的关系。超市客户群市场调查列举数据应用实例。调查超市客户群体。理解数据结构的概念。认识数据结构在解决问题过程中的重要作用。抽取事物中的数据。分析客户的属性。确定数据关系。分析客户数据关系。建立数据模型。确定客户数据模型。实 施实施项目学习各项探究活动，进一