2019秋石大遠程在線考試《數(shù)據(jù)結構課程設計》

中國石油大學（北京）遠程教育學院期 末 考 試數(shù)據(jù)結構課程設計學習中心：_ 姓名：_ 學號：_ 關于課程考試違規(guī)作弊的說明1、提交文件中涉嫌抄襲內(nèi)容（包括抄襲網(wǎng)上、書籍、報刊雜志及其他已有論文），帶有明顯外校標記，不符合學院要求或?qū)W生本人情況，或存在查明出處的內(nèi)容或其他可疑字樣者，判為抄襲，成績?yōu)椤?”。 2、兩人或兩人以上答題內(nèi)容或用語有50%以上相同者判為雷同，成績?yōu)椤?”。3、所提交試卷或材料沒有對老師題目進行作答或提交內(nèi)容與該課程要求完全不相干者，認定為“白卷”或“錯卷”，成績?yōu)椤?”。數(shù)據(jù)結構課程設計一.課程設計題目選題說明：學號尾號為0、1、2的學生完成第1題學號尾號為3、4、5的學生完成第2題學號尾號為6、7的學生完成第3題學號尾號為8、9的學生完成第4題1. 任意長的整數(shù)加減法運算設計算法，實現(xiàn)一個任意長的整數(shù)進行加法、減法運算的演示程序。例如：1234，5123，4512，3451，2345與-1111，1111，1111，1111，1111的加法結果為：0123，4012，3401，2340，1234。基本要求如下：（1） 利用鏈表實現(xiàn)長整數(shù)的存儲，每個節(jié)點含一個整型變量；（2） 整型變量的范圍：-（215 -1）（215 -1）；（3） 輸入與輸出形式每四位一組，組間用逗號分隔開。如：1986,8213,1935,2736,3299；（4） 界面友好，每步給出適當?shù)牟僮魈崾?，并且系統(tǒng)具有一定的容錯能力。至少給出下面的測試數(shù)據(jù)：（1）0； 0 （2）-2345,6789； -7654,3211（3）-9999,9999； 1,0000,0000,0000 （4）1,0001,0001； -1,0001,0001（5）1,0001,0001； -1,0001,0000（6）-9999,9999,9999； -9999,9999,9999（7）1,0000,9999,9999； 1 2. 建立通信網(wǎng)絡在n個城市建設通信網(wǎng)絡，只需架設n-1條線路即可。設計算法，求出如果以最低的經(jīng)濟代價建設這個通信網(wǎng)絡。要求如下：（1） 至少包含10個城市；（2） 城市數(shù)n由鍵盤錄入；（3） 城市坐標由隨機函數(shù)產(chǎn)生小于100的整數(shù)；（4） 輸出生成樹中各條邊以及它們的權值；3. 實現(xiàn)兩個鏈表的合并基本功能要求：（1）建立兩個鏈表A和B，鏈表元素個數(shù)分別為m和n個。（2）假設元素分別為(x1,x2,xm)，和(y1,y2, yn)。把它們合并成一個線性表C，使得：當m=n時，C=x1,y1,x2,y2,xn,yn,xm當nm時，C=y1,x1,y2,x2,ym,xm,yn輸出線性表C（3）用直接插入排序法對C進行升序排序，生成鏈表D，并輸出鏈表D。測試數(shù)據(jù)：（1） A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）（2） A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）4. 二叉樹的建立與遍歷問題描述建立一棵二叉樹，并對其進行遍歷（先序、中序、后序），打印輸出遍歷結果?；疽髲逆I盤接受輸入（先序），以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），并采用遞歸算法對其進行遍歷（先序、中序、后序），將遍歷結果打印輸出。測試數(shù)據(jù)ABCDEGF（其中表示空格字符）則輸出結果為 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA二.課程設計要求（1）要求利用結構和程序設計語言C語言或C+完成上述題目。（2）課程設計要獨立思考，獨立完成。課程設計報告雷同超過60%，不論什么原因，一律0分處理。（3）算法設計及實現(xiàn)中，只能采用線性表、樹和圖結構完成，不得用數(shù)據(jù)庫。（4）最后提交的內(nèi)容：源程序與課程設計報告word文檔。提交word文檔，將源程序粘貼在課程設計報告最后面，不能提交壓縮包文檔。（5）請以遠程教育學院課程設計報告模板為樣本，完成設計報告。三.課程設計報告書寫規(guī)范課程設計報告必須包含下面內(nèi)容：（1）需求分析此部分敘述算法的功能、輸入、輸出及運行環(huán)境。（2）概要設計在此部分給出算法用到的主要數(shù)據(jù)結構、主要函數(shù)及其功能的介紹，各函數(shù)之間的調(diào)用關系示意圖。（3）詳細設計此部分給出