1 内蒙古科技大学信息工程学院计算机系
《数据结构与算法》实验报告
姓名 谢航宇 学号 1367159137 实验成绩
班级 软件13-1 实验日期 第 9 周（星期二） 10 月28 日第 7、8节
项目号、实验名称 2、栈和队列的算法
实
验
要
求
（任课
教
师
提
供） 1、该实验要求掌握栈和队列的应用算法的实现；
2、验证性实验要求在实验前认真研读相关教材，作好充分的预习准备工作，写出实验预习报告；
3、学生必须在规定时间内独立完成，对实验过程中出现的问题，要求尽量做到独立思考，独立解决；
4、每次实验的结果必须经过教师认可后，实验方可结束；
5、要求学生必须认真对待每一个实验，不得缺席、迟到、早退；
6、要求实验中认真做好实验记录，实验后认真完成实验报告；
实
验
内
容
（由学
生
填
写） （一）栈的顺序存储的入栈与出栈
首先建立一个空栈，还需要插入一个新的元素为栈顶元素，在插入新元素之前需要判断当前栈是否已经满了，如果栈满了则发生溢出现象，如栈内有剩余空间则将栈顶指针增一，再将新的元素插入新的栈顶位置。
1.程序如下：
2.运行的结果如下：
2 3.入栈的程序为：
4.出栈的程序为：
3 （二）栈的链式存储的入栈与出栈
在链中插入一个新的元素，且只能插入在栈顶的位置。
1. 入栈的程序如下：
2.运行结果如下：
4 3.在出栈时需要在链中删除一个数据元素，只能删除栈顶元素，在删除栈顶元素之前需要判断当前栈是否为空，以防发生下溢现象。
4.出栈的程序如下：
以上完成了本次的实验报告。
5 评
语
（由教
师
填
写）
说明：
1、每个实验项目填写一份实验报告，电子版命名方式为：学号姓名项目号.doc。例如：1167111182张三3.doc表示张三做的第3个项目的实验报告。
2、实验报告电子版应该在实验后一周内由学习委员收齐后存放在一个文件夹下，文件夹命名方式为：软件12-1班3，表示软件12-1班第3个项目的实验报告，压缩。第一时间发送给任课教师。必须以班级为单位上交。
计算机操作系统(第三版)复习资料
- 1 - ★OS概念：OS是控制和管理计算机硬件和软件资源，合理组织计算机工作原理以及方程用户的功能的集合。
★OS目标：1有效性；2方便性；3可扩充性；4开放性。
★OS作用：1 OS作为用户与计算机硬件系统之间的接口；2 OS作为计算机系统资源的管理者；
3 OS实现了对计算机资源的抽象。
■OS特征：并发性、共享性、虚拟性和异步性四个基本特征；最基本的特征是并发性。
★OS功能：
1 处理机管理：作业和进程调度；
2 存储器管理：内存分配，地址映射，内存保护，内存扩充；
3 设备管理：缓冲区管理，设备分配，设备驱动，设备无关性；
4 文件管理：文件存储空间的管理，文件操作的一般管理，目录管理，文件的存取控制；
5 OS与用户之间的接口：程序接口，用户接口，联机接口，脱机接口，图形接口；
★多道批处理系统：
优点：资源利用率高、系统吞吐量大；
缺点：平均周转时间长、无交互能力。
★分时系统概念：将一台计算机很好的提供给多个用户同时使用，提高计算机的利用率。
★实时系统概念：是计算机系统可以立即对用户程序要求或者外部信号作出反应的系统，它可以分为硬实时系统和软实时系统。
●分时系统与实时系统的比较(及时性、交互性、可靠性、多路性、独立性)：
1 及时性：实时信息处理系统对实时性的要求与分时系统类似，都是以人所能接受的等待时间来确定；而实时控制系统的及时性，是以控制对象所要求的开始截止时间或完成截止时间来确定的，一般为秒级到毫秒级，甚至有的要低于100微妙。
2 交互性：实时信息处理系统具有交互性，但人与系统的交互仅限于访问系统中某些特定的专用服务程序。不像分时系统那样能向终端用户提供数据和资源共享等服务。
3 可靠性：分时系统也要求系统可靠，但相比之下，实时系统则要求系统具有高度的可靠性。因为任何差错都可能带来巨大的经济损失，甚至是灾难性后果，所以在实时系统中，往往都采取了多级容错措施保障系统的安全性及数据的安全性。
1
By Loser 计算机操作系统复习资料
第一章 操作系统引论
1.1 操作系统的目标和作用
操作系统的目标：⑴有效性(提高系统资源利用率；提供系统的吞吐量) ⑵方便性 ⑶可扩充性 ⑷开放性
操作系统的作用：①OS作为用户与计算机硬件系统之间的接口 ②OS作为计算机系统资源的管理者 ③OS实现了对计算机资源的抽象
1.2 操作系统的发展过程
①无操作系统的计算机系统
②单道批处理系统
⒈由于系统对作业的处理都是成批地进行的，且在内存中始终只保持一道作业，故称此系统为单道批处理系统。
⒉特征：⑴自动性 ⑵顺序性 ⑶单道性
③多道批处理系统
⒈后备队列：用户所提交的作业都先存放在外存上并排成一个队列。
⒉OS引入多道程序设计技术的好处：⑴提高CPU的利用率 ⑵提高内存和I/O设备利用率 ⑶增加系统吞吐量
⒊优缺点：⑴资源利用率高 ⑵系统吞吐量大 ⑶平均周转时间长 ⑷无交互能力
⒋设计多道批处理系统时，首先要考虑的是系统效率和吞吐量。
④分时系统
⒈定义：在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。
⒉特征：⑴多路性（同时性）⑵独立性 ⑶及时性 ⑷交互性
⒊通常采用时间片轮转法
⑤实时系统
⒈定义：指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。
⒉实时系统通常采用抢占式的优先数高者优先算法。
从可靠性上看，实时系统更强；从交互性上看，分时系统更强。
1.3 操作系统的基本特性
①并发性
⒈并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事情在同一时间间隔内发生。
⒉在操作系统中引入进程的目的，就是为了使多个程序能并发执行。
⒊在操作系统中引入进程概念的关键在于共享资源。
②共享性
在一段时间内只允许一个进程访问的资源称为临界资源或独占资源。
③虚拟技术
计算机操作系统练习题及答案 引论.txt爱空空情空空，自己流浪在街中；人空空钱空空，单身苦命在打工；事空空业空空，想来想去就发疯；碗空空盆空空，生活所迫不轻松。总之，四大皆空！单项选择
操作系统是对—C—进行管理的软件。
A软件 B硬件 C计算机资源 D应用程序
2. 从用户的观点看，操作系统是—A—。
A用户与计算机硬件之间的接口
B控制和管理计算机资源的软件
C合理地组织计算机工作流程的软件
D计算机资源的管理者
3. 如果分时操作系统的时间片一定，那么—B—，则响应时间越长。
A用户数越少 B用户数越多 C内存越少 D内存越多
4. 操作系统是一种—B—。
A应用软件 B系统软件
C通用软件 D工具软件
5. 操作系统的—D—管理部分负责对进程进行调度。
A存储器 B设备 C文件 D处理机
6.—A—要保证系统有较高的吞吐能力。
A批处理系统 B分时系统
C网络操作系统 D分布式操作系统
7.使多个用户通过与计算机相连的终端，以交互方式同时使用计算机的操作系统是—C—。
A单道批处理系统 B多道批处理系统
C分时系统 D实时系统
8. 操作系统的基本类型主要有—C—。
A批处理系统、分时系统和多任务系统
B单用户系统、多用户系统和批处理系统
C批处理系统、分时系统和实时系统
D实时系统、分时系统和多用户系统
9. 所谓—B—是指将一个以上的作业放入内存，并且同时处于运行状态，这些作业共享处理机和外围设备等其它资源。
A多重处理 B多道程序设计
