《数据结构总复习和作业2015.ppt》由会员分享,可在线阅读,更多相关《数据结构总复习和作业2015.ppt(48页珍藏版)》请在三一文库上搜索。
1、数据结构总复习,考试时间:第10周周日(5月10日) 九、十节 考试教室安排: 考试方式:闭卷笔试 考试成绩卷面(80)平时作业(20) 考试题型(参考): 1、判断对错、选择、填空 2、综合应用 3、算法设计,数据结构答疑安排: 大黑楼 A802或A718 周三(5月6日)下午1:305:00,第一章 绪言 基本概念和术语(掌握) 数据结构,数据,数据元素,数据项 逻辑结构与存储结构 算法分析(掌握) 算法定义 算法特性: 算法评价: 时间复杂度与空间复杂度(了解),第二章 线性表 逻辑结构(掌握) 存储结构(掌握) 顺序存储结构 链式存储结构 单链表 双向链表 循环链表 双向循环链表 静态
2、链表(了解) 基本操作(掌握) 插入 删除 查找 应用-一元多项式相加(掌握),时间复杂度,第三章 栈和队列-操作受限的线性表 栈 特点(掌握) :FILO(LIFO) 存储结构(掌握) :顺序栈与链栈 基本操作(掌握) :入栈与出栈 应用(掌握) :回文、括号匹配、表达式求值,3,队列 特点(掌握) :FIFO(LILO) 存储结构(掌握) : 顺序队列 链队列 循环队列(掌握) 基本操作(掌握) 入队 出队 应用(了解):迷宫,优先队列等,队空、队满条件,第四章 数组 线性结构 存储结构 顺序存储结构(掌握) :次序约定 (算法实现不要求) 压缩存储(掌握) 对称矩阵 对角矩阵 三角矩阵
3、稀疏矩阵 算法:求转置矩阵(了解),第五章 树 逻辑结构: 按分支关系定义的层次结构 定义(掌握): 深度、度、叶子等 满二叉树、完全二叉树 二叉树性质(掌握) :5 存储结构 树(掌握) 双亲表示法 孩子表示法(孩子链表与多重链表) 孩子兄弟表示法(二叉链表),二叉树(掌握) 顺序存储结构 二叉链表 三叉链表 树、森林与二叉树转换(掌握) 遍历 按层次、先序、中序、后序 遍历递归(掌握)与非递归算法(了解) 遍历算法应用(掌握) 由先序序列建立二叉链表 统计叶子结点 求二叉树深度 已知先序和中序序列,构造二叉树,应用 Huffman树(掌握) 定义,WPL 构造方法 有n个叶子结点的Huff
4、man树共有2n-1个结点 应用 Huffman编码与译码 最佳判定树,第六章 图 定义(掌握) :图、有向图、度、连通、完备图等 存储结构 邻接矩阵(掌握) 邻接表与逆邻接表(掌握) 十字链表(了解) 邻接多重表(了解) 遍历:深度优先与广度优先(掌握遍历策略及算法)深度优先生成树、广度度优先生成树,应用(掌握求解过程,不要求写算法 ) 最小生成树(Prim与Kruscal) 拓扑排序 最短路径(Dijkstra),第七章 查找 静态查找表 顺序查找(掌握) 折半查找(掌握) 分块查找(了解) 动态查找表(了解) 二叉排序树 定义 构造方法 生成、插入、删除与查找 中序遍历二叉排序树可得到结
5、点有序序列,比较、ASL,哈希查找(掌握) 定义、基本思想 Hash函数构造方法 处理冲突方法 哈希表构造 哈希查找过程与ASL,第八章 排序 掌握排序的 基本概念和性能分析方法,排序策略 插入排序 直接插入排序(掌握) 折半插入排序(掌握) 希尔排序(了解) 交换排序 冒泡排序(掌握) 快速排序(了解) 选择排序 简单选择排序(掌握) 堆排序(掌握,不考算法),归并排序:2-路归并排序(了解) 基数排序:链式基数排序(了解) 排序方法思想 每趟排序结果 排序方法性能分析评价,本章“了解“的排序方法不要求掌握算法,作业1.线性表 从键盘读入n个整数(升序),请编写算法实现: CreateLis
6、t():建立带表头结点的单链表; PrintList():显示单链表(形如:H-10-20-30-40); InsertList():在有序单链表中插入元素x; ReverseList():单链表就地逆置; DelList():在有序单链表中删除所有值大于mink且小于maxk的元素。 选作:使用文本菜单完成功能选择及执行。思考题:你能将上述算法改为双向循环链表吗?,作业1,L,单链表就地逆置,L,单链表就地逆置,L,单链表就地逆置,L,4,单链表就地逆置,L,3,void ListReverse_L(LinkList ,单链表就地逆置,L,单链表就地排序,L,单链表就地排序,L,单链表就地排
7、序,L,单链表就地排序,L,单链表就地排序,L,4,单链表就地排序,L,5,单链表就地排序,LinkList SortList(LinkList L) /链表就地排序 LNode *p,*pre,*q,*temp; p=L-next; if(p=NULL) return L; /空表,不用排序,返回 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; else break; temp=q-next; /插入 pre-next
8、=q; q-next=p; q=temp; return L; ,作业2,若进栈序列为ABCD,请写出全部可能的出栈序列和不可能的出栈序列。 可能的出栈序列:(14种) dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈序列:(10种) dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc,元素a、b、c、d、e、f依次通过栈, 若出栈顺序是c、b、d、f、e、a,则栈S的容量至少是( ),3,表达式后缀形式,前缀形式,ab*cde/-f*+,a*
9、b+(c-d/e)*f,循环队列队满和队空的判别条件。 Q.front=Q.rear Q.front= =( Q.rear+1)%M,设A为n阶对称矩阵,采用压缩存储存放于一维数组Fn(n+1)/2中(从F0开始存放),请分别给出存放上三角阵时任一矩阵元素aij的地址计算公式和存放下三角阵时任一矩阵元素aij的地址计算公式。,存放下三角阵时,任一矩阵元素aij(1in, 1ji) 的地址计算公式为:,存放上三角阵时,任一矩阵元素aij(1in,ijn) 的地址计算公式为:,作业2,写出矩阵三元组表,十字链表,作业2,十字链表,请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。,作业3
10、,已知二叉树的先序遍历序列是EABDCFHGIKJ,中序遍历序列是ABCDEFGHIJK,请构造二叉树,并写出其层次遍历序列和后序遍历序列。,层次:E A F B H D G I C K J 后序-C D B A G J K I H F E,森林转换成一棵二叉树,作业3,二叉树还原成森林,设二叉树的后序遍历序列为:DCFEBHJKIGA,中序序列为:CDBEFAHGJIK,请构造这棵二叉树。,作业3,二叉树的中序遍历序列为:DBHEIAFJKCG,层次遍历序列为:ABCDEFGHIJK,请画出该二叉树,作业3,假设用于通信的电文由7个字母组成A,B,C,D,E,F,G,字母在电文中出现的频率分
11、别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码,并计算其带权路径长度WPL,WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56 A:101 B:001 C:100 D:0001 E:11 F:0000 G:01,算法设计题 二叉树采用二叉链表存储,试设计算法实现: CreateBT(BiTree &T):从键盘输入二叉树的先序遍历序列字符串(以”#”代表空结点),建立其二叉链表; 如输入:AB#D#CE#F# 则建立如下图所示二叉树的二叉链表 ExchangeBT(BiTree
12、T): 设计递归算法实现二叉树中所有结点的左右孩子交换; CountLeaf(BiTree T, TElemType x, int &count): 统计以值为x的结点为根的子树中叶子结点的数目; DispBiTree(BiTree T, int level) : 按树状打印二叉树。,作业3,/输入先序序列,创建二叉树的二叉链表 void CreateBT(BiTree ,/交换二叉树中结点的左右孩子 void ExchangeBT(BiTree T) BiTree temp; if(T) temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; Exc
13、hangeBT(T-lchild); ExchangeBT(T-rchild); ,BiTree SearchTree(BiTree T,char X) BiTree bt; if(T) if(T-data=X) return T; bt=SearchTree(T-lchild,X); if(bt=NULL) bt=SearchTree(T-rchild,X); return bt; return NULL; ,void LeafCount (BiTree T, int ,/按树状打印输出二叉树的元素,level表示结点的层次 void DispBiTree(BiTree T,int leve
14、l) int i; if(T) DispBiTree(T-rchild, level + 1); for(i = 0; i data); DispBiTree(T-lchild, level + 1); ,打印得到: #C #F #E A #D #B,已知带权有向图如下, 要求: 画出图邻接矩阵; 给出图的一个拓扑有序序列; 求从顶点a出发到其余个顶点的最短路径,拓扑有序序列: a, b, d, f, e, c, g, h,作业4,无向图邻接表存储结构如图所示: 画出该无向图; 写出在该邻接表上,从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。,作业4,DFS:1,3,
15、4,7,8,6,5,2 BFS:1,3,2,4,7,6,5,8,对下标为19的有序表进行二分法查找, 画出折半查找的判定树; 计算其ASL; 比较4次查找成功的结点共有 个。,5,ASL=(1+2*2+3*4+4*2)/9=25/9,2,作业5,设有关键字序列25,40,33,47,12,66,72,87,94,22,5,58 散列表长为12,散列函数为h(key)=key%11,用线性探测再散列处理冲突,请画出散列表,在等概率情况下,求查找成功和查找失败的平均查找长度,ASL=(1*6+2+3*2+5+6+9)/12=34/12,作业5,94,12,66,25,33,47,22,72,40,
16、1,1,3,1,2,6,1,1,3,11,87,1,5,5,58,9,设有关键字序列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,94,12,66,25,33,47,22,72,40,1,1,3,1,2,5,1,1,3,11,87,1,5,4,58,3,ASL=(1*7+2*3+3*2)/12=19/12,66,33,0 1 2 3 4 5 6 7 8 9 10
17、 11 12,12,25,72,40,87,5,作业5,设有关键字序列25,40,33,47,12,66,72,87,94,22,5,58 散列表长为12,散列函数为h(key)=key%11,用线性探测再散列处理冲突,请画出散列表,在等概率情况下,求查找成功和查找失败的平均查找长度,已知待排序序列为50,86,72,41,45,93,57,46,请写出按下列排序方法进行升序排序时的第一趟排序结果:,第一趟直接插入排序:50,86,72,41,45,93,57,46 第一趟冒泡排序: 50,72,41,45,86,57,46,93 第一趟简单选择排序:41,86,72,50,45,93,57,46 堆排序初建堆序列 : 93,86,72,46,45,50,57,41 (大顶堆),作业5,第一趟直接插入排序:86,50,72,41,45,93,57,46 第一趟冒泡排序: 86,72,50,45,93,57,46,41 第一趟简单选择排序:93,86,72,41,45,50,57,46 堆排序初建堆序列 :41,45,57,46,50,93,72,86 (小顶堆),降序,
链接地址:https://www.31doc.com/p-2157180.html