概论
 
 
 
 
名词解释:
 
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和组织数据的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作.
 
数据项:是数据不可分割的最小单位,用它可以识别一个或一组数据,一个数据元素可由若干数据项组成.
 
数据元素(记录):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理,一个数据元素可由若干数据项组成.
 
数据对象:是性质相同的数据元素的集合,是数据的一个子集.
 
数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称,是计算机化的信息.
 
数据类型:是一个值的集合以及定义在这个值集上的一组操作,可分为原子类型和结构类型.
 
抽象数据类型:是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作.
 
逻辑结构:是数据元素之间逻辑关系的描述.
 
物理结构(存储结构):是指数据的逻辑结构在计算机中的映像(又称表示),即数据结构在计算机中的存储方法.
 
算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作.
 
时间复杂度:算法执行所需时间的量度.
 
空间复杂度:算法执行所需存储空间的量度.
 
存储密度:指结点数据本身所占存储量和整个结构所占存储量之比.
 
填空题:
 
程序设计的一些基本原则:分解.抽象和信息隐蔽.
 
根据数据元素之间关系的不同特性,有四类基本的数据结构:集合结构,线性结构,树型结构,图形结构(网状结构).
 
数据的存储结构有:顺序存储结构.链式(链接)存储结构.索引存储结构,散列存储结构.常用的两种存储结构:顺序存储结构和链式存储结构.
 
算法的五个特性:确定性.有穷性.可行性.输入和输出.(可以有零个或多个数据输入,但必须至少有一个输出数据)
 
算法设计的要求:正确性,可读性,稳健性,高效率低存储量.
 
沃思公式:程序=算法+数据结构.
 
(算法分析)衡量算法的两个标准:时间复杂度和空间复杂度.
 
一个算法的设计取决于所选的逻辑结构.
 
一个算法的实现取决于所选的存储结构.
 
结构化程序设计思想的要求:自顶向下.逐步细化.模块化设计.结构化编程.
 
简答题:
 
顺序存储结构的特点?(顺序存储和链式存储的优缺点)
 
1.结点中只存放数据元素本身的信息,无附加内容.
 
2.可直接存取数据元素.
 
3.存取操作速度较快.
 
4.插入.删除数据元素时,由于需要保持数据元素之间的逻辑关系,必须大量移动元素,因此实现起来较慢.
 
5.顺序存储是一种静态结构,存储密度大,空间利用率低,预分配空间大小难以确定.
 
链式存储结构的特点?(顺序存储和链式存储的优缺点)
 
1.结点中除存放数据元素本身的信息外,还需存放附加的指针.
 
2.不能直接存取数据元素,需顺链查找,存取速度较慢.
 
3.插入.删除元素时不必移动其他元素,速度较快.
 
4.链式存储是一种动态存储结构,空间利用率高,存储密度小,不存在预分配空间问题.
 
线性结构与非线性结构的特点(或差异)?
 
线性结构的特点是:除第一个元素和最后一个元素外,每个数据元素都有唯一的前驱和唯一的后继,第一个元素没有前驱,最后一个元素没有后继,关系是一对一的.
 
非线性结构的特点是:表示结点间关系的前驱后继不具有唯一性,结点间是一对多或多对多的关系.
 
逻辑结构与物理结构的区别和联系?
 
1.数据的物理结构也称为存储结构.
 
2.数据的逻辑结构仅考虑数据之间的逻辑关系.
 
3.数据的物理结构是数据的逻辑结构在计算机中的映像.
 
4.数据的逻辑结构独立于数据的存储介质.
 
数据结构与数据类型的区别和联系?
 
数据结构是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和组织数据的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作.它偏向于逻辑方面,而数据类型是一个值的集合以及定义在这个值集上的一组操作,可分为原子类型和结构类型.它偏向于物理方面.
 
线性表
 
 
名词解释:
 
线性表:是最常用,最简单的一种数据结构,一个线性表是n个数据元素的有限序列,除首尾元素外,每个元素有唯一的前驱和唯一的后继.
 
顺序表:采用顺序存储结构的线性表通常称为顺序表.
 
链表:采用链式存储结构的线性表通常称为链表.
 
结点:由数据元素和指示其后继结点地址的信息组成的存储映像称为结点.
 
表长:表中元素的个数称为表的表长.
 
循环链表:是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环.
 
双链表:采用链式存储结构的线性表,每个结点除一个数据域外,还有两个指针域,其一指向直接前驱,另一指向直接后继.
 
静态单链表:是利用一块连续的空间,按链表的存储方式组织数据,按顺序存储结构分配空间,所构成的一种链表.
 
头指针:是指向链表表头结点的指针,只要链表存在,该指针始终不会改变,单链表由头指针唯一确定,因此单链表可以用头指针的名字来命名.
 
头结点:在链表的开始结点之前附加的一个结点,是链表的表头,当链表不空时,其内的指针指向链表的第一个结点,当链表是空链表是,该指针为空指针.
 
填空题:
 
线性表的两种基本的存储结构:顺序存储结构和链式存储结构.
 
从实现角度看,链表可分为静态链表和动态链表.
 
从链接方式的角度看,链表可分为单链表,循环链表,双链表.
 
添加哨兵可以保持首指针的稳定性,方便表示空表.
 
一元多项式的表示和相加可以使用链表实现.
 
简答题:
 
顺序表的优缺点?
 
优点:    1.无需为表示结点间的逻辑关系而增加额外的存储空间,存储密度大.
 
            2.可随机存取表中的任一元素,查找方便.
 
缺点:    1.插入,删除运算不方便,须移动大量元素,效率较低.
 
            2.存在预分配空间问题.
 
链表的优缺点?
 
优点:    1.插入,删除操作很方便.
 
            2.空间利用率高.
 
缺点:    1.查找不方便,需顺链查找
 
            2.存储密度小.
 
顺序表和链表的区别和联系及适用范围?
 
顺序表:    内存中地址连续
 
               长度一般不可变更
 
               支持随机查找,可在O(1)内查找元素
 
               适用于需要大量访问元素的,而少量增删元素的程序.
 
链表:        内存中地址连续或非连续都可以
 
                长度可实时变化
 
                不支持随机查找,查找元素的时间复杂度为O(n)
 
                适用于需要大量增删元素,而对访问元素几乎无要求的程序.
 
头指针和头结点的作用?
 
1.头指针是指向链表表头结点的指针,只要链表存在,该指针就不会变化,已知该指针便已知该链表.
 
2.头结点是在链表的开始结点之前夫妇家的一个结点,当链表是空链表时,该指针为空指针,因此空表和非空表的处理也就统一了.
 
简述在单循环链表上尾指针取代头指针的作用?
 
在用头指针表示的单循环链表中,找开始结点a1的时间是O(1),然而要找终端结点an则需要从头指针开始遍历整个链表,其时间是O(n) ,在很多实际问题中,表的操作常常是在表尾进行的,此时头指针表示的单循环链表就显得不够方便,如果改用尾指针来表示单循环链表,则查找开始结点a1和终端结点an都很方便,查找时间都是O(1).
 
栈和队列
 
 
 
 
名词解释:
 
 
 
栈:也叫后进先出表,是限定仅在表尾进行插入和删除操作的线性表,表尾端称为栈顶,表头端称为栈底,不含元素的空表称为空栈,
 
顺序栈:采用顺序存储结构的栈称为顺序栈.
 
链栈:采用链式存储结构的栈称为链栈.
 
队列:是一种先进先出的线性表,它只允许在表的一段进行插入,而另一端删除元素,允许插入的一端叫做队尾,允许删除的一端称为队首.
 
链队列:用链表示的队列,需要两个指针分别指示队头和队尾,为了操作方便,也给链队列添加一个哨兵结点.
 
循环队列:队列是"先进先出表",随着入队出队的进行,会使整个队列整体向后移动,当队尾指针移到最后,若再有元素入队就会出现"假溢出",因为此时队头部分还有空间可用,循环队列是将队列的数据区看成头尾相接的循环结构,可解决"假溢出"现象.
 
双端队列:是限定插入,删除在表的两端进行的线性表,这两端分别称为端点.
 
填空题:
 
栈的两种存储方式:顺序存储和链式存储.
 
栈满的判断条件:s.top==stack.size.
 
栈空的判断条件:s.top==0.
 
栈满入栈栈上溢,栈空出栈栈下溢.
 
链栈使用多栈共享技术时,可使用静态链表结构实现.
 
队列的两种存储方式:顺序存储和链式存储.
 
循环队列采用少用一个元素存储空间的办法下,判断队列满的条件:front==(rear+1)%size.
 
循环队列判断队列满的方法有:少用一个元素存储空间,增设一个标志量,使用计数器.
 
队列的应用:杨辉三角.
 
栈的应用:数制转换,括号匹配,表达式求值,汉诺塔(递归用栈实现).
 
简答题:
 
什么是多栈共享技术?
 
在一个程序中经常会同时使用多个栈,使用顺序存储结构的栈,空间大小难以估计,这样使得有的栈已出,有的栈还有空闲空间,可以让多个栈共享一个足够大的连续向量空间(数组),通过利用栈的动态特性來使其存储空间互相补充,这就是多栈的共享技术,两个栈共享空间,主要利用了"栈底位置不变,栈顶位置动态变化"的特性.
 
与顺序队列相比,循环队列有哪些优点?
 
可解决假溢出现象(内容自行拓展).
 
简述线性表,栈,队列的区别和联系?
 
相同点:    都是线性结构,都是逻辑结构的概念,都可以用顺序存储或链式存储,栈和队列是两种特殊的线性表,即受限的线性表,只对插入和删除运算加以限制.
 
不同点:    1.运算规则不同,线性表为随机存取,而栈只允许在一端进行插入,删除运算,因而是后进先出表,队列只允许在一端进行插入,另一端删除运算,因而是先进先出表.
 
                2.用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理,指令寄存及其他运算等.
 
串
 
 
名词解释:
 
串:是由零个或多个字符组成的有限序列.
 
子串:串中任意个连续的字符组成的子序列称作该串的子串.
 
主串:包含子串的串相应的称为主串.
 
子串在主串中的位置:子串的第一个字符在主串中的位置表示.
 
空串:长度为零的串称为空串.
 
空格串:串中元素均为空格的串称为空格串.
 
串相等:长度相等且对应位置字符都相等.
 
填空题:
 
在程序中,串分为串常量和串变量.
 
串的存储结构:顺序存储结构,链式存储结构,堆存储结构.
 
串的应用:文本编辑.
 
简答题:
 
串和线性表的区别?
 
串的逻辑结构与线性表极为相似,区别仅在于串的数据对象约束为字符集,然而串的操作与线性表有很大的差别,在线性表基本操作中,大多以单个元素作为操作对象;而在串的基本操作中通常以"串的整体"作为操作对象.
 
简述静态分配的顺序串与动态分配的顺序串的区别?
 
程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串,在程序运行过程中,动态分配空间能以链表形式存在的顺序串称为动态顺序串,静态串在内存一片连续的数据区中,动态串在内存堆中.
 
串的链式存储与串的顺序存储相比,在哪些操作上效率更高?
 
插入,删除,因为无需移动其他元素(内容自行扩充).
 
数组与广义表
 
 
 
名词解释:
 
广义表:是由零个或多个单元素或子表所构成的有限序列,是线性表的推广,也有人称其为列表.
 
数组:类型一致的有限个数据元素按顺序连续存储.
 
矩阵的压缩存储:有的矩阵中有许多值相同元素或者是零元素,为了节省存储空间对这类矩阵采用多个值相同的元素只分配一个存储空间,有时零元素不存储的存储策略,称为矩阵的压缩存储.
 
特殊矩阵:值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵称为特殊矩阵.
 
稀疏矩阵:非零的数据元素个数很少的矩阵称为稀疏矩阵.
 
对称矩阵:一个n阶方阵,若满足aij=aji,则称该矩阵为对称矩阵.
 
三角矩阵:主对角线上方和下方的元素(不包括对角线)均为常数或零元素的矩阵.
 
行表:记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表.
 
三元组表:若线性表顺序存储的每一个结点均是三元组,则该线性表的存储结构称为三元组表.
 
带状矩阵:所有非零元素均集中在以主对角线为中心的带状区域的矩阵.
 
填空题:
 
数组的两种存储方式:顺序存储和链式存储.
 
数组的顺序存储有两种方式:按行存储和按列存储.
 
稀疏矩阵可以采用三元组表和十字链表来存储.
 
简答题:
 
广义表和线性表的区别?
 
1.广义表是线性表的推广,是由零个或多个单元素或子表所构成的有限序列.
 
2.线性表的成分都是结构上不可分割的单个数据元素,而广义表的成分既可以是单元素,也可以是有结构的表,其定义是递归的定义.
 
树和二叉树
 
 
 
名词解释:
 
树:是n个结点的有限集合,n≥0,有且只有一个称为根的结点,根结点无前驱.
 
森林:m(m≥1)棵互不相交的树的集合.
 
有序树:树中结点的各子树看成是从左至右依次有序的,且不能交换.
 
二叉树:是一种树型的结构,它的特点是每个结点之多有两棵子树,且有左右之分,不可任意颠倒.
 
完全二叉树:深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时.
 
满二叉树:是一棵深度为k的,且有(2^k)-1个结点的二叉树.
 
遍历二叉树:是按照某种搜索路径巡访二叉树中的每个结点,使得这些结点均被访问一次.
 
线索二叉树:由每个结点中包含左指针,左标志位,数据域,右标志位,右指针五部分组成的二叉链表,叫做线索链表,指向前驱或后继的指针叫做线索,以二叉树某一种遍历顺序给空指针加线索的过程叫做线索化,线索化了的二叉树称为线索二叉树.
 
哈夫曼树:又称最优二叉树,是一类带权路径长度最短的树.
 
哈夫曼编码:在哈夫曼树中,约定左分支代表0,右分支代表1,把叶子结点到根结点的路径上的左右分支代表的码从下至上一次连接起来,组成的字符串称为该叶子结点的哈夫曼编码,这就是哈夫曼编码.
 
二叉排序树:或者是空树,或者是符合以下性质的二叉树.
 
                    1.若它的左子树不空,则左子树上所有结点均小于它的根结点值.
 
                    2.若它的右子树不空,则右子树上所有结点均大于它的根结点值.
 
平衡二叉排序树(AVL树):或者是空树,或者是符合一下性质的二叉排序树.
 
                    1.左子树和右子树的高度之差的绝对值小于等于1.
 
                    2.左子树和右子树也是平衡二叉排序树.
 
B-树(B树):略,看书.
 
填空题:
 
在二叉树中,第i层结点最多为2^k-1个.
 
深度为k的二叉树中,结点总数最多为(2^k)-1个.
 
二叉树中,n0=n2+1,n2=n0-1(n0为二叉树中度为0的结点的个数,n2为二叉树中度为2的结点的个数).
 
有n个结点的完全二叉树,深度为k,则k=⌊log2n⌋+1.(log以2为底,括号是向下取整,不是方括号)
 
k层的完全二叉树至少有2^k-2个叶子结点.
 
二叉树的两种存储结构:顺序存储结构和链式存储结构.
 
树的三种常用的存储方法:孩子表示法,双亲表示法和孩子兄弟表示法.
 
树的遍历方法:先根遍历和后根遍历.
 
简答题:
 
非线性结构的特点?
 
表示结点间关系的前驱后继不具有唯一性,结点间是一对多或多对多的关系.
 
二叉树的五种基本形态?
 
(1)空二叉树——如图(a)；
 
(2)只有一个根结点的二叉树——如图(b)；
 
(3)只有左子树——如图(c)；
 
(4)只有右子树——如图(d)；
 
(5)完全二叉树——如图(e)。
 
 
只有三个结点的二叉树的五种形式?
 
因为二叉树是有序树,所有有左右之分,这是五棵不同的二叉树,但若下列五棵是树,不是二叉树,则后面四种为同一棵树.
 
 
 
 
图
 
 
名词解释:
 
图:图G由两个集合V和E组成,记为G=(V,E),其中V是顶点的有穷非空集合,E是由V中顶点的序偶组成的有穷集,这些序偶称为边或弧.
 
顶点:图中的数据元素称为顶点.
 
完全图:边数恰好等于n(n-1)/2的n个顶点的无向图称为完全图(无向图中任意两个顶点之间都有一条边相连,称该图为完全图).
 
有向完全图:有n(n-1)条边的有向图称为有向完全图(图中每个顶点和其余n-1个顶点都有弧相连).
 
入度:以顶点V为头的弧的数目称为V的入度.
 
出度:以顶点V为尾的弧的数目称为V的出度.
 
连通图:在无向图中,任意两个顶点之间都有路径相通.
 
强连通图:在有向图中,任意两个顶点之间都有来回路径相通.
 
生成树:生成树是无向连通图的一个极小连通子图,它含有图中的全部顶点和使任意顶点都连通的最少的边.
 
邻接矩阵:表示图中结点之间关系的矩阵称为邻接矩阵.
 
邻接表:由顶点数据表和表示数据关系的边(弧)构成的表.
 
十字链表:可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种存储形式.
 
图的遍历:从某一顶点出发按序访问图中所有结点,且使每个结点仅被访问一次.
 
最小生成树:无向网中边上权值之和为最小的生成树.
 
DAG:有向无环网.
 
拓扑排序:由某个集合上的一个偏序得到该集合上一个全序的操作称为拓扑排序.
 
关键路径:在AOE网中,从源点到汇点的最长路径称为关键路径.
 
AOE网:用顶点表示事件,用弧表示活动,弧的权值表示活动所需的时间,构造的有向网称为AOE网.
 
简单路径:一条路径上除了开始顶点和结束顶点外,其余顶点均不相同.
 
弧头:边的终点称为弧头.
 
弧尾:边的始点称为弧尾.
 
填空题:
 
边很少的图称为稀疏图,反之称为稠密图.
 
有向图中,所有顶点的入度与出度的和等于边个数的2倍.
 
图的存储方法:邻接矩阵,邻接表,邻接多重表,十字链表和边集数组.
 
图的深度优先搜索类似于树的先根遍历.
 
图的广度优先搜索类似于树的层次遍历.
 
连通图→深度优先搜索遍历→深度搜索生成树
 
连通图→广度优先搜索遍历→广度搜索生成树
 
简答题:
 
邻接矩阵表示法的特点?
 
1.对于无向图而言,它的邻接矩阵是对称矩阵,因此可以采用特殊矩阵的压缩存储法,但对于有向图而言,其中的弧是由方向的,因此有向图的邻接矩阵不一定是对称矩阵,对于有向图的邻接矩阵的存储则需要n*n个存储空间.
 
2.采用邻接矩阵表示法,便于判断图中任意两个顶点之间是否有边相连,即根据邻接矩阵中的信息来判断,另外还便于求得各个顶点的度,对于无向图而言,其邻接矩阵第i行元素之和就是图中第i个顶点的度.
 
邻接表表示法的特点?
 
1.n个顶点,e条边的无向图,若采取邻接表作为存储结构,需要n个顶点数据和2e个表示边的结点,显然在边很稀疏的情况下,用邻接表存储所需的空间比邻接矩阵所需的空间少.
 
2.无向图的度,在无向图的邻接表中,顶点Vi的度恰好就是第i个边链表上结点的个数.
 
3.有向图的度,在有向图中,第i个边链表上结点的个数就是顶点Vi的出度,只需通过表头向量表中找到第i个顶点的边链表的头指针,实现顺链查找计数即可.
 
DFS(深度优先搜索遍历)的基本思路?
 
假设初始状态是图中所有顶点均未被访问过,则深度优先搜索可从某个顶点V出发,首先访问此顶点(称此顶点为初始点),然后依次从V的任一个未被访问的邻接点出发进行深度优先搜索遍历,直到图中所有与V有路径相通的顶点都被访问到,若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作为初始点,重复上述步骤,直到图中所有顶点都被访问过为止.
 
BFS(广度优先搜索遍历)的基本思路?
 
1.从图中某个顶点V0出发,首先访问V0,依次访问V0的各个未被访问的邻接点.
 
2.分别从这些邻接点(端结点)出发,依次访问各个未被访问的邻接点,访问时应保证:如果Vi和Vk为当前结点,且Vi在Vk之前被访问,则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问.
 
3.重复步骤2,直到所有结点均没有未被访问的邻接点.
 
4.若此时还有顶点未被访问,则选一个未被访问的顶点作为起始点,重复上述过程,直至所有顶点均被访问过为止.
 
查找
 
 
 
 
名词解释:
 
关键字:是数据元素中某个数据项的值,用它可以识别一个或一组数据元素.
 
查找:根据给定的关键字的值,检索某个与该值相等的数据元素是否在查找表中,找到为查找成功,找不到为查找失败.
 
查找表:是由同一类型的数据元素或记录构成的集合.
 
静态查找表:查询某个特定的数据元素是否在查找表中,检索某个特定的数据元素的各种属性.
 
动态查找表:在查找过程中同时插入查找不存在的数据元素,或者从查找表中删除已存在的某个数据元素.
 
平均查找长度(ASL):为确定数据元素在查找表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度.
 
冲突:两个不同的关键字,其散列函数值相同,因而被映射到同一表位置的现象称为冲突.
 
填空题:
 
哈希函数的构造方法:直接定址法,数字分析法,平方取中法,折叠法,除留余数法和随机数法.
 
哈希函数处理冲突的方法:开放地址法,再哈希法,链地址法和建立一个公共溢出区.
 
简答题:
 
各查找方法的基本思想,平均查找长度?
 
顺序查找的基本思路:对于给定的关键字k,从线性表的第一个元素开始依次向后与记录的关键字域相比较,如果某个记录的关键字等于k,则查找成功,否则查找失败.平均查找长度ASL=3(n+1)/4.
 
折半(二分)查找的基本思路:先取表的中间位置的记录关键字和所给关键字进行比较,若相等,则查找成功,如果给定关键字比该记录的关键字小,则说明所要查找的记录只可能在表的前半部分,反之,则在后半部分,重复步骤,每一次比较就可以将查找范围缩小一半,直到找到给定的关键字的记录,查找成功,找不到为查找失败.平均查找长度ASL=log2(n+1)-1.
 
分块查找(索引顺序表查找)的基本思路:先确定待查记录所在的块(子表),然后在块中顺序查找.平均查找长度ASL=1/2[(n/s)+1]+s/2.
 
哈希查找(散列查找)的基本思路:在进行查找时,在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字k为自变量,通过函数h(k)计算出该元素的存储位置,我们将h函数称为散列函数或哈希函数,这种查找方法称为散列查找或哈希查找.
 
排序
 
 
 
 
名词解释:
 
排序:就是按关键字值的递增或递减的次序,把文件中的各记录一次排列起来,可使一个无序文件变成有序文件的一种操作.
 
排序算法的稳定性:相同元素排序前后的相对位置没有发生变化,则为稳定,反之为不稳定.
 
内部排序:在排序过程中,所有待排序记录都放在内存中进行的排序称为内部排序.
 
外部排序:当待排序的记录很多,排序时不仅要使用内存,而且还要使用外部存储器的排序方法称为外部排序.
 
简答题:
 
各排序方法的基本思想,时间复杂度,空间复杂度及稳定性?
 
 
 
直接插入排序的基本思想:直接插入排序是一种最简单的排序方法,基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的,记录数量增一的有序表.时间复杂度O(n^2).空间复杂度O(1).直接插入排序是稳定的.
 
希尔排序的基本思想:先将整个待排元素序列分割成若干子序列分别进行直接插入排序,然后依次缩减增量再进行排序,使整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序,实质就是分组直接插入排序.时间复杂度O(n^2).空间复杂度O(1).希尔排序是不稳定的.
 
冒泡排序的基本思想:先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字,以此类推,直至第n-1个记录和第n个记录的关键字进行过比较为止.时间复杂度O(n^2).空间复杂度O(1).冒泡排序是稳定的.
 
快速排序的基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据进行快速排序,整个排序过程可以递归进行,以达到整个序列有序.时间复杂度O(nlog2n).空间复杂度O(nlog2n).快速排序是不稳定的.
 
直接选择排序的基本思想:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录与第一个记录的位置交换,接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小的记录并与第二个记录的位置交换,重复该过程,直到进行比较的记录只有一个时为止.时间复杂度O(n^2).空间复杂度O(1).直接选择排序是不稳定的.
 
堆排序的基本思想:堆排序是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种,可以利用数组的特点快速定位索引的元素,堆分为大根堆和小根堆,是完全二叉树.时间复杂度O(nlog2n).空间复杂度O(1).堆排序是不稳定的.
 
归并排序的基本思想:将待排序序列看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序表再次归并,得到n/4个长度为4的有序序列;如此重复进行下去,最后得到一个长度为n的有序序列.时间复杂度O(nlog2n).空间复杂度O(n).归并排序是稳定的.
 
基数排序的基本思想:是借助"分配"和"收集"两种操作对单逻辑关键字进行排序的一种内排序方法.时间复杂度O(d*n).空间复杂度O(n+r).基数排序是稳定的.
 
作图题
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
附加内容:
 
文件:是由大量性质相同的记录组成的集合,可按其记录的类型不同而分成两类:操作系统文件和数据库文件.
 
定长纪录文件:文件中每个记录含有的信息长度相同,则称这类记录为定长记录,由这类记录组成的文件称为定长纪录文件.
 
不定长记录文件:文件中每个记录含有的信息长度不相同,则称这类记录为不定长记录,由这类记录组成的文件称为不定长纪录文件.
 
文件的操作有两类:检索和修改.
 
文件的检索有三种方式:顺序存取,直接存取,按关键字存取.
 
文件的修改包括插入一个记录,删除一个记录和更新一个记录三种操作.
 
顺序文件:物理记录的顺序与逻辑记录的顺序是一致的.
 
连续文件:若次序相继的两个物理记录在存储介质上的存储位置是相邻的,则称连续文件.
 
串联文件:物理记录之间的次序由指针相链表示,则称串联文件.
 
索引文件:包含文件数据区和索引表两大部分的文件称作索引文件.
 
索引项:索引表中的每一项称为索引项.
 
索引顺序文件:数据区中记录也按关键字顺序排列,则称索引顺序文件,反之为索引非顺序文件.

数据（DATA）是描述客观事物的数字、字符以及所有能输入计算机并能被计算机接受的各种符号集合的统称。
 
数据结构(data structure):数据元素之间存在的关系，由n(n >= 0)个数据元素组成的有限集合，数据元素之间具有某种特定的元素。
 
数据的逻辑结构：线性结构、树结构、图
 
数据的存储结构：顺序存储、链式存储
 
对数据进行操作：初始化、判断是否是空、存取、统计个数、遍历、插入、删除、查找、排序 ————用算法进行描述。
 
数据类型和抽象数据类型。
 
算法：有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法设计依赖数据的逻辑结构，实现依赖数据的存储结构。算法分析的两个方面：时间代价、空间代价。
 
线性表的顺序存储（顺序表）和链式存储（链表）
 
一、顺序表（SeqList)使用一维数组一次存放书元素。一维数组占用一块内存空间，每个存储单元的地址是连续的，通过下标识别元素，它的下标就代表了他的存储单元序号，也就表示了它的位置。
 
查找顺序表中的元素是方便的，根据下标就可以取出要取的元素。
 
当顺序表的容量不够时，顺序表不能就地扩容，要申请另一个更大容量的数组进行数组元素复制。
 
对于插入、删除元素：先根据下标找到相应位置，若插入元素，将新插入插入位置后，将被加入位置的旧元素及之后的元素向后移动，移动次序是由后向前。若删除元素，将要删除的元素删除，其后的元素向前移动。插入和删除的操作时间主要用于移动元素。
 
二、线性表的链式存储结构(链表LinkedList)是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。存储一个数据元素的存储单元成为结点Node，单链表的表示方式：结点（数据域，地址域）。
 
对于单链表的操作：遍历操作是从第0个结点开始，沿着结点的Next链，依次访问单链表中的每个结点，并且每个节点只访问一次。插入（删除）操作：根据要插入（删除）的结点数，从第0个结点遍历找到要插入（删除）的位置，将要插入的数据元素插入（将要删除的元素删除），改变原来结点间的链接关系，不用移动数据元素。而操作所花的时间都在查找上面。
 
三、特殊的线性表（栈和队列）
 
（一）特殊之处在于插入和删除操作的位置受到限制：
 
若插入和删除的操作只允许在线性表的一端进行，则为栈(stack)，特点是先进后出；
 
若插入和删除操作分别在线性表的两端进行，则为队列(queue)，特点是先进先出。
 
（ps. 栈和线性表是不同的抽象数据类型，栈的概念不依赖于线性表而存在。）
 
（二）应用
 
栈是嵌套调用机制的实现基础：由于函数返回次序与调用次序正好相反，借助栈来实现记忆函数的路径，就能获得函数返回的路径，当函数被调用时，操作系统将该函数的有关信息（地址、参数、局部变量值等）入栈，称为保护现场；一个函数执行完返回时，出栈，获得调用函数信息，称为恢复现场，程序返回调用函数继续运行。
 
使用栈以非递归方式实现递归算法（存在直接或间接调用自身的算法称为递归算法）；
 
队列用于处理排队等待问题。（优先队列）
 
树和二叉树
 
完全二叉树（满二叉树）；
 
Huffman树：带权外路径长度最小的二叉树，也成最优二叉树；Huffman编码是数据压缩技术中一种无损压缩编码。
 
树的遍历规则主要有两种：先根次序遍历和后根次序遍历。
 
树的存储结构：一棵树包含个结点间的层次关系与兄弟关系，两种关系的存储结构不同；树的层次关系，必须采用链式存储结构存储，通过链连接父母结点和孩子结点；一个结点的多个孩子结点（互称兄弟）之间是线性关系，可以采用顺序存储结构或链式存储结构存储。
 
B树：存储效率高，查询效率低——数据库索引
 
图
 
矩阵和规划
 
排序
 
插入排序：每次将一个元素，按其关键字值的大小插入到它前面已排序的子序列中，依次重复，直到插入全部元素。
 
直接插入排序：最好情况是N;最坏情况是N*N;空间复杂度是O(1);
 
二分法插入排序：在插入排序时采用顺序查找算法寻找位置。
 
希尔排序：缩小增量排序，即分组地直接插入排序。时间复杂度不容易计算，取决于增量的选择。
 
交换排序：
 
冒泡排序：比较相邻的两个元素的大小，每次将数据序列中最大元素交换到最后。N*N;空间复杂度：O(1).
 
快速排序：在数据序列里选择一个元素作为基准值，每次从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。同时，序列划分为两个子序列，再分别对两个子序列进行快速排序，直到子序列长度为1，则完成排序。最好情况：NN ;最坏情况是NN;快排是递归算法，会花费一定的时间和空间，使用栈保存参数，栈所占的空间和递归调用的次数有关，空间复杂度为O(N) ~ O(n).
 
直接选择排序：第一趟从n个元素的数据序列中选出关键字最大或最小的元素并放在最前或最后位置，下一趟再从n-1个参数中选出其中最大或最小的数放在相应位置，依次类推。 时间复杂度为O(n*n);空间复杂度为O(1).
 
堆排序：利用完全二叉树。将最大值或最小值移到根节点然后换下来，再找剩下的里面最大值或最小值。时间复杂度为O(n*N);堆排序的空间复杂度为O(1).
 
归并排序：将另个排序的子序列合并，形成一个排序数据序列。时间复杂度为O(n*N)；空间复杂度为O(n).

1、用链表表示线性表的优点是（便于插入和删除操作）
 
2、单链表中，增加头结点的目的是（方便运算的实现）
 
3、栈和队列的共同特点是（只允许在端点处插入和删除元素）
 
4、栈通常采用的两种存储结构是（线性存储结构和链表存储结构）
 
5、队列具有（先进先出）的特征，栈具有（后进先出）的特征。
 
6、链表（插入和删除不需要移动元素，但是无法随机访问任一元素）
 
7、循环链表的主要优点是（从表中任一结点出发都能访问到整个链表）
 
8、线性表（除了第一个和最后一个元素外，其余每个元素都有一个直接前驱和直接后继）
 
9、线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构）
 
10、深度为5的满二叉树中，叶子结点的个数为（16）。其共有（31）个结点。
 
   设一棵完全二叉树共有699个结点。则该二叉树的叶子结点数为（350）个。 

         #完全二叉树总的结点数为N，若N为奇数，则叶子结点数为（N+1）/2；若N为偶数，则叶子结点数为N/2。
 
11、具有3个结点的二叉树有（5）种形态。 #高度为2层的是：根-左-右。高度为3层的是：根-左-左、根-左-右、根-右-右、根-右-左。
 
12、一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13）个。
 
  #叶子结点数n0与度为2的结点数n2的关系是：n0＝n2＋1，所以度为2的结点个数为3-1=2。所以总的结点数为 n=n0+n1+n2, 8+2+3=13.
 
13、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（cedba）。#过程见文章：点击打开链接
 
14、已知二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,它的前序遍历序列是（gdbehfca）。
 
15、算法是指（解决方案的准确而完整的描述）。
 
16、算法由（顺序、选择、循环）控制结构组合而成。
 
17、算法的时间复杂度是指（算法执行过程中所需要的基本运算次数）。
 
18、算法的空间复杂度是指（执行过程中所需要的存储空间）。
 
19、算法分析的目的是（分析算法的效率以求改进）。
 
20、数据的存储结构是指（数据的逻辑结构在计算机中的表示）。
 
21、数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构）。
 
22、根据数据结构中各元素之间前后件关系的复杂程度，可将数据结构分为（线性结构和非线性结构）。
 
线性结构一般是首无前驱，尾无后继，中间元素有唯一的前驱和后继。主要有：列表、链表、队列、栈。
 
非线性结构主要有1、没有对应关系的 集合。2、一对多关系的 树。3、多对多关系的 图。
 
23、（队列，循环队列，顺序表）不具有记忆功能，（栈）具有记忆功能。
 
24、递归算法一般需要用（栈）来实现。
 
#在递归算法的运行过程中，需要利用栈来保存其运算结果、参数和返回地址等。
 
25、算法的五个基本特征是：可行性，确定性，和拥有足够的情报
 
有限性：算法在执行有限步后必须终止。
 
确定性：算法的每个步骤都需要精确地定义，严格地、无歧义的运行。
 
输入：算法在运行之前赋给它的量。
 
输出：算法运行结束时的结果。
 
可行性：算法原则上能够精准地运行，而且人们用纸和笔做有限次运算后即可完成。
 
26、由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的概率）。
 
为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间。但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补
 
27、需要打印机输出数据时，一般将打印作业放在一个（队列）中。
 
28、非空的循环单链表head的尾结点（由 p 所指向） ，满足（p->next=head ）。
 
29、与单链表相比，双向链表的优点是（更容易访问相邻结点）。
 
30、
 
31、N个顶点的连通图中边的条数至少为（N-1）条。#将所有顶点连成一条线即可
 
32、N个顶点的强连通图中边的条数至少为（N）条。#将所有顶点连成一条圈
 
33、对长度为n的线性表进行顺序查找，最坏情况下需要比较（N）次。
 
34、最简单的交换排序是（冒泡排序）。
 
35、对长度为n的线性表进行顺序冒泡排序，最坏情况下需要比较（n(n-1)/2）次。
 
    #一共比较n-1遍，第1遍需要比较n-1次，第1遍需要比较n-2次,........最后一遍需要比较1次。是一个等差序列，对其进行求和即可。
 
36、在序列基本有序的情况下，效率最高的方法是（A） #如果将插入排序换为冒泡排序，则选冒泡排序
 
     A．插入排序   B．选择排序   C．快速排序   D．堆排序

    插入排序通过数据元素的交换来逐步消除线性表中的逆序，所以比较的次数与初始排列次序有关，在待排序的元素序列基本有序的前提下，效率最高。而选择排序和堆排序的比较次数与初始排列次序无关。快速排序虽然与初始排列次序有关，但在待排序的元素序列基本有序的前提下，效率低于插入排序。
 
37、希尔排序属于（插入类排序），堆排序属于（选择类排序）。
 
38、在下列几种排序方法中，要求内存量最大的是（D）.
 
    A．插入排序  B．选择排序  C．快速排序  D．归并排序

    快速排序的基本思想是，通过一趟排序将待排序记录分割成独的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)，然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组成合成一个新的序列表。
 
39、已知数据表 A中每个元素距其最终位置不远，为节省时间， 应采用（直接插入排序）。
 
40、数据结构是指相互有关联的( 数据元素 )的集合。
 
41、数据元素之间的任何关系都可以用 (前驱和后继) 关系来描述。
 
42、顺序存储方法是把逻辑上相邻的结点存储在 (物理位置) 相邻的存储单元中。
 
43、栈的基本运算有三种：入栈、退栈与读栈顶元素。
 
44、队列主要有两种基本运算：入队和退队。
 
45、在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为 (可利用栈) .
 
46、栈和队列通常采用的存储结构分别是 链式存储和顺序存储。
 
47、当循环队列非空且队尾指针等于对头指针时， 说明循环队列已满，不能进行入队运算。这种情况称为 (上溢)
 
48、当循环队列为空时， 不能进行退队运算， 这种情况称为 (下溢)。
 
49、在一个容量为 25 的循环队列中， 若头指针 front=16 ， 尾指针 rear=9 ， 则该循环队列中共有 18 个元素。 注： 当 rear<front 时， 元素个数＝总容量－（ front －rear ）； 当 rear>front 时，元素个数＝ rear －front 。
 
50、判断一个链表是否存在环：点击打开链接
 
    单链表中元素的反转：点击打开链接

    判断两个数组中是否有相同的数字：点击打开链接

    从一个子序列中找出其最大子序列的和：点击打开链接

    按单词反转字符串：点击打开链接

    删除数组中重复的元素：点击打开链接
 
51、数组和链表的区别
 
  数组不允许动态地定义其大小，只能够将其定义成足够大小，这样可能会造成空间的浪费。

  数组在内存中是顺序的存储，可以以O(1)时间查找元素，但是需要O(n)时间插入和删除元素（因为其后面的元素都需要跟着移动）。

  链表可以动态地定义其大小。其在内存中是链式的存储，访问元素是需要从头开始向后顺序访问，所以需要O(n)时间查找元素；如果在所需位置直接插入或删除元素，需要O(1)时间，如果在需要先找到所需位置再插入或删除元素，需要O(n)时间。
 
52、链表的基本操作：反转，是否存在环，循环链表点击打开链接和双向链表点击打开链接的查找、插入、删除操作。
 
53、栈的入栈和出栈：点击打开链接，队列的入队和出队：点击打开链接
 
54、二叉树的基础知识：点击打开链接及其三种遍历（递归和非递归实现）：点击打开链接
 
55、图的基础知识：点击打开链接
 
56、常用散列函数和冲突消解机制：点击打开链接
 
57、排序算法中基本的冒泡排序、选择排序、插入排序需要很快地用代码实现。堆排序、归并排序、快速排序需要掌握其主要思想，并熟悉常用排序算法的时间和空间复杂度，及其应用范围：
 
(1) 当数据规模较小时，直接采用直接插入排序或直接选择排序。

(2) 当数据已经基本有序时，可以用直接插入排序或冒泡排序。

(3) 当数据规模较大时，可以用快速排序。当记录随机分布时，快速排序的平均时间最短。当最坏情况时，其时间复杂度为O(n2)，空间复杂度为O(n)。

 (4) 堆排序所需的辅助空间比快排少，但这两种方法都不稳定。

 (5) 归并排序既可以用于内部排序，也可以用于外部排序，是一种稳定的算法。
 
58、能熟练写出二分查找的程序。
 
59、熟悉算法的思想：贪心算法，动态规划，分治算法。

 
文章目录
 
第一章 绪论
1.1 数据结构的基本概念
1.1 练习题
    
1.2 算法和算法评价
1.2 练习题
   
   
第二章 线性表
2.1 线性表的定义和基本操作
2.1 练习题
    
2.2 线性表的顺序表示
2.2 练习题
   
  
 

 
由于最近实在没时间导致这个更新鸽了。。。实在不好意思。
 
第一章 绪论
 
1.1 数据结构的基本概念
 
数据结构的三要素：逻辑结构、存储结构（物理结构）、数据的运算。
数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构，集合、树和图是典型的非线性结构。
 

 
 
数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。
顺序存储：优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
链式存储：优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
索引存储。在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点是检索速度快，缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。优点是检索、增加和删除节点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
可以用抽象数据类型（ADT）定义一个完整的数据结构。
在存储数据时，不仅要存储数据元素的值，而且要存储数据元素之间的关系。
 
1.1 练习题
 
以下属于逻辑结构的是（）
 A、顺序表
 B、哈希表
 C、有序表
 D、单链表
 解析：有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，它既可以链式存储也可以顺序存储，故属于逻辑结构。顺序表、哈希表、单链表是三种不同的数据结构，既描述逻辑结构，又描述存储结构和数据运算。
 答案：C
以下与数据的存储结构无关的术语是（）
 A、循环队列
 B、链表
 C、哈希表
 D、栈
 解析：循环队列（易错点）是用顺序表表示的队列，是一种数据结构。栈是一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。
 答案：D
以下关于数据结构的说法中，正确的是（）
 A、数据的逻辑结构独立于其存储结构
 B、数据的存储结构独立于其逻辑结构
 C、数据的逻辑结构唯一决定了其存储结构
 D、数据结构仅由其逻辑结构和存储结构决定
 解析：数据的逻辑结构只采用抽象表达方式，独立于存储结构，数据的存储方式有多种不同的选择；而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。数据结构包括三个要素，缺一不可。
 答案：A
链式存储设计时，结点内的存储单元地址（）
 A、一定连续
 B、一定不连续
 C、不一定连续
 D、部分连续，部分不连续
 解析：链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续。
 答案：A
对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？
 解答：应该注意到，数据的运算也是数据结构的一个重要方面。
 对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为O(n)，而二叉排序树的时间复杂度为O(log2n)。
试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。
 解答：线性表既可以用顺序存储方式实现，又可以用链式存储方式实现。在顺序存储方式下，在线性表中插入和删除元素，平均要移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除的时间复杂度都是O(1)。
 
1.2 算法和算法评价
 
算法是对特定问题求解步骤的一种描述，是指令的有限序列，它还具有5个重要特性：有穷性、确定性、可行性、输入、输出。通常，设计一个“好”的算法应考虑达到以下目标：正确性、可读性、健壮性、效率与低存储量需求。
算法的时间复杂度记为T(n)=O(f(n))，通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度，基本运算的频度不仅与问题规模n有关，而且与输入中各元素的取值有关。
空间复杂度是问题规模n的函数，记为S(n)=O(g(n))，算法原地工作是指算法所需的辅助空间为常量，即O(1)。
 
1.2 练习题
 
一个算法应该是（）
 A、程序
 B、问题求解步骤的描述
 C、要满足五个基本特性
 D、A和C
 解析：本题是中山大学某年的考研真题，容易误选C，五个特性只是算法的必要条件，不能成为算法的定义。
 答案：B
 
 
第2题代码：
 
	x=2;
	while(x<n/2)
	x=2*x;
 
【2011统考真题】设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）。
 A、O(log2n)
 B、O(n)
 C、O(nlog2n)
 D、O(n2)
 解析：每执行一次，x乘2，设执行次数为t，则有2t+1 < n/2，所以 t < log2(n/2) - 1 = log2n - 2，得T(n) = O(log2n)
 答案：A
 
 
第3题代码：
 
	int fact(int n){
		if(n<=1) return 1;
		return n*fact(n-1);
	}
 
【2012统考真题】求整数n（n≥0）的阶乘的算法如下，其时间复杂度是（）
 A、O(log2n)
 B、O(n)
 C、O(nlog2n)
 D、O(n2)
 解析：计算阶乘n!的递归代码，一共执行 n 次递归调用，T(n)=O(n)。
 答案：B
【2013统考真题】已知两个长度分别为m和n的升序链表，若将它们合并为长度为m+n的一个降序链表，则最坏情况下的时间复杂度是（）。
 A、O(n)
 B、O(mn)
 C、O(min(m,n))
 D、O(max(m,n))
 解析：两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置（取较小元素，头插法）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，所以时间复杂度为O(max(m,n))。
 答案：D
 
 
第5题代码：
 
	count=0;
	for(k=1;k<=n;k*=2)
		for(j=1;j<=n;j++)
			count++;
 
【2014统考真题】下列程序段的时间复杂度是（）。
 A、O(log2n)
 B、O(n)
 C、O(nlog2n)
 D、O(n2)
 解析：和第2题差不多，内层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)，根据乘法规则可知，该段程序的时间复杂度T(n)=T1(n) × T2(n) = O(n) × O(log2n) = O(nlog2n)。
 答案：C
 
 
第6题代码：
 
	int func(int n){
		int i=0, sum=0;
		while(sum<n) sum += ++i;
		return i;
	}
 
【2017统考真题】下列函数的时间复杂度是（）
 A、O(log2n)
 B、O(n1/2)
 C、O(n)
 D、O(nlog2n)
 解析：每执行一次，i自增1，我们如果把 i 当作一个首项为0，公差为1的等差数列的话，那么sum就是等差数列的和，由等差数列求和公式得，sum=(i+1)*i/2，设循环次数为 t ，则 t 满足(t+1)*t/2<n，因此时间复杂度为O(n1/2)。
 答案：B
 
 
第7题代码：
 
	x=0;
	while (n>=(x+1)*(x+1))
	x=x+1;
 
【2019统考真题】设n是描述问题规模的非负整数，下列程序段的时间复杂度是（）
 A、O(log2n)
 B、O(n1/2)
 C、O(n)
 D、O(n2)
 解析：假设第 k 次循环终止，则第 k 次执行时，(x+1)2 > n，x 的初始值为0，第k次判断时，x=k-1，即k2 > n，k > n1/2，因此该程序段的时间复杂度为O(n1/2)，因此选B。
 答案：B
某算法的时间复杂度为O(n2)，表明该算法的（）。
 A、问题规模是n2
 B、执行时间等于n2
 C、执行时间与n2成正比
 D、问题规模与n2成正比
 解析：时间复杂度T(n)=O(n2)，执行时间与n2成正比。T(n)是问题规模n的函数，其问题规模仍然是n而不是n2。
 答案：C
 
 
第9题代码：
 
	int m=0, i, j;
	for(i=1;i<=n;i++)
		for(j=1;j<=2*i;j++)
			m++;
 
"m++"的执行次数为（）。
 A、n(n+1)
 B、n
 C、n+1
 D、n2
 解析：m++语句的执行次数为${\sum }_{i=1}^n{\sum }_{j=1}^{2i}1={\sum }_{i=1}^{n}2i=2{\sum }_{i=1}^{n}i=n(n+1)$
 答案：A
 
第二章 线性表
 
2.1 线性表的定义和基本操作
 
线性表的定义。线性表是具有相同数据类型的 n (n ≥ 0)个数据元素的有限序列，其中 n 为表长，当n = 0时线性表是一个空表。若用 L 命名线性表，则其一般表示为 L = (a1,a2,…,ai,ai+1,…,an)式中，a1是唯一的“第一个”数据元素，又称表头元素；an是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。这种线性有序的逻辑结构正是线性表名字的由来。
线性表的基本操作。
 线性表的主要操作如下：
 InitList(&L)：初始化表。构造一个空的线性表。
 Length(L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数。
 LocateElem(L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
 GetElem(L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。
 ListInsert(&L,i,&e)：插入操作。在表 L 中的第 i 个位置上插入指定元素e。
 ListDelete(&L,i,&e)：删除操作。删除表 L 中的第 i 个位置的元素，并用 e 返回删除元素的值。
 PrintList(L)：输出操作。按前后顺序输出线性表 L 的所有元素值。
 Empty(L)：判空操作。若 L 为空表，则返回 true ，否则返回 false 。
 DestroyList(&L)：销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。
 注意：①基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。②“&”表示C++中的引用调用。若传入的变量是指针型变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型。在C中采用指针的指针也可达到同样的效果。
总结：线性表的特点：表中元素的个数有限，表中元素具有逻辑上的顺序性，表中元素有其先后次序。表中元素都是数据元素，每个元素都是单个元素。表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
 
2.1 练习题
 
线性表是具有 n 个（）的有限序列。
 A、数据表
 B、字符
 C、数据元素
 D、数据项
 解析：线性表由具有相同数据类型的有限数据元素组成的，数据元素由数据项组成的。
 答案：C
以下（）是一个线性表。
 A、由 n 个实数组成的集合
 B、由100个字符组成的序列
 C、所有整数组成的序列
 D、邻接表
 解析：线性表定义的要求为：相同数据类型、有限序列。选项C的元素个数是无穷个，错误；选项A集合中的元素没有前后驱关系，错误；选项D属于存储结构，线性表是一种逻辑结构，只有选项B符合要求。
 答案：B
 
2.2 线性表的顺序表示
 
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧接着存储的是第 i + 1 元素，称 i 为元素 ai在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
线性表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的。
假定线性表的元素类型为 ElemType，则线性表的顺序存储类型描述为
 
#define MaxSize 50				//定义线性表的最大长度 
typedef struct
{
	ElemType data[MaxSize];		//顺序表的元素 
	int length;					//顺序表的当前长度 
}SqList;						//顺序表的类型定义 
 
一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。
 
#define InitSize 100			//表长度的初始定义 
typedef struct
{
	ElemType *data;				//指示动态分配数组的指针 
	int MaxSize, length;		//数组的最大容量和当前个数  
}SeqList;						//动态分配数组顺序表的类型定义 
 
C的初始动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
C++的初始动态分配语句为L.data=new ElemType[InitSize];
动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。
顺序表最主要的特点是随机访问，即通过首地址和元素符号可在时间O(1)内找到指定的元素。
顺序表的存储密度高，每个节点只存储数据元素。顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素，平均时间复杂度为O(n)。
按值查找操作（顺序查找）在顺序表L中查找第一个元素值等于e的元素，时间复杂度为O(n)。
 
2.2 练习题
 
线性表的顺序存储结构是一种（）
 A、随机存取的存储结构
 B、顺序存取的存储结构
 C、索引存取的存储结构
 D、散列存取的存储结构
 解析：本题易误选B。存取方式是指读写方式。顺序表是一种支持随机存取的存储结构，根据起始地址加上元素的序号，可以很方便地访问任意一个元素，这就是随机存取的概念。
 答案：A
一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入删除操作，则利用（）存储方式可以节省时间。
 A、顺序表
 B、双链表
 C、带头结点的双循环链表
 D、单循环链表
 解析：只有顺序表可以按序号随机存取，且在最后进行插入和删除操作不需要移动任何元素。
 答案：A
在 n 个元素的线性表的数组表示中，时间复杂度为O(1)的操作是（）。
 I、访问第 i (1 ≤ i ≤ n)个结点和求第 i (2 ≤ i ≤ n)个结点的直接前驱
 II、在最后一个结点后插入一个新的结点
 III、删除第 1 个结点
 IV、在第 i (1 ≤ i ≤ n)个结点后插入一个结点
 A、I
 B、II、III
 C、I、II
 D、I、II、III
 解析：在最后位置插入新结点不需要移动元素，时间复杂度为O(1)；被删结点后的结点需依次前移，时间复杂度为O(n)。
 答案：C
设线性表由 n 个元素，严格说来，以下操作中，（）在顺序表上实现要比链表上实现的效率高。
 I、输出第 i (1 ≤ i ≤ n)个元素值
 II、交换第 3 个元素与第 4 个元素的值
 III、顺序输出这 n 个元素的值
 A、I
 B、I、III
 C、I、II
 D、II、III
 解析：对于II，顺序表上实现仅需 3 次交换操作；链表上则需要分别找到两个结点前驱，前 4 个结点断链后再插入到第 2 个结点后面，效率较低。
 答案：C
若长度为 n 的非空线性表采用顺序存储结构，在表的第 i 个位置插入一个数据元素，i 的合法值应该是（）。
 A、1 ≤ i ≤ n
 B、1 ≤ i ≤ n + 1
 C、0 ≤ i ≤ n - 1
 D、0 ≤ i ≤ n
 解析：线性表元素的序号是从 1 开始，而在第 n + 1 个位置插入相当于在表尾追加。
 答案：B
【2010统考真题】设将 n（n>1）个整数存放到一维数组 R 中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1,)。要求：
 （1）给出算法的基本设计思想。
 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 （3）说明你所设计算法的时间复杂度和空间复杂度。
 解答：
 （1）算法的基本设计思想：可将这个问题视为把数组 ab 转换成数组 ba （a代表数组的前 p 个元素，b代表数组中余下的 n - p 个元素），先将 a 逆置得到 a-1b ，再将 b 逆置得到 a-1b-1 ，最后将整个a-1b-1逆置得到 (a-1b-1)-1 = ba。设 Reverse 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3 (p=3)个位置的过程如下：
 Reverse(0, p - 1)得到 cbadefgh；
 Reverse(p, n - 1)得到 cbahgfed；
 Reverse(0, n - 1)得到 defghabc；
 注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。
 （2）使用C语言描述算法如下：
 （3）上述算法中三个Reverse 函数的时间复杂度分别为O(p/2)、O((n-p)/2)、O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。
 
//第2小问代码
void Reverse(int R[], int from, int to)
{
	int i, temp;
	for(i = 0; i < (to - from + 1) / 2; i++)
	{
		temp = R[from + i];
		R[from + i] = R[to - i];
		R[to - i] = temp;
	}
}
void Converse(int R[], int n, int p)
{
	Reverse(R, 0, p - 1);
	Reverse(R, p, n - 1);
	Reverse(R, 0, n - 1);
}
 
 
【2011统考真题】一个长度为L(L≥1)的升序序列S，处在第$\lceil$$\frac{L}{2}$$\rceil$个位置的数称为S的中位数。例如列S1=(11，13，15，17，19)，则S1中的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若92=(2，4，6，8，20)，则．S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：
 （1）给出算法的基本设计思想。
 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 （3）说明你所设计算法的时间复杂度和空间复杂度。
 解答：
 （1）算法的基本设计思想如下：
 分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数的过程如下：
 ①若a=b，则a或b即为所求中位数，算法结束。
 ②若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。
 ③若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。
 在保留的两个升序序列中，重复过程①、②、③，直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。
 （2）本题代码如下：
 （3）算法的时间复杂度为O(log2n)，空间复杂度为O(1)。
 
int M_Search(int A[], int B[], int n)
{
	int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
	//分别表示序列A和B的首位数、末位数和中位数 
	while(s1 != d1 || s2 != d2)
	{
		m1 = (s1 + d1) / 2;
		m2 = (s2 + d2) / 2;
		if(A[m1] == B[m2]) return A[m1];	//满足条件① 
		if(A[m1] < B[m2])					//满足条件② 
		{
			if((s1 + d1) % 2 == 0)	//若元素个数为奇数 
			{
				s1 = m1;		//舍弃A中间点以前的部分且保留中间点 
				d2 = m2;		//舍弃B中间点以后的部分且保留中间点 
			}
			else					//若元素个数为偶数 
			{
				s1 = m1 + 1;	//舍弃A中间点及中间点以前的部分
				d2 = m2;		//舍弃B中间点以后的部分且保留中间点 
			}
		}
		else								//满足条件③ 
		{
			if((s2 + d2) % 2 == 0)			//若元素个数为奇数 
			{
				d1 = m1;		//舍弃A中间点以后的部分且保留中间点 
				s2 = m2;		//舍弃B中间点以前的部分且保留中间点 
			}
			else					//若元素个数为偶数 
			{
				d1 = m1;		//舍弃A中间点以后的部分且保留中间点 
				s2 = m2 + 1;	//舍弃B中间点及中间点以前的部分 
			}
		}
	}
	return A[s1] < B[s2] ? A[s1] : B[s2];
}
 
 
【2013统考真题】已知一个整数序列A=(a0,a1,…,an-1)，其中0 ≤ ai < n(0 ≤ i < n)。若存在ap1=ap2=…=apm=x且m＞n/2(0 ≤ pk < n，1 ≤ k ≤ m)，则称 x 为A的主元素。例如A=(0，5，5，3，5，7，5，5)，则5为主元素；又如A=(0，5，5，3，5，1，5，7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
 （1）给出算法的基本设计思想。
 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 （3）说明你所设计算法的时间复杂度和空间复杂度。
【2018统考真题】给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：
 （1）给出算法的基本设计思想。
 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 （3）说明你所设计算法的时间复杂度和空间复杂度。
 
最后一次更新时间：2021/03/09 23:20