|
#2
azzbcc2013-04-08 08:56
|
综合性实验（满分100）
以下综合性实验都做
（1）表达式求值问题
①问题描述
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。
②基本要求
从文件或键盘读入中缀表达式。
设计操作数为多位整数，操作符为加、减、乘、除、求模的中缀表达式求值算法。
设计将中缀表达式转换为后缀表达式的算法。
设计将中缀表达式转换为前缀表达式的算法。
设计后缀表达式求值算法。
设计前缀表达式求值算法。
输出各种形式的表达式。
③设计要点提示
算数表达式的计算往往是通过栈来实现的。
读入或扫描表达式的同时，完成运算符和操作数的识别处理。
识别操作数时，注意将其字符序列转换成整数（如：‘15’→15）或实数（如：‘15.4’ →15.4）形式进行存储。
可以将表达式转换成一棵二叉树，通过先序、中序、后序遍历得到前缀、中缀、后缀表达式。
仿表1来构建测试用例。
表1 表达式计算测试用例示例
测试项目 测试用例 预期结果
基本测试 3 3
1+2*3-4/2 5
11+22 33
1+22*(5-3)/4 12
(((2)))-3 -1
…
容错测试 1+2（ 表达式出错提示
2/0 表达式出错提示
2%0 表达式出错提示
(2-4)3.1 表达式出错提示
2+3)(-5 表达式出错提示
(((2))-3 表达式出错提示
2.5%2 表达式出错提示
1+++1 表达式出错提示
2 2 表达式出错提示
1#1 表达式出错提示
… 表达式出错提示
（2）任务调度
①问题描述
多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。
忽略任务提交的时间差，即认为各任务同时提交。
各任务不同时提交。
②基本要求
为任务列表设计数据结构和存储结构。
任务输入，至少包括任务编号及所需CPU的服务时间，任务数不得少于5个。
如果按提交顺序执行，求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间。
按平均等待时间最短，设计任务调度算法，输出任务的执行序列；求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间；并把结果与上一时间对比。
③设计要点提示
为使各任务平均等待时间最短，如果忽略任务提交的时间差，调度时应该按短任务优先进行调度，即：按照各任务需要CPU服务时间的长短，确定执行顺序，短的在前，长的在后。
例：任务列表2如下，则执行序列如表3所示。
表2 任务列表
任务 所需CPU时间(s) 任务 所需CPU时间(s)
P1 8 P5 9
P2 4 P6 20
P3 12 P7 15
P4 5
表3 任务执行序列
任务 所需CPU时间(s) 等待时间 结束时间 开始时间
P1 4 0 4 0
P2 5 4 9 4
P3 8 9 17 9
P4 9 17 26 17
P5 12 26 38 26
P6 15 38 53 38
P7 20 53 73 53
根据上一问题的分析，需要根据任务列表，按任务的CPU服务时间进行排序。
如果考虑任务提交的时间差，应该按“最短剩余时间”优先进行调度。调度发生在每次任务提交时，从未完成任务中选择需要CPU时间最短的任务。
例：任务提交情况如表4所示。
表4 任务列表
任务 提交时刻 所需CPU时间(s) 任务 提交时刻 所需CPU时间(s)
P1 0 8 P5 4 9
P2 1 4 P6 5 20
P3 2 12 P7 6 15
P4 3 5
0时刻，只有P1，所以运行P1。
1s时，P2提交，此时，P2需要CPU服务时间为4，P1还需7，则暂停P1，先运行P2。
2s时，P3提交，此时，P1、P2、P3各自需CPU服务时间为：7、3、12，所以继续运行P2。
依次类推，直至所有任务完成。
④思考
最短作业优先，存在“长任务饥饿”的问题，即如果动态地不断加入作业，只要提交作业所需要的CPU服务时间比较短，则先提交的长任务将一直得不到服务，如何解决该问题？
PS：这道题价值100分，最后我没写。作了一道80分的题目，想知道这道题的答案，哪位高手愿意写一写？
