A. 计算机考研：数据结构常用算法解析(2)
数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。猎考考研就带大家一一梳理这些知识点。
第二章
循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。
判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。
何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答：
在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表;反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜;反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
第2章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!
更多详情请点击：计算机考研：数据结构常用算法解析汇总
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
B. 计算机考研：数据结构常用算法解析(3)
第三章
例如：Exp=a*b+(c-d/e)*f
若 Exp=a*b+(c-d/e)*f 则它的
前缀式为： +*ab*-c/def
中缀式为： a*b+c-d/e*f
后缀式为： ab*cde/-fx+
综合比较它们之间的关系可得下列结论：
1.三式中的 “操作数之间的相对次序相同”;
(二叉树的三种访问次序中，叶子的相对访问次序是相同的)
2.三式中的 “运算符之间的的相对次序不同”;
3.中缀式丢失了括号信息，致使运算的次序不确定;
(而前缀和后缀运算只需要一个存储操作数的栈，而中缀求值需要两个栈，符号栈和操
作数栈)
4.前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;
5.后缀式的运算规则为：
·运算符在式中出现的顺序恰为表达式的运算顺序;
·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;
6.中缀求值的运算规则：
如果是操作数直接入栈。
如果是运算符。这与当前栈顶比较。个如果比当前栈顶高，则入栈，如果低则说明当前栈顶是最高的必须把他先运算完了。用编译原理的话就是说当前栈顶已经是最左素短语了)
其实中缀表达式直接求值和把中缀表达式转化成后缀表达式在求值的过程惊人的相似，只不过是直接求值是求出来，而转化成后缀是输出来。
中缀表达式直接求值算法：
OPNDType EvalueExpression()
{ //OPTR 和OPND分别为运算符栈和操作数栈
InitStack(OPTR);Push(OPTR,’#’);
InitStack(OPND);c=getchar();
While(c!=’#’|| GetTop(OPTR)!=’#’)
{
If(!IN(c,OP) ) //如果是操作数，直接入操作数栈
{ push(OPND,c);
c=getchar();
}
Else //如果是运算符，则与当前的栈顶比较
{
Switch(Precede(GetTop(OPTR),c))
{
Case ‘<’: push(OPTR,c);//比当前栈顶高，这入栈
c=getchar();
break;
Case ’= ’:Pop(OPTR,x); //在我们设计的优棚肆枯先级表中，
c=getchar(); //只有’(’和’)’存在相等的情况，
break; //而在规约中间只存在‘(’‘)’
//所以我们直接把’(’弹出就可以了
Case ‘>’: //比当前栈顶低，则要把栈顶先运算完(先规约)
pop(OPTR,theta); //把栈顶运算符弹出
Pop(OPND,b); //取出操作数，并且是前操作数雹搭
Pop(OPND,a); //在下面(栈的先进后出)
Push(OPND,Operate(a,theta,b)); //运算的结果入栈
//(他是其他运算符的操作数)
Break;
}//Switch
}//链洞else
}//whild
Return GetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。
}
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
C. 计算机组成原理中，对算法进行分析时，主要是分析算法的什么
时间复杂度，也就是算法处理一个问题需要多长时间。空间复杂度也要分析，不过时间复杂度更重要。
D. 计算机考研：数据结构常用算法解析(4)
第四章
KMP算法和朴素的匹配算法的关键区别就是解决了主串指针i的回溯，原理如下：
设主串S[]和模式串T[],如比较到模式串的第j个字符。 当主串指针i和模式串指针j比较时 ，说明他们前面的所有字符都已经对应相等了。而
Next[j]=k的定义是T1T2…Tk-1==Tj-k+1Tj-k+2….Tj-1且k是最大了，没有更长的了。
所以Si和Tj比较失败时Si和Tk去比较。不可能有 这种匹配的成功，因为S2S3…..Si-1= =T2T3……Tj-1,而T2T3….Tj-1是不等于T1T2….Tj-2。除非next[j]=j-1;因为next定义的是最长的。所以任何挪动小于next[j]的串的匹配都是不能成功的。直到Tnext[j]和S[i]相比是才是最早有可能成功的。
Int KMP_Index(Sstring S,Sstring T,int pos)
{
i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{
If(j=0||S[i]=T[j])//j=0表示模式串已经退到起点了说明在这个位置彻底不可能了，
{ ++i; ++j; } //i必须下移,j回到1开始
Else j=next[j];
}
If(j>T[0]) return i-T[0];
Else return 0;
}
求next[j]的方法和原理
设尺肆羡k=next[j];那么T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1;
若Tj= =Tk,那么T1T2…Tk-1Tk= =Tj-k+1……Tj-2Tj-1Tj;
所以 next[j+1]=k+1=next[j]+1;且T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1已经是
最长雹弊的序列，所以k+1也是next[j+1]最长的
若Tj不等于Tk,那么就需要重找了。即…..Tj-1Tj ?,
T1T2….
所以next[j+1]首先=k=next[j]; 即…..Tj-1Tj ?,
T1T2…Tk-1.
若不相等，则next[j+1]=next[k]; 即…..Tj-1Tj ?,
T1T2….Tnext[k]-1
直到找到这样的序列， 即…..Tj-1Tj ?,
T1T2 ...To
那么，next[j+1]=next[next[j]]=next[next[next[j]]]…..=o+1;
Void get_next(Sstring T,int next[])
{
i=1; next[1]=0; j=0;//i表示当前求的next
While(i
{
if(j=0 | | T[i]=T[j])
{
++i;
++j;
next[i]=j;
}
Else j=next[j];
}
}
因为 next[ ] 在匹配过程中，若T[ j ]=T[ next[j] ];那么当 S[i]不等于T[j],
S[ i]肯定也不等于T[k= next[j] ];
所以 S[i]应直接与T[next[k]]比较，而我们通陵拍过将next[j]修正
为nextval[j]=next[next[j]];这样能使比较更少。
Void get_nextval(Sstring T,int nextval[])
{
i=1; nextval[1]=0; j=0;
while(i
{
if(j=0 || T[i]= T[j])
{
++i;
++j;
if(T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=next[j];
}
else
j=nextval[j];
}
空格串是指__由空格字符(ASCII值32)所组成的字符串，其长度等于 空格个数____。
在模试匹配KMP算法中所用失败函数f的定义中，为何要求p1p2……pf(j)为p1p2……pj两头匹配的真子串?且为最大真子串?
失败函数(即next)的值只取决于模式串自身，若第j个字符与主串第i个字符失配时，主串不回溯， 模式串用第k(即next[j])个字符与第i个相比，有‘p1…pk-1’=‘pj-k+1…pj-1’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中存在的多个k值，应取其中最大的一个。这样，因j-k最小，即模式串向右滑动的位数最小，避免因右移造成的可能匹配的丢失。
第4章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!
更多详情请点击：计算机考研：数据结构常用算法解析汇总
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
E. 什么叫计算机的算法
计算机的算法具有的特性：
1.有穷性。一个算法应包含有限的操作步骤，而不能是无限的。事实上"有穷性"往往指"在合理的范围之内"。如果让计算机执行一个历时1000年才结束的算法，这虽然拆带是有穷的，但超过了合理的限度，人们不把他视为有效算法。
2. 确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。算法中的每一个步骤应当不致被解释成不同的含义，而应是十分明确的。也就是说，算野旦法的含义应当是唯一的，而不应当产生"歧义性"。
3. 有零个或多个输入、所谓输入是指在执行算法是需要从外界取得必要的信息。
4. 有一个或旅脊芦多个输出。算法的目的是为了求解，没有输出的算法是没有意义的。
5.有效性。 算法中的每一个 步骤都应当能有效的执行。并得到确定的结果。
计算机算法简介：
算法必须具备以下性质:
(1)算法首先必须是正确的，即对于任意的一组输入，包括合理的输入与不合理的输入，总能得到预期的输出。如果一个算法只是对合理的输入才能得到预期的输出，而在异常情况下却无法预料输出的结果，那么它就不是正确的。
(2)算法必须是由一系列具体步骤组成的，并且每一步都能够被计算机所理解和执行，而不是抽象和模糊的概念。
(3)每个步骤都有确定的执行顺序，即上一步在哪里;下一步是什么，都必须明确，无二义性。
(4)无论算法有多么复杂，都必须在有限步之后结束并终止运行;即算法的步骤必须是有限的。在任何情况下，算法都不能陷入无限循环中。
一个问题的解决方案可以有多种表达方式;但只有满足以上4个条件的解才能称之为算法。
F. 计算机考研：数据结构常用算法解析(8)
第九章 查找
查找分成静态查找和动态查找，静态查找只是找，返回查找位置。而动态查找则不同，若查找成功，返回位置，若查找不成功，则要返回新记录的插入位置。也就是说，静态查找不改变查找表，而动态查找则会有插入操作，会改变查找表的。
不同的查找所采用的存储结构也不同，静态查找采用顺序表，而动码迟态查找由于经常变动，所以用二叉排序树，二叉平衡树、B-和B+。
静态查找有，顺序查找，折半查找，分块查找(索引顺序查找)
顺序查找(Sequential Search)是最简单的一种查找方法。
算法思路
设给定值为k，在表(R1 R2……Rn)中，从Rn即最后一个元素开始，查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k，则查找成功，返回记录序号i;否则，查找失败，返回0。
算法描述
int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//
{ int i;
r.data[0].key=k; //k存入监视哨//
i=r.len; //取表长//
while(r.data[i].key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧：先将k存入监视哨，若对某个i(≠0)有r.data[i].key=k，则查找成功，返回i;若i从n递减到1都无记录的key为k，i再减1为0时，必有r.data[0].key=k，说明查找失败，返回i=0。
平均查找成功长度ASL= ，而查找失败时，查找次数等于n+l。
折半查找算法及分析
当记录的key按关系≤或≥有序时，不管是递增的还是递减的，只要有序且采用顺序存储。
算法描述
int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空间存在时//
{ mid=(low+high)/2; //求当前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //调整上界，向左部查找//
else
low=mid+1; //调整下界，向右部查找//
}
return(0); //low>high，查找失败//
}
判定树：用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树，但他的叶子结点所在层次之差不超过1。所以，折半查找在查找成功时和给定值进行比笑困较的关键字个数至多为
ASL=
分块查找算法及分析
分块查找(Blocking Search)，又称索引顺序查找(Indexed Sequential Search)，是顺序查找方法的一种改进，目的也是为了提高查找效率。
1.分块
设记录表长为n，将表的n个记录分成b= 个块，每块s个记录(最后一块记录数可以少于s个)，即：
且表分块有序，即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。
2.建立索引
每块对应一索引项：
KeymaxLink
其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。
3.算法思路 分块索碰模念引查找分两步进行：
(1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)
(2)在块内顺序查找。(只能用顺序查找，块内是无序的)
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
G. 计算机考研：数据结构常用算法解析(7)
第七章：
对于无向图，e的范围是：
数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。
对于有向图，e的范围是：
图的各种存储结构
邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。
邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些薯早握点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。
在十字链睁历表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)又称为数组表示法
typedef struct
{ vextype vexs[maxn]; ∥顶点存储空间∥
adjtype A[maxn][maxn]; ∥邻接矩阵∥
int vexnum,arcnum; //图的顶点数和边数
GraphKind Kind; //图的类型
} mgraph;
2.邻接表(有向图和无向图和网)
typedef struct node ∥边
{ int adj; int w; ∥邻接点、权∥
struct node *next; ∥指向下一弧或边∥
}linknode;
typedef struct ∥顶点类型∥
{ vtype data; ∥顶点值域∥
linknode *farc; ∥指向与本顶点关联的第一条弧或边∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥顶点表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
边结点
datafirstarc
顶点结点
3.十字链表(有向图和有向网)
headvextaivexhlinktlinkinfo
边结点
datafirstinfirstout
顶点结点
4.邻接多重表(无向图)
markivexjvexilinkjlinkinfo
边结点
datafirstedge
顶点结点
有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。
顶点的度：
无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数
有向图：顶点V的度D(V)=ID(V)+OD(V)
强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量
“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个 连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是强连通的。
考研有疑问、不知道如何总结考研考点内容、不清楚数庆考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
H. 计算机算法是什么
问题一：什么叫算法？什么叫计算机算法？ 算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。�同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平方阶。
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
[font class=Apple-style-span style=font-weight: bold; id=bks_etfhxykd]算法 Algorithm [/font]
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：
1、有穷性： 一个算法必须保证执行有限步之后结束；
2、确切性： 算法的每一步骤必须有确切的定义；
3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
算法的设计要求
问题二：计算机算法是什么？ 在数学和计算机科学之中，算法为一个计算的具体步骤，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。
而程序算法是指:
人们使用计算机，就是要利用计算机处理各种不同的问题，而要做到这一点，人们就必须事先对各类问题进行分析，确定解决问题的具体方法和步骤，再编制好一组让计算机执行的指令即程序，交给计算机，让计算机按人们指定的步骤有效地工作。这些具体的方法和步骤，其实就是解决一个问题的算法。
例子:
如何用程序比较3个数字, 找出他们最大的那一个?
1) 输入A、B、C。
2) A与B中大的一个放入M A X中。
3) 把C与M A X中大的一个放入M A X中。
4) 输出M A X，M A X即为最大数。
这就是算法.
int max = a > b ? a : b;max = max > c ? max : c;最终max 中就是a,b,c中最大的值.
问题三：计算机算法是什么 个人觉得算法就是使用适合计算机计算的代码，告诉计算机如何解决问题；
也就是一种给计算机设计的解决特定问题的方法有时候一个计算机算法并不适合人类使用去解决同一个问题
问题四：计算机算法要素是什么 算法是指完成一个任务准确而完整的描述.也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据.
问题五：计算机算法指的是什么 计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。
�忧乐美 团队---半缘修道半缘女�为您解答
=====满意请采纳为满意答案吧====
问题六：计算机的算法具有哪些特性？ 一个算法必须具备以下性质： （1）算法首先必须是正确的，即对于任意的一组输入，包括合理的输入与不合理的输入，总能得到预期的输出。如果一个算法只是对合理的输入才能得到预期的输出，而在异常情况下却无法预料输出的结果，那么它就不是正确的。 （2）算法必须是由一系列具体步骤组成的，并且每一步都能够被计算机所理解和执行，而不是抽象和模糊的概念。 （3）每个步骤都有确定的执行顺序，即上一步在哪里，下一步是什么，都必须明确，无二义性。 （4）无论算法有多么复杂，都必须在有限步之后结束并终止运行，即算法的步骤必须是有限的。在任何情况下，算法都不能陷入无限循环中。 一个问题的解决罚案可以有多种表达方式，但只有满足以上4个条件的解才能称之为算法。
综上所述，我选A、B、E，个人感觉C也选，但我不确定，希望不要误导你。
最好根据上面的解释或是算法书自己看一下。
问题七：在计算机算法中，它们有什么区别 算法就是一种解决问题的方法,我的理解就是,面对一个问题,我们让计算机来解决这个问题,这种方法就是算法.
问题八：研究计算机算法对于编程有什么作用？ 让我来告诉你，算法通俗意义上来讲――就是解决一个问题的方法。据此而论，编写程序解决的任何一个问题都可以叫做算法。狭义上来讲研究算法就是在使用相同的计算资源的并解决同一个问题的情况下怎么样可以更加的节约资源，也就是说使计算速度更快。
拿一个例子来讲就是排序，我们现在了解到的算法有：冒泡，快速，插入，堆排序等等很多，在不同的输入数据规模的情况下采用不同的算法，因为可以节约计算资源。
问题九：计算机编程的算法是什么意思 平时说的算法就是数学上的计算方法，计算机中的算法是：解决问题的方法，不一定用数学方法（但大多都是数学方法），只要能通过计算机语言表达出来，达到最终目的的步骤都叫算法