数据结构总复习和作业PPT学习教案

1、会计学1数据结构总复习和作业数据结构总复习和作业考试时间：第10周周日(5月月10日日) 九、十节考试教室安排：考试方式：闭卷笔试考试成绩卷面(80)平时作业(20)考试题型(参考）：1、判断对错、选择、填空2、综合应用3、算法设计数据结构答疑安排：数据结构答疑安排：大黑楼大黑楼A802或或A718周三周三(5月月6日日)下午下午1:305:00第1页/共48页第2页/共48页时间复杂度第3页/共48页&第三章 栈和队列-操作受限的线性表2 栈F特点（掌握） ：FILO(LIFO)F存储结构（掌握） ：顺序栈与链栈F基本操作（掌握） ：入栈与出栈F应用（掌握） ：回文、括号匹配、表达式求值3第

2、4页/共48页2 队列F特点（掌握） ：FIFO（LILO）F存储结构（掌握） ： 顺序队列 链队列F循环队列（掌握）F基本操作（掌握） 入队 出队F应用（了解）：迷宫，优先队列等队空、队满条件第5页/共48页&第四章 数组2 线性结构2 存储结构F顺序存储结构（掌握） ：次序约定 （算法实现不要求）F压缩存储（掌握） 对称矩阵 对角矩阵 三角矩阵 稀疏矩阵2 算法：求转置矩阵（了解）三元组表行逻辑链接的顺序表带行指针向量的单链表十字链表第6页/共48页&第五章 树2 逻辑结构：按分支关系定义的层次结构2 定义（掌握）：F深度、度、叶子等F满二叉树、完全二叉树2 二叉树性质（掌握） ：52 存

3、储结构F树（掌握） 双亲表示法 孩子表示法（孩子链表与多重链表） 孩子兄弟表示法（二叉链表）第7页/共48页F二叉树（掌握） 顺序存储结构 二叉链表 三叉链表F树、森林与二叉树转换（掌握）F遍历 按层次、先序、中序、后序 遍历递归（掌握）与非递归算法（了解） 遍历算法应用（掌握）由先序序列建立二叉链表统计叶子结点求二叉树深度已知先序和中序序列，构造二叉树第8页/共48页2 应用FHuffman树（掌握） 定义，WPL 构造方法 有n个叶子结点的Huffman树共有2n-1个结点 应用Huffman编码与译码最佳判定树第9页/共48页&第六章 图2 定义（掌握） ：图、有向图、度、连通、完备图等

4、2 存储结构F邻接矩阵（掌握）F邻接表与逆邻接表（掌握）F十字链表（了解）F邻接多重表（了解）2 遍历：深度优先与广度优先（掌握遍历策略及算法）深度优先生成树、广度度优先生成树构成特点(与顶点度关系)第10页/共48页2 应用（掌握求解过程，不要求写算法掌握求解过程，不要求写算法 ）F最小生成树（Prim与Kruscal）F拓扑排序F最短路径（Dijkstra）第11页/共48页&第七章 查找2 静态查找表F顺序查找（掌握）F折半查找（掌握）F分块查找（了解）2 动态查找表（了解）F二叉排序树定义构造方法生成、插入、删除与查找中序遍历二叉排序树可得到结点有序序列比较、ASL第12页/共48页2

5、 哈希查找（掌握）F定义、基本思想FHash函数构造方法F处理冲突方法F哈希表构造F哈希查找过程与ASL第13页/共48页&第八章 排序2 掌握排序的 基本概念和性能分析方法，排序策略 2 插入排序F直接插入排序（掌握）F折半插入排序（掌握）F希尔排序（了解）2 交换排序F冒泡排序（掌握）F快速排序（了解）2 选择排序F简单选择排序（掌握）F堆排序（掌握，不考算法）第14页/共48页2 归并排序：2-路归并排序（了解）2 基数排序：链式基数排序（了解）F排序方法思想F每趟排序结果F排序方法性能分析评价本章了解的排序方法不要求掌握算法第15页/共48页作业作业1.线性表线性表从键盘读入从键盘读入

6、n个整数（升序），请编写算法实现：个整数（升序），请编写算法实现：CreateList()：建立带表头结点的单链表；：建立带表头结点的单链表；PrintList()：显示单链表：显示单链表(形如形如:H-10-20-30-40);InsertList()：在有序单链表中插入元素：在有序单链表中插入元素x；ReverseList()：单链表就地逆置；：单链表就地逆置；DelList()：在有序单链表中删除所有值大于：在有序单链表中删除所有值大于mink且小且小于于maxk的元素。的元素。选作：使用文本菜单完成功能选择及执行。选作：使用文本菜单完成功能选择及执行。思考题：思考题：你能将上述算法改为

7、双向循环链表吗？你能将上述算法改为双向循环链表吗？作业作业1 1第16页/共48页L 3 1 2 45 qptempq 单链表就地逆置第17页/共48页L 1 3 2 45 ptempqq 单链表就地逆置第18页/共48页L 2 1 3 45 tempqptempq 单链表就地逆置第19页/共48页L 5 2 1 43 qptempq 单链表就地逆置第20页/共48页L 4 5 2 31 voidListReverse_L(LinkList&L)LinkListp,q,u;p=L-next;if(p=NULL|p-next=NULL)/空链表或只有一个结空链表或只有一个结点点return;q=

8、L-next-next;/q指向第二个结点指向第二个结点p-next=NULL;while(q)u=q-next;q-next=L-next;L-next=q;q=u; 单链表就地逆置第21页/共48页L 3 1 2 45 qppretempq 单链表就地排序第22页/共48页L 1 3 2 45 ppretempqq 单链表就地排序第23页/共48页L 1 2 3 45 tempqqppre 单链表就地排序第24页/共48页L 1 2 3 45 tempqqppre 单链表就地排序第25页/共48页L 1 2 3 45 tempqqppre 单链表就地排序第26页/共48页L 1 2 3 4

9、5 qppre 单链表就地排序第27页/共48页L 1 2 3 54 单链表就地排序第28页/共48页LinkListSortList(LinkListL)/链表就地排序链表就地排序LNode*p,*pre,*q,*temp;p=L-next;if(p=NULL)returnL;/空表空表,不用排序，返回不用排序，返回q=p-next;p-next=NULL;while(q!=NULL)pre=L;p=L-next;while(p!=NULL)/查找插入位置查找插入位置if(q-datap-data)pre=p;p=p-next;elsebreak;temp=q-next;/插入插入pre-n

10、ext=q;q-next=p;q=temp;returnL;第29页/共48页作业作业2 2若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。可能的出栈序列：(14种)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出栈序列：(10种)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc 元素元素a、b、c、d、e、f依次通过栈，依次通过栈，若出栈顺序是若出栈顺序是c、b、d、f、e、a，则栈，则栈S的容量至少是（的容量至少是（）3表达式后缀形式，前缀形式表达式后缀形式，前缀形式

11、ab*cde/-f*+a*b+(c-d/e)*f循环队列队满和队空的判别条件。循环队列队满和队空的判别条件。Q.front=Q.rearQ.front=(Q.rear+1)%M第30页/共48页ij11-1Loc(a )=Loc(a )+*2(2n+2-i)ijilij11-1Loc(a )=Loc(a )+1*2iijl设A为n阶对称矩阵，采用压缩存储存放于一维数组Fn(n+1)/2中（从F0开始存放），请分别给出存放上三角阵时任一矩阵元素aij的地址计算公式和存放下三角阵时任一矩阵元素aij的地址计算公式。存放下三角阵时，任一矩阵元素aij（1in, 1ji）的地址计算公式为：存放上三角阵

12、时，任一矩阵元素aij（1in,ijn）的地址计算公式为： a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0作业作业2 2 a11 a12 a13 . a1n 0 a22 a23 . a2n 0 0 0 . ann an-1n-1an-1n第31页/共48页400000503008000000000700200000A 5 6 6 1 1 4 2 1 5 2 3 3 2 6 8 4 4 7 5 1 2 三元组表i j v0 1 2 3 4 5 6写出矩阵三元组表，十字链表作业作业2 2114512447233268215十字链表第32页/共48页请分

13、别画出具有请分别画出具有3个结点的树和个结点的树和3个结点的二叉树的所有不同形态。个结点的二叉树的所有不同形态。作业作业3 3 已知二叉树的先序遍历序列是已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。，请构造二叉树，并写出其层次遍历序列和后序遍历序列。EACBDIJHFGK层次：E A F B H D G I C K J后序-C D B A G J K I H F E第33页/共48页森林转换成一棵二叉树森林转换成一棵二叉树作业作业3 3BACDFGEHIJKL二叉树还原成森林二叉树还原

14、成森林ACHBFDMEGNJIKL第34页/共48页设二叉树的设二叉树的后序遍历序列为：后序遍历序列为：DCFEBHJKIGA，中序序列为：，中序序列为：CDBEFAHGJIK，请构造这棵二叉树。，请构造这棵二叉树。作业作业3 3二叉树的中序遍历序列为：二叉树的中序遍历序列为：DBHEIAFJKCG，层次遍历序列为：，层次遍历序列为：ABCDEFGHIJK，请画出该二叉树，请画出该二叉树第35页/共48页作业作业3 3假设用于通信的电文由假设用于通信的电文由7个字母组成个字母组成A,B,C,D,E,F,G，字母在电文中出现的频率分别为，字母在电文中出现的频率分别为0.17、0.09、0.12、

15、0.06、0.32、0.03、0.21。试为这。试为这7个字母设计哈夫曼编码，并计算其带权路径长度个字母设计哈夫曼编码，并计算其带权路径长度WPL 10.390.610.180.210.090.090.290.320.120.170.030.06AEGBDFWPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56A:101 B:001 C:100 D:0001 E:11 F:0000 G:01第36页/共48页算法设计题算法设计题二叉树采用二叉链表存储，试设计算法实现：二叉树采用二叉链表存储，试设计算法实现：CreateBT(BiTree

16、&T)：从键盘输入二叉树的先序遍历序列字符串（以：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；代表空结点），建立其二叉链表；如输入：如输入：AB#D#CE#F# 则建立如下图所示二叉树的二叉链表则建立如下图所示二叉树的二叉链表ExchangeBT(BiTree T): 设计递归算法实现二叉树中所有结点的左右孩子设计递归算法实现二叉树中所有结点的左右孩子交换；交换；CountLeaf(BiTree T, TElemType x, int &count): 统计以值为统计以值为x的结点为根的结点为根的子树中叶子结点的数目；的子树中叶子结点的数目；DispBiTree

17、(BiTree T, int level) : 按树状打印二叉树按树状打印二叉树。作业作业3 3第37页/共48页/输入先序序列，创建二叉树的二叉链表输入先序序列，创建二叉树的二叉链表void CreateBT(BiTree &T)char ch; scanf(%c,&ch); if (ch = #) T = NULL; else T = (BiTNode *)malloc(sizeof(BiTNode); T-data = ch; CreateBT(T-lchild); CreateBT(T-rchild);BCFAED/交换二叉树中结点的左右孩子交换二叉树中结点的左右孩子void Exch

18、angeBT(BiTree T) BiTree temp; if(T) temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; ExchangeBT(T-lchild); ExchangeBT(T-rchild);第38页/共48页BiTreeSearchTree(BiTreeT,charX)BiTreebt;if(T)if(T-data=X)returnT;bt=SearchTree(T-lchild,X);if(bt=NULL)bt=SearchTree(T-rchild,X);returnbt;returnNULL;voidLeafCount(B

19、iTreeT,int&count)if(T)if(T-lchild=NULL)&(T-rchild=NULL)count+;LeafCount2(T-lchild,count);LeafCount2(T-rchild,count);BCFAED第39页/共48页/按树状打印输出二叉树的元素按树状打印输出二叉树的元素,level表示结点的层次表示结点的层次voidDispBiTree(BiTreeT,intlevel)inti;if(T)DispBiTree(T-rchild,level+1);for(i=0;idata);DispBiTree(T-lchild,level+1);BCFAED打

20、印得到：#C#F#EA#D#B第40页/共48页已知带权有向图如下,要求：画出图邻接矩阵；给出图的一个拓扑有序序列；求从顶点a出发到其余个顶点的最短路径abcdehfg2169322430587210 2 6 9 0 30 1 0 5 0 2 8 0 7 3 0 24 0 21 0拓扑有序序列：a, b, d, f, e, c, g, h作业作业4 4第41页/共48页无向图邻接表存储结构如图所示：画出该无向图； 写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。 作业作业4 413247586DFS：1，3，4，7，8，6，5，2 BFS：1，3，2，

21、4，7，6，5，8 第42页/共48页对下标为对下标为19的有序表进行二分法查找，的有序表进行二分法查找，(1)画出折半查找的判定树；画出折半查找的判定树；(2)计算其计算其ASL;(3)比较比较4次查找成功的结点共有次查找成功的结点共有个。个。527136849ASL=(1+2*2+3*4+4*2)/9=25/92作业作业5 5第43页/共48页设有关键字序列设有关键字序列25，40，33，47，12，66，72，87，94，22，5，58散列表长为散列表长为12，散列函数为，散列函数为h(key)=key%11，用线性探测再散列处，用线性探测再散列处理冲突，请画出散列表，在等概率情况下，求

22、查找成功和查找失败理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败的平均查找长度的平均查找长度ASL=(1*6+2+3*2+5+6+9)/12=34/12作业作业5 536 0 5 361010730 0 1 2 3 4 5 6 7 8 9 10 9412662533472272401131261131187155589第44页/共48页设有关键字序列设有关键字序列25，40，33，47，12，66，72，87，94，22，5，58散列表长为散列表长为12，散列函数为，散列函数为h(key)=key%11，用二次探测再散列处，用二次探测再散列处理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败的平均查找长度的平均查找长度ASL=(1*6+2+3*3+4+5)/12=26/12作业作业5 536 0 5 361010730 0 1 2 3 4 5 6 7 8 9 10 9412662533472272401131251131187154