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也選，但我不確定，希望不要誤導你。
最好根據上面的解釋或是演算法書自己看一下。
問題七：在計算機演算法中，它們有什麼區別 演算法就是一種解決問題的方法,我的理解就是,面對一個問題,我們讓計算機來解決這個問題,這種方法就是演算法.
問題八：研究計算機演算法對於編程有什麼作用？ 讓我來告訴你，演算法通俗意義上來講――就是解決一個問題的方法。據此而論，編寫程序解決的任何一個問題都可以叫做演算法。狹義上來講研究演算法就是在使用相同的計算資源的並解決同一個問題的情況下怎麼樣可以更加的節約資源，也就是說使計算速度更快。
拿一個例子來講就是排序，我們現在了解到的演算法有：冒泡，快速，插入，堆排序等等很多，在不同的輸入數據規模的情況下採用不同的演算法，因為可以節約計算資源。
問題九：計算機編程的演算法是什麼意思 平時說的演算法就是數學上的計算方法，計算機中的演算法是：解決問題的方法，不一定用數學方法（但大多都是數學方法），只要能通過計算機語言表達出來，達到最終目的的步驟都叫演算法