第二章 数组与链表（复习课件）信息技术浙教版2019选择性必修1

复习课件 第二章 数组与链表 浙教版（2019） 选修一 数组 01 链表 02 复习内容总览 数组 PART 01 第1节 数组 知识结构 第1节 数组 知识点一 数组 的概念 数组是一组具有相同数据类型的变量集合，用一个数组名和下标来唯一确定数组元素。 数组在内存中存储的结构简单，创建数组时系统会分配一块连续的存储空间，每个数组元素按照下标顺序依次存储。 数组的存储结构 数组 的特性 ①数组元素(下标变量)的数据类型相同 ②通过下标变量对数组元素的值进行访问 ③存储空间固定不变 第1节 数组 知识点一 数组 列表 区别 数组 列表 元素类型 一致 可以不一致 存储结构 顺序（连续）存储 链式（不连续）存储 … … … 当列表中每个数据元素所含数据项的数量和数据类型均相同时，可以将该列表视为数组，列表索引可视为数组的下标。 ≠ 第1节 数组 知识点二 数组的基本操作 1.数组的创建 数组的创建实质是在系统内存中划分一块连续区域，用来保存数组所含的所有数据元素。 2. 数组元素的访问 数组元素的访问指的是寻址到特定的数据元素，并根据存储地址对该数据元素进行读取、修改等操作。 数组元素可通过数组名和下标快速定位其内存地址，因此可通过数组名和下标直接进行访问 3. 数组元素的插入与删除 要删除数组中的某个元素，只需将其后的所有元素依次前移一位，并将数组长度减一即可。 第1节 数组 提升练习 1.阿福将我国部分省份及其省会城市存储到二维数组中，并依次输出各省及其省会名称，例如“湖南省的省会是长沙市”。相关代码如下: a=[["浙江省","杭州市"]，["吉林省","长春市"],["湖南省","长沙市"],["湖北省","武汉市"],["江苏省","南京市"],["广东省","广州市"]] for p in a: print(f"{ }的省会是{ }") 则划线①和②处分别应填写的代码为( ) A.①p[1];②p[0] B.①p[0];②p[1] C.①a[p][0];②a[p][1] D.①p[1];②p[2] B 解析 考查数组的基本知识。遍历a数组的元素，p[0]获取省份,p[1]获取城市,因此①、②处分别应填写的代码为p[0],p[1]。故选:B。 第1节 数组 提升练习 2.下列有关数据的描述正确的是（ ） A.数组是由多种不同类型的变量构成的一个序列 B.数组是由相同类型的变量构成的一个序列 C.一个数组在内存中的存储空间不一定是连续的 D.一个数组在内存中的存储方式为非顺序结构 B 解析 本题考查数组的定义。数组是由相同类型的变量构成的一个序列;一个数组在内存中的存储空间是连续的,存储方式为顺序结构。故选B。 第1节 数组 提升练习 3.数组a的数据存放情况如下表，则当i=2时，a[6/i-1]的值是 。 52 解析 当i=2时，a[6/i-1]=a[6/2-1]=a[3-1]=a[2]=52。 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 48 52 98 26 47 22 82 33 链表 PART 02 第2节 链表 知识结构 第2节 链表 知识点一 概念 特性 链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表中的每个节点一般由“数据区域”和“指针区域”两部分构成。 链表的概念与特性 （1）同一链表中每个节点的结构均相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 （3）链表占用的空间不固定 第2节 链表 知识点二 节点访问 插入与删除 访问与遍历 基本操作 空链表的创建 链表的基本操作 第2节 链表 知识点二 链表的创建 创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。 链表节点的访问 链表只能通过头指针(head)进行访问，其他节点通过节点间的指针依次访问。 链表节点的插入与删除 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的指针，将新节点插入到链表的正确位置。链表节点的删除，则通过将需要删除的节点的前驱节点和其后继节点直接相连的方式实现。 链表节点的访问与遍历 链表中的节点通过指针相互链接，当需要访问某个位置的节点元素时，只能通过头指针进入链表并通过节点间的链接关系一个一个往下访问，直到找到指定位置的节点。 解题技巧 1.采用列表模拟单向链表，data[p][0]为数据区域，data[p][1]为指针区域。在单向链表指针为 p的节点之后插入指针为 s 的节点，正确的操作是( ) A.data[s][1]=p data[p][1]=data[s][1] B.data[p][1]=s data[s][1]=data[p][1] C.data[s][1]=data[p][1] data[p][1]=s D.data[p][1]=data[s][1] data[s][1]=p 解析 [解析]在单向链表指针为p的节点之后插入指针为s的节点，则s的指针域指向p的下一个节点，即data [s] [1] = data [p] [1]，其次将p和s连接起来即p的指针域指向s，所以选项C符合题意。 C 解题技巧 2.有如下 Python 程序段: a =[[7,1],[8,2],[9,-1]] head =0 p=1 a. append([6,a[p][1]]) a[p][1] =len(a) -1 则程序执行后,下列说法正确的是( ) 解析 考查链表。程序创建了一个链表a,其节点数据值依次为7→8→9;然后在节点p之后插入一个新节点,使得链表各节点数据值依次为7→8→6→9,对应列表a的值为[[7,1]，[8,3],[9,-1],[6,2]],故答案为C。 C A.a[2][0]的值为6,链表a的尾结点数据值为6 B.a[2][0]的值为9,链表a的尾结点数据值为6 C.a[3][1]的值为2,链表a的尾结点数据值为9 D.a[3][1]的值为-1,链表a的尾结点数据值为9 解题技巧 3.有如下python程序段: a=[[7,1],[8,2],[9,-1],[6,0]] head=3 head=a[head][1] 则程序执行后，链表a有 个节点。 解析 程序创建了一个拥有4个节点的链表a，刚开始其头指针head 值为3，则头节点为a[3]。语句head=a[head][1]的作用是删除头节点，并让头指针指向新的头节点a[0]。故程序执行后，链表a的节点数量为3。 3 第2章 数组与链表 浙教版（2019） 选修一 谢谢观看 $$