【正文】 小生成樹的算法。1設(shè)有向圖用鄰接表表示,圖有n個頂點(diǎn),表示為1至n,試寫一個算法求頂點(diǎn)k的入度(11寫出圖的深度優(yōu)先搜索DFS算法的非遞歸算法。假設(shè)有向圖以鄰接表存儲，試編寫算法刪除弧的算法。試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑（ij）。設(shè)已給出圖的鄰接矩陣，要求將圖的鄰接矩陣轉(zhuǎn)化為鄰接表，試實(shí)現(xiàn)其算法。給出以十字鏈表作存儲結(jié)構(gòu)，建立圖的算法，輸入(i,j,v)其中i,j為頂點(diǎn)號，v為權(quán)值。即接受用戶輸入的(以其中之一為0標(biāo)志結(jié)束),對于每條這樣的邊,申請一個結(jié)點(diǎn),并插入到的單鏈表中,如此反復(fù),直到將圖中所有邊處理完畢。試編寫用鄰接表存儲該圖的算法。請寫出在后序線索樹上找給定結(jié)點(diǎn)p^ 的直接前驅(qū)q 的算法。其中，data存放結(jié)點(diǎn)的值；lc，rc為指向左、右孩子或該結(jié)點(diǎn)前驅(qū)或后繼的指針；ltag，rtag為標(biāo)志域，各值為：0，則lc，rc為指向左、右孩子的指針；值為1，則lc，rc為指向某前驅(qū)后繼結(jié)點(diǎn)的指針2設(shè)后序線索樹中結(jié)點(diǎn)構(gòu)造為(Ltag,Lchild,Data,Rchild,Rtag)。2寫出算法，求出中序線索二叉樹中給定值為x的結(jié)點(diǎn)之后繼結(jié)點(diǎn)，返回該后繼結(jié)點(diǎn)的指針。2已知中序線索二叉樹T右子樹不空。編寫構(gòu)造huffman 樹 的算法。試寫出算法，求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值。1設(shè)一棵二叉樹中各結(jié)點(diǎn)的值互不相同，其前序序列和中序序列分別存于兩個一維數(shù)組pre[1..n ]和mid[1..n ]中，試遍寫算法建立該二叉樹的二叉鏈表。1已知二叉樹以二叉鏈表存儲，編寫算法完成：對于樹中每一個元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。編寫算法計(jì)算二叉樹中各個結(jié)點(diǎn)的平衡因子。用C語言編寫二叉樹的排序程序。1二叉樹排序方法如下：（1）將第一個數(shù)據(jù)放在樹根。1叉樹用二叉鏈表存儲，任給一個二叉樹表示的四則運(yùn)算表達(dá)式，編寫算法，由該二叉樹輸出該表達(dá)式，若原表達(dá)式有括號亦加上。編寫先序遍歷二叉樹的非遞歸算法。編寫一算法，在二叉樹中查找值為x的結(jié)點(diǎn)，并打印值為x的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。叉樹用二叉鏈表存儲，編寫一算法，判別給定的二叉樹是否為完全二叉樹。叉樹用二叉鏈表存儲，寫一個算法交換各結(jié)點(diǎn)的左右子樹。知二叉樹用二叉鏈表存儲，寫出求二叉樹寬度的算法。sum+=x。void test(int amp。（2）寫出求解該遞歸函數(shù)的非遞歸算法。1已知求兩個正整數(shù)m與n的最大公因子的過程用自然語言可以表述為反復(fù)執(zhí)行如下動作：第一步：若n等于零，則返回m；第二步：若m小于n，則m與n相互交換；否則，保存m，然后將n送m，將保存的m除以n的余數(shù)送n。1已知Q是一個非空隊(duì)列，S是一個空棧。要求：（1）寫出循環(huán)隊(duì)列的類型定義；（2）寫出“從隊(duì)尾刪除”和“從隊(duì)頭插入”的算法。（請寫明算法的思想及必要的注釋）假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，如圖所示（編者略），請寫出相應(yīng)的入隊(duì)列和出隊(duì)列算法。已知棧的三個運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個結(jié)點(diǎn)有兩個域：ch和link，其中ch域?yàn)樽址愋?。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。規(guī)定：逆波蘭表達(dá)式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、*、/四種運(yùn)算。(注：算法中可調(diào)用棧操作的基本算法。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法。設(shè)計(jì)一個算法，利用棧的基本運(yùn)算返回指定棧中棧底元素。限定算法的時間復(fù)雜度為O（m+n+p），其中m、n和p分別為三個表的長度。1編寫一個算法來交換單鏈表中指針P所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)，HEAD是該鏈表的頭指針，P指向該鏈表中某一結(jié)點(diǎn)。例如：（7，10，10，21，30，42，42，42，51，70）將變作（7，10，21，30，42，51，70）。1在一個遞增有序的線性表中，有數(shù)值相同的元素存在。1已知p指向雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、llink、rlink三個域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。已知遞增有序的單鏈表A,B分別存儲了一個集合，請?jiān)O(shè)計(jì)算法以求出兩個集合A和B 的差集AB（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。要求：不得額外申請新的鏈結(jié)點(diǎn)。試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除（一個）最小值結(jié)點(diǎn)的（高效）算法。設(shè)L為單鏈表的頭結(jié)點(diǎn)地址，其數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)都是正整數(shù)且無相同的，設(shè)計(jì)一個將該鏈表整理成數(shù)據(jù)遞增的有序單鏈表的算法。已知LL2分別為兩循環(huán)單鏈表的頭結(jié)點(diǎn)指針，m,n分別為LL2表中數(shù)據(jù)結(jié)點(diǎn)個數(shù)。設(shè)計(jì)一個算法從順序表L中刪除所有值為x的元素設(shè)計(jì)一個算法從順序表L中刪除所有值為x到y(tǒng)之間（x鏈表：假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。（3）若找不到將其插入表中并使表中元素仍遞增有序。要求設(shè)計(jì)一算法完成：（1）用最少時間在表中查找數(shù)值為x的元素。請?jiān)O(shè)計(jì)一個算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性。第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)分類題目線性表順序表：設(shè)有一元素為整數(shù)的線性表L=(a1,a2,a3,?,an),存放在一維數(shù)組A[N]中,設(shè)計(jì)一個算法,以表中an作為參考元素,將該表分為左、右兩部分,其中左半部分每個元素小于等于an,右半部分每個元素都大于an, an位于分界位置上(要求結(jié)果仍存放在A[N]中)。設(shè)線性表存于A[1..size]的前num各分量中，且遞增有序。線性表(a1,a2,a3,?,an)中元素遞增有序且按順序存儲于計(jì)算機(jī)內(nèi)。（2）若找到將其與后繼元素位置相交換。已知數(shù)組A[0:n1]的元素類型為int，試設(shè)計(jì)算法將其調(diào)整為左右兩個部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。要求設(shè)計(jì)一算法，用最快速度將兩表合并成一個帶頭結(jié)點(diǎn)的循環(huán)單鏈表。設(shè)計(jì)算法將一個帶頭結(jié)點(diǎn)的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn)）。設(shè)L為單鏈表的頭結(jié)點(diǎn)地址，請寫一算法，將鏈表中數(shù)據(jù)域值最小的那個鏈結(jié)點(diǎn)移到鏈表的最前面。已知兩個單鏈表A和B,其頭指針分別為heada和headb，編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。已知一個單鏈表中每個結(jié)點(diǎn)存放一個整數(shù)，并且結(jié)點(diǎn)數(shù)不少于2，請?jiān)O(shè)計(jì)算法以判斷該鏈表中第二項(xiàng)起的每個元素值是否等于其序號的平方減去其前驅(qū)的值，若滿足則返回ture，、兩個整數(shù)序列A=a1,a2,a3,?,am和B=b1,b2,b3,?,bn已經(jīng)存入兩個單鏈表中，設(shè)計(jì)一個算法，判斷序列B是否是序列A的子序列。1設(shè)有一個由正整數(shù)組成的無序單鏈表，編寫完成下列功能的算法：（1）找出最小值結(jié)點(diǎn)，且打印該數(shù)值；（2）若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的數(shù)值交換；（3）若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除。若存儲方式為單鏈表，設(shè)計(jì)算法去掉數(shù)值相同的元素，使表中不再有重復(fù)的元素。1設(shè)有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試編寫能實(shí)現(xiàn)下列功能的算法 ：（要求用最少的時間和最小的空間）(1)確定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計(jì)算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的數(shù)有5個）；(2)在單鏈表將比正整數(shù)x小的數(shù)按遞減次序排列；(3)將正整數(shù)（比）x大的偶數(shù)從單鏈表中刪除。1．已知三個帶頭結(jié)點(diǎn)的線性鏈表A、B和C中的結(jié)點(diǎn)均依元素值自小至大非遞減排列（可能存在兩個以上值相同的結(jié)點(diǎn)），編寫算法對A表進(jìn)行如下操作：使操作后的鏈表A中僅留下三個表中均包含的數(shù)據(jù)元素的結(jié)點(diǎn)，且沒有值相同的結(jié)點(diǎn)，并釋放所有無用結(jié)點(diǎn)。棧和隊(duì)列設(shè)計(jì)一個算法，利用棧的基本運(yùn)算將指定棧中的內(nèi)容逆轉(zhuǎn)。設(shè)有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區(qū)[O..maxsize1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，?，an,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai≠1時，將ai進(jìn)棧；當(dāng)ai=1時，輸出棧頂整數(shù)并出棧。設(shè)表達(dá)式以字符形式已存入數(shù)組E[n]中，‘’為表達(dá)式的結(jié)束符，試寫出判斷表達(dá)式中括號（‘（’和‘）’）是否配對的C語言描述算法：EXYX(E)。)從鍵盤上輸入一個逆波蘭表達(dá)式，用偽碼寫出其求值程序。例如：234 34+2*$寫出一個算法，判定所給的操作序列是否合法。設(shè)計(jì)一個算法，判斷一個算術(shù)表達(dá)式中的括號是否配對。請利用兩個棧S1和S2來模擬一個隊(duì)列。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個運(yùn)算：enqueue:插入一個元素入隊(duì)列； dequeue:刪除一個元素出隊(duì)列；queue_empty：判隊(duì)列為空。如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。1在一個循環(huán)鏈隊(duì)中只有尾指針（記為rear，結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data，指針域next），請給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過程。僅用隊(duì)列和棧的操作編寫一個算法，將隊(duì)列Q中的所有元素逆置。（1）將上述過程用遞歸函數(shù)表達(dá)出來（設(shè)求x除以y的余數(shù)可以用x MOD y 形式表示）。1試將下列遞歸過程改寫為非遞歸過程。sum){ int x； scanf(x)；if(x=0)sum=0 else {test(sum)。} printf(sum)； }樹和二叉樹二叉樹用二叉鏈表存儲，寫一個算法將二叉樹中的葉子結(jié)點(diǎn)按從右至左的順序建立一個單鏈表。所謂寬度是指在二叉樹的各層上，具有結(jié)點(diǎn)數(shù)最多的那一層上的結(jié)點(diǎn)總數(shù)。二叉樹用二叉鏈表存儲，若結(jié)點(diǎn)的左孩子的數(shù)據(jù)域的值大于右孩子數(shù)據(jù)域的值，則交換其左右子樹。個結(jié)點(diǎn)的完全二叉樹以一維數(shù)組為存儲結(jié)構(gòu)，編寫一非遞歸算法實(shí)現(xiàn)對該樹的先序遍歷。編寫中序遍歷二叉樹的非遞歸算法。編寫后序二叉樹的非遞歸算法。1有n個結(jié)點(diǎn)的完全二叉樹存放在一維數(shù)組A[1..n]中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹，根由tree指向。（2）將隨后讀入的數(shù)據(jù)與樹根中的數(shù)據(jù)相比較，若比樹根大，則置于右子樹，反之則置于左子樹，建成一棵二叉樹；（3）利用中序遍歷打印排序結(jié)果。1二叉樹結(jié)點(diǎn)的平衡因子（bf）定義為該結(jié)點(diǎn)的左子樹高度與右子樹高度之差。1設(shè)計(jì)算法：統(tǒng)計(jì)一棵二叉樹中所有葉結(jié)點(diǎn)的數(shù)目及非葉結(jié)點(diǎn)的數(shù)目。1試編寫算法，對一棵以孩子—兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個數(shù)。1試設(shè)計(jì)一個算法打印出由根結(jié)點(diǎn)出發(fā)到達(dá)葉結(jié)點(diǎn)的所有路徑。2給定一組項(xiàng)及其權(quán)值，假定項(xiàng)都存放于二叉樹的樹葉結(jié)點(diǎn)，則具有最小帶權(quán)外部路徑長度的樹稱為huffman 樹。2已知一中序線索二叉樹,寫一算法完成對它的中序掃描。設(shè)計(jì)算法，將S所指的結(jié)點(diǎn)作為T的右子樹中的一個葉子結(jié)點(diǎn)插入進(jìn)去，并使之成為T的右子樹的（中序序列）第一個結(jié)點(diǎn)（同時要修改相應(yīng)的線索關(guān)系）。線索樹中結(jié)點(diǎn)結(jié)構(gòu)為：（ltag,lc,data,rc,rtag）。其中:Ltag,Rtag 值為0時,Lchild、Rchild 分別為兒子指針；否則分別為直接前驅(qū),直接后繼的線索。圖設(shè)無向圖G有n個頂點(diǎn)，m條邊。（設(shè)頂點(diǎn)值用1～n或0～n1編號）已知有向圖有n個頂點(diǎn),請寫算法,根據(jù)用戶輸入的偶對建立該有向圖的鄰接表。提示：先產(chǎn)生鄰接表的n個頭結(jié)點(diǎn)（其結(jié)點(diǎn)數(shù)值域從1到n）。設(shè)有向G圖有n個點(diǎn)(用1,2,?,n表示),e條邊,寫一算法建立有向圖的逆鄰接表。編寫算法，將圖的鄰接矩陣存儲改為鄰接表的存儲。已知無向圖采用鄰接表存儲方式，試寫出刪除邊（i，j）的算法。假設(shè)有向圖以十字鏈表存儲，試編寫算法，插入弧。1已知帶權(quán)圖用鄰接矩陣表示，編寫函數(shù)實(shí)現(xiàn)用Kruskal算法構(gòu)造最小生成樹的算法。1編寫函數(shù)實(shí)現(xiàn)從指定頂點(diǎn)到其余各頂點(diǎn)的最短路徑的Dijkstra 算法。查找和排序設(shè)計(jì)一個二分查找的遞歸算法。實(shí)現(xiàn)散列表的相關(guān)算法（1）給定一個序列，和散列函數(shù)，并利用線性探測再散列處理沖突，建立散列表。實(shí)現(xiàn)二叉查找樹的相關(guān)算法（1）給定序列，創(chuàng)建一二叉查找樹（2）判定一棵樹是否為二叉查找樹（3）采用遞歸和非遞歸算法，查找某一個關(guān)鍵字（4）編寫函數(shù)，刪除找某一個關(guān)鍵字編寫函數(shù)實(shí)現(xiàn)直接插入算法、希爾排序算法。編寫函數(shù)實(shí)現(xiàn)堆排序算法。1編寫函數(shù)實(shí)現(xiàn)基數(shù)排序算法。第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目（限1 人完成）任務(wù)：參加運(yùn)動會有n個學(xué)校，學(xué)校編號為1……n。項(xiàng)目編號為男子1……m，女子m+1……m+w。（m功能要求：1)可以輸入各個項(xiàng)目的前三名或前五名的成績； 2)能統(tǒng)計(jì)各學(xué)?？偡郑?)可以按學(xué)校編號或名稱、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；4)可以按學(xué)校編號查詢學(xué)校某個項(xiàng)目的情況；可以按項(xiàng)目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。進(jìn)行程序測試，以保證程序的穩(wěn)定。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計(jì)程序完成功能；（限1 人完成）功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個數(shù)。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英