数据结构与算法PPT

PPT 内容
PPT 图集

1. 数据结构与算法
2. 目录页第2页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
3. 知识结构知识结构第3页计算机世界的研究问题：建模+算法+实现数据结构的研究视角：（1）数据的逻辑结构和物理结构；（2）基于特定结构的通用操作描述。抽象数据类型：数据+数据间联系+数据上的操作集合
4. 大礼包大礼包第4页不属于考核范围的内容： Chapter 2： 2.5、 2.6 Chapter 3： 3.3 Chapter 6： 6.2 Chapter 7： 7.4、7.5、7.6 Chapter 9： 9.5.2、9.6、9.7 Chapter 10
5. 内容温习Chapter1 知识点第5页数据结构数据+关系：前驱、后继数据逻辑结构：（线性结构+非线性结构）线性、树型、集合、图数据存储结构顺序、链接、散列、索引算法及其分析输入+输出+步骤算法性能评价：时间复杂度 + 空间复杂度 O()
6. 温故知新Chapter1 测试一下第6页数据结构在计算机内存中的表示是（） A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系为规模n的问题设计了一个算法，其中最频繁操作的执行次数是n的函数： f(n)=3n3+100n2+9n+10000，则该算法的时间复杂度是多少。
7. 内容温习Chapter2 知识点第7页逻辑结构视角线性表：（直接）前驱、（直接）后继抽象数据类型：插入操作、删除操作物理结构视角顺序表数据元素存储地址的计算顺序存储的线性表，插入或删除一个元素，平均移动多少个元素？链接表（插入+删除）结点结构：数据域 + 指针域单链表双向链表循环链表问题分析1：链表中头结点的用途？判定带头结点的单链表是空表的条件？问题分析2：顺序表和链接表的优缺点对比
8. 温故知新Chapter2 测试一下第8页请分析下面代码段的功能。 typedef struct Node{ Elemtype data; Struct Node *next; } Node; int count ( Node *list, ElemType x) { int i=0; Node *p=list; while(p!=NULL) { if (p->data = = x) i++; p=p->next; } return i; }
9. 温故知新Chapter2 测试一下第9页2. 请分别给出删除结点b和结点c的操作1. 请分别给出删除结点c和插入结点x的操作
10. 温故知新Chapter2 测试一下第10页P168 16 list1和list2分别是两个带有头结点的有序（升序）单向链表的头指针，请写出将两个有序链表合并为一个有序链表（升序）的算法。（要求在原表基础上合并）
11. 温故知新Chapter2 测试一下第11页P168 16//升序合并为升序 PList mergeList(PList list1, PList list2) { PList p1=list1, p2=list2, head=NULL, tail=NULL, temp; if(p1->value<p2->value) { head=p1; tail=p1; p1=p1->next; tail->next=NULL; } else { head=p2; tail=p2; p2=p2->next; tail->next=NULL; } while((p1!=NULL)&&(p2!=NULL)) { if(p1->value>p2->value) { temp=p2->next; tail->next=p2; tail=p2; tail->next=NULL; p2=temp; } else { temp=p1->next; tail->next=p1; tail=p1; tail->next=NULL; p1=temp; } } if(p1!=NULL) tail->next=p1; if(p2!=NULL) tail->next=p2; return head; }请问升序转降序如何实现？
12. 内容温习Chapter3 知识点第12页字符串是一种线性表，可以采用顺序存储结构和链式存储结构。其与普通线性表的区别在于：表中的每个元素是一个字符。两个字符串相等的充要条件是：两个字符串的长度相等 + 两个字符串中对应位置上的字符相同
13. 内容温习Chapter4 知识点第13页栈特点：FILO；栈顶、出栈、入栈；顺序栈和链栈；栈在递归中的作用；队列特点：FIFO；队头、队尾、出队列、入队列；队列的顺序存储实现和链接存储实现；循环队列：假溢出；队列满和空的条件；栈和队列的综合应用
14. 温故知新Chapter4 测试一下第14页若已知一个栈的入栈序列是1, 2, 3, …, n，其输出序列是p1, p2, p3, …, pn，若p1=n，则pi是（） A. 1 B. n-1 C. n-i+1 D. 不确定
15. 温故知新Chapter4 测试一下第15页下图描述的队列（1）如何在队列中进行删除操作；（2）如何插入current指向的结点。
16. 温故知新Chapter4 测试一下第16页循环单链表，head和tail分别是头指针和尾指针。 1. 请给出该循环单链表的定义 2. 若将其作为一个栈，如何实现入栈和出栈操作 3. 若将其作为一个队列，如何实现入队列和出队列操作
17. 温故知新Chapter4 测试一下第17页采用循环单链表作为队列，只有尾指针tail的三种状态。
18. 温故知新Chapter4 测试一下第18页采用循环单链表作为队列，只有尾指针tail的三种状态。typedef struct QueueElement{ int value; struct QueueElement *next; }QueueElement; typedef QueueElement *PQueue; PQueue initQueue() { PQueue queueTail; queueTail=(PQueue)malloc(sizeof(QueueElement)); queueTail->value=-1; queueTail->next=queueTail; return queueTail; }PQueue insertElement(PQueue queueTail, int v) { QueueElement *q=(QueueElement *)malloc(sizeof(QueueElement)); q->value=v; q->next=queueTail->next; queueTail->next=q; queueTail=q; return queueTail; } 请问删除操作如何实现？
19. 内容温习Chapter5 知识点第19页二叉树的基本术语根结点、树叶、分支结点父结点、孩子结点、兄弟结点路径、路径长度结点的层数（根结点的层数为0）、树的高度结点的度、树的度二叉树是一棵有序树只有三个结点的二叉树有多少种不同形态完全二叉树、满二叉树及其性质父结点和孩子结点编号的对应关系二叉树中度为0的结点和度为2的结点之间的关系深度k的二叉树最少（多）有多少个结点扩充二叉树
20. 内容温习Chapter5 知识点第20页二叉树的存储结构顺序存储：适合完全二叉树二叉链表三叉树表二叉树的遍历（周游）深度优先周游：先序、中序、后序遍历广度优先周游线索二叉树：二叉树结点的左右指针赋予了新的含义采用二叉链表存储，n个结点的空指针数目是多少。哈夫曼树（最优二叉树）前缀编码最优（短）编码如何构造哈夫曼树和计算WPL
21. 内容温习Chapter5 知识点第21页树及其遍历深度优先遍历、广度优先遍历树、树林与二叉树的相互转换
22. 温故知新Chapter5 测试一下第22页下列编码中属前缀码的是( ) （A）{1,01,000,001} （B）{1,01,011,010} （C）{0,10,110,11} （D）{0,1,00,11} 一棵深度为6的满二叉树有___________个分支结点和___________个叶子结点。设一棵完全二叉树有700个结点，则共有__________个叶子结点。某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（） A. 3 B. 2 C. 4 D. 5
23. 温故知新Chapter5 测试一下第23页P168 13 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，请问该树中有多少个叶子结点？
24. 温故知新Chapter 5 测试一下第24页P169 算法题 1 采用二叉链表存储二叉树，请写一个算法，统计二叉树中结点值在20到50之间的叶子结点的数目。int countNode(PBinTree root) { if(root==NULL) return 0; if((root->lchild==NULL)&&(root->rchild==NULL) &&(root->value>20)&&(root->value<50)) return 1; return countNode(root->lchild)+countNode(root->rchild); }
25. 内容温习Chapter6 知识点第25页集合与字典的基本概念查找操作与（等概率）平均查找长度字典的顺序存储结构（有序顺序表）二分检索法字典的散列表示散列函数、负载因子散列冲突：（同义词）碰撞、（非同义词）堆积解决散列冲突的方法开地址法：线性探测法拉链法散列表的构造和平均查找长度计算
26. 温故知新Chapter6 测试一下第26页设散列表容量为8（散列地址空间0..7），给定字典的关键字序列（30，36，47，52，34，40），散列函数H(k) = k mod 7，分别采用线性探查法和拉链法解决冲突，要求：（1）构造散列表；（2）等概率情况下查找成功时的平均查找长度ASL。有序表为{16，40，82，105，132，246，285，362，375，390，882，995，1008}，当二分查找值为82和395的结点时，查找的次数分别是多少？
27. 内容温习Chapter7 知识点第27页索引：提高查找速度二叉排序树基于二叉排序树的查找二叉排序树的插入、删除二叉排序树的中序遍历具有什么特征最佳二叉排序树、平衡二叉排序树（平衡因子）的基本概念 B树、B+树的基本定义和结构
28. 温故知新Chapter 7 测试一下第28页P248 复习题7 已知元素个数为12的字典，其元素集合为{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}，按元素的次序依次插入一棵初始时为空的二叉排序树，请：（1）画出插入完成之后的二叉排序树；（2）等概率下的平均检索长度ASL；（3）画出删除Mar之后的二叉排序树。
29. 内容温习Chapter8 知识点第29页插入排序直接插入排序、二分插入排序、希尔排序选择排序直接选择排序堆：构造大（小）根堆、筛选交换排序冒泡排序、快速排序分配排序基数排序归并排序各算法的平均时间复杂度，最好（坏）情况时间复杂度
30. 温故知新Chapter8 测试一下第30页设一组初始记录关键字序列（15, 22, 6, 13, 8，5，32，4，56），分别以每个区间第一个记录关键字为基准进行快速排序，请给出每一趟的排序结果。
31. 温故知新Chapter 8 测试一下第31页P285 算法题3 设计一个有效的算法，在1000个无序的元素中，挑选出其中前5个最大的元素。堆排序的实现算法。考核点：堆排序的实现算法
32. 温故知新第32页P285 算法题3 void griddle(Heap heap, int index, int bound) { int lchild=2*index+1; int rchild=2*index+2; while((lchild<=bound)||(rchild<=bound)) { int maxKeyIndex=index; if((lchild<=bound)&&(heap.pvector[maxKeyIndex].key<heap.pvector[lchild].key)) maxKeyIndex=lchild; if((rchild<=bound)&&(heap.pvector[maxKeyIndex].key<heap.pvector[rchild].key)) maxKeyIndex=rchild; if(maxKeyIndex==index) return; Record temp=heap.pvector[maxKeyIndex]; heap.pvector[maxKeyIndex]=heap.pvector[index]; heap.pvector[index]=temp; lchild=2*maxKeyIndex+1; rchild=2*maxKeyIndex+2; index=maxKeyIndex; } } Chapter 8 测试一下
33. 温故知新第33页P285 算法题3 void createHeap(Heap heap) { for(int i=heap.n-1;i>=0;i--) griddle(heap, i, heap.n-1); } void sortByHeap(Heap heap) { for(int i=heap.n-1;i>0;i--) { Record temp=heap.pvector[i]; heap.pvector[i]=heap.pvector[0]; heap.pvector[0]=temp; griddle(heap, 0, i-1); } } Chapter 8 测试一下
34. 温故知新第34页P285 算法题3 void find5MaxKey(Heap heap) { for(int i=heap.n-1;i>=heap.n-5;i- -) { Record temp=heap.pvector[i]; heap.pvector[i]=heap.pvector[0]; heap.pvector[0]=temp; griddle(heap, 0, i-1); } for(int i=heap.n-5;i<heap.n;i++) printf("%d ",heap.pvector[i].key); }Chapter 8 测试一下
35. 温故知新第35页P285 算法题5 试设计一个算法，在尽可能少的时间内重排数组，将所有取负值的排序码放在所有取非负值的排序码之前。考核点：快速排序的实现算法 int dividByFirstElement(int a[], int i, int j) { int temp=a[i]; while(i<j) { while((i<j)&&(a[j]>temp)) j- -; if(i<j) a[i++]=a[j]; while((i<j)&&(a[i]<=temp)) i++; if(i<j) a[j--]=a[i]; } a[i]=temp; return i; }void quickSort(int a[], int i, int j) { int m=dividByFirstElement(a, i, j); if(i<m-1) quickSort(a, i, m-1); if(m+1<j) quickSort(a, m+1, j); } Chapter 8 测试一下
36. 温故知新第36页P285 算法题5 //key为指定的分割点（即选取的基准关键字） void splitByZero(int a[], int i, int j, int key) { while(i<j) { while((i<j)&&(a[j]>key)) j--; while((i<j)&&(a[i]<=key)) i++; if(i<j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; i++; j--; } } }Chapter 8 测试一下
37. 内容温习Chapter9 知识点第37页图的定义及相关术语有向图、无向图顶点的度简单路径连通图、连通分量完全图：n个结点的无向完全图和有向完全图各有多少条边网络（带权的连通图）图的存储结构邻接矩阵：无向图对应邻接矩阵的特点邻接表、逆邻接表
38. 主标题Chapter9 知识点第38页图的周游深度优先周游广度优先周游最小生成树克鲁斯卡尔算法普里姆算法最短路径的概念拓扑排序与关键路径的相关概念 AOV网与AOE网
39. 温故知新Chapter9 测试一下第39页具有n个结点的连通图至少有（）条边。 A. n-1 B. n C. n(n-1)/2 D. 2n
40. 目录页这里填写二级标题第40页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
41. 关于考试试题类型第41页应用题占50%算法与程序设计占20%填空题　　　　　　占10%选择题　　　　　　占20%
42. 关于考试考试时间与地点第42页考试时间壹数据结构与算法： 20周周二 15：00～17：00考试地点贰17312Nothing叁
43. 休息一下休息一下第43页
44. 目录页目录页第44页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
45. 温故知新测试与训练第45页设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。 A. 快速排序 B. 堆排序 C. 归并排序 .D 插入排序有8个结点的无向图最多有（）边。 14 B. 28 C. 56 D. 112 设栈S和队列Q的初始状态为空，元素a，b，c，d ，e，f依次进栈，一个元素出栈后即进入队列Q。如果6个元素出队列的顺序是b,d,c,f,e,a，则栈S的容量至少应该是。现有存储n个元素的一维数组，则（1）读取数组中第i个元素的平均时间复杂度是多少；（2）查找数组中元素x的平均时间复杂度是多少。
46. 温故知新测试与训练第46页有一份电文中共使用7个字符：a、b、c、d、e、f、g，它们的出现频率依次为4，5，6，12，8,10,18。要求：（1）试画出对应的哈夫曼树；（2）每个字符的哈夫曼编码；（3）求带权外部路径长度(WPL)。
47. 温故知新测试与训练第47页一组记录的关键字集合如下：{70, 67, 75, 61, 86, 69}，请给出采用直接插入排序法对该序列进行升序排序时每一趟的结果，其时间复杂度是多少？给定一组关键字，4，2，58，3，6，10，14，请构造一棵小根堆。构造大根堆呢？
48. 温故知新测试与训练第48页已知一个图的顶点集V和边集E分别为：　V={1, 2, 3, 4, 5, 6, 7, 8}; E={(1,2,19), (1,3,8), (2,4,12), (2,5,30),(3,4,8), (3,6,6), (3,7,5),(4,6,9), (4,8,12), (5,8,10), (6,8,5), (7,8,4)}; （1）分别给出该图的邻接矩阵、邻接表、逆邻接表表示；（2）给出从1号顶点出发按深度优先搜索遍历的顶点序列；（3）给出从1号顶点出发按广度优先搜索遍历的顶点序列；（4）采用PRIM算法，从1号顶点出发，构造该图的最小生成树。
49. 温故知新测试与训练第49页某无向图G采用如图1所示的邻接表存储，则从顶点A开始的深度优先遍历序列为；从顶点A开始的广度优先遍历序列为。
50. 课后习题测试与训练第50页P168 8 已知二叉树的先根周游序列为ABDEGCFHIJ，对称序周游序列为DBGEAHFIJC，请给出该二叉树的后根周游序列。 P167 3 请将下图所示的二叉树转换成树林。
51. 主标题测试与训练第51页P168 14 根据下图，（1）给出图的先根、中根和后根遍历序列（2）将其转换为二叉树
52. 主标题测试与训练第52页P327 7 根据下图 1. 请给出该图的邻接表表示（顶点表+出边表（出边表结点））； 2.以顶点v0为起点的深度优先周游序列及对应的生成树； 3.以顶点v0为起点的广度优先周游序列及对应的生成树； 4. 以v0为原点，采用Dijstra算法到其它各顶点的最短路径。
53. 温故知新测试与训练第53页建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,……,n，要求创建过程中的结点的数据域依次为n, n-1, ……, 2, 1。/* 单链表结点的定义 */ typedef struct Node{ int data; struct Node *next; } Node; Node *create(n) { Node *head , *p; int i; p=(Node *)malloc(sizeof(Node)); head= ; pnext=NULL; for(i=n; i>=1; i--) { p= ; p->data=i; p->next= ; ; } return(head); }
54. 目录页这里填写二级标题第54页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
55. 答疑及其它答疑时间与地点第55页All teachers’ time19周周三下午 14：00～16：005教505 软件工程系办公室
56. 答疑及其它Your time第56页Pay AttentionWelcome any question.
57. 感谢大家对这门课程的参与祝大家考试顺利!

下载需要 10 香币 [ 香币充值 ]

亲，您也可以通过分享原创文档来获得香币奖励！

服务器/托管费、人工审核、技术维护等都需要很多费用，请您支持香当网的发展

下载PPT

数据结构与算法PPT

该用户的其他文档

相关PPT

相关文档