可做奧鵬院校所有作業(yè)，畢業(yè)論文，咨詢請(qǐng)?zhí)砑観Q：3230981406 微信：aopopenfd777
中國(guó)石油大學(xué)（北京）遠(yuǎn)程教育學(xué)院
期 末 考 試
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》
學(xué)習(xí)中心：_______ 姓名：________ 學(xué)號(hào)：_______
關(guān)于課程考試違規(guī)作弊的說(shuō)明
1、提交文件中涉嫌抄襲內(nèi)容（包括抄襲網(wǎng)上、書籍、報(bào)刊雜志及其他已有論文），帶有明顯外校標(biāo)記，不符合學(xué)院要求或?qū)W生本人情況，或存在查明出處的內(nèi)容或其他可疑字樣者，判為抄襲，成績(jī)?yōu)椤?”。
2、兩人或兩人以上答題內(nèi)容或用語(yǔ)有50%以上相同者判為雷同，成績(jī)?yōu)椤?”。
3、所提交試卷或材料沒(méi)有對(duì)老師題目進(jìn)行作答或提交內(nèi)容與該課程要求完全不相干者，認(rèn)定為“白卷”或“錯(cuò)卷”，成績(jī)?yōu)椤?”。
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》
一.課程設(shè)計(jì)題目
選題說(shuō)明：
學(xué)號(hào)尾號(hào)為0、1、2的學(xué)生完成第1題
學(xué)號(hào)尾號(hào)為3、4、5的學(xué)生完成第2題
學(xué)號(hào)尾號(hào)為6、7的學(xué)生完成第3題
學(xué)號(hào)尾號(hào)為8、9的學(xué)生完成第4題
1. 任意長(zhǎng)的整數(shù)加減法運(yùn)算
設(shè)計(jì)算法，實(shí)現(xiàn)一個(gè)任意長(zhǎng)的整數(shù)進(jìn)行加法、減法運(yùn)算的演示程序。例如：1234，5123，4512，3451，2345與-1111，1111，1111，1111，1111的加法結(jié)果為：0123，4012，3401，2340，1234。基本要求如下：
（1） 利用鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)節(jié)點(diǎn)含一個(gè)整型變量；
（2） 整型變量的范圍：-（2^15 -1）~（2^15 -1）；
（3） 輸入與輸出形式每四位一組，組間用逗號(hào)分隔開(kāi)。如：1986,8213,1935,2736,3299；
（4） 界面友好，每步給出適當(dāng)?shù)牟僮魈崾?，并且系統(tǒng)具有一定的容錯(cuò)能力。
至少給出下面的測(cè)試數(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)絡(luò)
在n個(gè)城市建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。設(shè)計(jì)算法，求出如果以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)絡(luò)。要求如下：
（1） 至少包含10個(gè)城市；
（2） 城市數(shù)n由鍵盤錄入；
（3） 城市坐標(biāo)由隨機(jī)函數(shù)產(chǎn)生小于100的整數(shù)；
（4） 輸出生成樹(shù)中各條邊以及它們的權(quán)值；
3. 實(shí)現(xiàn)兩個(gè)鏈表的合并
基本功能要求：
（1）建立兩個(gè)鏈表A和B，鏈表元素個(gè)數(shù)分別為m和n個(gè)。
（2）假設(shè)元素分別為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個(gè)線性表C，使得：
當(dāng)m>=n時(shí)，C=x1,y1,x2,y2,…xn,yn,…,xm
當(dāng)n>m時(shí)，C=y1,x1,y2,x2,…ym,xm,…,yn
輸出線性表C
（3）用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。
測(cè)試數(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. 二叉樹(shù)的建立與遍歷
[問(wèn)題描述]
建立一棵二叉樹(shù)，并對(duì)其進(jìn)行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果。
[基本要求]
從鍵盤接受輸入（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹(shù)（以先序來(lái)建立），并采用遞歸算法對(duì)其進(jìn)行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。
[測(cè)試數(shù)據(jù)]
ABCффDEфGффFффф（其中ф表示空格字符）
則輸出結(jié)果為 先序：ABCDEGF
中序：CBEGDFA
后序：CGBFDBA
二.課程設(shè)計(jì)要求
（1）要求利用結(jié)構(gòu)和程序設(shè)計(jì)語(yǔ)言C語(yǔ)言或C++完成上述題目。
（2）課程設(shè)計(jì)要獨(dú)立思考，獨(dú)立完成。課程設(shè)計(jì)報(bào)告雷同超過(guò)60%，不論什么原因，一律0分處理。
（3）算法設(shè)計(jì)及實(shí)現(xiàn)中，只能采用線性表、樹(shù)和圖結(jié)構(gòu)完成，不得用數(shù)據(jù)庫(kù)。
（4）最后提交的內(nèi)容：源程序與課程設(shè)計(jì)報(bào)告word文檔。提交word文檔，將源程序粘貼在課程設(shè)計(jì)報(bào)告最后面，不能提交壓縮包文檔。
（5）請(qǐng)以遠(yuǎn)程教育學(xué)院課程設(shè)計(jì)報(bào)告模板為樣本，完成設(shè)計(jì)報(bào)告。
三.課程設(shè)計(jì)報(bào)告書寫規(guī)范
課程設(shè)計(jì)報(bào)告必須包含下面內(nèi)容：
（1）需求分析
此部分?jǐn)⑹鏊惴ǖ墓δ?、輸入、輸出及運(yùn)行環(huán)境。
（2）概要設(shè)計(jì)
在此部分給出算法用到的主要數(shù)據(jù)結(jié)構(gòu)、主要函數(shù)及其功能的介紹，各函數(shù)之間的調(diào)用關(guān)系示意圖。
（3）詳細(xì)設(shè)計(jì)
此部分給出主要算法的設(shè)計(jì)思想及實(shí)現(xiàn)。
（4）程序測(cè)試
在這部分給出程序運(yùn)行結(jié)果的屏幕截圖，以及測(cè)試分析。
（5）感想與體會(huì)
在這部分給出算法設(shè)計(jì)過(guò)程中的問(wèn)題、程序調(diào)試過(guò)程的問(wèn)題，算法存在的不足及改進(jìn)思路。
