2012年计算机科学与技术基础

NJU2012年计算机科学与技术基础试卷与答案科目名称：计算机科学与技术基础一、（10分）函数W递归定义如下：1)1(;2/)(wnwcnnW证明：)(nOW解：一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1）在每一次调用自己时，必须是（在某种意义上）更接近于解；2）必须有一个终止处理或计算的准则。考点：求解递归式算法导论P47-53二、（15分）问题P：任给一无向图G，判定它是否含有哈密顿（Hamilton）回路。我们知道问题P是NP-完全问题。问题N：任给一带权完全图H与一正整数k，判定H中是否含有总权数为k的哈密顿（Hamilton）回路，这就是著名的“旅行推销员问题”，我们知道问题Q也是NP-完全问题。假设对问题Q做如下简化：每条边的权值只能是1或21.简述如何利用问题P的NP-完全性证明简化的问题Q仍是NP-完全问题。2.给出具体的证明。答案来源：算法导论P624/641课程网址：在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的。对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。三、简述软件生命期的瀑布模型。并说明这个模型的优点（10分）瀑布模型（WaterfallModel）将将软件生命周期划分为系统需求分析、软件需求分析、概要设计、详细设计、编码、测试和运行维护等七个阶段，每一阶段工作的完成需要确认，并且规定了它们自上而下、相互衔接的固定次序，如同瀑布流水，逐级下落，最终得到软件产品，如图1所示。瀑布模型核心思想是按工序将问题化简，将功能的实现与设计分开，便于分工协作，即采用结构化的分析与设计方法将逻辑实现与物理实现分开。在瀑布模型中，软件开发的各项活动严格按照线性方式进行，当前活动接受上一项活动的工作结果，实施完成所需的工作内容。当前活动的工作结果需要进行验证，如果验证通过，则该结果作为下一项活动的输入，继续进行下一项活动，否则返回修改。瀑布模型的主要特点是：阶段间的顺序性和依赖性。开发过程是一个严格的下导式过程，即前一阶段的输出是后一阶段的输入，每一阶段工作的完成需要确认，而确认过程是严格的追溯式过程，后一阶段出现了问题要从前一阶段的重新确认来解决。因此，问题发现的越晚，解决问题的代价就越高。瀑布模型有以下优点（1）为软件项目提供了按阶段划分的检查点。（2）当前一阶段完成后，您只需要去关注后续阶段。（3）可在迭代模型中应用瀑布模型。增量迭代应用于瀑布模型，每次迭代产生一个可运行的版本，同时增加更多的功能。每次迭代必须经过质量和集成测试。（4）提供了一个模板，这个模板使得分析、设计、编码、测试和支持的方法可以在该模板下有一个共同的指导。瀑布模型的缺点瀑布模型强调文档的作用，并要求每个阶段都要仔细验证。但是，这种模型的线性过程太理想化，已不再适合现代的软件开发模式，几乎被业界抛弃，其主要问题在于：（1）各个阶段的划分完全固定，阶段之间产生大量的文档，极大地增加了工作量；（2）由于开发模型是线性的，用户只有等到整个过程的末期才能见到开发成果，从而增加了开发的风险；（3）早期的错误可能要等到开发后期的测试阶段才能发现，进而带来严重的后果。（4）通过过多的强制完成日期和里程碑来跟踪各个项目阶段。（5）瀑布模型的突出缺点是不适应用户需求的变化。第一，从认识论上讲，人的认识是一个多次反复的过程，软件开发是人的一个智力认识活动，不可能一次完成，需要多次反复地进行，但瀑布模型中划分的几个阶段，没有反映出这种认识过程的反复性。第二，软件开发是一个知识密集型的开发活动，需要人们合作完成。因此，人员之间的通讯和软件工具之间的联系，活动之间的并行和串行等都是必需的，但在瀑布模型中也没有体现出这一点。四、简述模型驱动的体系结构的概念，其中的平台无关模型（PlatformIndependentModels，PIM）和平台相关模型（PlatformSpecificModels，PSM）是指什么？（7分）参考网址：模型驱动体系架构（ModelDrivenArchitecture,MDA）是由OMG提出的新的软件方法学，被面向对象技术界预言为未来几年里最重要的软件方法学。模型驱动体系架构(MDA)把建模语言用作一种编程语言而不仅仅是设计语言，并以一种全新的方式将IT技术的一系列新的趋势性技术整合到一起。这些技术包括基于组件的开发、设计模式、中间件、说明性约束、抽象、多层系统、企业应用整合以及契约式设计等。模型(Model)是用某种工具对同类或其他事物的表达方式，它从某一个建模观点出发，抓住事物最重要的方面而简化或忽略其他方面，工程、建筑和其他许多领域中都用到模型概念。软件系统的模型用建模语言来表达，如UML是对系统的功能、结构或行为的形式化规范。(1)模型驱动(Model-driven)是指利用模型来指导系统开发的全过程[6]，包括系统理解、设计、架构、开发、部署、维护、集成等系统生命周期相关的全过程。(2)软件体系结构(Architecture)为软件总体结构框架，它是构件、连接器及其之间关系的系统规约。MDA主要使用模型来形式化描述软件体系结构及其风格。(3)软件平台(Platform)是指用来构建与支撑应用软件的独立软件系统。它是开发与运行应用软件的基础，是任何一个应用软件得以实现与应用的必要条件。软件平台有两个基本要素，即支撑环境和开发体系，其中支撑环境是指应用软件系统开发与运行的基本条件，开发体系是指开发与维护管理应用软件的工具与方法。平台无关模型(PlatformIndependentModel，PIM)是一个系统功能和结构的形式化规范，它从与实现技术无关的细节中抽象而来。平台相关模型(PlatformSpecificModel，PSM)是合成了系统实现平台技术细节的平台模型，它是平台无关模型到具体平台的映射。平台无关模型（PlatformIndependentModels，PIM）PIM准确的定义应该是/独立于平台的计算模型0,业务模型和需求模型也是平台独立的在现阶段的MDA开发过程中,平台独立意味着独立于信息格式化技术!3GL!4GL!分布式组件中间件和消息中间件在这个意义上,平台独立模型要比目前程序员工作的抽象层次更高一级平台相关模型（PlatformSpecificModels，PSM）平台相关模型是一个同特定的信息格式化技术!编程语言!分布式组件中间件!消息中间件相关的计算模型五、简述面向对象语言中是如何实现封装的。（8分）封装(encapsulation)：是隐藏对象的属性和实现细节，仅对外公开接口，控制应用程序中属性的读取和修改的访问级别。通过封装，可以实现对属性的数据访问限制，同时增加了程序的可维护性。由于取值方法和赋值方法隐藏了实现的变更，因此并不会影响读取或修改该属性的类，避免了大规模的修改，程序的可维护性增强。实现封装的方法有：（1）属性的封装：将属性私有化，提供公有的方法访问私有的属性修改属性的可见性来限制对属性的访问，并为每个属性创建一对取值（getter）方法和赋值（setter）方法，用于对这些属性的访问；在赋值和取值方法中，加入对属性的存取的限制。（2）类的封装：（3）方法的封装：六、解释题（10分）1.实时与分时实时是没有时间延迟或是很短，要求反应快，尽可能下达任务就能完成，所以实时系统多是单任务的，而且要去掉我们平时用的操作系统里冗余的部分，来达到尽可能快的要求。实时系统一般用在航天、导弹等这些需要快速计算的领域。分时则是一种实用方式，指的是多个任务轮流使用一个CPU，你用一会，他用一会，由于转换的比较快，每个人都认为只有自己用似的。分时系统就很多了，常见的UNIX，Linux，Windows都是分时的。分时不是为了提高效率，而是为了实现多任务。分时以后，就可以同时运行好几个任务了。2.操作系统的用户接口操作系统的用户接口，就是操作系统提供给用户，使用户可通过它们调用系统服务的手段。为了方便用户对计算机系统的使用和编程，操作系统向用户提供了用户与操作系统的接口，简称为用户接口。通过该接口，用户可以向操作系统请求特定的服务，操作系统提供服务的结果。用户接口可分为三个部分：（1）命令接口：为了便于用户直接或间接控制自己的作业，操作系统向用户提供了命令接口。命令接口是用户利用操作系统命令组织和控制作业的执行或管理计算机系统。命令是在命令输入界面上输入，由系统在后台执行，并将结果反映到前台界面或者特定的文件内。命令接口可以进一步分为联机用户接口和脱机用户接口。（2）程序接口：程序接口由一组系统调用命令组成，这是操作系统提供给编程人员的接口。用户通过在程序中使用系统调用命令来请求操作系统提供服务。每一个系统调用都是一个能完成特定功能的子程序。如早期的UNIX系统版本和MS-DOS版本。（3）图形接口：图形用户接口采用了图形化的操作界面，用非常容易识别的各种图标来将系统各项功能、各种应用程序和文件，直观、逼真地表示出来。用户可通过鼠标、菜单和对话框来完成对应程序和文件的操作。图形用户接口元素包括窗口、图标、菜单和对话框，图形用户接口元素的基本操作包括菜单操作、窗口操作和对话框操作等。3.进程死锁的必要条件如果在计算机系统中同时具备下面四个必要条件时，那么就会发生死锁。换句话说，只要下面四个条件有一个不具备，系统就不会出现死锁。（1）互斥条件。进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一个进程所占有。（2）不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。（3）部分分配条件。进程每次申请它所需要的一部分资源。在等待新资源的同时，进程继续占有已分配到的资源。部分分配条件又称为请求和保持条件。（4）环路等待条件。存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。4.虚存管理（虚拟内存管理）当程序的存储空间要求大于实际的内存空间时，就使得程序难以运行了。虚拟存储技术就是利用实际内存空间和相对大的多的外部储存器存储空间相结合构成一个远远大于实际内存空间的虚拟存储空间，程序就运行在这个虚拟存储空间中。能够实现虚拟存储的依据是程序的局部性原理，即程序在运行过程中经常体现出运行在某个局部范围之内的特点。在时间上，经常运行相同的指令段和数据（称为时间局部性），在空间上，经常运行与某一局部存储空间的指令和数据(称为空间局部性），有些程序段不能同时运行或根本得不到运行。虚拟存是把一个程序所需要的存储空间分成落干页或段，程序运行用到页和段就放在内存里，暂时不用就放在外存中。当用到外存中的页和段时，就把它们调到内存，反之就把它们送到外存中。装入内存中的页或段可以分散存放。虚拟内存管理是一种借助于外存空间，从而允许一个进程在其运行过程中部分装入内存的技术。虚拟内存技术允许执行的进程不必完全在内存中，其优点是程序可以比物理内存大。七、简答题（15分）1.说明操作系统的作用（3种以上）。操作系统（OperatingSystem，简称OS）是计算机系统中负责支撑应用程序运行环境以及用户操作环境的系统软件，同时也是计算机系统的核心与基石。作用：控制管理计算机的全部硬软件资源，合理组织计算机内部各部件协调工作，为用户提供操作和编辑界面的