计算机科学与技术基础答案详细版.docx
《计算机科学与技术基础答案详细版.docx》由会员分享，可在线阅读，更多相关《计算机科学与技术基础答案详细版.docx（31页珍藏版）》请在冰点文库上搜索。
计算机科学与技术基础答案详细版
NJU2013年计算机科学与技术基础试卷与答案
科目名称：
计算机科学与技术基础（算法导论、软件方法、操作系统、数据库）
一、简单描述Quicksort算法的原理与过程。
概述（即给出结果和理由，不需要严格的数学证明）最坏情况以及平均情况的时间复杂性分析。
（15分）
算法参考网址：
（1）
（2）
（3）
（4）算法演示：
1.Quicksort算法的原理
Quicksort算法是由冒泡排序算法改进而得到的，其基本原理是：
（1）在待排序的n个元素中任选一个元素作为基准（pivot），然后对数组a[n]进行分区操作，通过一趟排序之后将数组a[n]分割为独立的两部分，使得基准左边元素的值都不大于基准值、基准右边元素的值都不小于基准值，这时作为基本的元素排在这两部分的中间，并使得作为基准的元素调整到排序后的正确位置（或称为记录归位）。
（2）完成一趟快速排序之后，可采用递归方法对所得的两部分子数组分别重复上述快速排序，直至每部分内只有一个元素或元素为空为止，这时每个数组元素都将被排在正确的位置，整个数组达到有序。
因此，快速排序算法的核心是分区操作，即调整基准元素的位置以及调整调整返回基准的最终位置以便分治递归。
2.Quicksort算法的过程
一趟快速排序的算法是：
（1）设置两个变量start、end，排序开始的时候：
start=1，end=N；
（2）以第一个数组元素作为关键数据，赋值给pivot，即pivot=arry[1]；
（3）从end开始向前搜索，即由后开始向前搜索（end--），找到第一个小于pivot的值arry[end]，并与arry[start]交换,即swat（arry,start,end）；
（4）从start开始向后搜索，即由前开始向后搜索（start++），找到第一个大于pivot的arry[start]，与arry[end]交换,即swat（arry,start,end）;
（5）重复第3、4步，直到start=end，这个时候arry[start]=arry[end]=pivot，而pivot的位置就是其在整个数组中正确的位置；
（6）通过递归，将问题规模不断分解。
将pivot两边分成两个数组继续求新的pivot，最后解出问题。
3.Quicksort算法的时间复杂度分析
快速排序的时间主要耗费在划分操作上，对长度为n的区间进行划分，共需n-1次关键字的比较。
（1）最坏时间复杂度
最坏情况是每次划分选取的基准都是当前无序区间中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i（1≤i≤n-1），故总的比较次数达到最大值：
如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序（或递减序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。
（2）最好时间复杂度
在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。
设
表示对长度为n的表进行快速排序所需的比较次数，显然它应该等于长度为n的无序区间进行划分所需的比较次数n-1，加上递归地对划分所得的左、右两个无序子区间（长度
）进行快速排序所需的比较次数
，假设表长度
，则
，展开此递归关系式即可求得总的关键字比较次数：
设
表示对长度为1的区间进行快速排序所需的比较次数，可将它看作一个常数。
实际上，用递归树来分析最好情况下的比较次数更简单。
因为每次划分后左、右子区间长度大致相等，故递归树的高度为
，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数
。
因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为
，最好时间复杂度为
。
（3）平均时间复杂度
设
表示对长度为n的区间进行快速排序所需的平均比较次数，平均情况介于最好与最坏情况之间。
对于一个长度为n的区间执行一次划分操作，将区间分为三部分，设左右两个子区间分别包括k和n-k-1个元素。
通过两次递归调用分别对这两个子区间进行快速排序所需的时间分别为
和
。
由于基准元素位于0到n-1各位置上的可能性相等，则
最后计算可得快速排序的平均时间复杂度，即：
（4）空间复杂度
最小空间复杂度：
快速排序算法中一趟使用了i，j和tmp等3个辅助变量，为常量级，若每一趟排序都将记录序列（区间）均匀地分割为两个程度接近的子序列（区间）时，其深度为
，所需桟空间为
。
最大空间复杂度：
递归树的高度为
，所需桟空间为
。
平均空间复杂度：
。
二、简述什么是近似算法，什么是随机算法，如何评价这两类算法的优劣？
（10分）
1.近似算法
近似算法是计算机科学中算法研究的一个重要方向。
所谓“近似”，就是指结果不一定是最优的，但是也在可以承受的范围内，而且可以比精确求解消耗更少的资源。
这里的资源是计算复杂性理论中的标准，可以是时间，空间或者询问次数等。
在计算复杂性理论中的某些假设下，比如最著名的
假设下，对于一些可已被证明为NP完全的优化问题，无法在多项式时间内精确求到最优解，然而在现实或理论研究中，这类问题都有广泛的应用，在精确解无法得到的情况下，转而依靠高效的近似算法求可以接受的近似解。
许多组合优化问题都是NP-难的。
因此在P≠NP的情况下，这些NP-难问题没有多项式时间的算法，如何解决这些问题，已成为当前研究的重要问题。
前一章我们已提出解决这一问题的途径之一，是求其NP-难问题的一个“较好”的可行解，或者说求一个“近似”最优解．何为“近似”最优解？
在计算复杂性理论中的某些假设下，比如最著名的P≠NP假设下，对于一些可已被证明为NP完全的优化问题，无法在多项式时间内精确求到最优解，然而在现实或理论研究中，这类问题都有广泛的应用，在精确解无法得到的情况下，转而依靠高效的近似算法求可以接受的近似解。
定义：
设D是一个最优化问题，A是一个算法，若把A用于D的任何一个实例I，都能在I的多项式时间内得到I的可行解，则称算法A为问题D的一个近似算法，其中I表示实例I的规模或输入长度。
近似算法的性能
若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为
在通常情况下，该性能比是问题输入规模n的一个函数ρ（n），即
该近似算法的相对误差定义为：
若对问题的输入规模n，有一函数ε（n）使得
则称ε（n）为该近似算法的相对误差界。
近似算法的性能比ρ（n）与相对误差界ε（n）之间显然有如下关系：
2.随机算法
随机算法（randomizedalgorithm），是在算法中使用了随机函数，且随机函数的返回值直接或者间接地影响了算法的执行流程或执行结果。
就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。
随机算法，又叫概率算法，随机算法是算法本身包含了随机数生成器的算法。
根据《算法导论（中文第二版）》描述，在进行算法分析的时，有时可以在获得了一定输入分布信息之后对输入的分布进行一定的假定，在此基础上进行平均情况分析得到算法的时间复杂度。
然而有时候无法获得输入分布的信息，这时可以在算法本身增加一定的随机性，继而实现对算法进行平均情况分析。
通过设计随机算法有效地避免较多的较坏情况输入的出现，从而提高算法的平均情况下的性能。
有一些问题，用确定性的算法在可以忍受的时间内无法计算出结果，但可以用随机算法在可以很短的时间内得到基本可信的结果。
举一个简单的例子，计算平面左边上区域A是否包含着区域B。
用确定性算法的话，计算两个不规则区域的包含问题是很复杂的。
我们考虑用随机算法，随机在B中选择一个检测点P，然后检测点P是否在区域A内。
若不在区域A内，则得到不包含的结果。
若在区域A内，则随机选择另外一个节点进行同样的检测，一共选址K个检测点。
若K个点均在A内，则得到包含的结果。
该随机算法的准确率随着K的增大而增大。
随机算法并不要求对每一输入都计算出计算结果，但可以将错误率缩小到可以忽略的程度。
解问题
的随机算法定义为：
设
是问题
的一个实例，用算法解
的某些时刻，随机选取
，由
来决定算法的下一步动作。
优点：
（1）执行时间和空间，小于同一问题的已知最好的确定性算法；
（2）实现比较简单，容易理解。
随机算法分为两类：
（1）拉斯维加斯（Las Vegas）算法，要么给出正确解，要么无解。
无解时，需要再次调用该算法。
要么给出问题的正确答案，要么得不到答案。
反复求解多次，可使失效的概率任意小。
（2）蒙特卡罗（MonteCarlo）算法，总能给出解，但可能是正确解也可能是错误解。
多次调用该算法可降低错误率。
总能得到问题的答案，偶然产生不正确的答案。
重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。
至于用哪种算法取决于具体的应用。
对于一些不允许出错的应用则采用LasVegas算法，但若是允许小概率错误的话，MonteCarlo算法更加省时。
随机算法的优点：
对于某一给定的问题，随机算法所需的时间与空间复杂性，往往比当前已知的、最好的确定性算法要好；到目前为止设计出来的各种随机算法，无论是从理解上还是实现上，都是极为简单的；随机算法避免了去构造最坏情况的例子。
3.算法评价
三、在模型驱动的软件体系结构中，平台无关模型（PlatformIndependentModels，PIM）和平台相关模型（PlatformSpecificModels，PSM）分别描述软件的哪些方面？
软件运行时依赖的网络拓扑结构信息应该在PIM还是PSM中描述？
（15分）
对象管理组织（ObjectManagementGroup,OMG）提出了基于模型驱动的体系结构（ModelDrivenArchitecture,MDA）技术，将软件系统建立在各种模型的基础上，通过模型的变换来驱动系统的开发，设计轻便的、可操作的应用程序。
模型驱动体系（MDA）是对象管理组织定义的一个软件开发框架，为软件系统设计提供了一条新途径。
在MDA中，MDA将模型区分为平台无关模型（PlatformIndependentModel,PIM）和平台相关模型（PlatformSpecificModel,PSM），模型不再仅仅是描绘系统、辅助沟通的工具，而是软件开发的核心和主干。
它的核心思想是抽象出与实现技术无关、完整描述业务功能的平台独立模型（PIM），针对不同实现技术制定多个映射规则，通过这些映射规则及辅助工具将PIM转换成与具体实现技术相关的平台相关模型（PSM），最后，将PSM转换成代码。
PIM与PSM这两种模型是MDA体系结构中对于一个系统的不同视角的模型描述，它们之间是抽象和求精的关系。
与具体实现技术无关，PIM可以被多种实现技术复用，当技术平台发生变迁时，PIM不必做改动；PIM可以更加精确地体现系统的本质特征，对跨平台互操作问题进行建模非常容易，因为使用与平台无关的通用术语，语义表达会更加清晰。
PIM与PSM两个模型之间通过模型映像机制相互映像，从而保证了模型的可追溯性，这也体现了MDA软件开发过程是一个模型至顶向下、逐步求精的过程。
MDA将软件系统的模型分离为平台无关模型PIM和平台相关模型PSM，同时又能通过映射规则将它们统一起来，以这样的方式试图去摆脱需求变更所带来的困境。
在将模型自动转换成代码的研究中，平台相关模型PSM（PlatformSpecificModel）是针对特定平台的模型，在MDA框架中，首先使用平台无关的建模语言来搭建平台无关的模型PIM然后根据特定平台和实现语言的映射规则，将PIM转换以生成平台相关的模型PSM，最终生成应用程序代码和测试框架。
1.平台无关模型（PlatformIndependentModels，PIM）
平台无关模型（PIM）是模型驱动架构（MDA）的核心，在基于MDA的软件开发过程中，平台无关模型（PIM）扮演着核心角色，MDA通过建立PIM来生成实际执行系统，也通过修改PIM来修改执行系统。
模型驱动架构（MDA）是对象管理组织（OMG）为解决软件开发危机提出的软件开发架构，其基本思想是将模型作为软件开发的核心产品，严格区分系统的功能规约与实现细节。
MDA的典型开发过程如图1所示，分为3步：
首先对应用领域建模生成PIM，然后将PIM转换为一个或多个PSM，最后将PSM转换成代码。
其中，PIM在描述纯粹关注技术的业务逻辑中扮演了中心角色，PIM建模是至关重要的一步，关系着MDA开发的成败。
MDA的核心是PIM，它是一个软件系统功能和结构的形式化规范，与具体实现技术和硬件环境无关，所以PIM的建模语言也应是平台无关的。
平台无关模型（PlatformIndependentModel）类似于系统分析模型，它处于中间抽象层次，关注系统的整个架构实现，但却忽略掉与平台相关的部分。
平台独立模型可以转换成多个平台相关模型；平台独立模式（PIM）是一种高阶抽象的模式，该模式与开发技术独立。
PIM是系统分析与设计结果的重要产出，主要根据需求塑模（RM）的结果从如何支援企业运作的观点描述一个软件系统，并不涉及描述系统开发与运作之平台。
2.平台相关模型（PlatformSpecificModels，PSM）
四、什么叫做软件体系结构？
（10分）
软件体系结构是具有一定形式的结构化元素，即构件的集合，包括处理构件、数据构件和连接构件。
处理构件负责对数据进行加工，数据构件是被加工的信息，连接构件把体系结构的不同部分组组合连接起来。
软件体系结构包括定义能满足所有技术和业务要求的结构化解决方案，同时优化性能、安全性和可管理性等常见的质量特性。
它需要根据各种因素做出一系列决策，而每项决策都会对软件的质量、性能、可维护性和全面成功产生相当大的影响。
这一定义注重区分处理构件、数据构件和连接构件，这一方法在其他的定义和方法中基本上得到保持。
软件体系结构为软件系统提供了一个结构、行为和属性的高级抽象，由构成系统的元素的描述、这些元素的相互作用、指导元素集成的模式以及这些模式的约束组成。
软件体系结构不仅指定了系统的组织结构和拓扑结构，并且显示了系统需求和构成系统的元素之间的对应关系，提供了一些设计决策的基本原理。
一个程序和计算机系统该软件体系结构是指系统的一个或者多个结构。
结构中包括软件的构件，构件的外部可见属性以及他们之间的相互关系。
体系结构并非可运行软件，而是一种表达，使软件工程师能够
（1）分析设计在满足规定需求方面的有效性
（2）在设计变更相对容易的阶段，考虑体系结构可能的选择方案（3）降低与软件构造相关的风险。
五、解释题（10分）
1.内核
内核是操作系统最基本的部分，是为众多应用程序提供对计算机硬件的安全访问的一部分软件，这种访问是有限的，并且内核决定一个程序在什么时候对某部分硬件操作多长时间。
2.进程
进程是具有独立功能的程序在一定数据集合上的一次执行过程，是操作系统进行资源分配和调度的基本单位，是一个程序及其数据在处理器上顺序执行所发生的活动。
进程的基本特征
（1）结构性
进程包含有描述进程信息的数据结构和运行在进程上的程序。
操作系统用进程控制块描述和记录进程的动态变化过程；进程的数据结构包含进程控制块、程序块和代码块。
（2）动态性
进程是程序在数据集合上的一次执行过程，具有生命周期，由创建而产生，由调度而运行，由结束而消亡，是一个动态推进的过程。
（3）并发性
在同一段时间内，若干个进程可以共享一个处理器。
进程的并发性能够改进系统的资源利用率，提高计算机的效率。
（4）独立性
在操作系统管理上，进程是一个独立的资源分配单位，进程可以在创建时获取资源，也可以在运行过程中获取资源。
操作系统为进程分配各种资源，如处理器和内存地址空间等。
（5）异步性
在计算机环境中，处理器的数量总是小于进程的数量，多个进程被强制分享同一个处理器，进程以交替方式被处理器执行。
进程的这种执行方式为异步性。
进程与程序的关系
（1）进程是一个动态的概念，强调的是程序的一次“执行”过程；程序则是一组有序指令的集合，在多道程序设计环境下，它不涉及“执行”，是一个静态的概念。
（2）不同进程可执行同一个程序。
由进程的定义可知，区分进程的条件一是所执行的程序，二是数据集合。
即使多个进程执行相同的一个程序，只要它们运行在不同的数据集合上，它们就是不同的进程。
（3）每个进程都有自己的生命期。
进程的本质是程序的一次执行过程，当系统要完成某项工作时，它就“创建”一个进程，以便执行事先编写好的、完成该工作的那段程序。
程序执行完毕、完成预定的任务后，系统就“撤消”这个进程，收回它所占用的资源。
一个进程创建后，系统就感知到它的存在；一个进程撤消后，系统就无法再感知到它。
于是从创建到撤消，这个时间段就是一个进程的“生命期”。
（4）进程之间具有并发性。
在一个系统中，同时会存在多个进程，与它们对应的多个程序同时在系统中运行，轮流占用CPU和各种资源。
这正是多道程序设计的初衷，说明这些进程在系统中并发执行着。
（5）进程间会相互制约。
由于进程是系统中资源分配和运行调度的单位，因此在对资源共享和竞争中，必然会相互制约，影响了各自向前推进的速度。
线程
在进程的基础上需要提出新的并发机制，需要将进程作为资源分配的单位和调度单位分离开来，让进程只作为资源分配的单位，而用新的概念—线程，作为调度的基本单位。
线程是操作系统进程中能够独立执行的实体，是进程的组成部分，是处理器调度的基本单位。
在一个进程中允许多个并发执行的线程，同一进程的线程共享进程获得的内存空间和资源，但不独立拥有进程资源。
线程是操作系统中的基本调度和分派单位，线程具有唯一的标志符和线程控制块。
线程控制块中包含有线程的一切私有信息。
线程与进程的区别
⏹进程是拥有资源的基本单位，线程则是程序执行的基本单位。
⏹不同进程的地址空间相互独立，同一进程的各线程共享同一个地址空间。
⏹不同进程间的通信，须使操作系统提供的进程通信机制。
同一进程各线程间的通信，可直接通过访问共享的进程地址空间实现。
⏹不同进程间的调度切换，系统要花费很大开销；同一进程的线程间切换，无须转换地址空间。
⏹多个进程间可并发执行，多个线程间也可并发执行。
进程和线程都具有并发性、异步性、结构性；不同的是进程具有独立性，是独立的资源分配和调度单位，而线程具有共享性，所有属于同一进程的线程共享进程的资源；
作业（Job）：
是将命令、程序和数据按照预先确定的次序结合在一起，并提交给系统的一个组织单位。
3.页表
页表（pagetable）是系统为保证进程的正确运行而建立的页面映像表。
分页转换功能由驻留在内存中的表来描述，该表称为页表，存放在物理地址空间中。
用来将虚拟地址空间映射到物理地址空间的数据结构称为页表。
4.信号量
信号量（Semaphore），有时被称为信号灯，是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用。
在进入一个关键代码段之前，线程必须获取一个信号量；一旦该关键代码段完成了，那么该线程必须释放信号量。
其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。
信号量（Semaphore）--相当一个信号灯，程序里是一个非负整数，表示状态。
可以用来保护两个或多个关键代码段，这些关键代码段不能并发调用。
在进入一个关键代码段之前，线程必须获取一个信号量。
5.页面替换
在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。
当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。
而用来选择淘汰哪一页的规则叫做页面置换算法。
六、简答题（15分）
1.程序员编程可利用操作系统的什么接口，可用哪些功能（3种以上）？
操作系统为用户提供两个接口。
一个是命令接口，用户利用这些操作命令来组织和控制作业的执行或管理计算机系统；另一个是程序接口，编程人员使用它们来请求操作系统服务。
1．命令接口
使用操作命令进行作业控制的主要方式有两种：
脱机方式和联机方式。
脱机方式是指用户将对作业的控制要求以作业控制说明书的方式提交给系统，由系统按照作业说明书的规定控制作业的执行。
在作业执行过程中，用户无法干涉作业，只能等待作业执行结束之后才能根据结果信息了解作业的执行情况。
2.程序接口
程序接口由一组系统调用命令（简称系统调用）组成，用户通过在程序中使用这些系统调用命令来请求操作系统提供的服务。
（1）系统调用
所谓系统调用就是用户在程序中调用操作系统所提供的一些子功能。
具体地讲，系统调用就是通过系统调用命令中断现行程序，而转去执行相应的子程序，以完成特定的系统功能。
系统调用功能完成后，控制又返回到系统调用命令的逻辑后继指令，被中断的程序将继续执行下去。
实际上，系统调用命令不仅可以供用户程序使用，系统程序也要使用系统调用来实现其功能。
对于不同操作系统而言，其所提供的系统调用命令条数、格式以及所执行的功能等都不尽相同，即使是同一个操作系统，其不同版本所提供的系统调用命令条数也会有所增减。
通常，一个操作系统提供的系统调用命令有几十乃至上百条之多，它们各自有一个惟一的编号或助记符。
这些系统调用按功能大致可以分为设备管理、文件管理、进程控制、进程通信、存储管理几大类。
系统调用命令是为了扩充机器指令，增强系统功能，方便用户使用而提供的。
因此，在一些计算机系统中，把系统调用命令称为广义指令。
广义指令与机器指令在性质上是不同的，机器指令是用硬件线路直接实现的，而广义指令则是由操作系统提供的一个或多个子程序模块实现的。
（2）系统调用的执行过程
虽然系统调用命令的具体格式因系统而异，但是，从用户程序进入系统调用的步骤及其执行过程大体上是相同的。
用户程序进入系统调用是通过执行一条“调用指令”（在有些操作系统中称为访管指令或软中断指令）实现的，当用户程序执行到调用指令时，就中断用户程序的执行，转去执行实现系统调用功能的处理程序。
3．图形用户接口
随着大屏幕高分辨率图形显示设备和多种交互式输入/输出设备（如鼠标、触摸屏等）的出现，图形用户接口于20世纪80年代后期出现并迅速推广。
图形用户接口的目标是通过对出现在屏幕上的对象直接进行操作，以控制和操纵程序的运行。
例如，用键盘或鼠标对菜单中的各种操作进行选择，使命令程序执行用户选定的操作；用户也可以通过滑动滚动条上的滑动块在列表框中的选择项上滚动，以使所要的选择项出现在屏幕上，并用
升级会员 