| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1246 人关注过本帖
标题:数据结构老师布置的一道作业题,迷茫了一个星期之久。
只看楼主 加入收藏
心中的十九
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2013-3-12
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:4 
数据结构老师布置的一道作业题,迷茫了一个星期之久。
综合性实验(满分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分的题目,想知道这道题的答案,哪位高手愿意写一写?
搜索更多相关主题的帖子: 计算 表达式 优先级 
2013-04-07 15:49
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:10 
分明是两道题、、、、

表达式神马的用栈处理。

那个调度百度一下 处理机调度算法 ,那个 最高响应比优先算法 就可以解决 饿死 问题


[fly]存在即是合理[/fly]
2013-04-08 08:56
peach5460
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:武汉
等 级:贵宾
威 望:30
帖 子:2780
专家分:6060
注 册:2008-1-28
收藏
得分:10 
进程调度的话,不是有个银行家算法可以解决饿死问题么
如果我没记错

我总觉得授人以鱼不如授人以渔...
可是总有些SB叫嚣着:要么给代码给答案,要么滚蛋...
虽然我知道不要跟SB一般见识,但是我真的没修炼到宠辱不惊...
2013-04-08 21:17
心中的十九
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2013-3-12
收藏
得分:0 
满世界找伪代码
2013-04-12 14:54
nuistkevin
Rank: 2
等 级:论坛游民
帖 子:17
专家分:10
注 册:2013-4-15
收藏
得分:0 
猎头职位-软件工程师
岗位职责
1.与世界顶尖的软件工程师共同开发虚拟化云计算产品
2.能独立处理和解决所负责的任务;
3.进行程序单元、功能的测试,查出软件存在的缺陷并保证其质量。
任职资格
1、 211或985高校计算机科学与技术或软件专业,英文流利;
2、 具有很强的学习能力和解决问题的能力;
3、 至少3年以上软件开发经验,精通C语言/C++,热衷于技术专研;
4、 熟练的数据结构知识体系与较强的算法能力,对堆栈、2X树、多X树有一定了解
5、 熟悉Windows, Linux X86/64 操作系统;
6、 熟悉Network configurations and environments;

工作地点:上海
有意者可以发送您的中英文简历至邮箱:
junpingwu@
QQ:2571168815
2013-04-15 11:57
快速回复:数据结构老师布置的一道作业题,迷茫了一个星期之久。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017197 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved