下载文档原格式
实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。
二、实验内容1、①设a[0:n-1]是已排好序的数组。
请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
②写出三分搜索法的程序。
三、实验要求（1）用分治法求解上面两个问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。
如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。
2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。
如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。
上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。
五、实验结果分析二分搜索法：三分搜索法：时间复杂性：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。
（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂度：O（1）。
六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。
七、附录：（源代码）二分搜索法：#include<iostream.h>#include<stdio.h>int binarySearch(int a[],int x,int n){int left=0;int right=n-1;int i,j;while(left<=right){int middle=(left+right)/2;if(x==a[middle]){i=j=middle;return 1;}if(x>a[middle])left=middle+1;else right=middle-1;}i=right;j=left;return 0;}int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9};int n=10;int x=9;if(binarySearch(a,x,n))cout<<"找到"<<endl;elsecout<<"找不到"<<endl;return 0;}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。
1、（C）是长期存储在计算机内的有组织、可共享的数据集合。
A.数据库管理系统B.数据库系统C.数据库D.文件组织2、在手工管理阶段，数据是（B）A.有结构B.无结构C.整体无结构，记录有结构D.整体结构化的3、在文件系统管理阶段，数据（B）A.无独立性B.独立性差C.具有物理独立性D.具有逻辑独立性4、在数据库系统管理阶段，数据是（D）A.有结构的B.无结构的C.整体无结构，记录内有结构D.整体结构化5、数据库系统管理阶段，数据（D）A.具有物理独立性，没有逻辑独立性B.具有物理独立性和逻辑独立性C.独立性差D.具有高度的物理独立性和一定程度的逻辑独立性6、数据库系统不仅包括数据库本身，还要包括相应的硬件、软件和（D）A 数据库管理系统B数据库应用系统C相关的计算机系统D各类相关人员7、DBMS通常可以向（B）申请所需计算机资源。
A数据库B操作系统C计算机硬件D应用程序8、在DBS中，DBMS和OS之间的关系是（D）A .并发运行B.相互调用C. OS调用DBMSD. DBMS调用OS9\数据库管理系统（DBMS）是（C）A一个完整的数据库应用系统B一组硬件C一组系统软件D既有硬件，又有软件10、描述数据库全体数据的全局逻辑结构和特性是（A）A模式B内模式C 外模式D用户模式11、（D）不是DBA数据库管理员的职责。
A完整性约束说明B定义数据库模式C数据库安全D数据库管理系统设计12、关系数据库的数据及更新操作必须遵循（D）等完整性规则。
A实体完整性和参照完整性B参照完整性和用户定义完整性C实体完整性和用户定义完整性D实体完整性、参照完整性和用户定义完整性13、现实世界中事物的特性在信息世界中称为（D）A实体B键C记录D属性14、E-R模型用于建立数据库的（A）A概念模型B结构模型C物理模型D 逻辑模型15、数据模型的三要素是（D）A外模式、模式和内模式B关系模型、层次模型、网址模型C实体、属性和联系D数据结构、数据操作和完整性约束16、设某学校中，一位教师可讲授多么课程，一门课程可由多位教师讲授，则教师与课程之间的联系是（D）A一对一联系B一对多联系C多对一联系D多对多联系17、逻辑模式（A）A有且仅有一个B最多只能有一个C至少两个D可以有多个18、数据独立性是指（C）A用户与数据分离B用户与程序分离C程序与数据分离D人员与设备分离19、在数据库三级模式间引入二级映像的主要作用是（A）A提高数据与程序的独立性B提高数据与程序的安全性C保持数据与程序的一致性D提高数据与程序的可移植性20、在数据库中，产生数据不一致的根本原因是（D）A没有严格保护数据B数据冗余量太大C未对数据进行完整性控制D数据冗余21、关系数据库建立在关系数据库模型基础上，借助（A）等概念和方法来处理数据库中的数据。
操作系统的基本类型操作系统（Operating System，简称 OS），通常也称作系统软件，是控制计算机硬件与软件资源的计算机程序，也是计算机系统中最基本、最重要的系统软件之一。
操作系统具有宏观掌控计算机各种资源的功能，包括管理处理器、存储器、输入输出设备、文件系统等，可以大大提高计算机的效率和安全性。
操作系统按照其功能和特征可以分为以下几种类型：一、单任务操作系统单任务操作系统（Single Tasking Operating System），指的是一次只能处理一个任务的操作系统。
在单任务操作系统中，只有一个应用程序能在同一时间运行，其他程序必须等待当前程序结束才能启动。
单任务操作系统中系统资源分配的方式往往是先到先服务（First Come First Serve），即当一个进程到来后，系统会保留一定的资源给它，并等待进程完成后才为下一个进程分配资源。
单任务操作系统简单、易用、稳定，往往运行速度较快，适合于单一应用、资源受限的环境。
目前单任务操作系统已经很少使用，被多任务操作系统取代。
典型的单任务操作系统包括 MS-DOS、Windows 1.0。
多任务操作系统（Multi-Tasking Operating System），指的是能同时运行多个任务的操作系统。
在多任务操作系统中，每个程序都有自己的内存空间和系统资源，它们可以相互独立运行，互不影响。
多任务操作系统可根据进程优先级和任务特点，通过任务调度算法来实现多任务的分时使用。
多任务操作系统可以提高计算机的利用率，增加计算机的并发处理能力。
它适用于高负荷、多功能的环境。
操作系统分时分配资源，可以平衡各个任务之间的资源争用，提高计算效率。
目前主流的操作系统都是多任务操作系统，如微软的Windows系列、Linux、Unix等。
三、多用户操作系统多用户操作系统（Multi-User Operating System），是指多个用户同时使用同一台计算机，每个用户都可以独立地进入操作系统，并且操作系统可以为每个用户提供独立的资源和环境。
计算机操作系统试题题库及答案一、选择题1. 下列哪个不是操作系统的特征？A. 并发B. 共享C. 有序D. 异步答案：C2. 操作系统的主要功能不包括以下哪项？A. 处理机管理B. 存储器管理C. 设备管理D. 文件管理答案：D3. 下列哪种类型的操作系统用于实现多任务处理？A. 单用户单任务B. 单用户多任务C. 多用户单任务D. 多用户多任务答案：B4. 在操作系统中，进程和线程的区别是什么？A. 进程是系统进行资源分配和调度的基本单位，线程是进程的组成部分B. 线程是系统进行资源分配和调度的基本单位，进程是线程的组成部分C. 进程和线程都是系统进行资源分配和调度的基本单位D. 进程和线程没有区别答案：A5. 下列哪个进程调度算法可能会导致“饥饿”现象？A. 先来先服务（FCFS）B. 最短作业优先（SJF）C. 优先级调度D. 最高响应比优先答案：C二、填空题6. 操作系统中的进程与程序的区别是：进程是______的实例，而程序是______的实例。
答案：进程；程序7. 在操作系统中，为了解决进程之间的同步问题，通常使用______机制。
答案：信号量（Semaphore）8. 虚拟存储器的作用是扩大______，提高______。
答案：物理存储器；存储器的利用率9. 文件系统的主要功能包括：文件的______、______、______和______。
答案：创建；删除；读写；权限管理10. 设备驱动程序的作用是实现对______的______。
答案：设备；控制三、判断题11. 进程和线程是操作系统的基本单位，它们都可以独立执行程序。
答案：错误。
进程是基本单位，线程是进程的组成部分，线程可以独立执行程序。
12. 在操作系统中，所有的进程都可以并发执行。
答案：错误。
在单处理器系统中，进程不能同时执行，而是分时执行。
13. 虚拟存储器的容量仅受物理存储器的限制。
答案：错误。
虚拟存储器的容量受物理存储器和硬盘空间的限制。
C语言的多核编程与并行执行概述C语言是一种广泛使用的编程语言，可以用于开发各种类型的应用程序。
在当今计算机硬件技术的快速发展中，多核处理器已经成为主流。
多核处理器具有多个独立的CPU核心，可以同时执行多个任务。
为了充分利用多核处理器的潜力，开发人员需要使用适当的技术和编程模型来进行多核编程和并行执行。
本文将介绍C语言中的多核编程和并行执行的基本概念和技术，并提供一些实例来帮助读者理解。
什么是多核编程和并行执行多核编程是指在多核处理器上编写代码以利用多个CPU核心并行执行任务的过程。
在单核处理器上，程序的执行是线性的，即一次只能执行一个指令。
而在多核处理器上，不同的CPU核心可以同时执行不同的代码片段，从而加快程序的执行速度。
并行执行是指多个任务同时进行，每个任务在一个独立的线程中执行。
通过在不同的CPU核心上创建线程，可以实现多个任务的并行执行。
多核编程的挑战虽然多核处理器有助于提高计算机系统的性能，但多核编程也带来了一些挑战。
以下是一些常见的挑战：数据共享和同步在多核编程中，多个线程可以同时访问和修改共享的数据。
这可能导致数据竞争和不一致的结果。
为了解决这个问题，开发人员需要使用同步机制来确保线程之间的正确协同工作，例如使用互斥锁、条件变量等。
负载平衡在多核处理器上，任务的负载应该平衡在不同的CPU核心上。
如果负载不平衡，某些核心可能一直处于空闲状态，而其他核心却忙于处理更多的任务。
开发人员需要设计和实现合适的调度算法来平衡任务的负载。
可扩展性多核编程要求程序能够有效地扩展到多个CPU核心上。
如果程序的设计和实现不具备可扩展性，增加CPU核心的数量可能无法提高性能。
开发人员需要使用可扩展的算法和数据结构来实现可扩展的程序。
C语言中的多核编程技术C语言提供了一些用于多核编程的技术和库。
以下是一些常用的技术：线程库C语言提供了线程库（pthread）来创建和管理线程。
线程库提供了创建线程、销毁线程、同步线程等功能。
第一章引论1操作系统：操作系统是管理和控制计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。
2管态：当执行操作系统程序时，处理机所处的状态3目态：当执行普通用户程序时，处理机所处的状态。
4多道程序设计：在这种设计技术下，内存中能同时存放多道程序，在管理程序的控制下交替的执行。
这些作业共享CPU和系统中的其他资源。
5并发：是指两个或多个活动在同一给定的时间间隔中进行。
它是宏观上的概念。
6并行：是指两个或多个活动在同一时刻同时执行的情况。
7吞吐量：在一段给定的时间内，计算机所能完成的总工作量。
8分时：就是对时间的共享。
在分时系统中，分时主要是指若干并发程序对CPU时间的共享。
9实时：表示“及时”或“既时”。
10系统调用：是用户在程序中能以“函数调用”形式调用的、由操作系统提供的子功能的集合。
每一个子功能称作一条系统调用命令。
它是操作系统对外的接口，是用户级程序取得操作系统服务的唯一途径。
11特权指令：指指令系统中这样一些指令，如启动设备指令、设置时钟指令、中断屏蔽指令和清内存指令，这些指令只能由操作系统使用。
12命令解释程序：其主要功能是接收用户输入的命令，然后予以解释并且执行。
13脱机I/O：是指输入/输出工作不受主机直接控制，而由卫星机专门负责完成I/O，主机专门完成快速计算任务，从而二者可以并行操作。
14联机I/O：是指作业的输入、调入内存及结果输出都在CPU直接控制下进行。
15资源共享：是指计算机系统中的资源被多个进程所功用。
例如，多个进程同时占用内存，从而对内存共享；它们并发执行时对CPU进行共享；各个进程在执行过程中提出对文件的读写请求，从而对磁盘进行共享等等。
第二章进程和线程1顺序性：是指顺序程序所规定的每个动作都在上个动作结束后才开始的特性。
2封闭性：是指只有程序本身的动作才能改变程序的运行环境。
3可再现性：是指程序的执行结果与程序运行的速度无关。
计算机操作系统（第四版）汤小丹课后习题答案第一章1.设计现代OS的主要目标是什么？答：（1）有效性；（2）方便性；（3）可扩充性；（4）开放性。
2.OS的作用可表现在哪几个方面？答：(1)OS作为用户与计算机硬件系统之间的接口；(2)OS作为计算机系统资源的管理者；(3)OS实现了对计算机资源的抽象；3.为什么说OS实现了对计算机资源的抽象？答：OS首先在裸机上覆盖一层I/O设备管理软件，实现了对计算机硬件操作的第一层次抽象；在第一层软件上再覆盖文件管理软件，实现了对硬件资源操作的第二层次抽象。
OS通过在计算机硬件上安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节，由它们共同实现了对计算机资源的抽象。
4.试说明推动多道批处理系统形成和収展的主要动力是什么？答：主要动力来源于四个方面的社会需求与技术发展；(1)不断提高计算机资源的利用率；(2)方便用户；(3)器件的不断更新换代；(4)计算机体系结构的不断发展。
5.何谓脱机I/O和联机I/O？答：脱机I/O是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机，在外围机的控制下，把纸带或卡片上的数据或程序输入到磁带上。
该方式下的输入输出由外围机控制完成，是在脱离主机的情况下进行的。
而联机I/O方式是指程序和数据的输入输出都是在主机的直接控制下进行的。
6.试说明推动分时系统形成和发展的主要动力是什么？答：推动分时系统形成和发展的主要动力是更好地满足用户的需要。
主要表现在：CPU的分时使用缩短了作业的平均周转时间；人机交互能力使用户能直接控制自己的作业；主机的共享使多用户能同时使用同一台计算机，独立地处理自己的作业。
7.实现分时系统的关键问题是什么？应如何解决？答：关键问题是当用户在自己的终端上键入命令时，系统应能及时接收并及时处理该命令，在用户能接受的时延内将结果返回给用户。
解决方法：针对及时接收问题，可以在系统中设置多路卡，使主机能同时接收用户从各个终端上输入的数据；为每个终端配置缓沖区，暂存用户键入的命令或数据。
