选择性必修一 第二章 数据的存储方式-普通高中春招考试备考教材 信息技术（第六版）

选择性必修一　数据与数据结构　 同，数据处理的效率也不同。 （　　） 17. 数据的逻辑结构和数据的存储结构是相同的。 （　　） 18. 数据的物理结构是指数据及其关系在计算机中的存储形式。 （　　） 19. 数据结构的选择，对程序开发速度和程序运行的效率没有太大的影响。 （　　） 20. 在线性关系中，仅有一个前驱的一定是最后一个元素。 （　　） 三、填空题 21. 无法用常规软件工具进行高效捕捉、管理和处理的数据集合，被称为　　　　。 22. 数据的基本单位是　　　　，在计算机程序中通常作为一个整体进行考虑和处理。 23. 在计算机世界中，把数据元素及数据元素之间的关系构成的集合称为　　　　。 24.　　　　是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体 描述。 25. 按数据类型“值”的不同特性，高级程序设计语言中的数据类型可分为简单类型和 　　　　两种。 四、应用题 26. 简述数据的抽象过程。 27. 简要绘制数据结构的思维导图。 第二章　数据的存储方式 一、数据存储的顺序结构与链式结构 1.数据存储的顺序结构 线性结构：K＝｛a_1， a_2，…，a_（i-1），a_i，…a_（n-1），a_n｝ 在以上数据结构中，第一个元素仅有一个后继元素，最后一个元素仅有一个前驱元素， 其他元素仅有一个前驱和一个后继元素。a_（i-1）是 a_i 的前驱，a_i 是 a_（i-1）的后继。存储 69 空间为 sizeof（a_1）*d 字节。 2.数据存储的链式结构 一个数据元素有两个域：数据域和指针域。数据域存储数据，指针域存放后继元素的存 储位置，最后一个数据元素的指针域为空。由于每个数据元素的存储位置是保存在它的前 驱元素的指针域中，只有当访问到其前驱元素后才能沿着前驱元素的指针域访问到该数据 元素。 二、数据的顺序存储与组织 1.数组 由具有相同名称、相同类数据类型、所占空间连续的数据元素构成的序列，称为数组。 定义数组的基本格式：类型说明符 数组名［数组长度］； 类型说明符可以是任意合法的数据类型；数组名是由字母、数字和下画线组成，开头只 能是字母或下画线；数组长度必须是常量或常数。 数组元素的引用是通过下标来确定的，下标是从 0 到数组长度-1。数组名是一个特别 的量，它的值是数组的第一个元素的地址，即指向第一个元素。例如，下面是一个长度为 4 的一维数组： int a［4］。 由此可以看出，a 指向第一个元素，a+1 指向第二个元素，a+2 指向第三个元素，a+3 指向 第四个元素，a+4 指向一个不确定的元素的地址（发生溢出）。a［0］至 a［3］分别是对应内存的 名称，它相应于一个单变量，代表对应内存空间存储的值。 在 Python 的基本数据类型中，没有哪一种类型与这种标准数组对应，这是因为 Python 是 一种动态语言，不需要事先声明一个量就可以直接使用这个量，而且在 Python 的基本数据类 型中，列表、元组、集合、字典等中每一个元素的类型都不相同。数组有点像一个特殊的列 表，因此，在 Python 中，常用列表来替代数组，只是在使用时要注意遵循数组运算规则即可。 多维数组：可以把每一行看作一组数组来处理的数组。下面以二维数组为例。 基本格式：类型说明符 数组名［常量表达式 1］［常量表达式 2］； 例如，int a［3］［4］； 其实质： a→a［0］ →a［0］［0］ a［0］［1］ a［0］［2］ a［0］［3］ a［1］ →a［1］［0］ a［1］［1］ a［1］［2］ a［1］［3］ a［2］ →a［2］［0］ a［2］［1］ a［2］［2］ a［0］［3］ 由上可以看出，数组名 a 是整个数组的起始地址，指向第一行元素地址，即量 a 与 a［0］是 70 选择性必修一　数据与数据结构　 指向整个数组的第一个元素 a［0］［0］的地址，a+1 与 a［1］是指向第二行元素的第一个元素 a［1］［0］的地址，a+2 与 a［2］是指向第三行的第一个元素 a［2］［0］的地址。在 Python 中，可以 用列表来临时表示二维数组，如要表示一个 3 行 4 列的数组，用列表可表示为：L＝［［，，，］， ［，，，］，［，，，］］（在给列表 L 的元素赋值时一定遵循数组的规则）。 2.数组基本操作（以Python为例） 遍历：将列表 L 中的所有元素输出。 for i in L： 　print（i） 查找：在列表 L 中查找 x，若有输出 True，否则输出 False。 　if x in L： 　　print（“True”） 　else： 　　print（“False”） 插入：将 x 插入到列表 L 的第 i 个位置。 　L.insert（i，x） 删除：删除位置 i 上的元素。 　del L［i］ 提示：在其他语言中，对数组的遍历、查找、插入、删除等操作要使用循环结构。 三、数据的链式存储与组织（以Python语言为例） 1.指针 指针就是某个内存单元的地址。 2.链表 简单链表的节点有两个域，一个是指针域，用于保存下一个节点的地址，另一个是数据 域，用于保存需要存储的数据，由此构成一个数据序列。 由于在 Python 语言中没有指针类型，且变量的类型由其值来决定，因此，在 Python 中使 用类来替代其他语言中的结构体。下面是用 Python 语言定义的节点。 class Node（object）： 　　def __init__ （self，data，next = None）： 　　　　self.data = data 　　　　self.next = next 在上面节点中，data 是保存当前节点数据的量，next 是指向下一个节点的地址，如果没有 71 下一个节点，则其值为 None。 3.链表操作 （1）链表的初始化 def Create_List（lt）：　#lt 为要建立的链表的各节点的数据 　 head = Node（lt［0］） 　 p = head 　 for i in lt［1：］： 　　　new_node = Node（i） 　　　p.next = new_node 　　　p=new_node 　 return head （2）链表元素的遍历 def print_List（link）： #link 为指向链表的头节点的指针 　　while link： 　　　 print（link.data，end= ） 　　　 link = link.next （3）链表节点元素的插入 下面是链表插入操作的示意图和 Python 语言程序。 def Insert_Link（head，index，item）： 　　p=head 　　if index==None：#如果要把节点插入在第一个位置 　　　　q=Node（item） 　　　　q.next=self.head 　　　　self.head=q 　　else： 　　　　post=head 　　　　j=0 　　　　while p.next！= None and j < index： #查找插入的位置 72 选择性必修一　数据与数据结构　 　　　　　　post=p 　　　　　　p=p.next 　　　　　　j=j+1 　　　　if index==j： 　　　　　　q=Node（item，p） 　　　　　　post.next=q 　　　　　　q.next=p （4）链表的节点删除操作 下面是链表删除操作的示意图和 Python 语言程序。 def Delete_Link（head，index）： 　　p=head 　　if index == None： 　　　　q=head 　　　　head=q.next 　　　　p=head 　　else： 　　　　post=head 　　　　j=0 　　　　while p.next！= None and j < index： 　　　　　　post=p 　　　　　　p=p.next 　　　　　　j=j+1 　　　　if index==j： 　　　　　　post.next = p.next （5）获取链表的节点数 def get_length（head）： 　　p=head 　　length = 0 73 　　while p！= None： 　　　　length=length + 1 　　　　p=p.next 　　return length （6）获取链表中子节点的值 def GetElement（head，i）： 　　L=get_length（head） 　　if i>=L： 　　　　print（"元素位置范围为：0-%d"%（L-1）） 　　　　return 　　p=head 　　n=0 　　while True： 　　　　if i==n： 　　　　　　return p.data 　　　　p=p.next 　　　　n=n+1 　　return 四、数组与链表及其应用 在逻辑上都是属于线性关系，区别是数组是连续的存储，而链表并非连续存储，数组的 长度是固定的，链表是动态申请内存。 对于确定长度的、需要连续使用内存单元，并且不需要频繁进行增加、删除操作的就用 数组，反之使用链表。 随堂练习 一、单项选择题 1. 线性结构的数据在存储时，数据元素之间的位置是（　　）。 A. 随机的 B. 相邻的 C. 不确定的 D. 以上都可能 2. 链式存储结构所占存储空间（　　）。 A. 分两部分：一部分存放节点的值，另一个部分存放表示节点间关系的指针 B. 只有一部分，存放节点的值 C. 只有一部分，存储表示节点间关系的指针 D. 分两部分：一部分存放节点的值，另一部分存放节点所占单个元素 3. 当以链式结构存储数据时，数据元素至少包含（　　）部分信息。 74 选择性必修一　数据与数据结构　 A.1 B.2 C.3 D.4 4. 在 Python 语言中，定义一个链表的节点使用的关键字是（　　）。 A.def B.import C.class D.from 5. 在数据的链式存储结构中，数据元素 αi的存储位置保存在（　　）。 A.αi的指针域中 B.αi+1的指针域中 C.αi-1的指针域中 D. 无法确定 6. 指针即内存单元地址，在 C++语言中指针也是一种数据类型，但其没有专门的关键字 来定义，而是在其数据类型符后用（　　）来表示后面的变量是一个指针。 A.//　　 B.& C.# D.* 7. 要在单向链表中将数据 e 放入到链 L 的 i-1 处与 i 处之间，首先应该（　　） A. 将 i-１处的指针指向数据 e　 B. 将数据 e 放入 i 处的节点的值域中 C. 将 i-1 和 i 处的指针同时指向数据 e　 D. 生成新节点，并把数据 e 放入到其值域中 8. 执行 int a=3；int *pi；pi=&a；*pi+=1；后，a 的值为（　　）。 A.2 B.3 C.4 D.5 9. 有一组数：1，1，2，3，5，8，…，55，保存在数组 a 中。这组数有这样一个特点：a［i+2］= a［i+1］+a［i］，则 a［7］等于（　　）。 A.11 B.13 C.21 D.33 10. 在长度为 n 的数组中插入数据，最多和最少移动数据的次数分别是（　　）。 A.n 和 0 B.n 和 1 C.n-1 和 0 D.n-1 和 1 11. 在数组的第 i 个位置（0<i<n-1，数组最大长度 n）插入一个元素 e，首先要（　　）。 A. 将位置为 i 的元素向后移一个位置 B. 将位置为 n 的元素向后移一个位置 C. 将位置为 n-1 的元素向后移一个位置 D. 将新数据 e 保存到数组的第 i 个位置 12. 结构体是一种复合型的数据类型，即由多个简单数据类型的量通过特定结构组合成 一个复合体，这个复合体可作为简单类型的方式来使用，如果要引用其成员变量则结构体与 成员之间通常用（　　）符号来连接。 A.. B.， C.； D.！ 13. 设指针变量 P 指向单链表中节点 A，若删除单链表中节点 A，则需要修改指针的操作 序列为（　　）。 q=p->next； p->data=q->data； p->next=q->next； delete q； A. q=p->next； q->data=p->data； p->next=q->next； delete q； B. 75 q=p->next； p->next=q->next； delete q； C. q=p->next； p->data=q->data； delete q； D. 14. 以下的程序片段是实现从具有 n 个元素的数组 a 中删除第 t 个元素的功能，横线处缺 少的代码应该是（　　）。 for （i=t； i<n； i++） ｛ 　　　　　　　　　　 ｝ A.a［t］=a［i］； B.a［i］=a［i+1］； C.a［i］=a［i-1］； D.a［i-1］=a［i］； 15. 下列关于数组的说法，不正确的是（　　）。 A. 所有元素的数据类型都相同 B. 占用连续的内存空间 C. 可以根据下标确定数组中的元素，下标从 1 开始 D. 元素的类型可以是简单数据类型，也可以是结构类型 16. 单向链表与数组都属于线性表，它们都是用于存储具有相同属性的数据，下列说法 不正确的是（　　）。 A. 数组适合用于最大元素个数容易确定的情况 B. 存储相同的元素，单向链表比数组占用的存储空间要多 C. 查找特定元素，使用单向链表比使用数组方便 D. 对于需要频繁添加、删除元素的情况，使用单向链表比使用数组合适 二、判断题 17. 顺序结构存储方式的优点是查找方便，插入、删除效率高。 （　　） 18. 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （　　） 19. 链表的每个节点都包含一个指针域。 （　　） 20. 数组会造成存储空间的浪费，而链表不会，所以链表的空间利用率比数组高。（　　） 21. 需要频繁插入、删除数据时，应选择顺序存储结构。 （　　） 22. 定义一个二维数组 float a［3］［4］；表示这是一个 3 行 4 列的矩阵，共有 12 个元素，其 中最后一个元素为 a［3］［4］。 （　　） 23. 链表、队列、字符串的数据模型都是线性表。 （　　） 24. 链表中各元素之间只能有一个“链”相连。 （　　） 76 选择性必修一　数据与数据结构　 三、填空题 25.定义一个数组 int a［n］；要访问该数组中第 i个元素（0≤i≤n-1），则查找下标为　　　　 的元素。 26. 定义一个二维数组，int a=［［1，2，3］，［4，5，6］，［7，8，9］，［10，11，12］］；那么 a［2］［2］ 的值是　　　　。 27.　　　　是用来实现链式结构的数据存储与组织，它是由节点组成的。 28. 为了链表操作的方便，一般会在链表的第一个节点前面增加一个节点，这个节点的 data 域不保存数据，将这个特殊的节点称为　　　　。 29. 在链表中，节点之间是通过节点中的　　　　联系到一起的，将多块不连续的内存 空间连接，在逻辑上形成一片连续的数据存储空间。 四、应用题 30. 下图是使用单链表来存储数据元素 a1、a2、a3、a4、a5，其中 next 指向下一节点的地址。 请根据要求回答问题。 （1）在该链表中，L 指向的下一个节点称为　　　　　　。 （2）在最后一个节点中的指针域，符号“∧”表示指针域为　　　　　　。 （3）在单链表中查询数据 a3，要在数据元素　　　　的指针域中查找其存储地址。 （4）若要在该单链表中数据元素 a2、a3 之间插入一个新的数据元素 x，相关步骤如下： ①使用关键词　　　　　　创建一个新的节点 p，用来存放数据 x。 ②将数据 x 存入节点 p 的数据域。 ③将节点 p 的指针域指向数据元素　　　　所在的节点。 ④将 a2 节点的 next 指向节点 p。 第三章　线性数据的组织和存储 一、线性表 1.线性表的结构特点 线性表的结构特点：均匀性和有序性。 2.线性表常见的基本运算 线性表常见的基本运算包括置空（setnull（L））、求长度（length（L））、取值（get（L，i））、取 前驱（prior（L，ai））、取后继（next（L，ai））、查找（Locate（L，x））、插入（insert（L，x，i））、删除 77 第二章 数据的存储方式 五、随堂练习 （一）选择题 1-5BABCC 6-10DDCCA 11-16CACDCC （二）判断题 17-24✖✔✔✔✖✖✔✖ （三）填空题 25.i-1 26.9 27.链表 28.头结点 29.指针 （四）应用题 30. （1）头结点 （2）空 （3）a2 （4）new a3 学科网（北京）股份有限公司 $$