周《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計任務(wù)書

1、沈陽工程學院課程設(shè)計任務(wù)書課程設(shè)計題目： 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計系 別信息工程系班級學生姓名 學號指導教師 職稱課程設(shè)計進行地點：任務(wù)下達時間：年月日起止日期：年 月 日起一至年月日止教研室主任年月日批準一、課程設(shè)計的原始資料及依據(jù)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計是在完成數(shù)據(jù)結(jié)構(gòu)理論課程學習之后進行的一個綜合性的實踐教學環(huán)節(jié)，是對課程理論和課程實驗的一個補充通過課程設(shè)計，培養(yǎng)學生綜合運用已學過的理論和技能去分析和解決實際問題的能力，并使所學知識得到進一步鞏固、深化和擴展.二、課程設(shè)計主要內(nèi)容及要求設(shè)計內(nèi)容：1、 設(shè)有一元素為整數(shù)的線性表 L=(a1,a2,a3；,an)，存放在一維數(shù)組AN中，設(shè)計 一個

2、算法，以表中an作為參考元素，將該表分為左、右兩部分，其中左半部分每 個元素小于等于an,右半部分每個元素都大于an, an位于分界位置上(要求結(jié) 果仍存放在AN中).2、 設(shè)線性表存于A1.size的前num各分量中，且遞增有序.請設(shè)計一個算法， 將x插入到線性表的適當位置上，以保持線性表的有序性.3、 線性表(a1,a2,a3；,an)中元素遞增有序且按順序存儲于計算機內(nèi).要求設(shè)計一 算法完成：4、用最少時間在表中查找數(shù)值為x的元素.5、若找到將其與后繼元素位置相交換.6 若找不到將其插入表中并使表中元素仍遞增有序.7、已知數(shù)組A0:n-1的元素類型為int,試設(shè)計算法將其調(diào)整為左右兩個部

3、分， 左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù).8、 設(shè)計一個算法從順序表L中刪除所有值為x的元素9、 設(shè)計一個算法從順序表L中刪除所有值為x到y(tǒng)之間(x<=y)的元素10、假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點存放歸并后的單鏈表.11、已知L1、L2分別為兩循環(huán)單鏈表的頭結(jié)點指針，m,n分別為L1、L2表中數(shù)據(jù)結(jié)點個數(shù).要求設(shè)計一算法，用最快速度將兩表合并成一個帶頭結(jié)點 的循環(huán)單鏈表.12、設(shè)L為單鏈表的頭結(jié)點地址，其數(shù)據(jù)結(jié)點的數(shù)據(jù)都是正整數(shù)且無相同的，設(shè)計一個將該鏈表整理成

4、數(shù)據(jù)遞增的有序單鏈表的算法.13、設(shè)計算法將一個帶頭結(jié)點的單鏈表 A分解為兩個具有相同結(jié)構(gòu)的鏈表 B、 C,其中B表的結(jié)點為A表中值小于零的結(jié)點，而 C表的結(jié)點為A表中值大 于零的結(jié)點（鏈表A的元素類型為整型，要求 B、C表利用A表的結(jié)點）.14、試編寫在帶頭結(jié)點的單鏈表中刪除（一個）最小值結(jié)點的（高效）算法 .15、設(shè)L為單鏈表的頭結(jié)點地址，請寫一算法，將鏈表中數(shù)據(jù)域值最小的那 個鏈結(jié)點移到鏈表的最前面.要求：不得額外申請新的鏈結(jié)點.16、已知兩個單鏈表A和B,其頭指針分別為heada和headb,編寫一個過程 從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到 單鏈表B的

5、第j個元素之前.17、已知遞增有序的單鏈表A,B分別存儲了一個集合，請設(shè)計算法以求出兩個集合A和B的差集A-B （即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成 的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù).18、已知一個單鏈表中每個結(jié)點存放一個整數(shù)，并且結(jié)點數(shù)不少于2,請設(shè)計算法以判斷該鏈表中第二項起的每個元素值是否等于其序號的平方減去 其前驅(qū)的值，若滿足則返回ture，否則返回false.19、兩個整數(shù)序列 A=a1,a2,a3,am和B=b1,b2,b3,bn已經(jīng)存入兩個單 鏈表中，設(shè)計一個算法，判斷序列 B是否是序列A的子序列.20、已知p指向雙向循環(huán)鏈表中的一個結(jié)點，其結(jié)點結(jié)構(gòu)

6、為data、llink、rlink三個域，寫出算法change（p）,交換p所指向的結(jié)點和它的前綴結(jié)點的 順序.21、設(shè)有一個由正整數(shù)組成的無序單鏈表，編寫完成下列功能的算法：（1）找出最小值結(jié)點，且打印該數(shù)值；（2）若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換；（3）若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除.22、在一個遞增有序的線性表中，有數(shù)值相同的元素存在.若存儲方式為單鏈表，設(shè)計算法去掉數(shù)值相同的元素，使表中不再有重復的元素.例如：（7,10，10，21, 30，42，42，42，51，70）將變作（7，10，21，30，42，51, 70）.23、編寫一個算法來交換單鏈表中指針 P所

7、指結(jié)點與其后繼結(jié)點，HEAD是該 鏈表的頭指針，P指向該鏈表中某一結(jié)點.24、已知三個帶頭結(jié)點的線性鏈表 A、B和C中的結(jié)點均依元素值自小至大非 遞減排列（可能存在兩個以上值相同的結(jié)點），編寫算法對A表進行如下操 作：使操作后的鏈表A中僅留下三個表中均包含的數(shù)據(jù)元素的結(jié)點，且沒有 值相同的結(jié)點，并釋放所有無用結(jié)點.限定算法的時間復雜度為 0（ m+n+p, 其中m n和p分別為三個表的長度.25、設(shè)計一個算法，利用棧的基本運算將指定棧中的內(nèi)容逆轉(zhuǎn).26、設(shè)計一個算法，利用棧的基本運算返回指定棧中棧底元素27、設(shè)有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區(qū) O.maxsize-1,為了

8、盡量利用空間，減少溢出的可能，可采用棧頂相向， 迎面增長的存儲方式試設(shè)計S1,S2有關(guān)入棧和出棧的操作算法.28、設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實現(xiàn)：用 棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai工-1時，將ai進棧；當ai=-1時，輸出棧頂 整數(shù)并出棧算法應對異常情況(入棧滿等)給出相應的信息29、設(shè)表達式以字符形式已存入數(shù)組 En中，#'為表達式的結(jié)束符，試寫 出判斷表達式中括號(和)是否配對的C語言描述算法：EXYX(E); (注：算法中可調(diào)用棧操作的基本算法.)30、從鍵盤上輸入一個逆波蘭表達式，用偽碼寫出其求值程序規(guī)定：逆波蘭 表達式的長度不超過一行，以$

9、符作為輸入結(jié)束，操作數(shù)之間用空格分隔，操 作符只可能有+、-、*、/四種運算例如：234 34+2*$31、寫出一個算法，判定所給的操作序列是否合法.若合法，返回true，否 則返回false (假定被判定的操作序列已存入一維數(shù)組中).32、設(shè)計一個算法，判斷一個算術(shù)表達式中的括號是否配對.算術(shù)表達式保存在帶頭結(jié)點的單循環(huán)鏈表中，每個結(jié)點有兩個域：ch和link，其中ch域為字符類型.33、請利用兩個棧S1和S2來模擬一個隊列.已知棧的三個運算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x): ST棧頂元素出棧，賦給變量 x; Sempty(ST)：判ST棧是否為空.那么如何

10、利用棧的運算來實現(xiàn)該隊列的三個 運算：enqueue:插入一個元素入隊列；dequeue:刪除一個元素出隊列；queue_empty:判隊列為空.(請寫明算法的思想及必要的注釋)34、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點， 但不設(shè)頭指針，如圖所示(編者略)，請寫出相應的入隊列和出隊列算法.35、如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作.要求：(1) 寫出循環(huán)隊列的類型定義；(2) 寫出“從隊尾刪除”和“從隊頭插入”的算法.36、在一個循環(huán)鏈隊中只有尾指針(記為rear，結(jié)點結(jié)構(gòu)為數(shù)據(jù)域data，指 針域next)，請給出這種隊列的入隊和出隊操作的實現(xiàn)過程.37

11、、已知Q是一個非空隊列，S是一個空棧.僅用隊列和棧的操作編寫一個算 法，將隊列Q中的所有元素逆置.38、已知求兩個正整數(shù) m與n的最大公因子的過程用自然語言可以表述為反 復執(zhí)行如下動作：第一步：若 n等于零，則返回m第二步：若m小于n， 則m與n相互交換；否則，保存 m,然后將n送m將保存的m除以n的余 數(shù)送n.(1) 將上述過程用遞歸函數(shù)表達出來(設(shè)求 x除以y的余數(shù)可以用x MOW 形式表示).(2) 寫出求解該遞歸函數(shù)的非遞歸算法.39、試將下列遞歸過程改寫為非遞歸過程.void test(i nt &sum) int x；sca nf(x)；if(x=0) sum=0 else

12、 test(sum); sum+=x;prin tf（sum）；40、二叉樹用二叉鏈表存儲，寫一個算法將二叉樹中的葉子結(jié)點按從右至左 的順序建立一個單鏈表41、知二叉樹用二叉鏈表存儲，寫出求二叉樹寬度的算法所謂寬度是指在二叉樹的各層上，具有結(jié)點數(shù)最多的那一層上的結(jié)點總數(shù).42、叉樹用二叉鏈表存儲，寫一個算法交換各結(jié)點的左右子樹43、二叉樹用二叉鏈表存儲，若結(jié)點的左孩子的數(shù)據(jù)域的值大于右孩子數(shù)據(jù) 域的值，則交換其左右子樹44、叉樹用二叉鏈表存儲，編寫一算法，判別給定的二叉樹是否為完全二叉 樹45、個結(jié)點的完全二叉樹以一維數(shù)組為存儲結(jié)構(gòu)，編寫一非遞歸算法實現(xiàn)對 該樹的先序遍歷.46、編寫一算法，在

13、二叉樹中查找值為 x的結(jié)點，并打印值為x的結(jié)點的所 有祖先結(jié)點.47、編寫中序遍歷二叉樹的非遞歸算法.48、編寫先序遍歷二叉樹的非遞歸算法.49、編寫后序遍歷二叉樹的非遞歸算法.50、叉樹用二叉鏈表存儲，任給一個二叉樹表示的四則運算表達式，編寫算 法，由該二叉樹輸出該表達式，若原表達式有括號亦加上51、有n個結(jié)點的完全二叉樹存放在一維數(shù)組 A1.n中，試據(jù)此建立一棵 用二叉鏈表表示的二叉樹 ，根由tree指向.52、二叉樹排序方法如下：（1）將第一個數(shù)據(jù)放在樹根.（2）將隨后讀入的數(shù)據(jù)與樹根中的數(shù)據(jù)相比較，若比樹根大，則置于右子 樹，反之則置于左子樹，建成一棵二叉樹；（3）利用中序遍歷打印排序

14、結(jié)果. 用C語言編寫二叉樹的排序程序.53、二叉樹結(jié)點的平衡因子（bf）定義為該結(jié)點的左子樹高度與右子樹高度 之差.編寫算法計算二叉樹中各個結(jié)點的平衡因子.54、設(shè)計算法：統(tǒng)計一棵二叉樹中所有葉結(jié)點的數(shù)目及非葉結(jié)點的數(shù)目.55、已知二叉樹以二叉鏈表存儲，編寫算法完成：對于樹中每一個元素值為 x的結(jié)點，刪去以它為根的子樹，并釋放相應的空間.56、試編寫算法，對一棵以孩子一兄弟鏈表表示的樹統(tǒng)計葉子的個數(shù).57、設(shè)一棵二叉樹中各結(jié)點的值互不相同，其前序序列和中序序列分別存于 兩個一維數(shù)組pre1.n 和mid1.n 中，試遍寫算法建立該二叉樹的二 叉鏈表.58、試設(shè)計一個算法打印出由根結(jié)點出發(fā)到達葉

15、結(jié)點的所有路徑.59、試寫出算法，求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上 各結(jié)點的值.60、給定一組項及其權(quán)值，假定項都存放于二叉樹的樹葉結(jié)點，則具有最小 帶權(quán)外部路徑長度的樹稱為 huffman樹.編寫構(gòu)造huffman樹的算法.61、已知一中序線索二叉樹，寫一算法完成對它的中序掃描.62、已知中序線索二叉樹T右子樹不空.設(shè)計算法，將S所指的結(jié)點作為T 的右子樹中的一個葉子結(jié)點插入進去，并使之成為T的右子樹的（中序序列）第一個結(jié)點（同時要修改相應的線索關(guān)系）63、寫出算法，求出中序線索二叉樹中給定值為x的結(jié)點之后繼結(jié)點，返回該后繼結(jié)點的指針.線索樹中結(jié)點結(jié)構(gòu)為：（ltag,lc,

16、data,rc,rtag ）.其中， data存放結(jié)點的值；lc，rc為指向左、右孩子或該結(jié)點前驅(qū)或后繼的指針； ltag，rtag為標志域，各值為：0，則lc，rc為指向左、右孩子的指針；值 為1，則lc，rc為指向某前驅(qū)后繼結(jié)點的指針64、設(shè)后序 線索樹中結(jié)點 構(gòu)造為（Ltag,Lchild,Data,Rchild,Rtag）. 其中:Ltag,Rtag 值為0時丄child、Rchild分別為兒子指針；否則分別為直 接前驅(qū),直接后繼的線索.請寫出在后序線索樹上找給定結(jié)點pA的直接前驅(qū)q的算法.65、設(shè)無向圖G有n個頂點，m條邊.試編寫用鄰接表存儲該圖的算法.（設(shè) 頂點值用1n或0n-1編

17、號）66、已知有向圖有n個頂點，請寫算法,根據(jù)用戶輸入的偶對建立該有向圖的 鄰接表.即接受用戶輸入的<vi,vj>（以其中之一為0標志結(jié)束）,對于每條這 樣的邊，申請一個結(jié)點，并插入到的單鏈表中，如此反復，直到將圖中所有邊 處理完畢.提示：先產(chǎn)生鄰接表的n個頭結(jié)點（其結(jié)點數(shù)值域從1到n）.67、給出以十字鏈表作存儲結(jié)構(gòu)，建立圖的算法，輸入（i,j,v） 其中i,j為頂 點號，v為權(quán)值.68、設(shè)有向G圖有n個點（用1,2,n表示）,e條邊,寫一算法建立有向圖的 逆鄰接表.69、設(shè)已給出圖的鄰接矩陣，要求將圖的鄰接矩陣轉(zhuǎn)化為鄰接表，試實現(xiàn)其 算法.70、編寫算法，將圖的鄰接矩陣存儲改為

18、鄰接表的存儲.71、試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點V到頂點V的路徑（i<>j ）.72、已知無向圖采用鄰接表存儲方式，試寫出刪除邊（i , j ）的算法.73、假設(shè)有向圖以鄰接表存儲，試編寫算法刪除弧<V，V>的算法.74、假設(shè)有向圖以十字鏈表存儲，試編寫算法，插入弧<V,Vj>.75、設(shè)有向圖用鄰接表表示,圖有n個頂點,表示為1至n,試寫一個算法求頂 點k的入度（1<k<n）.76、寫出圖的深度優(yōu)先搜索DFS算法的非遞歸算法.77、寫出圖的廣度優(yōu)先搜索算法的非遞歸算法.78、已知帶權(quán)圖用鄰接矩陣表示，編寫函數(shù)實現(xiàn)用Kr

19、uskal算法構(gòu)造最小生成樹的算法.79、編寫函數(shù)實現(xiàn)用Prim算法構(gòu)造最小生成樹的算法.80、編寫函數(shù)實現(xiàn)從指定頂點到其余各頂點的最短路徑的Dijkstra 算法.81、實現(xiàn)圖的拓撲排序算法.82、設(shè)計一個二分查找的遞歸算法.83、設(shè)計一個算法，利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序性.84、實現(xiàn)散列表的相關(guān)算法（1）給定一個序列，和散列函數(shù)，并利用線性探測再散列處理沖突，建立散列表.（2）編寫函數(shù)，查找某一個關(guān)鍵字（3）編寫函數(shù)，刪除找某一個關(guān)鍵字85、設(shè)計一個順序查找算法86、編寫一個算法，統(tǒng)計 一個字符串中出現(xiàn)字符的次數(shù)87、實現(xiàn)二叉查找樹的相關(guān)算法（1）給定序列

20、，創(chuàng)建一二叉查找樹（2）判定一棵樹是否為二叉查找樹（3）采用遞歸和非遞歸算法，查找某一個關(guān)鍵字（4）編寫函數(shù)，刪除找某一個關(guān)鍵字88、線索二叉樹問題描述：建立一個中序線索二叉樹，并且完成中序遍歷求該中序線索二叉樹上已知結(jié)點在中序的前驅(qū)和后繼；89、約瑟夫環(huán)問題問題描述：設(shè)編號為1, 2, 3，n的n（n>0）個人按順時針方向圍 坐一圈，每個人持有一個正整數(shù)密碼.開始時任選一個正整數(shù)作為報數(shù)上 限m,從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)， 報m的人出列，將他的密碼作為新的 m值，從他的下一個人開始重新 從1報數(shù).如此下去，直到所有人全部出列為止.令n最大值取30.要求設(shè)

21、 計一個程序模擬此過程，求出出列編號序列90、表達式求值（探）問題描述：從鍵盤上輸入中綴算數(shù)表達式，計算出表達式的值.基本要求：1. 程序?qū)λ斎氲谋磉_式做簡單的判斷，如果表達式有錯，能給出適當?shù)奶崾?2. 能處理+、一、X、十 這四種基本的算術(shù)運算符.91、求圖的中心點（探）問題描述：假設(shè)有一個公司在某個地區(qū)有 n個產(chǎn)品銷售點，現(xiàn)根據(jù)業(yè)務(wù) 需要打算在其中某個銷售點上建立一個中心倉庫負責向其他銷售點提 供產(chǎn)品.由于運輸路線不同，運輸費用也不同.假定每天需要向每個銷售 點運輸一次產(chǎn)品，那么應將中心倉庫建在哪個銷售點上才能使運輸費用 最低.92、集合的交、并和差運算的實現(xiàn)（探）問題描述：用有序單鏈

22、表表示集合，實現(xiàn)集合的交、并、差運算基本要求：空間復雜度為0（1）93、單鏈表實現(xiàn)十進制大整數(shù)運算（探）問題描述：使用單鏈表實現(xiàn)不限大小的整數(shù)，每個結(jié)點存儲一位數(shù)字， 要求實現(xiàn)加、減運算.即能從鍵盤上輸入兩個大整數(shù)，比如：和,則加的結(jié)果應為： 減的結(jié)果應為：23456234562345623456.基本要求： 從鍵盤上輸入運算數(shù)和運算符，輸出結(jié)果.94、哈夫曼編碼（探）問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本.這就要求在發(fā)送端通過一個編碼系統(tǒng)對待 傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼.對于雙工信道（即可 以雙向傳輸信息的信道），每端都需要一

23、個完成的編譯碼系統(tǒng).試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng) 基本要求：1. 初始化從終端讀入字符集大小n,以及n個字符和n個權(quán)值，建 立哈夫曼樹.2. 編碼.利用已建好的哈夫曼樹，對正文進行編碼.3. 譯碼.對編碼好的內(nèi)容進行譯碼.4. 打印編碼.95、稀疏矩陣運算器(探)問題描述：實現(xiàn)兩個稀疏矩陣的加、減、乘運算 基本要求：可用三元組順序表存儲稀疏矩陣，矩陣的運算結(jié)果以通常的 陣列形式輸出.96、校園導游程序(探)問題描述：用無向圖表示你所在學校的景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道 路，存放路徑長度等消息.基本要求：1. 能查詢各

24、景點的相關(guān)信息2. 為來訪客人提供景點的問路查詢，即已知一個景點，查詢到某 景點之間的一條最短路徑及長度.97、八皇后問題(探)問題描述：八皇后問題，是一個古老而著名的問題，是回溯算法的典型 例題.該問題是十九世紀著名的數(shù)學家高斯 1850年提出：在8X 8格的國 際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處 于同一行、同一列或同一斜線上.基本要求：統(tǒng)計總共有多少種擺法，并以一定方式輸出擺好的格局.98、平衡二叉樹操作演示(探)問題描述：利用平衡二叉樹實現(xiàn)動態(tài)查找表. 基本要求：設(shè)計平衡二叉樹實現(xiàn)動態(tài)查找表的操作演示.(1) 實現(xiàn)動態(tài)查找表的三種基本功能：查找、插入、刪除.(2) 合并兩棵平衡二叉樹.(3) 分解兩棵平衡二叉樹.99、設(shè)有一個正整數(shù)序列組成的有序單鏈表(按遞增次序有序，且允許有相等的整數(shù)存在)，試編寫能實現(xiàn)下列功能的算法：(要求用最少的時間和最 小的空間)(探)(1) 確定在序列中比正整數(shù)x大的數(shù)有幾個(相同的數(shù)只計算一次，如序列 20,20,17,16,15,15,11,10,8,7,7,5,4 中比 10大的數(shù)有 5個)；(2) 在單鏈表將比正整數(shù)x小的數(shù)按遞減次序排列；(3) 將正整數(shù)比x大的偶數(shù)從單鏈表中刪除. 設(shè)計要求：(1) 每名同學任選三題；標號的題為選做題，完成有加分