數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目-read

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目,題目一約瑟夫環(huán),【問(wèn)題描述】 約瑟夫（Joseph）問(wèn)題的一種描述是：編號(hào)為1，2，…, n的n個(gè)人按順時(shí)針?lè)较驀蝗Γ咳顺钟幸粋€(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。,題目一

2、約瑟夫環(huán),【基本要求】 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序打印出各人的編號(hào)。,題目一約瑟夫環(huán),【測(cè)試數(shù)據(jù)】 m的初值為20；密碼：3，1，7，2，4，8，4（正確的結(jié)果應(yīng)為6，1，4，7，2，3，5）。,題目一約瑟夫環(huán),【實(shí)現(xiàn)提示】 程序運(yùn)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)n≤30。,題目一約瑟夫環(huán),【選作內(nèi)容】 向上

3、述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。,題目二停車(chē)場(chǎng)管理,【問(wèn)題描述】 設(shè)停車(chē)場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在車(chē)場(chǎng)的最北端），若車(chē)場(chǎng)內(nèi)已停滿n輛汽車(chē)，則后來(lái)的汽車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后開(kāi)入的車(chē)輛必須先退出車(chē)

4、場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其它車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。,題目二停車(chē)場(chǎng)管理,【基本要求】 以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：

5、若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或便道上的停車(chē)位置；若是車(chē)輛離去，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。,題目二停車(chē)場(chǎng)管理,【測(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’，

6、0，0）。其中：‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。,題目二停車(chē)場(chǎng)管理,【實(shí)現(xiàn)提示】 需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車(chē)讓路而從停車(chē)場(chǎng)退出來(lái)的汽車(chē)，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車(chē)，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)的牌照號(hào)碼和進(jìn)入停車(chē)場(chǎng)的時(shí)刻。,題目二停車(chē)場(chǎng)管理,【選作內(nèi)容】 (1)兩個(gè)棧共享空間，思考應(yīng)開(kāi)辟數(shù)組的空間是多少？ (2)汽車(chē)可

7、有不同種類(lèi)，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車(chē)和1.5輛小汽車(chē)的占地面積相同，1輛十輪卡車(chē)占地面積相當(dāng)于3輛小汽車(chē)的占地面積。 (3)汽車(chē)可以直接從便道上開(kāi)走，此時(shí)排在它面前的汽車(chē)要先開(kāi)走讓路，然后再依次排到隊(duì)尾。 (4)停放在便道上的汽車(chē)也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車(chē)場(chǎng)的車(chē)低，請(qǐng)思考如何修改結(jié)構(gòu)以滿足這種要求。,題目三 構(gòu)造二叉樹(shù),【問(wèn)題的提出】 給定一棵二叉樹(shù)按某種次序遍歷可以得到唯一的結(jié)點(diǎn)序列。