《数据结构与算法》理论教案

教案

讲授章节第1讲概述

授课时数2

0教学目的：

1.了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容；

2.掌握数据结构的基本概念；

3.理解算法描述和简单的算法分析。

教学内容（讲授提纲）

一.课前导学（线上）

1.阅读：导学通知、课程介绍、学习方法、校内SPOC使用方法、本章节知识点等

2.观看导学视频

3.论坛讨论、反馈疑难点

二.课堂教学

01.介绍课程重要性和意义，以及学习目标等

2.什么是数据结构

2.1通过“中国软件和信息技术服务业现状”、“排队候车”等案例介绍线性结构。

表1中国软件和信息技术服务业现状

软件业收入统计人均创收软件从业人员数统计

年份

（亿元）（亿元）（万人）

20154284874.6574

20164823282.3586

20175510389.2618

o20186190995.0645

201971768106.6673

0

图1军人排队候车

2.2通过“早期华为组织结构图”、“族谱”等案例介绍树形结构

公司综合办公室

中研总部■市场总部■制造部■财经系统■行政管理部

认证部■投融斐部■财务部■审讨部

图2华为早期的管理组织结构图

图3族谱

2.3通过“高速铁路网”、“哥尼斯堡七桥问题”介绍图形结构

图4我国“四纵四横”高速铁路网

图5哥尼斯堡七桥问题

讨论：欧拉回路存在的充分必要条件是：

(1)图是连通的：(2)图中与每个顶点相连的边数(即顶点度数)必须是偶数。

3.基本概念和术语

3.1介绍数据(Data)、数据元素(DataElement)、数据项(DataIlem)、数据对象(DataObject)>

抽象数据类型(AbstractDataType)、数据结构三个要素。

3.2课堂练习

(1)在数据结构中，从逻辑上可以将之分为()。【中南大学】

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.内部结构和外部结构D.线性结构和非线性结构

(2)己知表头元素为c的单链表在内存中的存储状态如下表所示。【2012全国统考408】

现将f放于1014H处并插入到单链表中，若f在逻辑上位a和e之间，则a,e,f的琏接地

址”依次是()。

A.1010H,1014H,1004HB.1010H,I004H,10I4H

C.1014H,1010H,1004HD.1014H,1004H,1010H

4.算法和算法分析

4.1介绍算法的定义、特性、设计要求及算法效率的衡量方法。

4.2“百钱买百鸡”问题

讨论+翻转：我国占代数学家张丘建在《算经》一书中曾提出过著名的百钱买百鸡问题，

小组讨论“百钱买百鸡”算法思路，开展翻转课堂活动，最后教师总结算法的重要性。

4.3引导学生归纳总结各种常见阶数时间复杂度

4.4课堂练习

(1)求整数n(n>=0)阶乘的算法如下，其时间复杂度是()。【2012全国统考4081

intfact(intn){

if(n<=l)rctum1;

教案

讲授章节第2讲线性表、顺序表

授课时数2

0教学目的：

1.理解非空线性结构的四个特征。

2.线性表是重要的线性结构，要掌握线性表的定义。

3.掌握线性表的操作在顺序表中的实现。

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

2.论坛讨论、反馈疑难点

二.课堂教学

1.通过中国软件和信息技术服务业现状统计表，引入线性结构学习，总结非空线性结构的

四个特征

软件业收入统计人均创收软件从业人员数统计

年份

1亿元）（亿元）（万人）

20154284874.6574

20164823282.3586

2UI75510389.2618

20186190995.0645

0201971768106.6673

2.线性表的概念

3.线性表的抽象数据类型

data〜curl.n—.h•

%a|&2.....at»-l

,—mjaiSixc•

4.给定线性表的逻辑结构设计算法

（1）遍历线性表L

（2）合并线性表1:设La和Lb是元素属于同一数据对象且非递减有序的两个线性表，

现要求将两个线性表合并成一个新的非递减有序的线性表Lc。

（3）合并线性表2:设La和Lb是元素属于同一数据对象的两个线性表，试将线性表Lb合

并到线性表La中。要求Lb中元素和La中元素相同的不再合并。

要分析为什么（2）和（3）的时间复杂度分别是O（m*n）和O（m+n）。

5.线性表的顺序表示及类型定义

6.顺序表上基本运算的实现

（1）构造一个空顺序表；（2）拷贝构造函数；（3）遍历顺序表；（4）查找元素；15）求

前驱和后继；（6）插入运算：（7）删除运算；（8）逆置运算；（9）扩大表空间；

重点分析在插入和删除操作中的时间复杂度。

7.算法设计举例

（1）顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，

线性表空间足够大。试给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持

非递减有序。高效指最大限度的避免移动元素。

（2）【北京航空航天大学】已知长度为n的线性表A采用顺序存储结构，请写一时诃复杂

度为0（n）、空间复杂度为0（1）的算法，该算法删除线性表中所有值为item的数据元素。（0（1）

表示算法的辅助空间为常量）。

（3）[2010全国统考408】设将n（n>l）个整数存放到一维数组R中。试设计一个在时

间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移P（0<P<n）个位置，即

将R中的数据由（X0,Xl,...,Xn-l）变换为（Xp,Xp+l,...,Xn-1,X0,X1..,Xp-1）.要求：a）给出

算法的基本设计思想。b）采用C或C++或JAVA语言描述算法c）说明算法的时间复杂度和

空间女杂度。d）讨论：若采用直接左移p位，空间笈杂度仍为0（1）,但时间女杂度为O（np）。

三.课后巩固（线上）

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点：

1.重点是顺序表的定义，基本操作的实现。

2.难点是高效算法设计，例如国家2010年硕士研究生入学考试算法题就有5种解法

教学方法、教学手段：

1.线性表和顺序表的概念和类型定义（30分钟）

2.顺序表上基本运算的实现（30分钟）

3.顺序表算法举例（30分钟）

4.使用教具：计算机和投影仪；

5.辅助教学：雨课堂、校内SPOC、“百科园”在线考试系统、学堂在线MOOC、算法演示

动画；

6.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法；课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题：

1.分析在顺序存储结构卜.插入和删除结点时平均需要移动多少个结点。

2.顺序表la与1b非递减有序，顺序表空间足够大。试设计一种高效算法，将1b中元素合到

la中，使新的la的元素仍保持非递减有序。高效指最大限度地避免移动元素。

改为:顺序表la非递减有序，1b非递增有序，求解该问题。

参考资料：

1.冯广慧，吴昊，文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,2019

2.陈守孔，胡潇琨，李玲，冯广慧.算法与数据结构考研试题精析（第四版）[M].机械工

业出版社，2020

教案

讲授章节第3讲单链表

授课时数2

0教学目的：

1.掌握链表的类型定义和基本操作的实现。

2.掌握单链表的建立方法，特别是头插法和尾插法。

3.了解单链表的应用。

教学内容（讲授提纲）

二.课前导学7线卫5

1.观看导学视频

2.论坛讨论、反馈疑难点

二.课堂教学

01从顺序存储结构的优缺点，引出链表的必要性

插入和删除必须大量移动元素：必须预先确定空间；表空间不易扩充。

head

II—1•…

2.链表的类型定义

几个概念：结点，首元结点，第一元素结点，头结点，指针，头指针

头指针头丝点甄结点

B—H3—♦I

o

3,线性表的操作在单链表中的实现

（1）单链表的初始化；（2）清空单链表；（3）求表长；（4）遍历链表；（5）查找位序为i

的元素的地址；（6）查找值为value的元素的位序；（7）查找值为value的元素的前驱；（8）求

某元素的后继：（9）插入元素：（10）删除元素。

4.单链表的建立方法（特别是头插法和尾插法）

（1）头插法；（2）尾插法。

5.算法设计举例

（1）【2012全国统考408】假定采用带头结点的单链表保存单词，当两个单词有相同的后

缀时.，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示，

设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为（data,next）请设

0计一个时间上尽可能高效的算法，找出由sW和slr2所指的两个链表共同后缀的起始位置（如

图中字符i所在结点的位置p）。要求：a）给出算法的基衣设计思想。b）根据设计思想，采用

C或C++或JAVA语音描述算法，关键之处给出注释。c）说明你所设计算法的时间复杂度。

（2）【2009全国统考408】已知一个带有表头结点的单链表，结点结构为（dataJink）,假设

该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表

中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返

回1;否则，只返回0,要求：a）描述算法的基本设计思想：b）描述算法的详细实现步骤；c）

根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关

键之处请给出简要注释。

三.课后巩固（线上）

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点：

1.动态存储（单链表）的概念。

2.单链表的算法设计。

教学方法、教学手段：

1.链表的定义和基本操作的实现（45分钟）

2.链表生成和链表应用的算法设计（45分钟）

3.使用教具：计算机和投影仪；

4.辅助教学：雨课堂、校内SPOC、“百科园”在线考试系统、学堂在线MOOC、算法演示

动画；

5.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法；课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题：

1.试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作用。

2.分析顺序存储结构和健式存储结构的优缺点，说明何时应该利用何种结构。

3.为什么在单循环链表中常使用尾指针，若只设头指针，插入元素的时间复杂度如何？

4.在单链表、双链表、单循环链表中，若知道指针p指向某结点，能否删除该结点，时间

复杂度如何？

5.设ha和脑分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两

个有序链衣合并成个非递增有序的单链衣。要求使用原链表空间，衣中无重复数据。

改：设施和脑分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这

两个有序链表合并成一个非递减有序的单链表。要求使用原链表空间，表中无重复数据，

参考资料：

1.冯广慧，吴昊，文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,2Q19

2.陈守孔，胡潇琨，李玲，冯广慧.算法与数据结构考研试题精析（第四版）[M].机械工

业出版社,2020

3.翁惠玉，俞勇.数据结构：思想与实现，高等教育出版社[M].高等教育出版社,2018

教案

讲授章节第4讲循环链表、双链表

授课时数2

0教学目的：

1.掌握循环链表引入的背景：从任一结点开始可以访问链表中的全部结点。

2.掌握循环链表（单循环链表，双循环链表）和双链表。

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

2.论坛讨论、反馈疑难点

二.课堂教学

1.比较顺序表和单链表操作的优缺点，使用范围

02.介绍单循环链表。指出：单循环链表往往只设尾指针

3.讲解两个只设尾指针的单循环链表合并成一个单循环链表的例子

4.双链表的定义

为深刻的理解双链表，展开讨论：

p->prior->next==?;

P->ncxt->prior==?;

引导学生理解双链表的特点：

p->prior->next==P->next->prior==p;

注意区分双链表和双循环链表是两种链表。

5.线性表的操作在双链表中的实现

o凡涉及一个方向的指针时，如求长度，取元素，元素定位等，其算法描述和单链表基本相

同。但是在插入或删除结点时，一个结点就要修改两个指针域，所以要比单链表复杂。由于双

链表有两个指针域，求前卵和后继都很方便。

s->prior=p->prior：

p->prior->ncxt=s;

s->next=p;

p->prior=s;

p->prior->next=p->next;

0p->next->prior=p->prior;

deletep;

92双缺中暗由巨

6.算法设计举例

（1）将单循环链表改为双循环链表。假设一个单循环链表，其结点含有三个域pre、data、

nexto其中data为数据域；pre为指针域，它的值为空指针（null）；next为指针域，它指向后继

结点。请设计算法，将此表改成双向循环链表。

（2）已知一双向循环链表，从第二个结点至表尾递增有序，（设alvxvan）。试编写算法，

将第一个结点删除并插入表中适当位置，使整个链表递增有序。

（3）［2015全国统考408】用单链表保存m个整数,节点的结构为（data,国k）,K|data|<n（n

为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅

保留第一次出现的节点而删除其余绝对值相等的节点。例如若给定的单链表head如下。

HE।AD1HEAD

匚土WG一国土EH—EB一匣］删除后03-03—ES-ELD

三.课后巩固（线上）

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点:

1.循环链表和双链表的概念C

2.难点是循环链表和双链表的应用算法设计。

教学方法、教学手段:

1.循环链表和双链表（45分钟）

2.算法设计（45分钟）

3.使用教具：计算机和投影仪；

4.辅助教学：雨课堂、校内SPOC、“百科园”在线考试系统、学堂在线MOOC、算法演示

动画；

5.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法；课后观

看习题视频，并在校内SP0C完成知识点在线测试。

作业、讨论题、思考题:

1.设la是一个双向循环链表，其表中元素递增有序。试写一算法插入元素x,使表中元素

依然递增有序。改为：设la是一个双向循环链表，其表中元素递减有序。试写一算法插入元素

X,使表中元素依然递减有序。

2.设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式

各自仅有奇次塞或偶次塞顶，并要求利用原链表中的结点空间来构造这两个链表。

参考资料:

1.冯广慧，吴吴，文全刚.算法与数据结构（C++语言版）1MJ.电子工业出版社,2019

2.陈守孔，胡潇琨，李玲，冯广慧.算法与数据结构考研试题精析（第四版）［M］.机械工

业出版社,2020

3.翁忠玉，俞勇.数据结构：思想与实现，高等教育出版社［M］.高等教育出版社,2018

教案

讲授章节第5讲栈

授课时数2

0教学目的：

1理解栈和队列仍属于线性结构，其操作是线性表操作的子集，是操作受限的线性表。但

从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。

2.掌握栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶

端。

3.掌握栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。

4.栈的应用：表达式求值。

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

02.论坛讨论、反馈疑难点

二.课堂教学

1.栈的基本概念：栈、栈顶、栈尾，栈只在栈顶操作。

o

2.栈的抽象数据类型定义

3.顺序栈及栈的操作在顺序栈中的实现

4.链栈及栈的操作在顺序栈中的实现

5.课堂练习

（1）【2010全国统考408】若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替

0进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）o

A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b

（2）［2013全国统考408】一个栈的入栈序列为1,2,其出栈序列是pl,p2,p3…pn。

若p2为3,则p3可能取值的个数是（）。A.n-3B.n-2C.n-1D.无法确定

6.栈的应用

（1）过程调用

（2）消除递归

（3）使用栈进行数制转换

（4）中缀表达式的求值

算术表达式中运算符（+,-,*,/等）的优先规则

设置两个工作栈：运算符栈SI和操作数栈S2oS2存放表达式的运算结果。

算法思想：

1首先置操作数栈S2为空栈，置运算符栈的栈底为表达式的起始符#（优先级最低）。

2依次读入表达式的每个字符ch,直至表达式结束：

若ch是操作数，则进S2栈；

若ch是运算符，若其优先级不高于栈顶运算符的优先级时，则取出枝S2的栈顶和次

栈顶的两个元素以及栈S1的栈顶运算符，进行相应的运算，并将结果放入栈S2中；如此下去，

直至ch的优先级高于栈顶运算符的优先级，将ch入S1枝。

三.课后巩固（线上）

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点：

1.重点是栈的概念和基础知识。

2.难点：中缀表达式求值。

教学方法、教学手段：

1.栈的基本概念和顺序栈（45分钟）

2.链栈、中缀表达式求值（45分钟）

3.使用教具：计算机和投影仪；

4.辅助教学：雨课堂、校内SPOC、“百科园”、学堂在线MOOC、算法演示动画；

5.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法：课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题：

1.有五个数依次进栈：I、2、3、4、5。在各种出栈的序列中以3、4先出的序列有哪几个。

2.铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1,2,3,

4,5,6,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能，说明

为什么不能；如果能，说明如何得到（即写出”进栈"或"出栈”的序列）。

3.设称正读和反读都相同的字符序列为“回文”，例如，“abba”和"abccba”是“回文”，“abcdc”

和“ababab”则不是“回文”，试写一个算法，判别读入的一个以@为结束符的字符序列是否是“回

文

参考资料：

I.冯广慧，吴昊，文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,2019

2.陈守孔，胡潇琨，李玲，冯广慧.算法与数据结构考研试题精析[M].机械工业出版七2020

教案

讲授章节第6讲校的应用

授课时数2

教学目的：

1.掌握栈的定义的本质：LIFO。栈是只准在一端进行插入和删除操作的线性表，该瑞称为

栈的顶端。

2.掌握栈的应用：中缀表达式转为后缀表达式，并求值。

3.掌握递归过程的应用。

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

2.论坛讨论、反馈疑难点

二.课堂教学

本次课继续学习栈的应用。

1.中缀表达式转为后缀表达式

（1）算法思想及实现

（2）举例：中缀表达式12*（6/205）转为后缀表达式

（3）介绍中缀表达式转为后缀表达式的简单方法

2.课堂练习

（1）[2012全国统考408】已知操作符包括，+',＜，（和）。将中绿表达式

a+b-a*（（c+d）/e-D+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运

算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。

A.5B.7C.8D.11

（2）【2014全国统考408】假设栈初始为空，将中缀表达式a/b+（c*d-e*f）/g转换为等价的

后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）。

A.+（*-B.+（-*C./+（*-*D./+-*

3.后缀表达式求值

（1）算法思想及实现

（2）举例：后缀表达式1262/0.5-*求值

4.递归：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的

应用，则称它们是递归的，或者是递归定义的。

5.递归过程的应用

问题的定义是递归的：f（n）=n*f（n-l）

数据结构是递归的：链表

问题的解法是递归的：Hanoi塔问题

6.递归算法的优缺点

7.递归的消除

(1)采用迭代算法

(2)尾递归的消除

(3)利用栈消除任何递归

三.课后巩固(线上)

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点；

1.中缀表达式转成前缀、后缀表达式，并对两种表达式求值。

2.用递归解决的问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归

的，掌握典型问题的算法。将递归算法转为非递归算法，特别是尾递归的消除。

教学方法、教学手段：

1.复习栈的基本概念、中缀表达式转为后缀表达式并求值(45分钟)

2.递归过程、消除递归(45分钟)

3.使用教具：计算机和投影仪；

4.辅助教学：雨课堂、校内SPOC、“百科园”在线考试系统、学堂在线MOOC、算法演示

动画；

5.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法；课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题：

1.写出下列中缀表达式的后缀表达式：

(1)A*B*C(2)(A+B)*C-D(3)A*B+C/①-E)(4)(A+B)*D+E/(F+A*D)+C

2.选择题：4个园盘的Hahoi塔，总的移动次数为()。

A.7B.8C.15D.16

3.已知Ackerman函数定义如下，试写出递归算法。

/7+1m=0

Akm(m,n)=akir^m-1,1)in*0,n=0

akn^m-\,akn^m9n-1))w0,〃工0

4.整数序列如，a2,an，给出求解最大值的递归程序。

5讨论：有哪些方式可以避免顺序队列的假溢出，如何判断队列满和空

参考资料：

1.冯广慧，吴昊，文全刚.算法与数据结构(C++语言版)[M].电子工业出版社,2019

2.陈守孔，胡潇琨，李玲，冯广慧.算法与数据结构考研试题精析(第四版)[M].机械工

业出版社,2020

3.翁惠玉，俞勇.数据结构：思想与实现，高等教育出版社[M].高等教育出版社,2018

教案

讲授章节第7讲队列

授课时数2

0教学目的：

1.队列的基本概念和算法，其木质是：FIFO。

2.掌握链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有牺牲一个单元

和设标记等方法。

3.栈和队列的综合应用

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

2.论坛讨论、反馈疑难点

0二.课堂教学

1.队列的基本概念和术语，其本质是：FIFOo

o

2.队列的类型定义

3.队列的顺序表示和实现.重点讲解循环队列

提出问题一产生矛盾一解决矛盾：顺序队列的假溢出一循环队列一队头队尾相等时是满和

空的判断。

循环队列的入队、出队、求队列元素个数等操作中，都要注意取模操作。

4.队列的链式表示和实现

05.课堂练习

[2014全国统考4081循环队列存放在一维数组中，endl指向队头元素，end2

指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M—

1个元素，初始时为空。下列判断队空和队满的条件中，王确的是（）。

A.队空：end1==end2;队满end1==(end2+l)modM

B.队空：endl==cnd2:队满：cnd2==(endl+l)mod(M-l)

C.队空：end2==(end1+1)modM;队满：endl==(end2+1)modM

D.队空：encl1==(end2+1)modM;队满：end2==(end1+1)mod(M-1)

6.算法设计举例

(1)假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，不设头指针，

试设计相应的入队列和出队列的算法

(2)要求完全利用循环队列中的元素空间，设置一个标志域lag,并以tag的值是0或1

来区分尾指针和头指针相同时的队列状态是"空''还是“不空请编写与此结构相对应的入队和

出队的算法。

(3)请利用两个栈SI和S2来模拟一个队列。【上海交通大学】【度门大学】

三.课后巩固(线上)

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点:

1.队列的概念，循环队列和链队列操作的实现。

2.循环队列中队列空川队头指针等于队尾指针来判断，队列满则可用牺牲一个单元及设标

记等方法。这里特别注意入队、出队和求元素个数等操作中的取模运算。

3.难点是栈和队列的综合运用

教学方法、教学手段:

1.队列的基本概念、循环队列(45分钟)

2.链队列(20分钟)

3.算法设计举例(25分钟)

4.使用教具：计算机和投影仪；

5.辅助教学：雨课堂、校内SPOC、百科园、学堂在线MOOC、算法演示动画；

6.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法：课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题:

1.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为。和3,当从

队列中删除一个元素，再加入两个元素后，rear和from的值分别为多少？

2.设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的时间如何？若

只设尾指针呢？

3.循环队列存储在数组中，则入队时的操作为().

A.rear=rear+1B.rear=(rear+l)%(m-1)

C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)

4.设用变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出

此循环队列的定义，并写出相应的入队(Queuein)和出队(QueueOul)算法。

5.讨论：循环队列的优点是什么，如何判断“空”和“满”。

参考资料:

1.冯广慧，吴昊，文全刚.算法与数据结构(C++语言版)[M].电子工业出版社,2019

2.陈守孔，胡潇琨,李玲冯广慧.算法与数据结构考研试题精析[M].机械工业出版七2020

教案

讲授章节第8讲串

授课时数2

0教学目的：

1.理解串的模式匹配。

2.掌握朴素模式匹配算法及改进（KMP）算法、求next口和nextval。的算法。

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

2.论坛讨论、反馈疑难点

二.课堂教学

1.串的概念和术语

02.串的表示和实现

比较顺序存储、链式存储（存储密度低）、块链式存储（算法实现复杂），字符串一般采用

顺序存储结构表示和实现。

3.朴素模式匹配算法

（1）算法思想及实现

（2）举例模拟匹配过程，主串S="GoogleGooseGood"，模式串T="Good”。

4.KMP算法——KMP—Knuth,Morris,Pratt三人发明

高德纳（DonaldErvinKnuth,1938年），美国著名计算

机科学家，斯坦福大学电脑系荣誉教授。高德纳教授被誉

为现代计算机科学的鼻祖，在计算机科学及数学领域发表

o了多部具广泛影响的论文和著作，与EdsgcrWybe

Dijkstra并称为我们这个时代最伟大的计算机科学家的

人。高德纳还是TheArtofComputerProgramming（中

译本《计算机程序设计艺术》）的作者以及TeX和Metafont

排版软件的发明人。

（1）算法特点，无需回溯，在O（n+m）的时间量级上完成串的模式匹配操作

（2）KMP算法思想

（3）求解next数组的算法思想，举例手工模拟过程

（4）算法实现

05.next数组的改进

讨论：模式串P=,aaaab'»其next函数值为01234,若主串为‘aaabaaabaaaab',当i=4,j

=4时siWpj,由next|j］的指示还需进行i=4、j=3,i=4、j=2,i=4、j=1等三次比较实际

L，由于模式中第1、2、3个字符和第4个字符都相等，囚此这种比较是不必要的，可以将模

式串一次向右滑动4个字符直接进行i=5、j=l的比较。也就是说，若next[jl=k,当si与pj

失配且pj=pk,则下一步不需将主串中的si与pk比较，而是直接与next[k]进行比较。由以上

思想对nexl函数进行改进。

6.朴素模式匹配算法与KMP算法的比较

虽然朴素模式匹配算法的时间复杂度是O（n*m）,但在一般情况下，其实际的执行时T近似

于O（n+m）,因此至今仍被采用。KMP算法仅当主串与模式间存在许多“部分匹配”的情况下才

显得快得多。KMP算法的最大特点是主串指针不回溯，在整个匹配过程中，对主串从头到尾扫

描一遍，对于处理存储在外存上的大文件是非常有效的。

7.课堂练习

【2015全国统考408】己知字符串S为"abaabaabacacaabaabcc"，模式串t为"abaabc'1,

采用KMP算法进行匹配，第一次出现“失配”（s[i]!=中]）时，i=j=5,则下次开始匹配时，i和

j的值分别是（）o

A.i=l,j=0B.i=5>j=0C.i=5»j=2D.i=6»j=2

8.算法设计举例，写出一个递归算法来实现字符串逆序存储。【中科院研究生院】

三.课后巩固（线上）

观看习题视频，并在校内SPOC完成知识点测试；在“百利园”完成线性结构闯关训练。

本章节的教学重点、难点:

1.本章重点是串的模式匹配、手工描述求匹配串的nexl和nextval函数值。

2.难点是KMP算法的推导过程。

教学方法、教学手段:

1.串的概念和术语、串的表示和实现（30分钟）

2.KMP算法、求解next和nextval（50分钟）

3.算法设计（10分钟）

3.使用教具：计算机和投影仪；

4.辅助教学：雨课堂、校内SPOC、“百科园”、学堂在线MOOC、算法演示动画；

5.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法；课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题：

1.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非

空且不同于S本身）的个数是多少？

2.用顺序结构存储的串S,编写算法删除S中第i个字符开始的j个字符。

3.模式率t=44abcaabbcaabdab'',求模式市的next和nextval数组的值。

4.对S='aabcbabcaabcaaba',T='bca',画出以T为模式串,S为目标串的匹配过程。

5.函数voidinsert（charchar*t,intpos）表示将字符串t插入到字符串s中，插入位置为

poso请编写实现该函数的算法。假设分配给字符串s的空间足够让字符串t插入。

6.讨论：kmp算法的特点是什么？BF算法已经不适用了吗？

参考资料：

1.冯广慧，吴昊，文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,2019

2.陈守孔，胡潇琨，李玲，冯广慧.算法与数据结构考研试题精析[M].机械工业出版社,2020

教案

讲授章节第9讲树、二叉树的概念和性质

授课时数2

0教学目的：

1.理解树是复杂的非线性数据结构，树，二又树的递归定义，基本概念，术语。

2.掌握二叉树的性质，存储结构

教学内容（讲授提纲）

一.课前导学（线上）

1.观看导学视频

2.论坛讨论、反馈疑难点

二.课堂教学

1.树的基本概念合术语

0

o

2.二叉树的基本概念和特点，二叉树的5种基本形态

3.二叉树的5个性质1对每个性质，都要会证明）

性质1：一个非空二叉网的第i层上至多有2M个结点（i>l）o

性质2：深度为k的二叉树至多有2k—1个结点（k>l）o

性质3：任何一棵二叉网中，若叶子数为no,度为2的结点个数为m，则110=112+1。

性质4：具有n个结点的完全二叉树的深度为「log2（〃+l）］。

性质5：如果对一棵有n个结点的完全二叉树按层次自上而下（每层自左而右）对结点

0从1到n进行编号，则对任意一个结点i（l<i<n）有：

（1）若i=l,则结点i为根，无双亲；若i>l,则结点i的双亲结点的编号是

（2）若2iWn,则i的左孩子的编号是2i,否则i无左孩子。

（3）若2i+，n,则i的右孩子的编号是2i+l,否则i无右孩子。

4.课堂练习

（1）[2011全国统考408】若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数

是（）＜■

A.257B.258C.384D.385

（2）[2009全国统考4）8】已知一棵完全二叉树的第6层（设根是第1层）有8个口一结点，

则该完全二叉树的结点个数最多是（）。

A.39B.52C.IllD.119

三.课后巩固（线上）

课后观看习题视频，并在校内SPOC完成知识点测试。

本章节的教学重点、难点：

重点和难点是二叉树的特点和5个性质。

教学方法、教学手段：

1.树的概念和术语（30分钟）

2.二又树的概念和性质（45分钟）

3.课堂练习（15分钟）

4.使用教具：计算机和投影仪；

5.辅助教学：雨课堂、校内SPOC、“百科园”在线考试系统、学堂在线MOOC、算法演示

动画；

6.课前观看导学视频；课中案例展开，应用翻转课堂、项目驱动以及实践教学法；课后观

看习题视频，并在校内SPOC完成知识点在线测试。

作业、讨论题、思考题：

1.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,求叶子数。

2.一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1

的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程