山东科技大学2007年招收硕士学位研究生入学考试
数据结构与操作系统试卷
数据结构部分
注意事项：
1、算法应说明基本思路，应对主要数据类型、
变量给出说明，所写算法应结构清晰、简明易懂，
应加上必要的注释。
2、算法可用（类）PASCAL语言、（类）C语言等你
所熟悉的高级语言编写，但要注明语种。
一、解答下列问题[每小题4分，共16分]：
1、[4分]为什么要分析算法的时间复杂度？
2、[4分]简述代码区、全局数据区、栈区、堆区
在程序运行时的作用。
3、[4分]求模式串s＝’aaaabc’的next及nextval
函数。
4、[4分]证明根据森林的先序序列与中序序列
可以唯一确定一个森林。
二、综合应用题[每小题8分，共24分]：
1、[8分]推导满k叉树上的叶子结点数n0和非
叶子结点数n1之间的关系（即用k和n1表示n
0）。
第一章： 1. 什么是操作系统？OS的基本特性是？主要功能是什么 OS是控制和管理计算机硬件和软件资源，合理组织计算机工作原理以及方程用户的功能的集合。特性是：具有并发，共享，虚拟，异步的功能，其中最基本的是并发和共享。主要功能：处理机管理，存储器管理，设备管理，文件管理，提供用户接口。 2. 操作系统的目标是什么？作用是什么？ 目标是：有效性、方便性、可扩充性、开放性 作用是：提供用户和计算机硬件之间的接口，提供对计算机系统资源的管理，提供扩充机器 3. 什么是单道批处理系统？什么是多道批处理系统？ 系统对作业的处理是成批的进行的，且在内存中始终保持一道作业称此系统为单道批处理系统。 用户所提交的作业都先存放在外存上并排成一个队列，然后，由作业调度程序按一定的算法从后备队列中选择若干个调入作业内存，使他们共享CPU和系统中的各种资源。 4 ?多道批处理系统的优缺点各是什么？ 优点：资源利用率高，系统吞吐量大。缺点：平均周转时间长，无交互能力。 引入多道程序技术的前提条件之一是系统具有终端功能，只有有中断功能才能并发。 5. 什么是分时系统？特征是什么？ 分时系统是指，在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互的方式使用计算机，共享主机中的资源。 特征：多路性、独立性、及时性、交互性 *有交互性的一般是分时操作系用，成批处理无交互性是批处理操作系统，用于实时控制或实时信息服务的是实时操作系统，对于分布式操作系统与网络操作系统，如计算机之间无主次之分就是分布式操作系统，因为网络一般有客户-服务器之分。 6. 什么是实时操作系统？ 实时系统：系统能及时响应外部事件的请求，在规定的时间内处理完。按照截止时间可以分为1硬实时任务（必须在截止时间内完成）2软实时任务（不太严格要求截止时间） 7用户与操作系统的接口有哪三种？ 分为两大类：分别是用户接口、程序接口。 用户接口又分为：联机用户接口、脱机用户接口、图形用户接口。 8. 理解并发和并行？并行（同一时刻）并发（同一时间间隔） 9. 操作系统的结构设计 1 ?无结构操作系统，又称为整体系统结构，结构混乱难以一节，调试困难，难以维护 2?模块化os结构，将os按功能划分为一定独立性和大小的模块。是os容易设计，维护, 增强os的可适应性，加速开发工程 3?分层式os结构，分层次实现，每层都仅使用它的底层所提供的功能 4. 微内核os结构，所有非基本部分从内核中移走，将它们当做系统程序或用户程序来实现，剩下的部分是实现os核心功能的小内核，便于扩张操作系统，拥有很好的可移植性。 第二章： 1 ?什么叫程序？程序顺序执行时的特点是什么？ 程序：为实现特殊目标或解决问题而用计算机语言编写的命令序列的集合特点：顺序性、封闭性、可再现性 2. 什么是前趋图？（要求会画前趋图）P35图2-2 前趋图是一个有向无循环图，记为DAG ,用于描述进程之间执行的前后关系。 3?程序并发执行时的特征是什么？ 特征：间断性、失去封闭性、不可再现性
谢谢阅读一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四 个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为（）。 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序B．起泡排序 C．简单选择排序 D．直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是O(1) B. 采用链式存储时，随机存取的时间复杂度是O(1) C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是（）。 A．4 B．3 C．1 D．不确定 5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是（）。 A．4 B．3 C．1 D．不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(h) 7.有10个节点的无向图，至少需要多少条边才能成为一个连通图（）。 A．5 B．45 C．9 D．10 8.关于邻接矩阵，下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C．若图G的邻接矩阵是对称的，则G不一定是无向图 D．若图G的邻接矩阵是对称的，则G不一定是有向图 9.折半查找算法中查找的时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(n2) 谢谢阅读
山东科技大学2009—2010学年第二学期 《操作系统》考试试卷（B卷） 班级姓名学号 一、判断题（回答“正确”或“错误”，并对错误命题简要说明理由）（每小题2分，共10分） 1、Wait、Signal操作中信号量的值永远代表着某类可用资源的数量。 2、死锁的形成只与资源分配策略有关，而与并发进程的执行速度无关。 3、进程A、B共享变量X，需要互斥执行；进程B、C共享变量Y，B、C也需要互斥执行。因此，进程A、C必须互斥执行。 4、请求分页系统中一条指令执行期间产生的缺页次数可能会超过4次。 5、最佳适应算法比首次适应算法具有更好的内存利用率。 二、填空题（每空1分，共10分） 1、在多道批处理系统中，通常采用以下两种作业调度算法：（1）和（2）。 2、一个作业从进入系统到运行结束，一般要经历的阶段是提交，（3），（4），（5）。 3、分时系统的特点是：（6）、（7）、及时性和交互性。 4、系统中各进程对互斥资源操作的程序段必须互斥执行。我们把这种互斥执行的程序段称为（8）。 5、缓冲的实现方法有（9）和（10）两种。 三、单项选择题（每小题2分，共30分） 1、响应比高者优先作业调度算法是以计算时间和______来考虑的。 A．输入时间B．完成时间C．周转时间D．等待时间
2、操作系统中______采用了以空间换时间的技术。 A．SPOOLing技术B．覆盖技术C．通道技术D．虚拟存储技术 3、虚存是______。 A．容量扩大了的内存B．提高运算速度的设备 C．实际不存在的存储器D．进程的地址空间及其内存扩大方法 4、在多道批处理系统中，用户的作业是由______组成的。 A．程序、数据、作业说明书B．程序、数据 C．程序、作业说明书D．程序 5、在可变式分配方案中，首先适应算法是将空白区在空白区表中按______次序排列。 A．地址递增8．地址递减C．容量递增D．容量递减 6、作业调度中的先来先服务算法是以______为出发点考虑的。 A．作业执行时间B．作业的周转时间 C．作业等待时间D．等待时间加运行时同 7、设m为同类资源数，n为系统中的并发进程数。当n个进程共享m个互斥资源时，每个进程的最大需求是w。下列情况下，系统会死锁的是______。 A．m=2, n=l, w=2 B．m=2, n=2, w=1 C．m=4, n=3, W=2 D．m=4, n=2, w=3 8、存储管理方案中，______可采用覆盖技术。 A．单一连续区B．可变分区C．段式D．段页式 9、分页式虚拟存储系统中，页面的大小与可能产生的缺页中断次数______。 A．成正比B．成反比C．无关D．成固定比值 10、从资源分配角度看，外设可分为若干种，其中不包括______。 A ．虚拟设备B．物理设备C．独占设备D．共享设备 11、采用树形目录结构可以______。 A．缩短查找文件的时间B．节省存储空间 C．减少文件的传送时间D．存储更多的文件 12、在进程基本调度状态转换时，会出现的情况是______。
毕业实习报告书 系（部）机电工程系 专业班级机制xxx班 学生姓名xxx 完成日期200x年4月25日山东科技大学x x校区
一、毕业实习目的 毕业实习是大学中最后一次理论与实践相结合的综合性实践锻炼，能让自己充分的将所学习的专业知识学以致用，从各方面锻炼提高自己的综合素质，毕业是我们机械设计制造及其自动化专业知识结构中不可缺少的组成部分。本次毕业实习的目的是为促进毕业设计的完成，根据学校安排组织进行实习参观，在实习过程中，使我们获得基本生产的感性认识，理论联系实际，扩大知识面，将所学的专业理论知识与生产实际相结合，从而进一步提高自己的理论基础和实践操作技能。通过本次实习进一步了解机械制造业的状况,以及一般零部件的生产加工，从而为毕业设计收集相关的实践技术资料及原始素材，并与现场技术人员进行技术咨询，为毕业设计做好充分的准备。 二、实习任务 这次毕业参观实习在指导老师的带领下我们分别参观了山东山工机械有限公司、山东省尤洛卡自动化装备股份有限公司。实习中学到了很多在课堂没学到的知识,让我们受益匪浅。 根据本次毕业实习目的，我们将要完成： 1、掌握机械加工工艺方面的知识及方法； 2、了解切削刀具方面的知识，熟悉常用刀具的结构、选择、用途等； 3、熟悉机械加工生产工艺和方法及加工机床； 4、了解企业生产管理模式，学习先进的管理方式方法； 5、了解液压系统及控制方法，为毕业设计做好准备。 三、实习内容 在指导老师的带领下我们依次参观了山东山工机械有限公司、山东省尤洛卡自动化装备股份有限公司。下面自己对这次毕业实习内容总述如下： 参观实习地点一：山东山工机械有限公司 公司简介： 山东山工机械有限公司坐落在古九州之一的山东省青州市，公司于2005年3月22日与世界500强之一的卡特比勒公司合资成立中美合资山东山工机械有限公司。属于国家大型一档企业，国家经贸委定点生产轮式装载机的重点
山东科技大学怎么样 山东科技大学，顶着种种压力和阻拦，毅然从泰安济南两校区分批搬迁至青岛，这可以称得上青岛发展史上重要的一笔，无论科技大学选择青岛，还是青岛选择科技大学，对两者都是重要的。 山东科技大学决定在黄岛建新校区，从开始到现在依然是默默进行，可谓享受了难得的孤独，而当地政府却也很少表态，对其支持和关心的力度也不够，青岛市民对其也不甚了解，只认为是一般的职业技术教育学院而漠视它的存在，甚至很少有人知道这个学校还搬迁到了黄岛，这些都让科技大学的师生无比尴尬。 在青岛市媒体宣传中也从不提山东科技大学的名字，只是反复强调青岛的四所本科院校，中国海洋大学,青岛大学,青岛科技大学,青岛理工大学.学校的师生的尴尬境地从他们的话中可见一斑：“也许青岛不稀罕我们这样的学校吧，人家需要的是北大，山大这样的高校引进，还是在济南和泰安好些。”“与一些青岛市民提起山东科技大学，会很诧异的看着你，说…你们是民办高校还是职业技术学院啊，没听过，只听过青岛科技大学。?我们直接和青岛科大合并算了，组建新的青岛科技大学。那样好多专家人才也不会走失了。?人才走失的原因，很多是因为搬迁到黄岛后位置过于偏僻，生活极其不方便导致。他们说与青岛科技大学合并的戏谑正是看中了青岛科技大学新校区的位置。目前因为山东科技大学搬迁而辞职的专家学者已经不少，他们有的是省部级重点实验室的相关带头人。不知道这是青岛市引进的尴尬，还是山东科技大学选择青岛的尴尬。 现在诸如学校园区建设问题，教师宿舍楼问题等等，都存在着许多障碍，至于如何解决，那就看青岛市的政府了。这些大问题暂且不考虑，只一简单的解决科技大学到薛家岛直达公交车的问题，就很让科大师生困惑。科技大学师生若到开发区够物游玩，需要先乘10路区间车到港头陈，再转乘1，2路车。期间浪费的时间和金钱不用多说。为此学校每到周末，只能开几趟前往长江路立群的班车，解决他们够物难的问题。我与当地一个公交车司机说到这件事，人家还振振有辞说，你们反映到区政府也没用，区里能为了你们一个科大增改公交线路？说的让我无言以对。这可是一个综合大学啊，目前师生已经过万，暑假后全部搬迁来此，将是2万---三万人。满足这么多师生生活问题是小事吗？市区政府不能给他们解决吗？ 山东科技大学本身在夹缝中生存已经很为难了，当地政府的不重视更让他们寒心。当初，刚决定搬迁时，是动员泰安校区的，学生已经把行李都运到了黄岛，但是遇到了当地政府和上级政府的阻拦，只好作罢，临时动员济南校区学生搬迁。雄赳赳气昂昂的大队人马在无人喝彩声中孤独的搬迁到了荒凉的地方。学生失望，老师失望，本想融入青岛这个城市，但是却遭遇到许多意想不到的困难，最重要的是当地政府的认同与支持。学校师生期望能与驻青各高校互增交往，共同发展。[原文为山东科技大学学生在贴吧内所发] [评:在地理位置上,山东科技大学位于青岛下辖的黄岛区,但不在市区,与青岛市区隔着胶州弯,实属各种交通不便;即便现在开通了海底隧道,从山东科技大学坐车到通过隧道到市区,也需要两个小时,更不用说这条公交线路有多机,每年因为交通不便原因,很多大公司都不来山科进行校园招聘,就业机会比在市区的四所大学少了不少,而且假期各种大学生兼职活动比市区的大学就更少了,山科的招生办的老师也说过,向别人介绍说,山东科技大学在青岛时,心里感觉是在骗人,因为在这你看不到半点青岛的影子….]
数据结构和操作系统试题 姓名________ 学号_________ 得分__________ 数据结构部分 一、判断题。（正确的在括号里打√，错误的打×） ①数据元素是数据的最小单位。（） ②完全二叉树中，若一个结点没有左孩子，则必是树叶。（） ③关键路径是AOE网络中从源点到汇点的最长路径。（） ④顺序存储法适用于存储结构为顺序或链式存储的线性表。（） ⑤对任何一棵二叉树，如果叶子结点数为n0，度为2的结点数为n2，则n2 = n0 - 1。（） ⑥快速排序是一种属于选择排序类的方法，时间效率较高。（） ⑦数组的常见操作有存取、修改、删除、插入。（） ⑧若非空二叉树中每个结点有两个子结点，且左子树的根小于根结点，右子树的根不小于根结点，则是二叉排序树。（） ⑨将一棵树转换为二叉树后，根结点没有左子树。（） ⑩在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。（） 二、选择和填空 1.在一个长度为n的顺序表（即顺序存储的线性表）中，向第i个元素（1<=i<=n+1）之前插入 一个新元素时，需向后移动______个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 2.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为__________。 3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 ________存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C. 双向循环链表 D.仅有尾指针的单循环链表 4.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过________。 A．n/2 B．n C．(n+1)/2 D．n+1 5. 对有18个元素的有序表A[1]～A[18]作二分查找，则查找A[3]的比较序列的下标为______。 A．1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 6. 下面程序段的时间复杂度是______________。 for (i=0; i 山东科技大学青岛校区景观文化建设综述在山东省委、省政府的正确领导下，在省委高校工委和省教育厅的直接领导下，在社会各界人士与朋友的热切帮助下，山东科技大学自2001年6月启动青岛校区建设，至2006年10月校庆55周年之际基本建设完成，历时五年多的时间。当前，这所占地面积3000亩、建筑面积达140万平方米的现代化校园已成为学校办学的主体，成为在校35000名师生的学习、工作与生活之家；因其环境幽雅，景色秀丽、功能完善、人文荟萃且深蕴科大历史发展内涵，也成为广大师生的健康之家、欢乐之家、精神之家。兹趁省委高校工委组织评选高校校园文化建设优秀成果、以系统推进高校校园文化建设的契机，将我校在校园景观文化上的设计理念、工作思路和景观概况，向各位领导与专家作一简略的介绍。 早在青岛校区建设之初，学校就提出了“总体规划，分期实施；高标准建设，可持续发展；五年初具规模，十年配套完善”的总体思路，制定了新校区建设的三个“三原则”，即：“高标准、高质量、高水平”；“大空间、大绿地、大水面”；“超前性、国际性、特色性”。本着这一总的建设思路与原则，联系科大历史发展的实际，我们在校园景观文化设计与建设上，具体做了如下的工作。 一、“山、海、泉”交融的校园景观文化特质 在整个青岛校区校园景观文化环境的培育上，我们根据校园南（教学办公区）与北（学生生活区）功能分区、以及教工住宅区相对独立的建筑布局特点，坚持对建筑群采用区域划分与系统命名的方 式，并结合科大近六十年来发展的历史实际以及在泰山、泉城、青岛三地办学的格局及现状，使学校校园景观在整体上呈现出“山、海、泉”交汇贯通的文化特质。具体而言： 将南部教学办公三个区自西向东命名为“历山园”、“泰山园”、“珠山园”，各个园区的主要景观——广场，分别命名为历山广场、泰山广场、珠山广场。其中，泰山广场对应学校主大门——南大门，处于整个校园东西的中轴线上。取义“历山”以成其“勤”，取义珠山以成其“勇”，取义泰山以成其“高”。 将北部学生生活三个区自西向东将其命名为“智泉园”、“悟泉园”、“慧泉园”，自古以来，中国人便以泉水作为智慧的象征，《周易·蒙卦》即以“山下出泉”为卦象，寄寓开启蒙昧之意。灵韵生动的济南七十二名泉，更是启迪我校师生智慧的永不枯竭的源泉。取义于此，希望广大莘莘学子在科大这片土地上体悟、探寻、开掘智慧之泉。 将教工住宅区命名为“山海花园”，住宅区四个小区自东向西命名为“怡山园”、“乐水园”、“天和园”、“地祥园”。科大教工住宅区依傍笔架山北腰而建设，不少住在顶楼的教工用户，拉开东侧书房窗帘，即可远眺祖国黄海之蔚蓝海岸，以及北方最大的港湾码头——青岛港前湾港码头。依山傍海，仁者乐山，智者乐水，天人一体，万物祥和。这样的景观文化设计与命名，充分体现了当今社会以人为本、科学发展的精神。 科大整个校园景观所体现出来的“山、海、泉”和谐一体的文化特质，是当今学校三地办学、协同发展、争创一流的一个缩影、一个 《数据结构与操作系统》考试大纲 一、考查目标 数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。 二、考试形式与试卷结构 （一）试卷成绩及考试时间 本试卷满分为150分，考试时间为180分钟。 （二）答题方式 答题方式为闭卷、笔试。 （三）试卷内容结构 各部分内容所占分值为： 数据结构75分 操作系统75分 （四）试卷题型结构 1．数据结构 选择题：15小题，每小题2分，共30分 简答题：3小题，每小题10分，共30分 算法题：1小题，每小题15分，共15分 2.操作系统 三、考查范围 数据结构 一、考查目标 1、掌握数据结构的基本概念、方法和技术。 2、掌握程序设计的基本方法和技巧。 3、能够应用相关知识解决一些有实际背景的问题。 二、考查内容 1. 绪论 数据结构的概念；基本概念与术语；算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。 2. 线性表 线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；线性表的各种实现方式能够实现指定的操作。 3.栈和队 栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。 4. 串 串的基本概念，朴素的模式匹配算法。 5.数组 数组的定义；数组的存储，行序和列序；特殊矩阵的定义；特殊矩阵的压缩存储。 6.树和二叉树 山东科技大学年中外合作办学招生简章 一、学校简介 山东科技大学建校于年，现已发展成为一所工科优势突出，行业特色鲜明，工学、理学、管理学、 文学、法学、经济学、艺术学等多学科相互渗透、协调发展的省属重点大学， 是山东省重点建设的应用基础型人才培养特色名校，现有在校生余人，学校在青岛、泰安、济南三地办学，合作办学各专业设在济南校区。 二、中外合作办学本科项目 专业情况： 序号专业名称层次合作学校教育部批号 信息管理与信息系统本科美国克拉克大学2A 国际经济与贸易本科美国克拉克大学2A 澳大利亚塔斯马尼2A 电气工程及其自动化本科 亚大学 澳大利亚塔斯马尼 2A 通信工程本科 亚大学 金融学本科英国伍斯特大学2A 合作学校简介： 美国克拉克大学建于年，是一所研究教案型大学，与哈佛大学、耶鲁大学同为著名的美国大学 协会创始成员，据《美国新闻与世界报道》，其最新排名为全美第位。 塔斯马尼亚大学始建于年，是英国高等教育评选出的全球强大学之一，是澳洲高等教育委员会评 选的最有研究成就的澳洲前十所大学之一。 伍斯特大学始建于年，是一所公立大学，为现任英国教育部部长的母校。伍斯特大学商学院是英国 最受欢迎的商学院之一，在欧洲拥有良好的声誉，商学院课程都经过了英国管理准则协会（）、英国国 家职业标准（）、英国管理标准中心（）的评估并获得了认证。 培养模式： 与美国克拉克大学合作办学：培养方案和培养计划由中美双方学校共同制定，学生在 山东科技大学学习四年，美国克拉克大学派教师与山东科技大学教师共同承担课程的教案， 学生完成培养计划规定的全部课程，成绩合格，获得山东科技大学普通高等教育本科毕业 1 / 3 计算机操作系统 一．单项选择题（每小题2分，共30分） 1.进程具有并发性和（）两大重要属性。 A.动态性 B.静态性 C.易用性 D.封闭性 2.在分时操作系统中，（）是衡量一个分时系统的一项重要指标。 A.响应时间 B.高可靠性 C.吞吐量 D.时间片轮转 3.进程所请求的一次打印输出结束后，将使进程状态从（）。 A.运行态变为就绪态 B.运行态变为等待态 C.就绪态变为运行态 D.等待态变为就绪态 4.常用的文件存取方法有两种：顺序存取和（）存取。 A.流式 B.串联 C.索引 D.随机 5.采用多道程序设计能（）。 A.减少调度次数 B.减少处理器空闲时间 C.缩短每道作业的执行时间 D.避免发生资源竞争现象 6.临界区是指并发进程中涉及共享变量的（）。 A.程序段 B.管理信息区 C.公共数据区 D.信息保留区 7.产生死锁的四个必要条件是：互斥使用、（）、不可抢占和循环等待资源。 A.请求并阻塞 B.占有并等待 C.请求并释放 D.释放并阻塞 8.（）是一种只能进行wait操作和signal操作的特殊变量。 A.调度 B.进程 C.同步 D.信号量 9.在下面的叙述中正确的是（）。 A.一个进程一定包含多个线程 B.进程是比线程更小的能独立运行的基本单位 C.线程的引入增加了程序执行时的时空开销 D.引入线程可提高程序并发执行的程度，可进一步提高系统效率 10.设有n个进程共用一个相同的程序段(临界区),如果每次最多允许m个进程(m 1.2操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核 现代操作系统中xx采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内核（microkernel），其他功能都在核外实现，通过微内核提供 的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核（monolithic kernel）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下3个方面的功能。 （1）xx处理。xx处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽xx的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当xx事件产生时，先由内核截获并转向xx处理例行程序进行原则处理，它分析xx事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束xx事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢 山东科技大学泰安科技学院2014-2015学年第一学期 《操作系统》考试试卷（A卷） 班级姓名学号 一、单项选择题（每小题1分，共10分） 1. 下面关于进程的叙述中正确的是（）。 A.进程获得CPU运行是通过调度得到的 B.优先级是进程调度的重要依据，一旦确定就不能改变 C.进程申请CPU得不到满足时，其状态变为阻塞 D.在单CPU的系统中，任何时刻都有一个进程处于运行状态。 2. 某基于动态管理的计算机，其存储容量为55MB（初始为空闲）,采用最佳分配算法，分配和释放的顺序为：分配15MB,分配30MB,释放15MB,分配8MB，分配6MB,此时主存中最大空闲分区的大小是（）。 A．7MB B.9MB C．10MB D．15MB 3. 属于实时控制系统的是（）。 A．飞机自动驾驶系统 B．飞机订票系统 C．电子商务系统 D．管理信息系统 4. 设m为同类资源数，n为系统中并发进程数。当n个进程共享m个互斥资源时，每个进程的最大需求是w；则下列情况会出现系统死锁的是( )。 A．m=4,n=3,w=1 B．m=4,n=2,w=3 C．m=2,n=l,w=2 D．m=2,n=2,w=l 5. 系统调用是（）。 A．用户编写的一个子程序 B．高级语言中的库程序 C．操作系统中的一条命令 D．操作系统向用户程序提供的接口 6.下列文件物理结构中，适合随机访问且易于文件扩展的是( ) 。 A．连续结构 B.索引结构 C.链式结构且磁盘块定长 D.链式结构且磁盘块变长 7．在I/O设备控制方式的发展过程中，最主要的推动力是 ( ) 。 A．提高资源利用率 B．提高系统吞吐率 C．减少CPU对I/O控制的干预 D．提高CPU和I/O设备并行操作的程度 8．文件系统中，（）利用二进制的一位来表示磁盘中一块的使用情况。 A．空白文件目录 B．位示图 C．空闲块链 D．空闲块成组链 9. 如果文件系统中有两个文件重名，不应采用（）。 A. 单级目录结构 B.两级目录结构 C. 树型级目录结构 D.多级目录结构 10. 如果I/O设备与存储设备间的数据交换不经过CPU来完成，则这种数据交换方式是( ) 。 A．程序查询方式 B．中断方式 C． DMA方式 D．外部总线方式 二、填空题（每小题2分，共20分） 1．操作系统具有__ ___、__ ___、共享和异步这四个基本特征。 2．某医院准备在挂号处增设一实时触摸屏查询系统，该系统除了应具有快速响应和高可靠性外，还应具有___________性功能。 3．是操作系统中最重要的记录型数据结构，记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息。 ４．引入缓冲技术可以提高CPU和I/O设备之间的___________操作程度。 ５.操作系统的目标是___ __、___ __、可扩充性和开放性。 ６．磁盘的访问时间分为：___ __、旋转延迟时间和传输时间。 ７．某计算机系统中有16台打印机，有K个进程竞争使用，每个进程最多需要4台打印机。该系统可能会发生死锁的K的最小值是_______。 ８．Unix系统采用的文件分配方式是___ __。 数据结构： 一、重点知识点 1.了解算法的时间复杂度的概念，会求一个算法的时间复杂度； 2.了解线性表的概念，掌握线性表的顺序表示与链式表示； 3.掌握链表的增、删、查、改等基本操作； 4.理解栈和队列的基本概念； 5.掌握循环队列的判空等基本操作； 6.掌握栈在括号匹配和递归中的应用； 7.了解数组的概念； 8.理解矩阵的压缩存储； 9.了解树和二叉树的基本概念； 10.掌握二叉树的遍历、线索二叉树等相关算法； 11.掌握二叉排序树、平衡二叉树以及Huffman树； 12.了解图的基本概念； 13.理解图的的邻接矩阵法存储与邻接表法存储的类型定义； 14.掌握图的遍历算法； 15.掌握图的最小生成树算法、最短路径以及拓扑排序应用及算法； 16.了解查找的基本概念； 17.理解顺序查找方法与折半查找方法； 18.理解B树的概念与基本操作； 19.掌握散列表的概念、构造以及处理冲突的方法； 20.了解排序的基本概念； 21.掌握几种排序算法； 22.理解几种排序算法性能优劣的比较； 二、重要概念 一、概述 1.数据：信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项：构成数据元素的不可分割的最小单位。 4.数据对象：性质相同的数据元素的集合，是数据的一个子集。 5.数据类型：一个值的集合和定义在此集合上一组操作的总称。、 6.时间复杂度：算法中所有语句在算法中重复执行的次数。 二、线性表 1.线性表：具有相同数据类型的n个数据元素的有限序列。 2.顺序表：用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。 3.单链表：通过一组任意的存储单元来存储线性表中的数据元素。 三、栈和队列 1.栈：只允许在一端进行插入或删除操作的线性表。 2.顺序栈：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶的位置。 3.共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。 4.队列：只允许在表的一端进行插入，而在表的另一端进行删除，这种操作受限的线性表。 5.循环队列：将顺序队列假想为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环。 6.数组:是由n(n>1)个相同类型的数据元素构成的有限序列。 7.压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空 对于青岛西海岸来说，2008年是一个特殊的年份，是一个发展史上的“分水岭”。之所以这样说，是因为经过这一年的发展、组合、沉淀和梳理，西海岸在发展变化过程中一些尚处在萌芽状态和动态变化中的不确定因素，正在走出朦胧而稳定成型，其代表青岛未来的禀赋，正在清楚地显现出来。青岛国资委在监管企业中开展了高层次人才岗位及项目需求征集工作。征集工作主要适应青岛市加快西海岸经济新区和蓝色硅谷建设，推进高端产业和战略性新兴产业快速发展和调整优化产业结构等重点工作的实际需求。重点引进能够促进企业自主创新、具有重大科研成果的高层次研究开发人才以及工作业绩突出、在业界有一定影响、熟悉相关产业领域和国际规则的高级经营管理人才、高级金融人才和高技能人才等。 2008年的西海岸，更精彩的不是速度的表现，而是结构和布局的明朗。 一、港口城市的地位得到真正的确立 据了解，到目前为止，青岛前湾新港区集装箱吞吐量，已经超过470万标准箱，全年超过500万标准箱已无疑义，由此跨过国际集装箱干线枢纽港的“临界点”，加上煤、油、矿，四大骨干货种已全部在西海岸港区吞吐，全港八成以上的吞吐量已由西海岸的新港区承担。正是由于前湾新港区的兴起，青岛港集装箱国际航线的密度以前所未有的速度增加，欧美干线比重不断加大，世界最新一代的集装箱船舶相继靠泊，由此，前湾新港区的发展前景，从今年起开始明朗化，2010 年和2020年集装箱吞吐量分别达到1200万和2100万标箱的发展预测，已跃然纸上，显示了一种发展的底气和自信。与其同步，航运服务业、物流业的规模迅速扩大，发展前景也因此而进一步明朗，全市航运业和物流业等港口产业集群的发展规划则因此而明确，提出了规模和档次要位居全国前列的目标。正是有了西海岸港航产业“垫底”，我们才敢于、才有条件提出这些目标。从这个意义上来说，西海岸正在逐渐地取代老城区的地位，这是2008年西海岸发展中一个最为显著的特点，它的意义，不仅是西海岸的航运业本身。一个吞吐能力只有两三千万吨的老港区，曾经支撑了青岛、山东乃至沿黄腹地几十年的经济腾飞，一个全新结构和全新功能的巨型新港区，在带动、辐射范围由过去的内陆腹地向东北亚更大范围拓展的同时，对西海岸新城区发展的“催化”作用，将是不言而喻的。青岛城市的国际化将因此真正成为现实，青岛三点布局、一线展开、组团发展的大都市战略目标，将因此而取得关键的突破。 二、产业集群的优势基本确立 在我市重点发展的家电电子、石油化工、汽车机车造船、新材料四大工业基地战略布局中，西海岸的优势在今年得到基本确立，几大制造业集群的框架，基本明朗。除了过去已在国内外形成明显竞争优势和品牌影响的家电电子产业集群以外，“中国石化青岛炼油化工公司”在2008年年末正式揭牌的动向，标志西海岸石化产业的框架由此确立，这一进程，为未来几年内青岛石化产业集群的规模和水平进入全国前列奠定了核心基础。就在海西湾造修船基地方兴未艾之际，又有总投资 17亿元的中海油海洋石油工程建设基地项目签约，这一海洋石油工程世界级项目的迅速跟进，并与世界级的造修船基地联手，形成有益的互 操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计 有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 1.2.1 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核现代操作系统中大都采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内 核（microkernel ），其他功能都在核外实现，通过微内核提供的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核 （monolithickernel ）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下 3 个方面的功能。 （1）中断处理。中断处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽中断的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当中断事件产生时，先由内核截获并转向中断处理例行程序进行原则处理，它分析中断事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束中断事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢复现场的工作。由于它是协调进程竞争处理器资源的程序，所以它不是进程而是内核中的一个程序。 （3）原语管理。原语是内核中实现某一功能的不可中断过程。为了协调进程完成通信、并发执行和共享资源，各种原语是必不可少的。通信原语为进程相互传递消息，同步原语能协调并发进程之间的种种制约关系。此外，还有其他原语，如启动外围设备工作的启动原语，若启动不成功则请求启动者应等待，显然，这个启动过程应该是完整的，否则在成为等待状态时，可能外围设备已经空闲。由于设备的操作与硬件密切相关，故通常设备驱动程序等功能都放在内核中完成。 内核是操作系统对裸机的首次改造，内核和裸机组成了一台虚拟机，进程就在这台虚拟机上运行，它比裸机的功能更强大，具有以下特性： （1）虚拟机没有中断，因而，进程的设计者不再需要有硬件中断的概念，用户进程执行中无须处理中断； （2）虚拟机为每个进程提供了一台虚拟处理器，每个进程就好像在各自的私有处理器上顺序地推进，实现了多个进程的并发执行； （3）虚拟机为进程提供了功能较强的指令系统，即它们能够使用机器非特权指令、系统调用和原语所组成的新的指令系统。 为了保证系统的有效性和灵活性，设计内核应遵循少而精的原则。如果内核功能过强，则一方面在修改系统时可能牵动内核；另一方面它占用的内存容量和执行时间都会增大，且屏蔽中断的时间过长也会影响系统效率。因而，设计内核时应注意：中断处理要简单；调度算法要有效；原语应灵活有力、数量适当。这样就可以做到下次修改系统时，尽量少改动内核，执行时中断屏蔽时间缩短。 2．进程管理 程序本身并不能做什么，只有在CPL执行它的指令时才能有所作为；因此，可以把进程看做是正在运行的程序。但是当我们进一步研究时，对进程的定义将更为普遍。例如：一个分时用户程序（如编译器）是一个进程，个人用户在PC上运行的字处理程序是一个进程，一个系统任务（如输出到打印机）也是一个进程，并可以提供允许进程创建与其并发执行的子进程的系统调用。 进程需要特定的资源（包括CPU寸间、内存、文件和I/O设备）来完成工作。这些资源或者在进程创建时分配给它，或者在其运行时分配。除了在进程创建时所获得的各种物理资源和逻辑资源以外，各种各样的初始化数据（或输入）也可能一同传送给进程。例如，考虑一个能够在终端的显示屏上显示一 你是我的眼 科大教授叶蔚和她先生的感人爱情 故事 你的眼睛可以看不见道路，但不能停止前进的脚步；你可以摔倒一百次，但一定要在第一百零一次站起来…… ——主人公语 2009年7月3日，汤建泉出席了在人民大会堂举行的第四次全国“自强模范”表彰大会，当胡锦涛主席和温家宝总理先后握着他的手表示祝贺时，他忍不住流下了激动的泪水…… 十五年前，汤建泉在中国矿业大学读研究生，当他正准备赴日本读博士时，突患视神经萎缩，半年里双目几近失明。巨大的心理落差，让他痛不欲生，连身为中科院院士的父亲也无能为力。是她——叶蔚，用她执着坚定的爱，引领他一步步走向人生的巅峰，成为一个盲人企业家…… 失明破灭留学梦，爱情成了黑暗中最大亮光 1970年12月31日，汤建泉出生于泉城济南。父亲宋振骐和母亲祝侃都是山东科技大学的教授，因为宋振骐是宋家养子，所以到了汤建泉这一代，他将儿子改回了汤姓。 高大、阳光、帅气的汤建泉于1988年以优异的成绩考入山东科技大学，并由人们向往的电气自动化专业主动要求转到艰苦危险的采矿专业。一入大学他就担任体育部长和足球队长，惹得众多女生对他倾心。但是，他对她们无动于衷，他心里只装着一个女孩，那就是高中同学叶蔚。 叶蔚，与汤建泉一同考入山科大，只不过汤建泉在泰安的本校区，而她则在济南的分校区。因为她的美丽聪慧和汤建泉的潇洒睿智，一直是同学们心中的“金童玉女”。但因叶母严厉的家教，叶蔚不轻言感情，汤建泉也一直不敢向她表白。直到大二的一天，汤建泉约叶蔚去看电影，正走着，一辆摩托车从他们身后疾驰而来。眼看路边一个水坑的水就要溅到叶蔚的白裙子上，汤建泉急忙把叶蔚一拉，挡在了她的前面。结果，雨水裹着泥巴溅了汤建泉一身。叶蔚平日里本来也很欣赏汤建泉在足球场上的表现，不想生活中也这么细心，当即就向他投去感激的一瞥。汤建泉见状，猛地握紧了山东科技大学青岛校区景观文化建设综述
831-数据结构与操作系统
山东科技大学中外合作办学招生简章
山东科技大学_计算机操作系统试题
操作系统结构
山东科技大学泰山科技学院 操作系统A卷及答案及评分标准
数据结构,操作系统重要概念整理
青岛青岛西海岸规划简介
操作系统结构
你是我的眼山科大爱
相关主题
文本预览