數(shù)據(jù)結(jié)構(gòu)課程設(shè)計分類題目

1、線性表順序表：K設(shè)有一元素為整數(shù)的線性表“匕,g遼宀,存放在一維數(shù)組AN中設(shè)計一個算法, 以表中盟作為參考元素，將該表分為左、右兩局部其中左半局部每個元素小于等于右半 局部每個元素都大于5 d位于分界位置上要求結(jié)果仍存放在AN中人2一設(shè)線性表存于Al"涮的前num各分量中,且遞增有序。請設(shè)計一個算法，將x插入 到線性表的適當位置上，以保持線性表的有序性*3. 線性表仏 如曲"山中元素遞地有序且按順序存儲于計算機內(nèi)。要求設(shè)計一算法完成: Q用最少時間在表中查找數(shù)值為X的元素6C刃假設(shè)找到將共與后維元素位置相交換。3 ：假設(shè)找不到將其插入表中并使表中元素仍遞增有序o4己知數(shù)組A

2、COlnl的元素類型為int,試設(shè)計算法將其調(diào)整為左右兩個局部左邊所有 元素為奇數(shù)耿右邊所有元素為偶數(shù)。5、設(shè)計一個算法從順序表L中刪除所有值為x的元素6、設(shè)計一介算法從順序表L中刪除所有值為x到y(tǒng)之間皿可?的元素 *4丫 <©鏈表： 上工1>假設(shè)有兩個按元素值遞增次序排列的線性表,均以單鏈表形式存儲6請編寫算法將這兩' 個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，:并要求利用原來兩個單鏈表的結(jié)點存 放歸并后的單鏈表，2. 己知LI、L2分別為兩循環(huán)單鏈表的頭結(jié)點指針 m,n分別為LX L2表中數(shù)據(jù)結(jié)點個數(shù)。 要求設(shè)計算法.用最快速度將兩表合并成個帶頭結(jié)點的循

3、壞單鏈表A了 r£ f FGF；3. 設(shè)L為單鏈表的頭結(jié)點地址F其數(shù)據(jù)結(jié)點的數(shù)據(jù)都是正整數(shù)且無相同的,設(shè)計一個將該 鏈表整理成數(shù)據(jù)遞增的有序單鏈表的算法右5、設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B級G,其中B表的 結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值夫于零的結(jié)點C鏈表扎的元素類型 為整型，要求B/C表利用A表的結(jié)點人6、試編寫在帶頭結(jié)點的單鏈表中刪除K一個最歩值結(jié)點的高效算法g7、設(shè)L為單鏈表的頭結(jié)點地址，請寫一算血 將鏈表中數(shù)據(jù)域值最小的那個鏈結(jié)點移到鏈 表的最前面臨要求;不得額外申請新的鏈結(jié)啟8、己知兩個單鏈表A和民其頭指針分別為hada和h

4、eadb,編寫一個過程從單鏈表A申刪 除自第i個元素起的共 山 個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前宴9、遞增有序的單鏈表A,B分別存僻了亠個集紜請設(shè)計算法以求岀兩個集合A和B的 姝A-B ®儀由程A中出現(xiàn)而忝津且中出M云素所構(gòu)翩擄佑九并図同粹冊絨存儲, 同時返回該集音的元素個數(shù).5；10、己知r卒單鏈表中每個結(jié)點存放一個整數(shù)，并且結(jié)點數(shù)不少于2,請設(shè)計算法以判斷 該鏈表中第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)的值訂假設(shè)滿足那么返回丁 V*9%9*"tiire> 否那么返回 false. . r . . . . 11、兩個整數(shù)序列A=alt

5、：a2f a3,:am和B=bl, b2, b3,bn已經(jīng)存入兩個單鏈表中箕設(shè)計一 金算法；判斷序列B是否是序列A的子序列o12、：p指向雙向循壞鏈表中的一個結(jié)點其結(jié)點結(jié)構(gòu)為data. Llink、Fink三個域, 寫出算法change p,交換p所指向的結(jié)點和它的前綴結(jié)點的顧序.13、設(shè)有一個由正整數(shù)組成的無序單鏈表'編寫莞成以下功能的算法工1找出最小值結(jié)點；且打印該數(shù)值；2假設(shè)該數(shù)值是奇數(shù)，那么將其與直接后繼結(jié)點的數(shù)值交換；2交假設(shè)該數(shù)值是偶數(shù)，那么將其直接后繼結(jié)點刪除和14、在一個遞增有序的線性表中，有數(shù)值相同的元素存在。假設(shè)存儲方式為單鏈表，設(shè)計算法 去掉數(shù)值相同的元素，使表中

6、不再有重復的元素。例如j 広10, ：10, 21, ：30, 42, 42 . 42, 51, 70?將變作7, 10, 21, 30, 42, 51, 70；15、設(shè)有一個正整數(shù)序列組成的有序單鏈表按遞增次序有序，且允許有相等的整數(shù)存在* 試編寫能實現(xiàn)以下功能的算法：要求用最少的時間和最小的空閭確麗在序列申比正整數(shù)&大的數(shù)看幾個相同的數(shù)只計負一洛 如序列.20> 20,17,16, 15/15,11,10, 8, £ 7, 5. 4中比 10 夫的數(shù)有 5個；2在單鏈表將比正鹽數(shù)x小的數(shù)按遞減次序排列；inn 將正整數(shù)4比川夫的偶數(shù)從單鏈表中刪除。16、編寫一個算法

7、來交換單鏈表中指針P所指結(jié)點身其后繼結(jié)點，HEAD是該鏈表的頭指針, P指向該璉表中某一結(jié)點°斤lial17；. B知三個帶頭結(jié)點的線性鏈表A, B和C中的結(jié)點均依元素值自小至夫非遞減排列可 能存在兩個以上值相同的結(jié)點?編寫算法對A表進行如下操作：使操作后的鏈表A中僅留 卞三個表中均包含的數(shù)據(jù)元素的結(jié)點，且沒有值相同的結(jié)點趴并釋放所有無用結(jié)點.限定算 法的時間復雜度為0 nrhl+pT其車m、n和衛(wèi)分別為三個表的長度©棧和隊列 L.設(shè)計一個算法，利用棧的根本運算將指定棧中的內(nèi)容逆轉(zhuǎn)也2、設(shè)計一個算法，利用棧的根本運算返回指定棧中棧底元素。3、設(shè)有兩個棧Si,0都采用順序棧方

8、式，并且共享一個存儲區(qū)0. - maxsize-lL為了盡量利 用空間，減少溢出的可能.可采用棧頂相向廠迎面增長的存僻方式。試設(shè)訐S對空有關(guān)入棧 和出棧的操作算法§4、設(shè)從鍵盤輸入一整數(shù)的序列:如隔as,，比,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的 整數(shù)，當辺亠1時將亦進棧；Ma 1時片輸出棧頂整數(shù)并出棧。算法應對異常情況入 棧滿等工給出相應的信息電4設(shè)表達式以字符形式已存入數(shù)組EM中為表達式的結(jié)束符，試寫出判斷表達式中 括號和是否配對的C語言描述算法：EXYX(E)算法中可調(diào)用棧操作的基M氐)5、從犍盤上輸入1個逆波蘭表達式用偽碼寫出其求值程序-規(guī)定：逆波蘭表達式的長度. 不超過：短

9、以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔二操作符只可能有2皐*、/四種 運算。例如躍234 34+2*$6、寫出f 算法，:判定所給的操作序列是否合法孕假設(shè)合法，返回truer否那么返回false (假 定被判定的操作序列已存入一維數(shù)組中)。，:7“設(shè)計r冷算法，判斷一個算術(shù)表達式中的括號是否配對。算術(shù)表達式保存在帶頭結(jié)點的 單循壞鏈表中.每個結(jié)點有兩個域；eh和link,其中品域為字符類型、8. 請利用兩個棧S1和S2來模擬一個隊列.己知棧的蘭個運算定叉如艮PUSH(ST,x)：元素 r.2A 芻x A ST g； POP (ST, x): ST棧頂元素出棧,賦給變量心Sempty (ST)

10、:判ST；棧是否為空唆 那么如何剎用橫的運昴岡現(xiàn)達虞列的三個運龜由詢曄嗨:質(zhì)入嚴木茹素入凰預h趣觸如! 刪除一個元素出隊列:queueempty：判隊列為空盤(請寫明算法的思想及必要的注釋)9. 假設(shè)以帯頭結(jié)點的循環(huán)鏈表表示隊列并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針， 如下圖(編者略/請寫出相應的入隊列和出隊列算法。10. 如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求(D寫出循環(huán)隊列的類型定義：(2)寫出童從隊尾刪除"和餵從隊頭插入的算法電11. 在一個循環(huán)鏈隊中貝有尾指針(乜為rear結(jié)點結(jié)構(gòu)為數(shù)據(jù)域data,指針域next), 請給出這種隊列的入隊和出隊操作的實現(xiàn)過

11、程事12. 己知Q是一個非空隊列.S是一個空棧勺僅用隊列和棧的操作編寫一個算法，將隊列Q 中的所宥元素逆置。13. 求兩個正整數(shù)m與II的最犬公因子的過程用自然語言可以表述為反復執(zhí)行如卞動作= 第一步廠假設(shè)n等于零，那么返回眄 第二步:善m小于m那么m身n相宜交換;杏那么總:保存m 然后將n送m,將保存的m除以n的余數(shù)送M£1?將上述過程用遞歸函數(shù)表達出來C設(shè)求x除以y的余數(shù)可以用次MOD y形武表示人 (2)寫出求解該遞歸函數(shù)的非遞歸算法° p 14. 試將以下遞歸過程改寫為非遞歸過程。void test (int: &sum) int x；scanf(x)；:i

12、f (x=0) sum=0 else test (sum)sum+=X7卜 printf (sum) ；.樹和二叉樹U二叉樹用二叉鏈表存儲，寫一個算法將二叉樹中的葉子結(jié)點按從右至左的順序建立f 單碎；2知二叉樹用二叉鏈表存儲，寫出求二叉樹寬度的算法.所謂寬度是指在二叉樹的各層上, 具有結(jié)點數(shù)最多的那一層上的結(jié)點總數(shù)。3、叉樹用二叉鏈表存儲，寫一個算法交換各結(jié)點的左右子樹。4、二叉樹用二叉鏈表存儲？假設(shè)結(jié)點的左孩子的數(shù)據(jù)域的值犬于右孩子數(shù)據(jù)域的值那么交換 其左右子松5、6s叉樹用二叉鏈表存儲，：編寫亠算法,判別給定的二叉樹是否為完全二叉樹?個結(jié)點的完全二叉樹以一維數(shù)組為存儲結(jié)構(gòu),編寫非遞歸算法實

13、現(xiàn)對該樹的先序遍 歷i編寫一算法在二叉樹中查找值為X的結(jié)點，并打印值為X的結(jié)點的所有祖先結(jié)髭U!編寫中序遍歷二叉樹的非遞歸算法右編寫先序遍歷二叉樹的非遞歸算法10、編寫后序二叉樹的非遞歸負法魚11、叉樹用二叉鏈表存儲，任給一個二叉樹表示的四那么運算表達式，編寫算法，由該二叉樹 輸出該表達式,著原表達式有括號亦加上12、有n個結(jié)點的完全U叉樹存放在一維數(shù)組Al.n中試據(jù)此建立;一棵用二叉鏈表表示 的二叉樹根由tree指向*13、二叉樹排序方法如下：(1) 將第一個數(shù)據(jù)放在樹根.(2) 將隨后讀入的數(shù)據(jù)與樹根中的數(shù)據(jù)相比擬,.假設(shè)比樹根戈：那么置于右子樹，反之那么 置于左子樹建成一棵二叉樹；(3)

14、 利用中序遍歷打印排序結(jié)果-用C語言編寫二叉樹的排序程序“14、二叉樹結(jié)點的平衡因子(bf)定義為該結(jié)點的左子樹高度與右子樹高度之差。編寫算法 訐算二叉樹中辛令結(jié)點的平衡因長15設(shè)計算法丫統(tǒng)計一棵二叉樹申所有葉結(jié)點的數(shù)目及非葉結(jié)點的數(shù)目。心己知二叉樹以二叉鏈表存儲廠編寫算法完成對于樹中每一個元素值為裏的結(jié)點復，刪去 以它為根的子樹，并釋放相應的空歐17試編寫算法，對一棵以孩子一兄弟鏈表表示的樹統(tǒng)計葉子的個數(shù)。18、設(shè)r棵二叉樹中各結(jié)點的值互不相同卜其前序序列和中序序列分別存于兩個一維數(shù)組 preL小和midtL . n 申，試遍寫算法建立該二叉樹的二叉鏈表乜19、試設(shè)訐一個算法打印出由根結(jié)點出

15、發(fā)到達葉結(jié)點的所看路徑。20、試寫出算法?求任意二叉樹中第-條最長的路注長度,并輸出此路徑上各結(jié)點的值。21、給定一組項及其權(quán)值復假定項都存放于二叉樹的樹葉結(jié)點,那么具有最小帶權(quán)外部路徑長 度的樹稱為huff man樹。編寫構(gòu)造huff man樹的算法®22i :一中序線索二叉樹寫一算法完成對它的中序掃描厲23中序線索二叉樹T右子樹不空。設(shè)計算法，將S所指的結(jié)點作為T的右子樹中的一 個葉孑結(jié)點插入進去并使之成為T的右子樹的(中序序列)第一個結(jié)點同時要修改相應 的線索關(guān)系I1¥24. 寫出算法求出中序線索二叉樹中給定值為x的結(jié)點之后繼結(jié)點,返回孩后継結(jié)點的指針°線索

16、樹中結(jié)點結(jié)構(gòu)為:(ltag, lc, data, re, rtag)®其中氏data存放結(jié)點的M; lc» re 為指向左.右孩子或該結(jié)點前驅(qū)或后繼的指針：班詢h屈為標志域，各值為：0 m：ic, re為指向左右孩子的指針;值為1那么g re為指向某前驅(qū)后繼結(jié)點的指針25、鍍后序妁蠢材申緒點構(gòu)猊觸無，詛盟些理與RQKi ld»舉唧».奐機匚坦筋僅為、 O At誠五4&嗣迅班別疝叨喻h咅那么涵另直蕨斶，左癒繼的線為 無諭社 后序線索樹上找給定結(jié)點p：的直接前驅(qū)誼的算法叭1. 設(shè)無向圖G有n個頂點八m條邊。試編寫用鄰接表存儲該圖的算法設(shè)頂點值用Kn

17、戒Ur注T.覇號2有向圖有n個頂點;請寫算法,根據(jù)用戶輸入的偶對建立該有向圖的鄰接表。即接受 用戶輸入的vvjm其中之一為0標志結(jié)束人對于每條這樣的邊，申請一個結(jié)點?并插入 到的單鏈表中如此反龍直到將圖中所有邊處理完畢提示:先產(chǎn)生鄰接衣的忑個頭結(jié)點其 結(jié)點數(shù)值域從到迫七3、給出以十字鏈表作存儲結(jié)構(gòu)建僉圖的算法相輸入® j ®其中id為頂點號宀為權(quán)值。4. 設(shè)有向G圖有n個點用h2 rn表示心條邊，寫一算法建立有向圖的逆鄰接表。5、6、7>設(shè)已給出圖的鄰接矩陣，要求將圖的鄰接矩陣轉(zhuǎn)化為鄰接表，試實現(xiàn)其算法， 編寫算法,將圖的鄰接矩陣存儲改為鄰接表的存儲。試寫一算法，判斷

18、以鄰接表方式存儲的有向圖中是杏存在由頂點哲到頂點礙的路徑 8己知無向圖采用鄰接表存儲方式,.試寫出刪除邊訂3的算法牛9、假設(shè)有向圖以鄰接表存儲，試編寫算法刪除弧%碇的算法。10i假設(shè)有向圖以十字鏈表存儲,試編寫算法，插入弧V沢12、設(shè)有向圖用鄰接表表示，圖有n個頂馬表示為1至n,試寫一個算法求頂鳥k的入度 lXk3 :14*15；16,1旅13. 寫出圖的深度優(yōu)先搜索DFS算法的非遞歸算激 帶權(quán)圖用鄰接矩陣表示,.編習函數(shù)實現(xiàn)用Kruskal 法構(gòu)造最小生成樹的算法" 編寫函數(shù)實現(xiàn)用Prim算法構(gòu)造最小生成樹的竟法。編寫函數(shù)實現(xiàn)從指定頂點到其余各頂點的最短路徑的Dijkstra算法。實現(xiàn)圖的拓撲排序算法查找和排序k設(shè)計一個二分查找的遞歸算法牡2、設(shè)計一個會法，利用二分查找算法在一個有序表中插入一個元素&并保持表的有序性。3、實現(xiàn)散列表的相關(guān)算法(1) 給定一個序列和散列函數(shù),：并利用線性探測再散列處理沖突，建立