數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè)模板

2011上機(jī)實(shí)習(xí)基本要求及內(nèi)容上機(jī)實(shí)習(xí)基本目標(biāo)計(jì)算機(jī)學(xué)科分為理論、抽象、設(shè)計(jì)三個(gè)形態(tài)。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科的重要分支研究領(lǐng)域之一。在算法分析與設(shè)計(jì)、操作系統(tǒng)、軟件工程、數(shù)據(jù)庫(kù)概論、編譯技術(shù)、計(jì)算機(jī)圖形學(xué)、人機(jī)交互等專業(yè)基礎(chǔ)課和專業(yè)課程中均有涉及。對(duì)特定領(lǐng)域或應(yīng)用要使用到頭特定的數(shù)據(jù)結(jié)構(gòu)：編譯系統(tǒng)要使用棧、散列表及語(yǔ)法樹(shù)；操作系統(tǒng)中要用隊(duì)列、存儲(chǔ)管理表及目錄樹(shù)等；數(shù)據(jù)庫(kù)系統(tǒng)要用線性表、多鏈表及索引樹(shù)等；在人工智能領(lǐng)域依求解問(wèn)題性質(zhì)的差異將涉及到各種不同的數(shù)據(jù)結(jié)構(gòu)，如廣義表，集合、搜索樹(shù)及各種有向圖等等。

通過(guò)數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)習(xí)要讓學(xué)生掌握鏈表、樹(shù)、圖是如何實(shí)現(xiàn)的，進(jìn)一步從理論、抽象、設(shè)計(jì)的角度來(lái)考慮問(wèn)題。第一，讓學(xué)生真正理解“數(shù)據(jù)結(jié)構(gòu)＋算法＝程序”。程序不僅僅是求解算法的實(shí)現(xiàn)，也要配有恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；第二，培養(yǎng)學(xué)生數(shù)據(jù)抽象的能力。讓學(xué)生了解鏈表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)是如何實(shí)現(xiàn)的，特別要加強(qiáng)對(duì)數(shù)據(jù)邏輯關(guān)系的分析與認(rèn)識(shí)；第三，培養(yǎng)學(xué)生使用數(shù)據(jù)結(jié)構(gòu)的能力。要把數(shù)據(jù)結(jié)構(gòu)與算法的理論分析與編程實(shí)踐相結(jié)合，靈活運(yùn)用于實(shí)際解題中。需要強(qiáng)調(diào)以下幾個(gè)方面的知識(shí)和能力：（1）掌握并能夠靈活應(yīng)用基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、存儲(chǔ)方法、主要的算法，特別是線性結(jié)構(gòu)、二叉樹(shù)、樹(shù)、圖、文件等；（2）掌握并應(yīng)用常用的排序、檢索和索引算法和方法；（3）掌握基本的算法設(shè)計(jì)和分析技術(shù)，并結(jié)合具體的設(shè)計(jì)，對(duì)所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行分析；（4）在進(jìn)行程序設(shè)計(jì)、調(diào)試中，注意綜合應(yīng)用，將所學(xué)到的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)應(yīng)用到對(duì)具體數(shù)據(jù)對(duì)象的特性分析。結(jié)合實(shí)際例子進(jìn)行設(shè)計(jì)，選擇合適的數(shù)據(jù)結(jié)構(gòu)和存貯結(jié)構(gòu)以及相應(yīng)的算法。上機(jī)實(shí)習(xí)基本要求1．合理地選用組織數(shù)據(jù)、有效地表示數(shù)據(jù)、正確地處理數(shù)據(jù)，清晰地表述算法。2．完成選定題目，按照規(guī)范格式（附件一）寫出實(shí)習(xí)報(bào)告(原問(wèn)題、設(shè)計(jì)算法、DS、程序、給出實(shí)例并分析結(jié)果、討論T(n))。3．線性關(guān)系、非線性關(guān)系、算法三部分的實(shí)習(xí)報(bào)告電子版提交日期在上機(jī)后2日內(nèi)提交；第四次機(jī)考電子版在上機(jī)結(jié)束時(shí)提交(電子版交liuxd@，將四次上機(jī)匯總打印紙版筆試前1周交西1樓711室)；請(qǐng)按時(shí)提交注意上交電子版與紙版應(yīng)一致。4.請(qǐng)按照附件給定報(bào)告內(nèi)容格式安排。

附件一：報(bào)告封面格式數(shù)據(jù)結(jié)構(gòu)與算法B上機(jī)實(shí)習(xí)報(bào)告第1次2011-9-dd題目名稱第2次yyyy-mm-dd題目名稱第3次yyyy-mm-dd題目名稱第4次yyyy-mm-dd題目名稱報(bào)告人：MMM班級(jí)：信息nn學(xué)號(hào)：nnnnnnnn

附件二：報(bào)告內(nèi)容格式（封面見(jiàn)附件一。正文要求：A4紙，小4#宋體，右下頁(yè)碼，最小行距）一、上機(jī)實(shí)習(xí)題目（原問(wèn)題解目標(biāo)）二、相關(guān)知識(shí)或技術(shù)（對(duì)應(yīng)DS部分）三、算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（算法設(shè)計(jì)）四、上機(jī)環(huán)境和使用語(yǔ)言（計(jì)算機(jī)程序?qū)崿F(xiàn)）五、源程序（帶注釋或說(shuō)明）、運(yùn)行結(jié)果（數(shù)據(jù)或屏幕顯示、結(jié)果分析、討論T(n)）六、上機(jī)總結(jié)（體會(huì)提高）七、參考資料

附件三：上機(jī)實(shí)習(xí)參考題目（1）各個(gè)DS的插入、刪除、建立、判空；（2）線性鏈表操作——插入、刪除、合并、排序、查找（3）將一個(gè)遞歸程序轉(zhuǎn)為非遞歸程序。（4）編制標(biāo)準(zhǔn)算法，將兩個(gè)線性表合并成一個(gè)。（5）用一個(gè)數(shù)組S（設(shè)大小為MAX）作為對(duì)開(kāi)棧的共享空間。請(qǐng)說(shuō)明共享方法、棧滿/?？盏呐袛鄺l件，設(shè)計(jì)入棧操作push(i,x),其中i為0或1，用于表示棧號(hào)，x為入棧值；并設(shè)計(jì)清、判空、判滿、出棧操作。（6）對(duì)于一個(gè)堆棧，若其入棧序列為1,2,3,...,n，不同的出入棧操作將產(chǎn)生不同的出棧序列。其出棧序列的個(gè)數(shù)正好等于節(jié)點(diǎn)個(gè)數(shù)為n的二叉樹(shù)的個(gè)數(shù)，且與不同形態(tài)的二叉樹(shù)一一對(duì)應(yīng)。請(qǐng)簡(jiǎn)要敘述一種從堆棧輸入（固定為1,2,3,...n）/輸出序列對(duì)應(yīng)一種二叉樹(shù)形態(tài)的方法，并以入棧序列1,2,3（即n等于3）為例加以說(shuō)明。（7）求Л到小數(shù)點(diǎn)后100位。（8）長(zhǎng)整數(shù)四則運(yùn)算ADT與存儲(chǔ)實(shí)現(xiàn)。（9）樹(shù)和二叉樹(shù)的遞歸遍歷/非遞歸遍歷；（10）求二叉樹(shù)中最長(zhǎng)/短路徑。（11）求最大平臺(tái)問(wèn)題（n個(gè)整數(shù)序列，相同值連續(xù)最大的稱最大平臺(tái)）。（12）最小生成樹(shù)；（13）檢索與查找算法。（14）排序與廣義表算法。（15）為圖書(shū)館借書(shū)處/食堂售卡處業(yè)務(wù)設(shè)計(jì)一個(gè)業(yè)務(wù)系統(tǒng)完成日常的相關(guān)工作。（16）為民航/火車售票處的票務(wù)業(yè)務(wù)設(shè)計(jì)一個(gè)計(jì)劃、團(tuán)體/零售、查詢系統(tǒng)。（17）已知二叉樹(shù)中結(jié)點(diǎn)的左右兒子域分別為left和right。p指向二叉樹(shù)的某一節(jié)點(diǎn)。請(qǐng)編一個(gè)非遞歸函數(shù)postfirst(p)，求p所對(duì)應(yīng)子樹(shù)的第一個(gè)后序（后根）遍歷節(jié)點(diǎn)。（18）已知樹(shù)中結(jié)點(diǎn)的用左孩子右兄弟表示，p指向二叉樹(shù)的某一結(jié)點(diǎn)。請(qǐng)編遍歷樹(shù)算法。（19）編程生成國(guó)際象棋棋盤，使馬踏棋盤各格一次且僅一次。（20）編程生成迷宮（平面，立體），指定出入口位置，找出一條/所有路徑。（21）圖的遍歷算法。（22）求最