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

选择性必修一　数据与数据结构　 三、填空题 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 （delete（L，i））。 3.线性表的应用 存储不确定个数的数据项就用线性表。 二、字符串及其存储 1.字符串 字符串的数据元素的类型限定为字符型。字符串既可以整体操作也可按单个元素 操作。 2.字符串的存储结构 字符串的存储可使用顺序存储和链式存储。顺序存储通常使用字符数组来存储，链式 存储就是使用一个带字符类型的数据域和一个指针域的链表来存储。 3.Python中字符串的基本操作 Python 中字符串的基本操作如下： 　 ● 字符串赋值：s1=" 20230305" ，s2=" 分类考试" 　 ● 字符串连接：s1+s2 　 ● 求长度：leng（s1） 　 ● 求子串：s1［0：4］#取字符串 s1 的前四个字符 在 Python 中，字符串的插入、删除、更改等操作都不可直接在源串上进行，只能通过方法 生成新串。 三、用队列组织先进先出数据 1.队列的定义 队列是一种特殊的线性表，它只允许在表的一端进行插入，在表的另一端进行删除。队 列符合先进先出规律（FIFO）。 2.队列的基本操作 ①初始化：rear=front=0 ②元素入队：rear=rear+1 ③元素出队：front=front+1 ④求队列长度：rear-front 78 选择性必修一　数据与数据结构　 ⑤判断队列：空，front=rear；满，rear=M 3.循环队列 　 ● 初始队列：条件 front=rear=0 　 ● 入队：条件 rear=（rear+1）%maxsize 　 ● 出队：条件 front=（front+1）%maxsize 　 ● 空：条件 front==rear 　 ● 满：（rear+1）%maxsize==front 四、用栈组织后进先出数据 1.栈 栈是只能在一端进行插入和删除的特殊线性表。栈中能进行插入、删除的一端称为栈 顶，而另一固定端称为栈底。把一个数据放入栈中的操作称为入栈，从栈中取出一个数据称 为出栈。 2.栈的基本操作 初始化、入栈、出栈、判断是否为空、判断是否满、求长度。 随堂练习 一、单项选择题 1. 线性表是（　　）。 A. 一个有限序列，可以为空 B. 一个有限序列，不可以为空 C. 一个无限序列，可以为空 D. 一个无限序列，不可以为空 2. 顺序表中第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是 （　　）。 A.110 B.108 C.100 D.120 3. 两个字符串相等的条件是（　　）。 A. 串的长度相等 B. 含有相同的字符集 C. 都是非空串 D. 两个串的长度相等且对应位置的字符相同 4. 定义了一个字符串 s="hello world！"，执行 print（s［2：-2］）命令后，结果是（　　）。 A.ello worl B.llo worl C.llo world D.ello world 5. 下列描述不准确的是（　　）。 A. 队列中没有元素时，称为零队列 79 B. 队列只允许在表的一端进行插入，在表的另一端进行删除 C. 在队列中，可以插入的一端称为队尾，可以删除的一端称为队头 D. 把一个数据元素插入队列中的操作叫作进队，从队列中删除一个数据元素的操作 叫作出队 6. 已知队列（6，5，4，1，2，3），第一个进入队列的元素是 6，请问第 3 个出队列的元素是 （　　）。 A.2 B.3 C.4 D.5 7. 已知循环队列的存储空间为数组 A［11］，且头指针和尾指针分别为 8 和 3，则该队列的 当前长度为（　　）。 A.8 B.6 C.7 D.5 8. 在一个长度为 n 的线性表中，在第 i 个元素（1≤i≤n+1）之前插入一个新的数据元素，需 要向后移动元素的个数是（　　）。 A.n-i B.n-i+1 C.n-i-1 D.i 9. 下列不是线性结构的是（　　）。 A. 树 B. 数组 C. 队列 D. 栈 10. 幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构 描述最合适？（　　） A. 链表 B. 字典 C. 栈 D. 队列 11. 下列选项中，采取“后进先出”的线性数据组织和存储的是（　　）。 A. 队列 B. 数组 C. 字符串 D. 栈 12. 依次在初始为空的队列中插入元素 a、b、c、d 以后，紧接着做了两次删除操作，此时的 队首元素是（　　）。 A.a B.b C.c D.d 13. 一个栈的入栈序列是 1、2、3、4、5，其出栈序列为 s1、s2、s3、s4、s5。若 s2 是 3，则 s1 不 可能是（　　）。 A.1 B.2 C.4 D.5 14. 设某个栈的输入序列为 A、B、C、D，则借助这个栈所得到的输出序列不可能是 （　　）。 A.A、B、C、D B.D、C、B、A C.A、C、D、B D.D、A、B、C 15. 设有编号为 1、2、3、4 的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺 序为（　　）。 A.1、2、3、4 B.1、2、4、3 C.1、3、2、4 D.1、4、2、3 16. 四个元素按 A、B、C、D 顺序进入 S 栈，执行两次 Pop（S，x）运算后，栈顶元素的值是 （　　）。 80 选择性必修一　数据与数据结构　 A.A B.B C.C D.D 17. 由于十进制数转为二进制数是将该十进制数对 2 进行整除，直到商为 0，再将每一次 整除得到的余数按从下到上的顺序排列组合起来，因此十进制数转二进制数的过程中，适合 用（　　）的数据结构来存储余数。 A. 队列 B. 栈 C. 二叉树 D. 图 18. 在单链表中，要将 s 所指节点插入到 p 所指节点之后，其语句应为（　　）。 A.s->next=p+1； p->next=s； B.（*p）.next=s； （*s）.next=（*p）.next； C.s->next=p->next； p->next=s->next； D.s->next=p->next； p->next=s； 二、判断题 19. 同一线性表的各数据元素必定具有相同的数据类型和长度。 （　　） 20. 长度为 1 的字符串与单个字符的意义及可执行的操作是相同的。 （　　） 21. 字符串的每个数据元素可以是由一个字符组成，也可以是由多个字符组成。（　　） 22. 字符串在存储时，既可以用顺序存储结构，也可以用链式存储结构。 （　　） 23. 某一个队列长度是 8，依次进队 8 个元素，依次出队 6 个元素，此时至少还能在队列中 插入 6 个元素。 （　　） 24. 栈是运算受限制的线性表。 （　　） 25. 在栈空的情况下，不能做出栈操作，否则产生下溢。 （　　） 26. 空栈就是所有元素都为 0 的栈。 （　　） 27. 一个栈的输入序列为 A、B、C、D ，可以得到输出序列为 C、A、B、D。 （　　） 28. 循环队列能实现对空间的更大限度的利用。 （　　） 三、填空题 29. 在数据结构中，具有“先进先出”特征的线性表是　　　　　　　　　　。 30. 在栈中，只能在　　　　进行数据元素的插入和删除。 31. 在一个队列中，队头的标志是 front，队尾的标志是 rear，队列的长度为　　　　。 32. 循环队列的引入，目的是克服列队的　　　　现象。 四、应用题 33. 数据元素 A、B、C 依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有 哪些？ 34. 用 I 表示进栈操作，用 O 表示出栈操作，如 A、B、C 三个元素，依次进栈写成“III”，依次 再出栈写成“OOO”，经过这样的“IIIOOO”操作序列之后，出栈的序列是 CBA。现有一个栈， 元素进栈的次序为 a、b、c、d、e，写出下列出栈的操作序列。 （1）c、b、a、d、e 81 （2）a、c、b、e、d 第四章　抽象数据类型 一、认识抽象数据类型 抽象数据类型是指由一种数据结构和在其上的一组操作所组成的、并不具体关心数据 的存储结构和操作的具体实现的抽象数据结构。 定义抽象数据类型的基本格式： ADT 抽象数据类型名 　｛ 　数据：<数据描述> 　操作：<基本操作的定义> 　｝ADT 抽象数据类型名 例如，长方形可以抽象为（以 Python 为例）： class rectangle（object）： 　　def __init__（self，a，b）： 　　　　self.a=a 　　　　self.b=b 　def area（self）： 　　　　s=self.a*self.b 　　　　return s 　　def perimeter（self）： 　　　　c=2*self.a+2self.b 　　　　return c 二、用抽象数据类型表示队列和栈 1.用抽象数据类型表示队列 ADT 队列 　　｛ 数据： 　　　　队列元素； 　　　　队头； 82 第三章 线性数据的组织和存储 四、随堂练习 （一）选择题 1-5 ABDBA 6-10CCBAD 11-15DCDDD 16-18BBD （二）判断题 19-23 ✔✖✔✔✖ 24-28✔✔✖✖✔ （三）填空题 29.队列 30.栈顶 31.real-front 32.假溢出 （四）应用题 33.出栈的序列可能有：ABC、CBA、BCA、BAC、ACB 34.(1)IIIOOOIOIO (2)IOIIOOIIOO 第三章 线性数据的组织和存储 四、随堂练习 （一）选择题 1-5 ABDBA 6-10CCBAD 11-15DCDDD 16-18BBD （二）判断题 19-23 ✔✖✔✔✖ 24-28✔✔✖✖✔ （三）填空题 29.队列 30.栈顶 31.real-front 32.假溢出 （四）应用题 33.出栈的序列可能有：ABC、CBA、BCA、BAC、ACB 34.(1)IIIOOOIOIO (2)IOIIOOIIOO 学科网（北京）股份有限公司 $$