数据结构课程设计备选题目.doc

《数据结构课程设计备选题目.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计备选题目.doc（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计备选题目1. 运动会分数统计22. 飞机订票系统33. 文章编辑54. 地图着色问题55. 宿舍管理查询软件66. 校园导航问题67. 学校超市选址问题（带权有向图的中心点）78. 教学计划编制问题79. 活期储蓄帐目管理1010. 二叉排序树的实现1011. 最小生成树问题1112 通讯录的制作1113. 哈夫曼编码/译码器1214. 图书管理系统1515. 散列表的设计与实现1616. 走迷宫游戏1717. 银行业务模拟与离散事件模拟1818. 航班信息的查询与检索1919. 药店的药品销售统计系统（排序应用）2120. 二叉树的遍历2321、树的应用2322. 排序综合2

2、323. 学生成绩管理系统2424. 图的遍历和生成树求解2525. 线索二叉树的应用2626. 稀疏矩阵实现与应用2627.简单的职工管理系统2628.全国铁路运输网最佳经由问题2831.平衡二叉树操作演示3032.全国交通咨询模拟3133.表达式类型的实现3334.关键路径的实现3435.求复杂表达式的值3536. 分析二分查找成功时的平均查找长度351. 运动会分数统计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、

3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文

4、件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2. 飞机订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果

5、该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；e客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；3. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共 ；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据

6、的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；4. 地图着色问题设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。5. 宿舍管理查询软件1) 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：A. 采用交互工作方式B. 建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)2) 查询菜单: (用二分查找实现以下操作)A. 按姓名查询 B. 按学号查

7、询 C. 按房号查询3) 打印任一查询结果（可以连续操作）6. 校园导航问题设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。1、 基本要求：1） 设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2） 为来访客人提供图中任意景点相关信息的查询。3） 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。2、 实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网

8、。顶点和边均含有相关信息。7. 学校超市选址问题（带权有向图的中心点）设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。8. 教学计划编制问题问题描述大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程

9、号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下： 课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原

10、理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。9. 活期储蓄帐目管理 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。10. 二叉排序树的实现 用顺序和二叉链表作存储结构 1) 以回车(n)为输入结束标志,输入数列L，生成一棵二叉排

11、 序树T；2) 对二叉排序树T作中序遍历，输出结果；3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；11. 最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。12 通讯录的制作模块要求：第一个模块主函数main()的功能是：根据选单的选项调用各函数，并完成相应的功能。 第二个模块Menu()的功能是：显示英文提示选单。 第三个模块Quit()的功能是：退出选单。 第四个模块Create()的功能是：创建新的通讯录。 第五个模块Add()的功能是：在通讯录的末

12、尾，写入新的信息，并返回选单。 第六个模块Find()的功能是：查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。 第七个模块Alter()的功能是：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。 第八个模块Delete()的功能是：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。 第九个模块List()的功能是：显示通讯录中的所有记录。;设计要求：1) 每条信息至包含 ：姓名（NAME ）、性别(GENDER)、电话（TEL） 、城市（CITY）邮编（EIP）几项。2) 作为一

13、个完整的系统，应具有友好的界面和较强的容错能力13. 哈夫曼编码/译码器问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用

14、已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据

15、（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。 字符MABCDEFGHIJKLM频度206413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161实现提示（1）文件CodeFile的基类型可以设为子界型bit = 0.1。（2）用户界面可以设计

16、为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行Quit。请用户键入一个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。14. 图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1) 每种书的登记内容包括书号、书名、著作者、现存量和库存量；2) 对书号建立索引表（线性表）以提高查找效率；3) 系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则

17、只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1) 系统功能的进一步完善；2) 索引表采用树表。3) 设计内容4) 程序流程图5) 源程序6) 软件测试报告（包括所用到的数据及结果）15. 散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1) 设每个记录有下列数据项：电话号码、用户名、地址；2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3) 采用一定的方法解决冲突；4) 查找并显示给定电话号码的记录；5) 查找并显示给定用户名的

18、记录。【进一步完成内容】1) 系统功能的完善；2) 设计不同的散列函数，比较冲突率；3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。16. 走迷宫游戏程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2) 迷宫的墙足够结实，老鼠不能穿墙而过；3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5) 找出走出迷宫的所有路径，以

19、及最短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能17. 银行业务模拟与离散事件模拟【问题描述】假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9：00am，关门5：00pm）起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户（建议：客户进入时间使用随机函数产生），如果某个窗口的业务员正空闲，则可上前办理业务；反之，若4个窗口均有窗户所占，他便会排在人数最少的队伍后面。【任务要求】（1）编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。（2）建议有如下设置：a.客户到达时间随机

20、产生，一天客户的人数设定为100人。b.银行业务员处理时间随机产生，平均处理时间10分钟。（3）将一天的数据（包括业务员和客户）以文件方式输出。【测试数据】由随机数产生器生成18. 航班信息的查询与检索【问题描述】 该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。【任务要求】对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、

21、到达时间、飞机型号以及票价等，假设航班信息表（8条记录）航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班

22、号一项的格式为：K0 K1 K2 K3 K4 K5CZ3869其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。【测试数据】自行设定，注意边界等特殊情况。19. 药店的药品销售统计系统（排序应用）【问题描述】设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。【实现提示】在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额

23、。药品编号共4位，采用字母和数字混合编号，如：A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法。药品信息的元素类型定义：typedef struct node char num4; /*药品编号*/ char name10; /*药品名称*/ float price; /*药品单价*/ int count; /*销售数量*/ float sale;

24、/*本药品销售额*/ DataType;存储药品信息的顺序表的定义：typedef struct DataType rMaxSize; int length;SequenList;20. 二叉树的遍历要求实现二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法，应包含建树的实现。要求：遍历内容可以是数值可以是字符或者记录等等。21、树的应用要求实现树与二叉树的转换的以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。遍历内容可以是数值可以是字符或者记录等等。22. 排序综合 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行

25、排序。要求：1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3) 如果采用4种或4种以上的方法者，可适当加分。23. 学生成绩管理系统现有学生成绩信息文件1（1.txt），内容如下姓名 学号 语文 数学 英语 张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47. . . . 学生成绩信

26、息文件2（2.txt）,内容如下:姓名 学号 语文 数学 英语 陈果 31 57 68 82李华明 32 88 90 68张明东 33 48 42 56李明国 34 50 45 87陈道亮 35 47 58 77. . . . 试编写一管理系统,要求如下:1) 实现对两个文件数据进行合并,生成新文件3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)5) 要求使用结构体,链或数组等实现上述要求.6) 采用多种方法

27、且算法正确者,可适当加分.24. 图的遍历和生成树求解【基本要求】1) 先任意创建一个图；2) 图的DFS,BFS的递归和非递归算法的实现3) 最小生成树（两个算法）的实现，求连通分量的实现4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现25. 线索二叉树的应用要求：实现线索树建立、插入、删除、恢复线索的实现。26. 稀疏矩阵实现与应用要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。27.简单的职工管理系统【问题描述】对单位的职工进行管理，包括插入、删除、查找、排序等功能。【基本要求】职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：

28、将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。【实现提示】职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的姓名按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。【选做内容】将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操

29、作。28.全国铁路运输网最佳经由问题【问题描述】这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。【基本要求】（1） 查询某站所属的铁路线（2） 要求具备新增铁路线的管

30、理功能（3） 要求具备新增车站的管理功能（4） 针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序29.模拟电梯工作【问题描述】设计一个模拟电梯工作过程的图形演示系统，要求所设计的电梯能符合市场上大多数系统的要求。30.停车场管理【问题描述】 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进

31、入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。【实现要求】 要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。【实现提示】汽车的模拟输入信息格式可以是：(到达离去，汽车牌照号码，到达离去的时刻)。例如，(A，1，5)表示1号牌照车在5这个时刻到达，而(D，

32、5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(E，0，0)时结束。本题可用栈和队列来实现。31.平衡二叉树操作演示【问题描述】利用平衡二叉树实现一个动态查找表【基本要求】实现动态查找表的三种基本功能：查找、插入和删除。【测试数据】自行设定【实现提示】（1）初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后应更新平衡二叉树的显示。（2）平衡二叉树的显示可以采用凹入表形式，也可以采用图形界面画出树形。（3）教科书已给出查找和插入的算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为x的结点。如果x

33、不在叶子结点上，则用它左子树中的最大值或右子树中的最小值取代x。如此反复取代，指导删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡变换，则可采用插入平衡变换的反变换（如，左子树变矮对应于右子树长高）32.全国交通咨询模拟【问题描述】 出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞

34、机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】参考教科书7.6节图7.33的全国交通图，自行设计列出时刻表和飞机航班【实现提示】（1）对全国城市交通图和列出时刻表及飞机航班的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的

35、到达时间和票价；列出时刻表则需要根据交通图给出各个路段的详细信息，例如：基于教科书7.6节图7.33的交通图，对从北京到上海的火车，需给出北京至天津，天津至徐州及徐州至上海各段的出发时间、到达时间和票价等信息。（2）以邻接表做交通图的存储结构，表示边的结点除含有邻接点的信息外，还应包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。33.表达式类型的实现【问题描述】一个表达式和一个二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树的表示的算术表达式Expression的操作。【基本要求】1.ReadExpr（E） 以字符序列的形式输入语法正确的前缀表示式并够着表达式E

36、。2.WriteExpr（E） 用带括弧的中缀表达式输出表达式E。3.Assign（V,c） 实现对变量V的赋值（V=c）,变量的初值为0。4.Value（E） 对算术表达式E求值。5.CompoundExpr(P,E1,E2) 构造一个新的复合表达式（E1）P(E2)。【测试数据】1. 分别输入0；a;-91；+a*bc；+*5x2*8x；+*3x3*2x2x6并输出。2. 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。【实现提示】1.在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理以及相应的运算。2.在识别出运算数的同时，要将其字符形式转换成整数形式。3.用后

37、根遍历的次序对表达式求值。4.用中缀表示输出式E时，适当添加括号，以正确反映运算的优先次序。34.关键路径的实现【题目描述】找出实际工程中的关键路径，合理安排关键活动的施工顺序。【基本要求】（1）表示工程的图可以用邻接表或邻接矩阵存储（2）应能以图形的方式输出图（3）输出关键路径和关键活动35.求复杂表达式的值【题目描述】设计一个程序，计算包含如下标识符的表达式的值：（1） 数值：包括整数和实数，数值可带正、负号。（2） 一般运算符：正号、负号、加、减、乘、除、求模和乘方，其中可以包含括号。（3） 单词即运算函数：abs、sqrt、exp、ln、log10、sin、cos。【测试数据】输入中缀表达式：2*sqrt(16)-(-3+5)*(-4)运算结果： 1636. 分析二分查找成功时的平均查找长度【题目描述】设计一个程序，建立有有序序列R0.n-1进行二分查找产生的判定树，在此基础上完成如下功能：（1） 输出n=11时的判定树，并求成功情况下的平均查找长度ASL。（2） 通过构造判定树可以求得的成功情况下的平均查找长度ASL1；当把含有n个结点的判定树看成是一棵满二叉树时，其成功情况下的平均查找长度的理论值ASL2约为log2（n+1）-1，对于n=10,100,1000,10000，,，求出其ASL1、ASL2和两者的差值。