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

《2011年计算机科学与技术基础》由会员分享，可在线阅读，更多相关《2011年计算机科学与技术基础（8页珍藏版）》请在金锄头文库上搜索。

1、NJU2011 年计算机科学与技术基础试卷与答案科目名称：计算机科学与技术基础一、( 10 分)我们有下列两个问题，并已有各自的算法：1. 已知等腰三角形各边长，求高。2. 已知直角三角形的任意两边长，求第三边的长度。利用这两个问题解释 多项式时间规约 的概念，并说明多项式时间规约在计算机算法理论中的作用。NP 问题的全称是： Non deterministic Ploynomial 问题，即非确定性多项式问题。 多项式时间 ( Polynomial time)在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小 n 的多项式倍数。答案参考： http:/ 2 的答案可用于解决问

2、题 1。因此问题 2 若能在多 项式时间内解决，则问题 1 也能在多项式时间内解决。 (多项式时间 归约 假定给了两个问题类 q 和 q0, 如果存在一个确定型图灵机 Mq和一个多项式 P, 对于 q中任意一个实例 x, Mq都能在 P( n)时间内计算出 q0中 一个实例 y(其中 n是实例 x 的编码长度 )，使得 x q 中有肯定回答的实例，当且仅当 y 是 q0中有肯定回答 的实例 , 我们就说 q 多项式时间归约到 q0 )多项式时间规约对于研究 NP，NP完全问题具有重大作用。对于一个规模为 n的输入，在最坏情况下的运行时间是 O(nk) ，其中 k是某一确定的常数，即称时间 负责

3、度为的算法为多项式时间算法。一般来说，在多项式时间内可解的问题是易处理的问题，在超过多项 式时间内解决的问题是不易处理的问题。不能够这样限制时间复杂度的算法被称为指数时间算法。例如， 时间复杂度为 O(nlog(n) 、 O(n3)的算法都是多项式时间算法，时间复杂度为O(nlog(n) 、O(n!) 、O(2n)的算法是指时间算法。计算复杂性理论所研究的资源中最常见的是时间(要通过多少步演算才能解决问题)和空间(在解决 问题时需要多少内存) 。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的

4、重要参 数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是 算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类 语言的某一问题，设有 X 个字( word )属于这个问题，把 X 放入这个图灵机的输入端，这个图灵机为解 决此问题所需要的工作带格子数总和称为空间。计算复杂性理论最成功的成果之一是 NP完备理论。 NP是指“在非确定性图灵机上有多项式时间算法 的问题”的集合，而 P 是指“在确定性图灵机上有多项式时间算法的问题”的集合。P 类问题、 NP 类问题

5、和 NP 完全性( NPC )P 类问题： 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将 这类问题的集合记为 P，因此在多项式时间内可解决的问题就称为P 类问题。一个问题如果没有找到多项式时间算法，那么直觉上它是“难解”的，但又往往无法证明多项式时间 算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在，这就给理论工作者带 来了一个难题：一方面证明一个问题不存在多项式时间算法是困难的，至今尚未给出；另一方面有越来越 多的问题无法给出多项式时间算法。为此，在20 世纪 70 年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数据猜想称为

6、NP 完全性理论。定义：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例I。该算法首先给出一个猜想，该猜想规模不超过 I 的输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，则 称该问题属于 NP 类。定义：如果 NP类中所有问题都可以多项式时间归约到 NP类中某个问题 x，则称 x是 NP-完全问题。 定义：如果某优化问题 x 的判定问题是 NP-完全的，则称问题 x 是 NP-难的；如果 x 的判定问题是强 NP-完全的，则称 x 是强 NP-难的。15 分）1. 以 Quicksort 算法为例，解释什么是最好情况时间复杂度、最坏时间复杂度、平均时间复杂度？2.

7、 在 Quicksort 算法中选择第一个元素为比较基准对象或者通过随机方法来选择一个元素为比较基准 对象效果有差别吗？请给出解释。三、在软件建模过程中，人们往往先建立平台无关的模型 （ Platform IndependentModels ，PIM ），然后再建立特定实现平台上的平台相关模型 （Platform SpecificModels，PSM）。请简单论述这种建模方法的优点（ 10 分）四、简述软件体系结构的概念。在模型-试图 - 控制器模式（ Model ViewController ，MVC ）中，视图主要担负什么样的责任？（ 7 分）软件体系结构是具有一定形式的结构化元素，即构件

8、的集合，包括处理构件、数据构件和连接构件。 处理构件负责对数据进行加工，数据构件是被加工的信息，连接构件把体系结构的不同部分组组合连接起 来。如何表示软件体系结构，即如何对软件体系结构建模。根据建模的侧重点的不同，可以将软件体系结 构的模型分为 5 种：结构模型、框架模型、动态模型、过程模型和功能模型。在这5 个模型中，最常用的是结构模型和动态模型。（ 1）结构模型 这是一个最直观、最普遍的建模方法。这种方法以体系结构的构件、连接件和其他概念来刻画结构， 并力图通过结构来反映系统的重要语义内容，包括系统的配置、约束、隐含的假设条件、风格、性质。研 究结构模型的核心是体系结构描述语言。（2）框架

9、模型 框架模型与结构模型类似，但它不太侧重描述结构的细节而更侧重于整体的结构。框架模型主要以一 些特殊的问题为目标建立只针对和适应该问题的结构。（3）动态模型 动态模型是对结构或框架模型的补充，研究系统的大颗粒 的行为性质。例如，描述系统的重新配置或演化。动态可能指系统总体结构的配置、建立或拆除通信通道或计算的过程。这类系统常是激励型的。（4）过程模型 过程模型研究构造系统的步骤和过程。因而结构是遵循某些过程脚本的结果。（5）功能模型 该模型认为体系结构是由一组功能构件按层次组成，下层向上层提供服务。它可以看作是一种特殊的 框架模型。这 5 种模型各有所长，也许将 5 种模型有机地统一在一起，

10、形成一个完整的模型来刻画软件体系结构 更合适。例如， Kruchten 在 1995 年提出了一个 4+1 的视角模型。 4+1 模型从 5 个不同的视角包括逻辑视 角、 过程视角、 物理视角、 开发视角和场景视角来描述软件体系结构。 每一个视角只关心系统的一个侧面， 5 个视角结合在一起才能够反映系统的软件体系结构的全部内容。MVC 全名是 Model View Controller ，是模型 （model） 视图 （view） 控制器 （controller） 的缩写，一种软 件设计典范，用一种业务逻辑和数据显示分离的方法组织代码，将业务逻辑被聚集到一个部件里面，在界 面和用户围绕数据的交

11、互能被改进和个性化定制的同时而不需要重新编写业务逻辑。 MVC 被独特的发展 起来用于映射传统的输入、处理和输出功能在一个逻辑的图形化用户界面的结构中。这个模式认为，程序 不论简单或复杂，从结构上看，都可以分成三层。1）最上面的一层，是直接面向最终用户的视图层 （ View ）。它是提供给用户的操作界面，是程序的外壳。2）最底下的一层，是核心的 数据层 （Model ），也就是程序需要操作的数据或信息。3）中间的一层，就是 控制层 （ Controller ），它负责根据用户从 视图层 输入的指令，选取 数据层 中的数据，然后对其进行相应的操作，产生最终结果。这三层是紧密联系在一起的，但又是互

12、相独立的，每一层内部的变化不影响其他层。每一层都对外提 供接口（ Interface ），供上面一层调用。这样一来，软件就可以实现模块化，修改外观或者变更数据都不用 修改其他层，大大方便了维护和升级。MVC 模式（ Model-View-Controller ）是软件工程中的一种软件架构模式，把软件系统分为三个基本部 分：模型（ Model ）、视图（ View ）和控制器（ Controller ）。MVC 是一个框架模式， 它强制性的使应用程序的输入、 处理和输出分开。 使用 MVC 应用程序被分成 三个核心部件： 模型、视图、控制器。它们各自处理自己的任务。 最典型的 MVC 就是 JS

13、P + servlet + javabean 的模式。1、模型（ Model ） 模型是应用程序的主体部分。模型表示业务数据，或者业务逻辑 .2、视图（ View ） 视图是应用程序中用户界面相关的部分，是用户看到并与之交互的界面。3、控制器（ controller） 控制器工作就是根据用户的输入，控制用户界面数据显示和更新 model 对象状态。MVC 式的出现不仅实现了功能模块和显示模块的分离，同时它还提高了应用系统的可维护性、可扩 展性、可移植性和组件的可复用性。MVC 模式的目的是实现一种动态的程式设计，使后续对程序的修改和扩展简化，并且使程序某一部 分的重复利用成为可能。除此之外，此

14、模式通过对复杂度的简化，使程序结构更加直观。软件系统通过对 自身基本部分分离的同时也赋予了各个基本部分应有的功能。专业人员可以通过自身的专长分组：（控制器 Controller ） -负责转发请求，对请求进行处理。（视图 View ）-界面设计人员进行图形界面设计。（模型 Model ）-程序员编写程序应有的功能（实现算法等等）、数据库专家进行数据管理和数据库设计 （可以实现具体的功能 ） 。模型（ Model ）“数据模型”（ Model ）用于封装与应用程序的业务逻辑相关的数据以及对数据的处理方 法。“模型”有对数据直接访问的权力，例如对数据库的访问。 “模型”不依赖“视图”和“控制器”

15、，也 就是说，模型不关心它会被如何显示或是如何被操作。但是模型中数据的变化一般会通过一种刷新机制被 公布。为了实现这种机制，那些用于监视此模型的视图必须事先在此模型上注册，从而，视图可以了解在 数据模型上发生的改变。 （比较：观察者模式（软件设计模式） ）视图（ View ）视图层能够实现数据有目的的显示（理论上，这不是必需的）。在视图中一般没有程序上的逻辑。为了实现视图上的刷新功能，视图需要访问它监视的数据模型（ Model ），因此应该事先在被它 监视的数据那里注册。视图 （View） 代表用户交互界面，对于 Web 应用来说，可以概括为 HTML 界面，但 有可能为 XHTML 、XML 和 Applet 。随着应用的复杂性和规模性，界面的处理也变得具有挑战性。一个应 用可能有很多不同的视图， MVC 设计模式对于视图的处理仅限于视图上数据的采集和处理，以及用户的 请求，而不包括在视图上的业务流程的处理。 业务流程的处理交予模型 （Model） 处理。比如一个订单的视图 只接受来自模型的数据并显示给用户，以及将用户界面的输入数据和请求传递给控制和模型。控制器（ Controller ） 控制器起到不同层面间的组织作用，用于控制应用程序的流程。它处理事件并 做出响应。“事件”包括用户的行为和数据模型上的改变。五、简述