數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)任務(wù)書(shū)

2023-2023第二學(xué)期《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)任務(wù)書(shū)課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

課程設(shè)計(jì)學(xué)分：1

課程設(shè)計(jì)周（時(shí)）數(shù)：1周課程設(shè)計(jì)授課單位：計(jì)算機(jī)專業(yè)教研室

指導(dǎo)方式：集體輔導(dǎo)與個(gè)別輔導(dǎo)相結(jié)合課程設(shè)計(jì)合用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)

、軟件工程、網(wǎng)絡(luò)工程

課程設(shè)計(jì)教材及重要參考資料：《數(shù)據(jù)結(jié)構(gòu)C++版》王紅梅、胡明、王濤編著清華大學(xué)出版社2023年《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏編著，清華大學(xué)出版社，2023年服務(wù)課程名稱：數(shù)據(jù)結(jié)構(gòu)服務(wù)課程講課學(xué)時(shí)：56

服務(wù)課程學(xué)分：3.5

一、課程設(shè)計(jì)教學(xué)目的及基本規(guī)定1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具有初步的獨(dú)立分析和設(shè)計(jì)能力；2.初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、數(shù)據(jù)結(jié)構(gòu)定義、算法流程分析、程序編碼、測(cè)試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)的規(guī)范完畢課程設(shè)計(jì)內(nèi)容，培養(yǎng)軟件工作者所應(yīng)具有的科學(xué)的工作方法和作風(fēng)。二、課程設(shè)計(jì)內(nèi)容及安排1.分析題目，設(shè)計(jì)解題思緒：根據(jù)設(shè)計(jì)題目的規(guī)定，充足地分析和理解問(wèn)題，明確問(wèn)題規(guī)定做什么？（而不是怎么做？）限制條件是什么？2.數(shù)據(jù)結(jié)構(gòu)定義：對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。寫出每個(gè)抽象數(shù)據(jù)類型的定義(涉及數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明)，各個(gè)重要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3.算法流程分析：在這個(gè)過(guò)程中，要綜合考慮題目的具體規(guī)定，使得解決算法流程清楚、合理、簡(jiǎn)樸和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡也許做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡也許明確具體。算法流程分析的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；4.編寫代碼：把具體設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；5.程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)?？梢约兪煺莆照{(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)擬定疑點(diǎn)，通過(guò)修改程序來(lái)證實(shí)它或繞過(guò)它。調(diào)試對(duì)的后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6.結(jié)果分析：程序運(yùn)營(yíng)結(jié)果涉及對(duì)的的輸入及其輸出結(jié)果和具有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；7.編寫課程設(shè)計(jì)報(bào)告；三、課程設(shè)計(jì)考核方法及成績(jī)?cè)u(píng)估課程設(shè)計(jì)結(jié)束時(shí)，規(guī)定學(xué)生寫出課程設(shè)計(jì)報(bào)告（附源程序），可運(yùn)營(yíng)的軟件系統(tǒng)課程設(shè)計(jì)成績(jī)分兩部分，設(shè)計(jì)報(bào)告占30％，設(shè)計(jì)作品占70％。按照優(yōu)秀、良好、中、及格，不及格五級(jí)給予成績(jī)。四、其他規(guī)定課程設(shè)計(jì)時(shí)間安排周一布置題目、分析題目指導(dǎo)教師呂冬梅張沛露岳俊華周二分析題目，設(shè)計(jì)解題思緒指導(dǎo)教師段淼鄭琦林娜周三數(shù)據(jù)結(jié)構(gòu)定義，算法流程分析指導(dǎo)教師呂冬梅張沛露岳俊華周四編寫代碼，調(diào)試分析指導(dǎo)教師段淼鄭琦林娜周五驗(yàn)收指導(dǎo)教師呂冬梅張沛露岳俊華段淼鄭琦林娜設(shè)計(jì)題目及基本規(guī)定第一題：關(guān)鍵途徑問(wèn)題當(dāng)一項(xiàng)工程被劃分為若干個(gè)子任務(wù)或活動(dòng)后，人們不僅需要擬定這些活動(dòng)的先后順序，并且需要進(jìn)一步計(jì)算完畢整個(gè)工程的時(shí)間，擬定哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)，以便合理組織人力、物力、財(cái)力，加快這些活動(dòng)的進(jìn)度，為準(zhǔn)時(shí)或提前完畢整個(gè)工程提供保證。規(guī)定：給定一個(gè)帶權(quán)的有向圖代表一個(gè)工程的AOE網(wǎng)絡(luò)，研究如下問(wèn)題：（1）完畢整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？示例圖：核心算法：圖的關(guān)鍵途徑第二題：電梯模擬模擬某校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個(gè)自動(dòng)電梯，能在每層停留。九個(gè)樓層由下至上依次稱為地下層、第一層、第二層、……第八層，其中第一層是大樓的進(jìn)出層，即是電梯的“本壘層”，電梯“空閑”時(shí)，將來(lái)到該層候命。乘客可隨機(jī)地進(jìn)出于任何層。對(duì)每個(gè)人來(lái)說(shuō)，他有一個(gè)能容忍的最長(zhǎng)等待時(shí)間，一旦等候電梯時(shí)間過(guò)長(zhǎng)，他將放棄。模擬時(shí)鐘從0開(kāi)始，時(shí)間單位為0.1秒。人和電梯的各種動(dòng)作均要消耗一定的時(shí)間單位（簡(jiǎn)記為t），比如：有人進(jìn)出時(shí)，電梯每隔40t測(cè)試一次，若無(wú)人進(jìn)出，則關(guān)門；關(guān)門和開(kāi)門各需要20t；每個(gè)人進(jìn)出電梯均需要25t；假如電梯在某層靜止時(shí)間超過(guò)300t，則駛回1層侯命。而題目的最終規(guī)定輸出時(shí)：準(zhǔn)時(shí)序顯示系統(tǒng)狀態(tài)的變化過(guò)程，即發(fā)生的所有人和電梯的動(dòng)作序列。核心算法：乘客采用棧，等待乘客采用隊(duì)列第三題：研究生入學(xué)考試成績(jī)解決假設(shè)某大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)招收研究生n名，現(xiàn)在要根據(jù)報(bào)考者的考試成績(jī)擇優(yōu)錄取?？荚囌n程有政治、英語(yǔ)、數(shù)學(xué)、專業(yè)綜合四門?？荚嚦煽?jī)分為兩類：第一類為每門課程都達(dá)成最低錄取線；第二類為有一門或多門課程未達(dá)成最低錄取線。錄取方法是在每門課程達(dá)成最低錄取線的考生中按總分從高到低錄取。試設(shè)計(jì)一個(gè)成績(jī)解決程序?qū)崿F(xiàn)以上功能。根據(jù)錄取方法，打印輸出n份錄取告知書(shū)，列出錄取者四門課程的成績(jī)及總分（規(guī)定采用堆排序）。并能實(shí)現(xiàn)對(duì)任一考生或任一門課程成績(jī)的查找（規(guī)定兩種查找方式，根據(jù)考號(hào)或姓名進(jìn)行查找，采用高效的查找算法）。錄取告知書(shū)的格式如下：核心算法：鏈表的查找第四題：哈夫曼編碼與譯碼問(wèn)題設(shè)計(jì)一個(gè)哈夫曼編碼、譯碼系統(tǒng)。對(duì)一個(gè)ASCII編碼的文本文獻(xiàn)中的字符進(jìn)行哈夫曼編碼，生成編碼文獻(xiàn)；反過(guò)來(lái)，可將編碼文獻(xiàn)譯碼還原為一個(gè)文本文獻(xiàn)。從文獻(xiàn)中讀入任意一篇英文短文（文獻(xiàn)為ASCII編碼，擴(kuò)展名為txt）；記錄并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標(biāo)點(diǎn)等也按字符解決）；根據(jù)字符頻率構(gòu)造哈夫曼樹(shù)，并給出每個(gè)字符的哈夫曼編碼；將文本文獻(xiàn)運(yùn)用哈夫曼樹(shù)進(jìn)行編碼，存儲(chǔ)成壓縮文獻(xiàn)（編碼文獻(xiàn)后綴名.huf）用哈夫曼編碼來(lái)存儲(chǔ)文獻(xiàn)，并和輸入文本文獻(xiàn)大小進(jìn)行比較，計(jì)算文獻(xiàn)壓縮率；進(jìn)行譯碼，將huf文獻(xiàn)譯碼為ASCII編碼的txt文獻(xiàn)，與原txt文獻(xiàn)進(jìn)行比較。核心算法：哈夫曼樹(shù)的編碼及譯碼第五題：校園導(dǎo)游圖用無(wú)向網(wǎng)表達(dá)本學(xué)校校園景點(diǎn)平面圖，選取若干個(gè)有代表性的景點(diǎn)抽象成無(wú)向帶權(quán)圖，圖中頂點(diǎn)表達(dá)校內(nèi)各頂點(diǎn)，邊上權(quán)值表達(dá)途徑長(zhǎng)度?？梢裕海?）為來(lái)訪客人查詢各景點(diǎn)的相關(guān)信息；（2）為來(lái)訪客人查詢圖中任意兩個(gè)景點(diǎn)間的最短途徑（3）為來(lái)訪客人查詢圖中任意兩個(gè)景點(diǎn)間的所有途徑（4）為來(lái)訪客人修改圖中頂點(diǎn)和邊的信息（5）為來(lái)訪客人增長(zhǎng)景點(diǎn)和途徑（6）為來(lái)訪客人刪除景點(diǎn)和途徑（7）為來(lái)訪客人輸出相應(yīng)編號(hào)景點(diǎn)的信息核心算法：圖的最短途徑第六題：簡(jiǎn)樸的文本編輯器內(nèi)容：輸入一頁(yè)文字，程序可以記錄出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行。規(guī)定：（1）分別記錄出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）記錄某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一字符或者子串，并將后面的字符前移。（4）插入某一字符或者子串。（5）查找某一字符或者子串。存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"所有字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章。通過(guò)題目及其規(guī)定可知，本程序應(yīng)實(shí)現(xiàn)以下功能：文章內(nèi)容的輸入：涉及字母、標(biāo)點(diǎn)符號(hào)、數(shù)字等；文章內(nèi)容的記錄：涉及文章中大寫字母、小寫字母、數(shù)字、標(biāo)點(diǎn)符號(hào)、空格以及文章所有字?jǐn)?shù)的個(gè)數(shù)的記錄；文章內(nèi)容的解決：涉及對(duì)文章內(nèi)容的查找、刪除以及對(duì)指定位置進(jìn)行插入操作，其中在查找的過(guò)程中記錄出該字符或字符串在文章中出現(xiàn)的次數(shù)；核心算法：鏈表的查找、刪除、插入第七題：運(yùn)動(dòng)會(huì)分?jǐn)?shù)記錄參與運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。比賽提成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）[基本規(guī)定](1)可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)；(2)能記錄各學(xué)?？偡?3)可以按學(xué)校編號(hào)、學(xué)?？偡帧⒛信畧F(tuán)隊(duì)總分排序輸出；(4)可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（假如做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提醒，各學(xué)校分?jǐn)?shù)為整形界面規(guī)定：有合理的提醒，每個(gè)功能可以設(shè)立菜單，根據(jù)提醒，可以完畢相關(guān)的功能規(guī)定。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能規(guī)定自己設(shè)計(jì)，但是規(guī)定運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文獻(xiàn)中。（數(shù)據(jù)文獻(xiàn)的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書(shū)上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：規(guī)定使用1、所有合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；核心算法：排序第八題：航空客運(yùn)訂票系統(tǒng)[問(wèn)題描述]通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文獻(xiàn)中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛到達(dá)城市，航班票價(jià)，票價(jià)折扣，擬定航班是否滿倉(cāng)）；可以輸入起飛到達(dá)城市，查詢飛機(jī)航班情況；訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文獻(xiàn)中，結(jié)構(gòu)自己設(shè)定）可以訂票，假如該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文獻(xiàn)；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文獻(xiàn)[基本規(guī)定]根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完畢功能；核心算法：隊(duì)列的操作第九題：模擬旅館管理系統(tǒng)的一個(gè)功能——床位的分派與回收[問(wèn)題描述]某旅館有n個(gè)等級(jí)的房間，第I等級(jí)有ai個(gè)房間，每個(gè)等級(jí)有bi個(gè)床位（1≤i≤n）。試模擬旅館管理系統(tǒng)中床位分派和回收的功能，設(shè)計(jì)能為單個(gè)旅客分派床位，在其離店便回收床位（供下次分派）的算法。[基本規(guī)定]（1）輸入數(shù)據(jù)分派時(shí)，輸入旅客姓名、年齡、性別、到達(dá)日期和所需房間等級(jí)。回收時(shí)，輸入房間等級(jí)、房間號(hào)和床位號(hào)。（2）輸出數(shù)據(jù)分派成功時(shí)打印旅客姓名、年齡、到達(dá)日期、房間等級(jí)、房間號(hào)碼和床位號(hào)碼。分派不成功時(shí)，如所有等級(jí)均無(wú)床位，則打印“客滿”信息；如旅客需要的等級(jí)均無(wú)空床位，則打印“是否樂(lè)意更換等級(jí)？”的詢問(wèn)信息。若旅客樂(lè)意更換，則重新輸入有關(guān)信息，再進(jìn)行分派，否則分派工作結(jié)束。核心算法：隊(duì)列的操作第十題：停車場(chǎng)管理[問(wèn)題描述]設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來(lái)的汽車只能在門外的便道上等候，一旦有車開(kāi)走，則排在便道上的第一輛車即可開(kāi)入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí)，在它之后開(kāi)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開(kāi)出大門外，其它車輛再按原順序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述規(guī)定進(jìn)行管理的模擬程序。[測(cè)試數(shù)據(jù)]設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)涉及三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“拜別”信息、汽車牌照號(hào)碼及到達(dá)或拜別的時(shí)刻，其中，‘A’表達(dá)成達(dá)；‘D’表達(dá)拜別，‘E’表達(dá)輸入結(jié)束。[基本規(guī)定]以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)涉及三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“拜別”信息、汽車牌照號(hào)碼及到達(dá)或拜別的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車拜別；則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。核心算法：棧和隊(duì)列的操作。第十一題：學(xué)生成績(jī)管理系統(tǒng)[問(wèn)題描述]編寫一個(gè)簡(jiǎn)樸的學(xué)生信息管理程序，能實(shí)現(xiàn)對(duì)學(xué)生信息的簡(jiǎn)樸管理。[基本規(guī)定]建立一個(gè)4個(gè)學(xué)生的信息登記表，每個(gè)學(xué)生的信息涉及：學(xué)號(hào)，姓名，和3門課程的成績(jī)（FOX,C,ENGLISH）。程序運(yùn)營(yíng)時(shí)顯示一個(gè)簡(jiǎn)樸的菜單，例如：（1）信息輸入（INPUT）（2）總分記錄（COUNT）（3）總分排序（SORT）（4）查詢(QUERY）其中：（1）對(duì)4個(gè)學(xué)生的信息進(jìn)行輸入；（2）對(duì)每個(gè)學(xué)生的3門課程記錄總分；(3)對(duì)4個(gè)學(xué)生的總分按降序排序并顯示出來(lái)；(4)查詢輸入一個(gè)學(xué)號(hào)后，顯示出該學(xué)生的有關(guān)信息；核心算法：查找和排序第十二題：哈希表的設(shè)計(jì)與實(shí)現(xiàn)[問(wèn)題描述]設(shè)計(jì)哈希表實(shí)現(xiàn)電話號(hào)碼查詢系統(tǒng)。[基本規(guī)定]1、設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；2、從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定電話號(hào)碼的記錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數(shù)擬定的前提下，嘗試各種不同類型解決沖突的方法（至少兩種），考察平均查找長(zhǎng)度的變化。核心算法：哈希表的存儲(chǔ)和查找第十三題：通訊錄管理系統(tǒng)該系統(tǒng)至少應(yīng)具有如下功能：1．輸入記錄規(guī)定隨時(shí)都能使用該項(xiàng)功能實(shí)現(xiàn)記錄的輸入，一次可以輸入一條記錄，也可以輸入多條記錄。2．輸出（1）按自然順序輸出（2）按某種排序順序輸出。至少兩種。3．查詢至少提供兩種查詢方式。4．修改至少提供兩種修改方式。5．刪除既能一次刪除一條記錄，也能一次刪除多條記錄。6．退出通訊錄管理結(jié)束后，正常退出系統(tǒng)。規(guī)定：每個(gè)記錄至少包含如下信息：姓名、電話、所在城市、所在單位、年齡、E-mail、備注等。以采單方式實(shí)現(xiàn)功能選擇控制。編寫功能獨(dú)立的函數(shù)實(shí)現(xiàn)各功能。4．記錄最大個(gè)數(shù)100。核心算法：鏈表的查找、插入和刪除第十四題：內(nèi)部排序算法比較[問(wèn)題描述]各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大約執(zhí)行時(shí)間。試通過(guò)隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。[基本規(guī)定]（1）對(duì)以下幾種常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序；折半折入排序；希爾排序；起泡排序；快速排序；簡(jiǎn)樸選擇排序；堆排序；歸并排序；基數(shù)排序。（2）待排序表的表長(zhǎng)不少于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參與的比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)（關(guān)鍵字互換計(jì)為3次移動(dòng)）。[測(cè)試數(shù)據(jù)]由隨機(jī)產(chǎn)生器決定。第十五題：記錄成績(jī)[問(wèn)題描述]給出n個(gè)學(xué)生的m門考試的成績(jī)表，每個(gè)學(xué)生的信息由學(xué)號(hào)、姓名以及各科成績(jī)組成。對(duì)學(xué)生的考試成績(jī)進(jìn)行有關(guān)記錄，并打印登記表。[基本規(guī)定]（1）按總數(shù)高低順序，打印出名次表，分?jǐn)?shù)相同的為同一名次；（2）按名次打印出每個(gè)學(xué)生的學(xué)號(hào)、姓名、總分以及各科成績(jī)。第十六題：大數(shù)相乘問(wèn)題[問(wèn)題描述]在用某種程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，也許需要解決非常大或者運(yùn)算精度規(guī)定非常高的整數(shù)（稱為大整數(shù)），這種大整數(shù)用該語(yǔ)言的基本數(shù)據(jù)類型無(wú)法直接表達(dá)。對(duì)這樣的兩個(gè)大整數(shù)，編寫程序計(jì)算兩個(gè)大整數(shù)相乘。[基本規(guī)定]輸入第一個(gè)數(shù)為：172586輸入第二個(gè)數(shù)為：1147程序運(yùn)營(yíng)后輸出172586*1147=對(duì)的答案。核心算法：用數(shù)組存儲(chǔ)大整數(shù)，數(shù)組元素代表大整數(shù)的一個(gè)位，通過(guò)數(shù)組元素的運(yùn)算模擬大整數(shù)的元素。第十七題：矩陣的運(yùn)算[問(wèn)題描述]矩陣式很多工程與科學(xué)計(jì)算問(wèn)題中的解決對(duì)象。在實(shí)際應(yīng)用中，經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中有很多零元素，稱為稀疏矩陣。對(duì)于這樣的矩陣可以進(jìn)行壓縮存儲(chǔ)，從而節(jié)省存儲(chǔ)空間，使矩陣的加法運(yùn)算可以有效的進(jìn)行。[基本規(guī)定](1采用十字鏈表表達(dá)稀疏矩陣，并實(shí)現(xiàn)矩陣的加法運(yùn)算。(2)要檢查有關(guān)運(yùn)算的條件，并對(duì)錯(cuò)誤的條件產(chǎn)生報(bào)警。第十八題：構(gòu)造n個(gè)城市連接的最小生成樹(shù)[問(wèn)題描述]一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。[基本規(guī)定]1)城市間的距離網(wǎng)采用鄰接矩陣表達(dá)，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。規(guī)定在屏幕上顯示得到的最小生成樹(shù)中涉及了哪些城市間的道路，并顯示得到的最小生成樹(shù)的代價(jià)。2)表達(dá)城市間距離網(wǎng)的鄰接矩陣(規(guī)定至少6個(gè)城市，10條邊)第十九題：字符串的模式匹配[問(wèn)題描述]在事務(wù)解決程序中，顧客的姓名、貨品的產(chǎn)地等一般都是作為字符串解決的。對(duì)于這些關(guān)鍵詞的查詢也就是在主串中尋找子串的過(guò)程，即為模式匹配。[基本規(guī)定]（1）輸入多條主串，及一條子串。（2）對(duì)于多條主串進(jìn)行模式匹配，假如匹配成功則返回主串內(nèi)容及子串在主串中的位置。假如匹配失敗，則返回0。第二十題：括號(hào)匹配的檢查[問(wèn)題描述]假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即（（）[]）或[（[][]）]等為對(duì)的格式，[（]）或（（（]均為不對(duì)的的格式。檢查括號(hào)是否匹配的方法可用“期待的緊迫限度”這個(gè)概念來(lái)描述。例如：考慮下列的括號(hào)序列：[([][])]12345678當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來(lái)的卻是2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的第7個(gè)括號(hào)“）”的出現(xiàn)，類似的，因只等來(lái)了第3個(gè)括號(hào)“[”，此時(shí)，其期待的緊迫限度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫限度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫限度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急切的任務(wù)了，??，依次類推?？梢?jiàn)這個(gè)解決過(guò)程正好和棧的特點(diǎn)相吻合。[基本規(guī)定]（1）讀入圓括號(hào)和方括號(hào)的任意序列，輸出“匹配”或“此串括號(hào)匹配不合法”。（2）以下面測(cè)試數(shù)據(jù)為例，若輸入（[]（）），結(jié)果應(yīng)輸出“匹配”輸入[（）]，結(jié)果應(yīng)輸出“此串括號(hào)匹配不合法”[實(shí)現(xiàn)提醒]設(shè)立一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則作為一個(gè)新的更急切的期待壓入棧中；若是右括號(hào)，并且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)相匹配，則將當(dāng)前棧頂?shù)淖罄ㄌ?hào)退出，繼續(xù)讀下一個(gè)括號(hào)，假如讀入的右括號(hào)與當(dāng)前棧頂?shù)淖罄ㄌ?hào)不匹配，則屬于不合法的情況。在初始和結(jié)束時(shí)，棧應(yīng)當(dāng)是空的。第二十一題：圖書(shū)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】設(shè)計(jì)一個(gè)計(jì)算機(jī)管理系統(tǒng)完畢圖書(shū)管理基本業(yè)務(wù)。【基本規(guī)定】（1）每種書(shū)的登記內(nèi)容涉及書(shū)號(hào)、書(shū)名、著作者、現(xiàn)存量、庫(kù)存量和借閱信息；（2）系統(tǒng)重要功能如下：①采編入庫(kù)：新購(gòu)一種書(shū)，擬定書(shū)號(hào)后，登記到圖書(shū)帳目表中，假如表中已有，則只將庫(kù)存量增長(zhǎng)；②借閱：假如一種書(shū)的現(xiàn)存量大于0，則借出一本，登記借閱者的書(shū)證號(hào)和歸還期限，改變現(xiàn)存量；③歸還：注銷對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。第二十二題：客戶消費(fèi)積分管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】針對(duì)客戶的消費(fèi)情況，進(jìn)行客戶管理，根據(jù)客戶的消費(fèi)積分對(duì)客戶實(shí)行不同限度的打折優(yōu)惠?！净疽?guī)定】⑴采用一定的存儲(chǔ)結(jié)構(gòu)進(jìn)行客戶信息的存儲(chǔ)；⑵對(duì)客戶的信息可以進(jìn)行修改、刪除、添加；⑶可以根據(jù)消費(fèi)情況進(jìn)行客戶積分的累加；⑷根據(jù)積分情況，對(duì)客戶實(shí)行不同限度的打折優(yōu)惠；第二十三題：家譜管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】設(shè)計(jì)并實(shí)現(xiàn)一個(gè)簡(jiǎn)樸的家譜管理系統(tǒng)?！净疽?guī)定】（1）建立家族關(guān)系并能存儲(chǔ)到文獻(xiàn)中。（2）實(shí)現(xiàn)家族成員的添加、刪除功能。（3）可以查詢家族成員的雙親、祖先、兄弟、孩子和后代等信息。（4）按某種順序輸出家譜信息（樹(shù)的遍歷操作）、以樹(shù)型結(jié)構(gòu)輸出家譜資料等功能。第二十三題：算術(shù)表達(dá)式求解【問(wèn)題描述】給定一個(gè)算術(shù)表達(dá)式，通過(guò)程序求出最后的結(jié)果。【基本規(guī)定】(1)從鍵盤輸入規(guī)定解的算術(shù)表達(dá)式；(2)采用棧結(jié)構(gòu)進(jìn)行算術(shù)表達(dá)式的求解過(guò)程；(3)可以判斷算術(shù)表達(dá)式對(duì)的與否；(4)對(duì)于對(duì)的的表達(dá)式給出最后的結(jié)果、并可以顯示運(yùn)算的整個(gè)過(guò)程。第二十四題：病人就醫(yī)管理【問(wèn)題描述】編寫一個(gè)程序?qū)崿F(xiàn)就醫(yī)管理。在病人就醫(yī)過(guò)程中，重要發(fā)生三件事：⑴預(yù)檢，分科室，掛號(hào)。⑵病人到達(dá)診室，將病歷本交給護(hù)士，排到等待隊(duì)列中候診。⑶護(hù)士從等待隊(duì)列中取出一位病人的病歷，該病人進(jìn)入診室就診?！净疽?guī)定】規(guī)定程序采用菜單方式，其選項(xiàng)及功能說(shuō)明如下：⑴掛號(hào)------預(yù)檢，分科室，生成就診號(hào)。⑵排隊(duì)------輸入病人的就診號(hào)，加入到病人排隊(duì)隊(duì)列中。⑶就診-------病人排隊(duì)隊(duì)列中最前面的病人就診，并將其從隊(duì)列中刪除。⑷查看排隊(duì)------從隊(duì)首到隊(duì)尾列出所有的排隊(duì)病人的病歷號(hào)。⑸下班---------退出運(yùn)營(yíng)。第二十五題：銀行業(yè)務(wù)模擬【問(wèn)題描述】設(shè)銀行有四個(gè)服務(wù)窗口，一個(gè)等待隊(duì)列,每個(gè)窗口均可以辦理存款、取款、掛失、還貸業(yè)務(wù)，每種業(yè)務(wù)所需的服務(wù)時(shí)間不同，優(yōu)先級(jí)不同。客戶到達(dá)銀行后，先到打號(hào)機(jī)上打號(hào)，號(hào)票上涉及到達(dá)時(shí)間、編號(hào)和需要辦理的業(yè)務(wù)，然后在銀行內(nèi)等候。當(dāng)任一服務(wù)窗口空閑時(shí),解決等候客戶中優(yōu)先級(jí)最高，排在最前面的客戶的業(yè)務(wù)。寫一個(gè)上述銀行業(yè)務(wù)的模擬系統(tǒng),通過(guò)模擬