数据结构复习指导市公开课金奖市赛课一等奖课件

数据结构复习指导第1页第1章绪论掌握内容：基本术语：数据、数据元素、数据对象、数据结构、抽象数据类型、次序存放结构和链式存放结构。算法：5个特征、时间复杂度和空间复杂度含义与估算。时间复杂度O(n)表示伴随数据规模n不停增加，算法执行时间将以线性速度增加。时间复杂度：O(n)、O(nlogn)、O(n2)第2页算法指是A.计算机程序 B.处理问题计算方法C.排序算法 D.处理问题有限运算序列第3页将长度为n单链表接在长度为m单链表之后算法时间复杂度为()。A.O(n) B.O(1) C.O(m) D.O(m+n)第4页抽象数据类型与数据结构定义区分在于

。

数据逻辑结构是从逻辑关系上描述数据，它与数据

无关，是独立于计算机。第5页第2章线性表知道线性表定义、各基本操作含义存放形式：次序存放结构与链式存放结构次序存放结构特点：1.逻辑结构与物理结构一致；2.属于随机存取方式缺点：插入、删除元素需要移动，平均约二分之一元素链式存放结构特点：1.逻辑结构与物理结构不一致；2.属于次序存取方式第6页次序表和有序表次序表：线性表采取次序存放结构表示有序表：内容按从小到大排列线性表算法：在有序表中插入一个元素使其仍有序在给定位置插入一个元素注意：不要采取书上使用指针确定元素位置方式，而用下标形式，可提升可读性。第7页链表不特殊说明，均带头结点算法：在有序链表中插入一个结点，使其仍保持有序给定元素位置，插入或删除对应结点正序或逆序创建链表注意：*对循环链表操作时，尾部判断

*双向链表插入、删除结点

*删除结点一定要释放空间第8页在头指针为head且表长大于1单链表中，指针p指向表中某个结点，若p->next->next=head，则正确说法是（）。A.p指向头结点B.p指向尾结点C.*p直接后继是头结点D.*p直接后继是尾结点第9页有序次序表与无序次序表相比，其操作优势是（）。A.删除快B.插入快C.生成快 D.查找快第10页在长度为n次序表中第i个元素(1in)之前插入元素时，需向后移动元素个数是

。sps->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

第11页pp->prior->next=p->next;p->next->prior=p->prior;deletep;第12页第3章栈和队列栈和队列定义，操作特点栈应用：*会写出递归执行过程*深度（纵向）遍历*正、反向操作*表示式、背包队列：按层遍历注意：次序队列都应该使用循环队列。

第13页栈经典题判回文、表示式括号配对情况假设入栈次序为1234，则以下不可能出现出栈序列为：4321342112343412给定一个序列ssxxssxxxxsxsxxxssss,s代表入栈，x代表出栈，这是正当操作序列吗？第14页仅允许在同一端进行插入删除线性表称为

。设元素15，25，35和45入队，然后三个元素出队，此时留在队列里元素是

。第15页设数组data[m]作为循环队列SQ存放空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为()。A.SQ.front=SQ.front+1 B.SQ.front=(SQ.front+1)%(m–1)C.SQ.front=(SQ.front–1)%m D.SQ.front=(SQ.front+1)%m第16页若已知一个栈入栈序列是1,2,…,n.其出栈序列为p1,p2,…,pn(表示1,2,…,n一个排列)。若p1=n，则pi为（）。A.iB.n-iC.n-i+1D.不确定第17页第4章串概念：串、子串、空串、匹配、相等基本操作含义存放结构：定长：数组堆分配：new链式在串S="structure"中，以t为首字符子串有

个。第18页第5章数组和广义表数组特点数组下标与存放地址映射计算矩阵压缩特殊矩阵压缩后稀疏矩阵三元组表示广义表存放结构，遍历算法第19页假设二维数组A[10][9]按行优先次序存放，若每个元素占用3个存放单元，且A[0][0]起始地址为100，则元素A[9][8]存放地址是

。LOC(9,8)=LOC(0,0)+(9*9+8)*3=100+89*3=100+267=367第20页已知广义表表头是((a))，表尾是((b)，(c，(d，e，(f))))，则该广义表为

(((a)),(b),(c,(d,e())))。第21页一个非空广义表表头()。A.不可能是子表 B.只能是子表C.只能是原子 D.能够是原子或子表画出以下广义表存放表示。L=((e,f),(a,(b)),((c,d)),(a,(b)))第22页已知两个4﹡5稀疏矩阵三元组表分别以下。请画出这两个稀疏矩阵之和三元组表：第23页第6章树与二叉树基本概念树与森林：定义、存放结构（双亲、孩子链表、孩子弟兄）二叉树：定义、性质、存放结构、遍历、完全二叉树树、森林与二叉树之间关系，相互转换结构赫夫曼树第24页与算法相关经典例题给定一棵二叉树先序和中序（后序和中序）遍历序列，结构对应二叉树经过二叉树，取得对应树或森林相关信息按层遍历二叉树/树利用某种遍历序列，对二叉树进行某种操作三序遍历递归和非递归算法第25页在一棵度为3树中，度为3结点个数为2，度为2结点个数为1，则度为0结点个数为()。A.4B.5 C.6 D.7已知一棵完全二叉树中共有768个结点，则该树中共有384个叶子结点。在一棵高度为h满三叉树中，结点总数是多少？写出计算步骤和结果。答：30+31+32+...+3h-1=3h-1第26页由五个分别带权值为9，2，5，7，14叶子结点组成哈夫曼树，写出该树带权路径长度并示明计算步骤。已知树T先根序列为ABCDEFGHIJKL，后根遍历序列为CBFGEHDKJLIA，请画出树T。第27页设高度为h二叉树中只有度为0和度为2结点，则这类二叉树中所包含结点数最少为（）。A.2h B.2h-1C.2h+1 D.h+1

设a、b为一棵二叉树上两个结点，在中序遍历时，a在b前条件是（）。A.a在b右方B.a是b祖先

C.a在b左方D.a是b子孙第28页假设通讯电文使用字符集为{a，b，c，d，e，f}，各字符在电文中出现频率分别为：0.34，0.05，0.12，0.23，0.08和0.18，试为该字符集设计Huffman编码，并计算对应Huffman树带权路径长WPL（要求树中左孩子结点权值小于右孩子结点权值，且左分支以0编码，右分支以1编码）。Huffman树：该树带权路径长度WPL=第29页对于给定正整数x，设计一递归算法，在由正整数为结点数据域值一棵二叉排序树中，找出最靠近且又小于x值（要求：写明算法思想，语句加注释，画出你跟踪算法数据模型。数据类型按常要求义，无须另加说明）。第30页voidsearch(BiTreeT,intx,int&pre){if(T){search(T->lchild,x,pre);if(T->data<x){pre=T->data;search(T->rchild,x,pre);}}}第31页第7章图有向图：弧、入/出度、有向完全图无向图：边、度、无向完全图存放结构（邻接/十字/多重—适用场所）图遍历算法（切记）最小生成树（算）、拓扑排序（算）、关键路径、一顶点到其余各顶点最短路径（按算法手工走给定例子）图连通性第32页经典题目深度或广度优先遍历第33页能够完成拓扑排序图一定是一个

有向无环图

。

n个顶点无向连通图最少有

n-1条边。已知一个有向图邻接矩阵表示，计算第i个结点入度方法是

统计第i列中1数目。第34页设一个有n个顶点和e条弧有向图用邻接表表示，则删除与某顶点vi相关全部弧时间复杂度是A.O(n) B.O(e) C.O(n+e) D.O(n*e)在含n个顶点和e条边无向图邻接矩阵中，零元素个数为

n*n-2*e。第35页已知一个无向图顶点集为{a,b,c,d,e},其邻接矩阵以下所表示：0100110010000110110110110(1)画出该图图形；(2)依据此邻接矩阵，从顶点b出发进行深度优先遍历和广度优先遍历，写出对应遍历顶点序列。第36页第9章查找次序查找、二分查找、分块查找二叉排序树（创建、查找、平衡(手工)、ASL）哈希表（常见哈希函数和处理冲突方法，计算ASL）查找特点构件次优查找树第37页在一个无序次序表中，查找不成功与能够找到一个元素所需时间相比较，耗时比较结果为（）。

A.长B.短C.相等D.不可判断假如要求一个线性表既能较快地查找，又能适应动态改变要求，能够采取（）。A.分块查找 B.次序查找C.折半查找 D.哈希查找第38页假设哈希表长度为m，哈希函数为H(key)，若用线性探测处理冲突，则探查地址序列形式表示为Hi=(H(key)+di)MODm。在各种查找方法中，平均查找长度与结点个数n无关查找方法是哈希。第39页采取分块查找方法查找长度为n线性表时，若用折半查找定位块，每块统计个数为s，则该分块查找平均查找长度为ASL=log2(n/s+1)+s/2。设a1,a2,a3是不一样关键字且a1>a2>a3，可组成6种不一样输入次序。画出其中哪几个输入次序所组成二叉排序树高度为3。第40页关键字:ABCDEPi:0.20.30.050.30.15

Ci:23123静态查找树表在不等概率查找情况下，折半查找不是有序表最好查找方法。比如:此时ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变比较次序21323则ASL=20.2+10.3+30.05+20.3+30.15=1.9第41页若只考虑查找成功情形，则最优判定树为带权内路径长度之和PH最小。即：其中：n：有序表长度hi：第i个结点在判定树中层次数wi=c*pipi：查找概率c：常量第42页关键字:ABCDEPi:0.20.30.050.30.15

Ci:23123Ci：21323CADBEPH=0.05+(0.2+0.3)*2+(0.3+0.15)*3=2.4BADBEPH=0.3+(0.2+0.3)*2+(0.05+0.15)*3=1.9第43页因为结构最优判定树代价过高，所以，通常寻找靠近最优判定树次优判定树。即带权内路径长度近似最小。第44页(rl,rl+1,...,rh)rl.key<rl+1.key<...<rh.key选择二叉树根结点ri，使最小

介绍一个次优二叉树结构方法：然后分别对子序列{rl,rl+1,...,ri-1}和{ri+1,...,rh}结构两个次优查找树，并分别将它们设为根结点ri左、右子树。第45页为了便于计算，引入累计权值和并设wl-1=0和swl-1=0，则推导可得：lih第46页023811151823lh211812431018h9608EC21Ah53lhG3013第47页ECGABDF所得次优二叉树以下所表示:

查找比较“总次数”

=32+41+25+33

+14+33+25

=

52

查找比较“总次数”

=32+21+35+13

+34+23+35

=

59和折半查找相比