1)了解数据元素、数据结构、抽象数据类型、存储结构等概念;了解算法概念及算法设计的基本要求 ;
2)掌握算法分析方法、语句的频度和估算时间复杂度、空间复杂度分析方法。
1.数据结构的研究内容
包括数据的逻辑结构、数据的存储结构和对数据元素施加的操作(即数据的运算)三方面。
五大特性:有穷性、确定性、可行性、输入性、输出性;
算法评价:正确性、可读性、健壮性、高效性、低存储性;
要特别弄清诸如语句频度、时间复杂度、空间复杂度等的概念,评价一个算法好坏的两个主要标准——时间复杂度和空间复杂度。
a. 程序不一定满足有穷性(如操作系统);
b. 程序中的指令必须是机器可执行的,算法中的指令则无此限制;
c. 算法代表了对问题的解,程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述,它才是一个程序);
d. 数据结构+算法=程序。
4.数据结构的相关概念
数据结构包括数据的逻辑结构和数据的存储结构。
数据元素是组成数据的基本单位。
数据项是数据不可分割的最小单位。
数据逻辑结构的两大类型(线性结构、非线性结构)、抽象数据类型(是指一个数学模型以及定义在该模型上的一组操作)。
数据的四种逻辑结构(集合、线性、树形、图形)
数据的四种存储结构(顺序、链式、索引、散列)
不管是顺序存储结构还是链式存储结构,都要存储数据元素本身和数据元素之间的关系
顺序存储结构、链式存储结构都可存各种逻辑结构
5.数据逻辑结构、存储结构的区别和联系
区别:数据的逻辑结构是一个数学模型;数据的存储结构是数据的逻辑结构在计算机内部的存储方式。
联系:一种逻辑结构可以用多种存储结构来存储;一种存储结构可以用来存多种逻辑结构。
1. 数据结构包括数据的逻辑结构、数据的存储结构和 数据的运算 。
2. 数据的逻辑结构可以分为 线性 和 非线性 两大类型。
3. 在算法正确的前提下,评价一个算法好坏的两个主要标准是 时间复杂度 和 空间复杂度 。
4. 对于给定的n个元素,可以构造出的逻辑结构有线性、树形 、 图形 和 集合 四种。
5. 数据的存储结构不仅有顺序存储结构、链式存储结构,还有 索引存储结构 和 散列存储结构 。
6. 组成数据的基本单位是 数据元素 。
7. 数据结构的两个要素是 数据元素 和 数据元素之间的关系 。
8. 语句频度是 语句重复执行的次数 。
9. 算法是 对特定问题求解步骤的一种描述,是指令的有限序列 。
10. 数值计算问题是 操作对象之间的关系可以用数学方程加以描述的问题 ;非数值计算问题是 操作对象之间的关系不能用数学方程加以描述的问题 。
11. 程序是 算法在计算机上的特定的实现 。
12. 抽象数据类型是 指一个数学模型以及定义在该模型上的一组操作 。
13. 学习数据结构课程的目的是 非数值计算问题的程序设计 。
14. 算法可用 自然语言、流程图、N-S图、计算机语言、伪码语言等 描述。
15. 存储密度是 一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比 。
1. 试说明算法与程序有哪些区别?
(1)程序不一定满足有穷性(如操作系统);
(2)程序中的指令必须是机器可执行的,算法中的指令则无此限制;
(3)算法代表了对问题的解,程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述,它才是一个程序);
(4)数据结构+算法=程序。
2. 举一个数据结构的例子,叙述其逻辑结构、存储结构和运算(操作)三方面的内容。
答:例如有一张学生成绩表,记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表,这个表就是一个数据结构。每个记录(有姓名、学号、成绩等项)就是一个结点,对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其它的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构——线性结构。
那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组存储,亦即顺序存储)还是随机存放各结点数据再用指针进行链接(链式存储)呢? 这就是存储结构的问题,我们都是从高级语言的层次来讨论这个问题的。
最后,我们有了这个表(数据结构),肯定要用它,那么就是要对这张表中的记录进行查询、修改、删除等操作,对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算(操作)问题了。
3. 什么叫算法效率?如何度量算法效率?
答:算法效率包括时间效率和空间效率。时间效率指算法运行得有多快;空间效率关心算法需要的额外空间。算法效率通常用时间复杂度和空间复杂度来度量。
4. 数据的逻辑结构与存储结构的区别和联系是什么?
答:区别:数据的逻辑结构是一个数学模型;数据的存储结构是数据的逻辑结构在计算机内部的存储方式。
联系:一种逻辑结构可以用多种存储结构来存储;一种存储结构可以用来存多种逻辑结构。
5. 算法有什么特性?评价一个算法有几个标准?
答:一个算法应该具有以下五个特性:
(1)有穷性。 一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成 (有限步完成)。
(2)确定性。算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口(无二义性)。
(3)可行性。一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的(每一步都可通过执行有限次基本操作实现)。
(4)输入性。一个算法有零个或多个输入,这些输入取自于某个特定的对象集合(有零个或多个输入)。
(5)输出性。一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量(有一个或多个输出)。
评价一个算法有以下几个标准:
(1) 正确性。算法应满足具体问题的需求。
(2) 可读性。 算法应该好读。以有利于阅读者对程序的理解。
(3) 健壮性。算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。
(4) 高效性。指算法执行的时间和执行过程中所需要的最大存储空间要少。一般,这两者与问题的规模有关。
1)理解线性表的定义和基本操作;线性表的抽象数据类型定义;
2)掌握线性表的顺序存储结构及应用方法;
3)掌握线性表的链式存储结构(单链表,双链表,循环链表)。
要求掌握线性表的顺序存储方式下的元素插入、元素删除及线性表遍历算法;要求掌握线性表的链式存储方式下,元素的插入、元素的删除及线性表遍历算法(带头结点及不带头结点的单链表)
1)理解栈的定义和基本操作及栈的抽象数据类型定义;
2)掌握顺序栈及链式栈的操作方法;
3)掌握栈在递归算法、 算术表达式求值及其它应用。
4)理解队列的定义和基本操作及队列的抽象数据类型;
5)掌握顺序队列的操作方法,了解链式队列的操作方法;
要求掌握栈的顺序存储和链式存储两种方式下入栈、出栈的算法;循环队列的顺序存储方式下,入队和出队算法。
1.栈和队列的概念、特点
如:栈和队列是特殊的线性表
栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。
同一栈内各元素的类型必须一致
栈是限定仅能在表尾一端进行插入、删除操作的线性表;
队列是限定仅能在表头进行删除、表尾进行插入的线性表;
队列的特点是先进先出。
若将1,2,3按先后次序入栈,出栈顺序不可能为3,1,2
在作进栈运算时应先判别栈是否已满,在作退栈运算时应先判别栈是否已空,当栈中元
素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为n。
2.顺序栈、链栈、循环队列、链队列
如循环队列解决什么问题?假溢出
循环队列队空、队满判断:
在少用一个存储单元的前提下
为了解决普通顺序存储结构队列的“假溢出”现象,节约内存单元,通过在队列操作中加入
数学中的求余运算,可以将其构造成循环队列;
在循环队列中,为了能够区分队满和队空,往往少用一个元素空间。在这种情况下,队满的
条件是尾指针+1等于头指针。
3.什么情况下要用栈?什么情况下要用队列?
如括号匹配、图的深度遍历等用栈实现。
二叉树的层次遍历、图的广度遍历等用队列实现。
例:解决计算机与打印机之间速度不匹配问题,须设置一个数据缓冲区,应是一个队列结构。
如设栈S和队列Q的初始状态均为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队序列为
5.对同一问题的求解程序,递归程序无论时间还是空间都不如非递归程序。
例:对同一问题的求解程序,递归程序比非递归程序要花费更多的时间;
任何一个递归过程都可以转换成非递归过程;
1. 为了解决普通顺序存储结构队列的“假溢出”现象,节约内存单元,通过在队列操作中 加入数学中的 求余 运算,可以将其构造成循环队列。 2. 解决计算机与打印机之间速度不匹配问题,须设置一个数据缓冲区,应是一个 队列 结构。 3. 循环队列是为了解决 假溢出
问题而将一个顺序表想像成一个首尾相接的顺序表。 4. 在循环队列中,如果其头指针为front,队列中元素个数为len,则该队列为空队的条件 5. 队列的插入操作在 队尾 进行。 6. 队列的删除操作在 队头 进行。 7.
一个栈的输入序列是:1,2,3 则不可能的栈输出序列是 3,1,2 。 8. 队列是限制插入只能在表的一端,而删除在表的另一端进行的线性表,其特点是 先进先出(或后进后出) 。 9.
队列的特点是 先进先出(或后进后出) 。 10. 队列 称作先进先出表。 11. 栈和队列是两种 操作受限制的 线性表。 12. 在作进栈运算时要判别栈是否 已满 。 13. 在作退栈运算时要先判别栈是否 已空 。 14.
在循环队列中,为了能够区分队满和队空,往往少用一个元素空间。在这种情况下,队 15. 栈的特点是 先进后出(或后进先出) 。 - 循环队列的优点是什么?如何判别循环队列的"空"或"满"?
答:循环队列的优点是:它可以克服顺序队列的"假上溢"现象,能够使存储队列的向量空间得到充分的利用。 判别循环队列的"空"或"满"通常有两种方法:
(1)另设一个变量num记录当前队列中的元素个数,当num==0时队空, num==maxsize时队满。 - 栈的特点是什么?队列的特点是什么? 答:栈的特点是先进后出,队列的特点是先进先出。 -
什么是递归?递归有什么优点? 答:一个直接调用自己或通过一系列调用间接调用自己的过程称为递归。 递归程序结构清晰,可读性强,而且容易用数学归纳法来证明程序的正确性。 - 什么是栈顶?什么是栈底? 答:允许插入和删除的一端是栈顶。 不允许插入和删除的一端是栈底。 - 出栈和读栈顶元素有无区别?若有,其区别是什么?
答:出栈和读栈顶元素有区别。在栈s存在且非空的情况下,出栈是将栈s的顶部元素从栈中删除,栈中少了一个元素,栈发生变化;读栈顶元素是读栈顶元素,栈不变化。 - 链栈和单链表有什么相同点和不同点? 答:链栈实际就是不带头结点的单链表。其结构完全一样,不同的是链栈只允许头插、头删,而单链表可在其它位置插入和删除。 -
链队列和单链表有什么相同点和不同点? 答:相同点:结点类型相同。 不同点:链队列只允许头删、尾插,而单链表可在其它位置插入和删除。 - 什么是顺序表?什么是顺序栈?两者之间有什么联系和区别?
答:线性表的顺序存储是指在内存中用地址连续的一块存储空间对线性表中的各元素按其逻辑顺序依次存放,用这种存储形式存储的线性表称为顺序表。利用顺序存储方式实现的栈称为顺序栈。顺序栈是顺序表的特殊情况,顺序栈只允许在栈顶插入和删除,而顺序表可在其它位置插入和删除。 -
设栈S和队列Q的初始状态均为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队序列为
e2,e4,e3,e6,e5,e1, 则栈S的容量至少为多少?写出其分析过程。 答:至少为3(分析过程略)。
1、利用栈实现表达式的转换(中缀转后缀,中缀赚前缀)
利用栈将中缀表达式转化成后缀表达式
目的:将中缀表达式(即标准形式的表达式)转换为后缀式。
1. 遇到操作数, 直接输出
2. 操作符的优先级为 () 最大, * / 次之, +- 最小. 遇到操作符后, 假如操作符堆栈为空, 则直接压入操作符, 否则判断当前操作符与栈顶操作符的优先关系, 假如栈顶操作符的优先级大于 等于当前操作符的优先级, 那么弹出栈顶操作符, 持续弹出, 直到栈顶操作符优先级小于当前操作符优先级或栈为空. 最后将当前操作符入栈
3. 如果遇到右括号, 那么将栈顶操作符弹出, 持续弹出直到遇到左括号, 左括号弹出但不输出
4. 表达式读入完毕, 若栈不为空, 则持续弹出栈顶操作符, 直到栈为空
建立一个栈来保存运算符,和一个字符容器存字符及运算符的输出。
从后向前扫描中缀表达式:
1、如果遇到的是普通字符那么存入容器中
2、如果遇到的是‘)’,存入容器中
3、如果遇到的是运算符(大于等于栈顶的优先级就入栈,否则弹栈)
如果当前栈为空或者当前运算符的优先级大于等于栈顶元素的优先级,那么入栈。
如果栈顶元素是‘)’,还是入栈。
如果当前运算符的优先级小于栈顶元素的优先级,那么弹栈存入容器中,一直到栈顶元素为‘)’或
者当前运算符的优先级大于或者等于栈顶元素的优先级。将当前运算符入栈。
4、如果遇到‘(’,那么弹栈存入容器一直遇到到‘)’,将‘)’弹出
5、返向输出容器中的字符
2、链栈进栈出栈代码实现
1)了解字符串的定义和基本操作及字符串的存储结构;
2)了解字符串的基本操作;
3)了解字符串模式匹配应用。
了解基本概念即可,不做重点处理,基本不会考,10年内没有考过
1)理解数组的定义和基本操作;
2)掌握数组的顺序存储结构及应用;
3)掌握特殊矩阵和稀疏矩阵的压缩存储。
具体要求:掌握三角矩阵的压缩存储方法和稀疏矩阵三元组法的压缩存储方法。
元素值 行下标 列下标
1)理解树的基本概念和基本操作,树的抽象数据类型。
2)理解二叉树的概念和性质,特殊二叉树及二叉树的存储结构;
3)掌握遍历二叉树:前序遍历,中序遍历,后序遍历,层次遍历。
4)掌握线索二叉树的概念和存储结构,二叉树的线索化的方法,线索二叉树的遍历方法。
5)理解树的存储结构;
6)掌握树与二叉树之间的转换,森林与二叉树之间的转换,森林的遍历方法。
7)掌握树的路径长度和带权路径长度的计算方法;
8)理解赫夫曼树(Huffman)的概念,并掌握哈夫曼算法, 哈夫曼编码树的构造方法。
掌握上述2)-8)基本概念相关的所有数据演示过程及相关计算,例如给定节点权值构造赫夫曼树、计算带权路径长度并给出赫夫曼树编码,给定二叉树构造出某种线索二叉树等等;
掌握二叉树的二叉链表存储方式下的先序、中序、后序遍历的算法、二叉树的叶子结点计数算法、节点计数的算法等。
当只有一个子树时,二叉树有序,树无序。 例 度不大于二的树不是二叉树。 2. 几种特殊形态的二叉树 满二叉树、完全二叉树、排序二叉树、的概念及区别。 例:完全二叉树不是最优的二叉树 注意:还有哈夫曼树、二叉判定树、二叉排序树、平衡二叉树等等。 顺序存储结构、二叉链存储结构、三叉链存储结构。
5.二叉树建立及其四种遍历方法 先、中、后序递归遍历及层次遍历,不仅要掌握遍历过程、会根据二叉树写出某种遍历结果,而且要会根据两种遍历结果(先序、中序或者中序、后序)画出二叉树。注意,给出先序和后序不能唯一地确定一棵二叉树。也即任意给出二叉树两种遍历结果不一定能把二叉树恢复出来。
例:已知一棵二叉树的先序遍历为cedba,中序遍历为debac,请画出该二叉树,并写出后序遍历结果 6. 线索二叉树(中序、先序、后序)概念 如写出二叉树结点个数、叶子结点个数、度为2的结点个数统计,二叉树深度计算,查找二叉树中结点(返回地址)算法(函数)等。
例:设二叉树的数据类型为结构体类型datatype,给出二叉链表存储二叉树的结点类型定义,并写出统计二叉树t中结点总数的算法。 第一种方法(使用全局变量): 第二种方法(不用全局变量):
8.哈夫曼树(最优二叉树)概念、总结点数(具有n个叶子结点的哈夫曼树有2n-1个结点)、构造、哈夫曼编码、WPL值计算
例:设给定一个权值集合W=(1,3,5,8,10,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL
假设用于通讯的电文由6个字母{A,B,C,D,E,F}组成,各字母在电文中出现的频率分别为7,19,5,6,32,3,试为这6个字母设计哈夫曼树并写出对应的哈夫曼编码。约定频率小的在左边,大的在右边。
9.树的存储结构、遍历(无中序)及树转化为二叉树 树的存储结构:双亲表示法、双亲孩子表示法、孩子-兄弟表示法; 树转化为二叉树后,相应的二叉树根结点无右子树;当以二叉链表作树的存储结构时,树的先根遍历可借用二叉树的先根遍历的算法实现,树的后根遍历可借用二叉树的中序遍历的算法实现等。 例:树是图的一种特殊情况; 对树而言,不合适的遍历是中序;
把任一棵树转化为二叉树,该二叉树的右子树必空; 森林F中有三棵树,节点数目分别为m1、m2、m3,与F对应的二叉树结构的根节点的右子树的节点数为m2+m3; 用孩子兄弟法存储树时,树的先序遍历结果与其对应的二叉树的先序遍历结果相同,树的后 序遍历结果与其对应的二叉树的中序遍历结果相同。
课后习题【二叉树部分】
1)理解图的基本概念和基本操作,图的抽象数据类型、有向图、无向图等概念。
2)掌握图的存储结构:数组表示法(邻接矩阵);邻接表,逆邻接表,十字链表;
3)掌握图的遍历:深度优先搜索法, 宽度优先搜索法, 求图的连通分量。
4)理解生成树、最小生成树的概念,并掌握克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法构造最小生成树的方法。
5)掌握从一个顶点到其余各顶点的最短路径。
掌握上面2)-5)相关的各算法的数据演示方法;
掌握在邻接矩阵存储方式下和邻接表方式下,图的深度优先搜索算法和图的广度优先搜索算法。
图和树的区别,四种图——有向图、无向图、有向网、无向网的区别;在一个具有n个顶点的无向完全图中,所含的边数为n*(n-1)/2,有n个顶点的强连通图最多有n(n-1)条边(有向边、弧),最少有n条边等。
2.图的邻接矩阵、邻接链表存储结构
如n个顶点e条边的无向图的邻接表的存储中,表头结点的个数是n,边结点的个数是2e;无向图的邻接矩阵具有对称性;带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中第i列非∞且非0的元素个数,顶点i的出度等于A中第i行非∞且非0的元素个数;从有向图中删除一条边<i,j>,其邻接矩阵第i行第j列要改为0;从无向图中删除一条边(i,j),其邻接矩阵的第i行第j列和第j行第i列都要改为0;已知一个有向图的邻接矩阵,要想删除所有以第i个顶点为起始点的弧,应该将邻接矩阵的第i行置零;设有向图G中有n个顶点和e条边,则其对应的邻接表中有e个边结点等。
深度和广度遍历,分别用栈和队列实现。 例:图的广度优先搜索利用队列实现; 图的深度优先搜索遍历算法要用栈来实现; 画出图邻接矩阵存储结构,并根据邻接矩阵写出从顶点A开始分别进行深度优先搜索遍历和广度优先搜索遍历的结果; 画出图的邻接链表存储结构,并写出根据该邻接链表从顶点A开始进行深度优先搜索和广度优先搜索遍历的结果。
4.最小生成树的概念及Prim和Kruskal两种方法生成最小生成树过程 最小生树不是边最少的生成树,而是所有n-1
条边的权值之和最小的生成树。若这个连通图有n个顶点,则它的生成树有n-1条边;如果含n个顶点的图形形成一个环,则它有n棵生成树;普里姆(Prim)算法适合于边稠密网;克鲁斯卡尔(Kruskal)算法适合于边稀少的网。图的最小生成树的形状可能不唯一。
不仅要会根据网图由Prim或Kruskal方法生成最小生成树,而且要会根据(V,E)(顶点集合V={1,2,3,…}和边集合E={(1
5,…}由Prim或Kruskal方法从某顶点开始构造生成最小生成树。Prim算法的时间复杂度为O(n2)。
迪杰斯特拉(Dijkstra)算法求最短路径的的基本思想是按路径长度(这里的路径长度指路径上边或者弧的权值之和)递增的次序产生最短路径,其时间复杂度为O(n2)。Floyd方法时间复杂度为O(n3)。要弄清求最短路径的过程。
1)理解排序的稳定性、比较关键字次数、移动记录次数等排序概念。
2)交换排序:冒泡排序,快速排序。
3)插入排序:直接插入排序,希尔排序。
4)选择排序:直接选择排序,堆排序。
6)掌握各种排序算法的特征评价,了解其应用。
掌握2)-5)各种排序方法的数据演示过程和特点、时间复杂度及空间复杂度;
掌握冒泡排序、直接插入排序、直接选择排序、快速排序的算法。
1、重点掌握各种排序方法(直插、折半插入、希尔、冒泡、快速、简选、堆排、二路归并, 基数排序了解)的排序过程及其特点(时间复杂度、稳定性、空间复杂度),尤其要弄清直插、冒泡、快速和堆排序。
2、如要知道排序按记录的次关键码进行,一般应选择稳定的排序方法;堆排序属于选择排序;在待排序的元素序列基本有序的前提下,效率最高的排序方法是直接插入排序和冒泡排序;直接插入排序、折半插入排序的效率与初始数据有关;快速、堆、冒泡、希尔排序算法中,空间复杂度最大的是快速排序;既稳定又省时间的排序算法是归并排序;冒泡排序在某一趟排序过程中若不存在交换就不需要下一趟排序了(就应退出循环)。会写直接插入排序、冒泡排序(升序或者降序,不特别指明为升序)等基本算法。给出一组数据,会写出初始堆(大顶堆或小顶堆,不特别指明为小顶堆)等。
例:稳定的排序方法是指在排序中,关键字值相等的不同记录间的前后相对位置保持不变;
直接选择排序是一种不稳定的排序方法。
3、设有1000个无序的数据元素,希望用最快的速度找到前10个最大元素,最好选用堆排序;
4、在已知待排序文件已基本有序的前提下,效率最高的排序方法是直接插入排序;
5、若排序按记录的次关键码进行,一般应选择稳定的排序方法;
6、希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中,要求辅助空间最多的是二路归并;
7、若需要在O(nlogn)的时间内完成对一组数的排序,且要求排序是稳定的,则可选择的排序方法是归并排序。
8、对n个元素采取冒泡排序,最少的比较次数是n-1;
9、用堆排序实现升序排列时,建立的初始堆必须是大顶堆;
10、对于一组给定的关键字{49,38,27,15,94,53},写出以第一个关键字作为基准元素运用快速排序方法进行升序排序时第一次划分的结果,如果要实现排序,共需进行几次划分;
1. 稳定的排序方法是指在排序中,关键字值相等的不同记录间的前后相对位置 不变 。 2. 希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中,要求辅助空间最多的是 二路归并排序 。 3. 分别采用堆、快速、插入、归并排序法对初始状态为递增序列的表按递增顺序排序,最费时的是 快速
算法。 4. 在直接插入、冒泡、快速排序和简单选择排序方法中,平均时间复杂度最低的排序方法是 快速排序 。 6. 具有12个记录的序列,采用冒泡排序最少的比较次数是 11 。 7.
设有1000个无序元素,希望用较快速度挑选出其中前10个最大元素,在快速排序,堆排序,基数排序,直接插入,归并排序这些方法中,采用 堆排序 方法最好。 8. 外排序的基本方法是 归并 。 9. 快速排序的最坏情况,其待排序的初始排列是 已经按其排序码从小到大排好序 。
10. 分别采用堆、快速、插入、归并排序法对初始状态为递增序列的表按递增顺序排序,最费时的是 快速 算法。 11. 对n个元素按某关键字用堆排序方法由小到大排序,应使用 大 顶堆。 12. 内排序指待排序列 在内存中 所进行的排序。 13. 外排序指排序过程中需访问 外存 的排序。
14. 在直接插入、冒泡、快速排序和简单选择排序方法中,具有稳定性的排序方法有 直接插入、冒泡 。 15. 在冒泡、快速、直接插入三种排序方法中,排序的趟数与数据表的初始排列顺序无关的是 直接插入 排序方法。 16. 当数据表初态基本有序的情况下,在冒泡、快速和简单选择排序方法中应选择 冒泡
排序方法,从而使得排序的趟数最少。 1. 对于一组给定的关键字{49,38,27,15,94,53},写出以第一个关键字作为基准元素
运用快速排序方法进行升序排序时第一次划分的结果,如果要实现排序,共需进行几次划分 要实现排序,共需进行4次划分。 2. 什么是排序算法的稳定性?举出一个稳定的排序算法和不稳定的排序算法的例子。
答:排序算法的稳定性是指待排序范围中多个关键字值相同的记录,使用某种排序算法进行排序后其相对次序与排序前相比没有改变。冒泡排序算法只进行元素间的顺序移动,所以是一个稳定的排序方法,而快速排序就是一种不稳定的排序方法(可用3,2,2'序列来验证)。
3. 对于一组给定的关键字{49,38,27,15,94,53,81},写出用冒泡排序法进行升序排列的各趟结果。
设一组初始记录关键字序列为(19,21,16,5,18,23),要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。
对于一组给定的关键字序列{58,12,33,20,65,77},分别写出用冒泡排序法和快速排序法进行升序排列的各趟结果。
6. 对于给定的一组数据:3、6、1、2、4、5,请分别写出直接插入排序和快速排序的各趟 直接插入排序各趟结果: 7.
对于一组给定的关键字序列{58,12,33,20,65,77},分别写出用冒泡排序法和简单选择排
序法进行升序排列的各趟结果。 简单选择排序各趟结果: 8.
对于一组给定的关键字{53,87,12,61,35,48},写出分别用直接插入法和简单选择法进行升序排列的各趟结果
直接插入排序各趟结果: 简单选择排序各趟结果: 9.
对于一组给定的关键字{53,87,12,61,35,48},写出分别用冒泡排序法和直接插入排序法
进行升序排列的各趟结果 直接插入排序各趟结果: 10.
对于一组给定的关键字{53,87,12,61,35,48},写出分别用冒泡排序法和直接插入排序法
进行降序排列的各趟结果。 直接插入排序各趟结果: 进行降序排列的各趟结果。 13.
对于一组给定的关键字序列{45,19,81,58,12},分别写出用直接插入排序法和快速排序
法进行降序排列的各趟结果 直接插入排序各趟结果: 14.
对于一组给定的关键字序列{45,19,81,58,12},分别写出用直接插入排序法和快速排序法进行降序排列的各趟结果
直接插入排序各趟结果: 15.
对于一组给定的关键字序列{45,19,81,58,12},分别写出用直接插入排序法和快速排序法进行升序排列的各趟结果。
直接插入排序各趟结果:
1)理解查找的概念,关键字比较次数,平均查找长度。
2)掌握顺序表的查找:顺序查找,折半查找。
3)掌握树表的查找:二叉排序树,二叉排序树的的概念和基本操作,二叉排序树的建立,二叉排序树其它操作实现;掌握平衡二叉树的概念。
4)掌握哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找方法,开放地址法及链地址法冲突处理方法及平均查找长度的计算方法。
掌握上述2)-4)相关的数据演示过程及平均查找长度的计算方法;
掌握在顺序存储的线性表上实施顺序查找和有序顺序表上实施折半查找的算法;掌握在二叉排序树中查找指定关键字的递归算法和非递归算法;掌握hash查找算法。
1. 三种查找方法及其区别、比较
顺序查找 折半查找 分块查找
存储结构 顺序、链式 顺序 索引存储
有序性 有序、无序 有序 按块有序
如顺序查找平均比较次数等
2.使用折半查找前提、折半查找算法及其判定树
例:折半查找只能在有序的顺序表上进行;
画出描述n=8(具有8个元素)的折半查找(即二分查找)过程判定树,并计算查找成功时的平均查找长度ASL(假定查找每个元素的概率相等);
对于一个具有100个元素的有序表,要用二分查找(即折半查找)查找某个元素,最多需要比较7 次。
折半查找其判定树应用,如有1000个元素最多比较多少次(10次)。
3. 排序二叉树(又称二叉排序树)的概念及其构造(插入)、查找、输出、删除某节点(还要保证其性质)
例:如果在一棵二叉树中,每个结点的值都大于它的左子树上所有结点的值,而小于它的右子树上所有结点的值,这样的一棵二叉树称为排序二叉树(或二叉排序树)
依次输入关键字{50,28,73,91,56,18,34,86},画出所生成的二叉排序树,并写出其中序遍历序列。
4. 哈希表构造及哈希查找过程
掌握常用哈希函数——直接定址法和除留余数法,常用处理冲突方法——线性探测法、二次探测法和拉链法及ASL计算。
例:在哈希函数H(k) = k % m(“%” 表示求余)中,一般来讲,m应取质数(素数);
设一组初始记录关键字集合为(25,10,8,27,32,68),哈希表地址区间为0~7,哈希函数H(k)=k mod 7,用线性探测再散列作为解决冲突的方法设计哈希表,将其内容填入下表(表1),并计算查找成功时的平均查找长度ASL;
5.静态查找与动态查找的区别
静态查找表与动态查找表的根本区别在于施加在其上的操作不一样
1. 折半查找(即二分查找)只能在 有序的顺序表 上进行。 2. 设有序查找表中有13个元素。采用折半查找方法进行查找,查找成功时最少比较 1 次,最多比较 4 次。 3.
如果在一棵二叉树中,每个结点的值都大于它的左子树上所有结点的值,而小于它的右子 树上所有结点的值,这样的一棵二叉树称为 二叉排序树 。 6. 已知一棵二叉排序树,通过 中序遍历 ,可得到结点的有序序列。 7. 设一哈希表表长M为100
,用除留余数法构造哈希函数,即H(K)=K MOD P(P<=M), 为使函数具有较好性能,P应选 质数 。 8. 不包括对数据元素的插入和删除操作的查找称为 静态 查找。 9.
包括对数据元素的插入和删除操作的查找称为 动态 查找 10. 分块查找的前提是 块间有序 。 11. 根据元素的关键码确定元素存储位置的存储方式叫 散列 存储。 12. 在哈希查找中,元素关键字值与其在哈希表中存放位置的对应关系称为 哈希函数 。 13.
在哈希查找中,不同关键字值对应到同一哈希地址上的现象称为 冲突 。 比较的次数是 3 次。 15. 在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关,最好的情况是二叉排序树为 平衡二叉树 树的时候。
全国排名: 学校代码:
专业数量:15 学校官网:/
随着网络的普及,基于分布式环境的应用系统已成为当前应用软件的中坚力量。但在分布式环境下,由于系统的运行效率依赖于各服务器的配置和网络状况,即使在目前计算机硬件性能和网络传输速度不断提高的情况下,软件的运行效率还是不能满足用户在性能上的要求。为了解决该问题,目前主要采取提高物理服务器配置、增大网络带宽等方式来提升分布式应用系统的运行效率,但此方式会不断增加企业成本。其实,在网络环境一定的情况下,网络中的流量是影响分布式环境下软件运行效率的关键。为此,本论文从软件自身的结构着手,研究了降低网络流量和提高软件运行效率的方法。主要研究内容如下: (1)研究分布式应用系统、软件框架的相关内容。以广泛使用的三层软件框架为研究对象,剖析了其中影响网络流量的关键成分,发现在业务逻辑层进行数据处理的过程中,会在应用服务器和数据库服务器之间传递大量的中间结果或SQL语句,从而占据大量网络带宽,降低了系统的运行效率。 (2)给出一种新的分布式应用软件框架。论述了新框架的组成结构、工作机理及各部分的设计。新框架以传统三层结构为基础,将业务逻辑层分为业务流转层和数据处理层,在业务流转层中以工作流的形式对业务流程进行编排,实现了不相关活动的并发执行;将数据处理层中的各模块利用公共语言运行时下移到DBMS中,一方面大幅降低了网络流量,另一方面使系统能够利用各数据库服务器的资源,以并行的方式完成各数据处理任务;在以上两层之间加入接口描述层以实现二者的松散耦合。论文还详细叙述了不相关活动并发执行的方法、代码下移的具体策略以及以多线程调用多数据库服务器并行处理的方法。 (3)详细描述了新框架在系统开发中的具体应用。以工时管理信息系统中的分工表展开模块为例,详细阐述了在新软件框架下业务的并发流转、代码下移和以多线程调度多数据库服务器并行处理的具体实现。在展开6万条分工表数据的实验中,新框架将网络数据传输量由28.41MB降低至0.59KB;在双数据库服务器环境下,并行展开2万条分工数据的平均时间是串行展开时间的0.52倍。 研究分析和实验表明,新框架在大幅降低网络带宽占用量、增强系统负载平衡能力、提高应用系统的运行效率等方面独具特色,对网络环境下分布式应用系统的开发具有普遍适用性。