數(shù)據(jù)結構實驗題目-read

1、數(shù)據(jù)結構實驗題目,題目一約瑟夫環(huán),【問題描述】 約瑟夫（Joseph）問題的一種描述是：編號為1，2，…, n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設計一個程序求出出列順序。,題目一

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

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

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

5、若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和交納的費用（在便道上停留的時間不收費）。棧以順序結構實現(xiàn)，隊列以鏈表結構實現(xiàn)。,題目二停車場管理,【測試數(shù)據(jù)】 設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’表示離去，‘E’表示輸入結束。,題目二停車場管理,【實現(xiàn)提示】 需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。,題目二停車場管理,【選作內容】 (1)兩個棧共享空間，思考應開辟數(shù)組的空間是多少？ (2)汽車可

7、有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。 (3)汽車可以直接從便道上開走，此時排在它面前的汽車要先開走讓路，然后再依次排到隊尾。 (4)停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這種要求。,題目三 構造二叉樹,【問題的提出】 給定一棵二叉樹按某種次序遍歷可以得到唯一的結點序列。