第三章 字符串、队列和栈（复习课件）信息技术浙教版2019选择性必修1

复习课件 第三章 字符串、队列和栈 浙教版（2019） 选修一 字符串 01 队列 02 栈 03 复习内容总览 字符串 PART 01 第1节 字符串 知识结构 第1节 字符串 知识点一 字符串 的概念 字符串是由零个或多个字符组成的有限序列。 一个字符串中可以包含多种字符集字符。字符串中所包含的字符个数称为字符串的长度。在字符串的应用中，会涉及一些特殊的字符串。 字符串 的特性 ①有限序列性 ۞字符串是一种线性表结构。 ۞数据元素个数是有限的。 ۞由零个或多个字符组成。 ۞可使用序列切片操作 ②可比性 空串:空串是不包含任何字符的串，其长度为零。 空格串:空格串是由空格组成的字符串，其长度为空格字符的个数。 第1节 字符串 知识点二 字符串的基本操作 1.创建 常用单引号()、双引号("")和三个单引号或双引号来创建。 2.子串判断 子串判断用于检查字符串a是否为字符串S的子串。 3.求子串 用于从字符串中取出其子串。 在Python中，可以用切片实现。 格式为“字符串[位置i:位置j]”。 使用[]来截取字符串。即:序列的索引和切片操作。 4.字符串的连接 Python中内置了非常丰富的字符串函数与方法，可直接调用。 第1节 字符串 提升练习 1.已知字符串a"人生苦短，我用Python”，则下列说法正确的是（ ） A.a[5]的值为"，"，a[:5]的值为"人生苦短" B.a[5]的值为"我”，a[:5]的值为"人生苦短" C.a[-5]的值为"y"，a[-5:]的值为" thon " D.a[-5]的值为"用"，a[-5:]的值为"ython " C 解析 a[5]表示字符串中的第6个字符，本题中a[5]为“我”。a[:5]表示取从第一个字符开始到下标为4的字符串，值为“人生苦短，”。AB选项错误。α[-5]表示从右往左数第5个字符，值为“y”。a[—5 :]表示从右往左数第5个字符开始到结束的字符串，值为“gthon”。 第1节 字符串 提升练习 2.有如下程序段： S=“2022 Hope To Get Out Of The Epidemic” t=“” for i in s: if i<“a” or i>“z”: t=”” t=i+t print(t) 该程序运行后，最后显示的内容是（ ） A.cimedipE B.cimedip C.cimed D.cime A 解析 该程序中语句“if i<“a” or i>“z”：；t=“””的功能是字符i为非小写字母时，变量t就清空。因此在“Epidemic”出现前，变量t中的内容为空。这样变量t中最后的内容为“Epidemic”的重新组合。语句t=i+t的功能就是将Epidemic”进行逆向组合。 第1节 字符串 提升练习 3.有如下Python程序段： text=”床前明月光，疑是地上霜。举头望明月，低头思故乡。” text=text.replace(“。”，“，”) ans=[s[0] for s in text.split(“,”) if s] ans=“”.join(ans) 则程序执行后，ans的值为（ ） A.“床前明月光” B.“床前明月” C.“床疑举低” D.”举头望明” C 解析 程序的功能是获取藏头诗。具体做法是先用“，”替换“。”，这样所有的分隔符均变成“，”，再用“，”将text分割成列表（注意最后一个列表元素为空串），并去列表元素的首字符，凭借成藏头诗。 队列 PART 02 第2节 队列 知识结构 第2节 队列 知识点一 概念 特性 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 队列的概念与特性 （1）先进先出、后进后出 入队：在队列中插入一个元素的过程 出队：在队列中删除一个元素的过程 （2）有限序列性 队列是一种线性表结构，元素的个数也是有限的 第2节 队列 知识点二 入队 建队 出队 常用操作 队列的基本操作 第2节 队列 知识点二 拓展链接 ①队列的链式存储结构： 队列的链式存储称为链队列，为了操作方便，可设置队首指针head记录链表的头节点，队尾指针tail记录链表的队尾节点。 ②循环队列：将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。 解题技巧 1.幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适( ) A.链表 B.字典 C.字符串 D.队列 解析 [解析]链表是存储结构，字段是数据类型，栈和队列是数据结构。排队玩滑滑梯是一头进一头出的队列结构。 D 解题技巧 2.已知队列元素的个数为6，则队首指针 head 和队尾指针 tail 的值不可能的是( ) A.head=0, tail=6 B. head=6,tail=0 C. head=3,tail=2 D. head=3,tail=8 解析 [解析]本题考查的是队列的相关知识。初始时，队列为空，队首指针head和队尾指针tail的值均为0，队列不为空时，队首指针指向队首元素，队尾指针指向队尾元素的下一个位置。选项A中入队6次，出队0次，那么head和tail的值为0，6该项正确;同理分析选项B，选项B，不可能入队0次，出队6次，该项错误。 B 解题技巧 3.小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分为为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（ ） A.4 7 B.4 8 C.5 7 D.5 8 解析 [解析]初始时,队列为空,队首指针head和队尾指针tail的值均为0,队列不为空时,队首指针指向队首元素,队尾指针指向队尾元素的下一个位置,本题中共进行了7次入队操作和4次出队操作，因此最终 head 和 tail 的值分别为4、7,因此答案为 A。 A 栈 PART 03 第3节 栈 知识结构 第3节 栈 知识点一 概念 特性 栈是一种先进后出的操作受限的线性表，仅允许在表的一端进行插入或删除。 栈的概念与特性 （1）先进后出、后进先出 （2）有限序列性 同队列一样，栈中的元素也是有限的。栈可以是空的，也可以包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。 第3节 栈 知识点二 栈的概念与特性 01 建栈 在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。 02 入栈、出栈 入栈又叫压栈操作，把数据元素压入栈顶。 03 栈的链式存储结构 利用链式存储方式实现的栈称为链栈。可用单链表的方式实现。 解题技巧 1.有1个栈，从栈顶到栈底依次为元素a、b、c并且已知元素d已入栈并出栈，则这四个元素的入栈顺序可能为（ ） A.a,b,c,d B.b,d,c,a C.c,d,b,a D.d,a,b,c 解析 [解析]因为d已经入栈并且出栈，因此其入栈的顺序对于我们是未知的，而a、6、c三个元素的相对顺序是确定的，所以他们之间的入栈顺序也是确定的，依次为c、b、a，而d可任意穿插在其中。故选:C。 C 解题技巧 2.在一个单向链表中,head 指针指向链表的头节点p,已知节点的指针区域为next,若要删除该链表中的头节点,则应执行的操作是（ ） A. head=head.next;p=head B. head=p.next;p.next=p C.p=p.next;head=p D.p=p.next;head.next=p 解析 [解析]本题主要考查的是在单向链表中删除节点。要删除链表中的头节点，应先将p指向p节点的下一个节点，然后将 head 指针指向p节点，因此答案为 C。 C 解题技巧 3.有一个空栈,规定用I表示一个元素入栈,用O表示一个元素出栈。现经过IIOIOOIO系列操作后,元素的出栈顺序是4,1,3,2,则元素的入栈顺序是（ ） A.1,3,4,2 B.3,4,1,2 C.2,3,1,4 D.1,4,3,2 解析 [解析]根据操作顺序“HIOIOOIO”，两次入栈后再出栈,因此第一个出栈的是第二个入栈的元素,所以元素4是第二个人栈的,接下来再次入栈一个元素,然后出栈,因此第三个入栈的是第二个出栈的元素,即元素1,此时栈内只有一个元素(即第一个人栈的元素),再次执行出栈,也就是第三个出栈的元素3,故第一个人栈的元素为3,最后元素2入栈出栈。 B 输出s 第3章 字符串、队列和栈 浙教版（2019） 选修一 谢谢观看 $$