北航操作系统补考试卷.参考答案

《操作系统》试卷

一、名词解释题（每题5分，共25分）

1、原语

2、快表

3、设备无关性

4、临界资源

5、文件系统

二、判断题（每题1分，共5分）

1、临界区的执行不能被中断。（）

2、资源顺序分配法破坏了死锁发生的循环等待必要条件。（）

3、对磁盘进行磁头调度的目的是为了缩短寻道时间。（）

4、采用页式存储管理时，重定位的工作是由用户完成的。（）

5、与设备相关的中断处理过程由设备驱动程序完成。（）

三、简答题（每题5分，共20分）

1、进程的含义是什么？如何构造和描述进程？

2、什么是死锁？产生死锁的必要条件是什么？

3、什么是开中断？什么是关中断？

4、分页存储管理中有哪几种常用的页面置换算法？

四、银行家算法（10分）

在银行家算法中，若出现以下资源分配情况：

进程资源最大需求已分配资源

P0 7,5,3 0,1,0

P1 3,2,2 2,1,0

P2 9,0,2 3,0,2

P3 2,2,2 2,1,1

P4 4,3,3 0,0,2

系统剩余资源数量：（3,2,2）。

（1）该状态是否安全（给出详细的检查过程）？

（2）若系统剩余资源数量为（3,1,0），系统是否安全？若系统处于安全状态，请给出安全序列；若系统处于不安全状态，请说明原因。

五、设备管理（10分）

设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个程序同时进入就绪状态，进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图，并说明：

（1）开始运行后，CPU有无空闲等待？若有，在哪段时间内等待？计算CPU的利用率。

（2）进程A运行时有无等待现象？若有，在什么时候发生等待现象？

（3）进程B运行时有无等待现象？若有，在什么时候发生等待现象？

六、进程同步（15分）

桌子上有一只盘子，每次只能放入或者取出一个水果。现有许多苹果与橘子。一家4口人各行其职。爸爸专向盘子中放入苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P操作, V操作来实现4人之间的同步算法。

七、存储管理（15分）

在分页虚拟存储管理系统中，假定系统为某进程分配了四个主存块（将开始4页先装入主存），页的引用顺序为：7,1,2,0,3,0,4,2,3,0,3,2,7,0,1，若采用FIFO调度算法，LUR调度算法时，分别产生多少次缺页中断？一次淘汰的页分别是什么？

参考答案：

一、名词解释题

1、原语：由若干条指令所组成，用来实现某个特定的操作。通过一段不可分割

的或者不可中断的程序实现其功能。

2、快表：存在于地址变换机构中的一个由高速寄存器组成的小容量的联想寄存

器，构成的一张表。

3、设备无关性：程序可以通过一组统一的操作过程来操作设备，这种操作接口

与具体的设备无关。

4、临界资源：某段时间内只允许一个进程使用的资源。

5、文件系统：一个负责存取和管理外部存储器上文件信息的机制。

二、判断题

1、错误

2、正确

3、正确

4、错误

5、正确

三、问答题

1、进程是程序的一次执行。进程由“进程控制块+程序+数据”构成，用进程控

制块描述进程。

2、死锁：两个以上的进程相互等待一个永远不可能发生的条件，这种僵持的局

面成为死锁。

死锁产生的必要条件：互斥条件；不剥夺条件；请求和保持条件；循环等待条件。

3、尽管产生了中断源和发出了中断请求，但CPU内部的处理机状态字的中断允

许位已被清除，从而不允许CPU响应中断，这种情况称为关中断。

CPU禁止中断后只有等到处理机状态字的中断允许位被重新设置后才能接收中断，处理机状态位的设置被称为开中断。

4、先进先出(FIFO)；

最近最少使用淘汰算法(LRU)；

最近不经常使用淘汰算法(LFU)；

最优算法(OPT)

四、死锁检测

（1）该状态是安全的，安全序列为p1,p4,p3,p0,p2(满足条件的安全序列均可，这只是其中一个安全序列)

（2）不安全，无法满足任何进程的资源需求。

五、设备管理

时序图：

0 50 100 150 180 200 300 (ms) 进程A: 计算打印计算打印

进程B: 等待计算输入等待计算（1）存在CPU空闲。CPU利用率为(300-50)/300=83.3%

（2）进程A运行后无等待现象。

（3）进程B运行后有等待现象(在A开始180ms到200ms之间；或者B在运行后130ms到150ms之间)。

六、进程同步

设信号量empty初值为1，apple表示盘中有苹果，orange表示盘中有橘子，初值均为0。

CoBegin:

爸爸：

Begin:

P(empty)；

放苹果；

V(apple);

End

妈妈：

Begin:

P(empty)；

放橘子；

V(orange);

End

女儿：

Begin:

P(apple)；

取苹果；

V(empty);

End

儿子：

Begin:

P(orange)；

取橘子；

V(empty);

End

CoEnd

七、存储管理

（1）FIFO调度算法，共发生了3次缺页中断，一次淘汰的页为7,2,1 （2）LRU调度算法，共发生了3次缺页中断，一次淘汰的页为7,1,4

北京航空航天大学《 数据库系统概论 》期末考试卷

数据库期末试题2010级 友情提醒：闭卷考试，有一定难度，英文，考试时间2小时，需要好好复习。建议好好做那份样卷（即09年试卷），大题目题型和那上面差不多，选择改为了判断，我们这届没有简答题。 题型：判断（10题），简答题（5题） 判断题没有记录，主要考基本概念。 简答题： （1）事务，串行化调度，两阶段锁协议 （2）Sql语句和关系代数语句写出查询 （3）ER图设计并写出关系主键，外键等 （4）给出函数依赖，并且推断属于何种范式（BCNF，第三范式） （5）题目给出关系表与关系代数表达式，求出运算结果

班号学号姓名成绩 《数据库系统概论》期末考试卷 注意事项：1、考试时间2小时； 2、答案写在答题纸上 题目： 一、……………………………………………………………( 分) 二、……………………………………………………………( 分) 三、……………………………………………………………( 分) 四、……………………………………………………………( 分) 五、……………………………………………………………( 分) 六、……………………………………………………………( 分)

一：单选题(本大题共12小题，每小题3分，共36分) 1. 对现实世界进行第一层抽象的是【 D 】 A. 用户数据模型 B. 物理数据模型 C. 逻辑数据模型 D. 概念数据模型 2. 以下不属于集合运算的是________。【 C 】 A. 并 B. 广义笛卡尔积 C. 除 D. 差 3. 若一个关系有函数依赖集（AB→CD, A→D），则可确定它最高属于：【 A 】 A. 1NF B. 2NF C. 3NF D. BCNF 4. 以下哪个SQL语句没有语法错误【 A 】 A. Grant select on TableA to User1 with grant option B. select count(a) from b where count(a)>3 C. insert into TableA set a=1, b=2 D. drop TableA where a=1 5. 定义学生对象来表示张三、李四等学生个体，这种抽象方法被称为【A】 A. 分类 B. 聚集 C. 类比 D. 概括 6. 哪一级封锁协议解决了读脏数据问题？【B】 A. 一级封锁协议 B.二级封锁协议 C. 三级封锁协议 D. 以上都不是 7. 工资表（职工号，岗位级别，岗位工资）中有如下约束：岗位级别低的职工的岗位工资 应低于岗位级别高的职工的岗位工资。这种约束属于什么约束类型？【 E】 A. 静态列级约束 B. 动态列级约束 C. 静态元组约束 D. 动态元组约束 E. 静态关系约束 F. 动态关系约束 8. 设有关系R（A，B，C）的值如下：

北航计算机复试面试题

操作系统： 1.文件系统和数据库系统的区别，哪个效率更高，为什么。 2.进程上下文切换具体过程，是什么实现的 3.BIOS的意思，程序的可移植性 4..操作系统的基本概念 5.操作系统开机过程； 6.操作系统分哪些部分，进程管理包含什么内容； 7.操作系统我们所学的其他课程有什么关系，还是操作系统是个独立 的课程 8.什么是系统调用？它和库函数调用有什么区别？ 计算机网络： 1.数据链路层是干什么的 2.输入数据在网络层叫什么 3.分组的生命期，为什么要设置这个生命期 4.dns的工作过程 5.点击一个链接的网络过程； 6.网络模型，网络层协议有哪些，应用层协议有哪些 7.两台计算机中的进程进行通信，需要解决什么问题？ 基础数学：

1.什么是极限，什么是趋近 2.极值的求法 3.泰勒级数的展开式；为什么把一个简单的函数表示成那么麻烦的 泰勒级数？ 4.信息和数据的区别？ 5.图形和图像有什么区别？ 6.概率的全概率公式，高数的傅立叶级数，现代秩的概念 7.一枚硬币抛三次，至少一次正面的概率 8.什么是图的同构 9.说一下数理逻辑的定义 10.矩阵的用途 11.线性相关与无关 12.离散数学包含那些部分； 13.集合的势，无限集合的大小比较，偏序，良序，全序，划分，欧拉图，Hamilton图 14.什么是群 15.谓词逻辑和命题逻辑的区别 16.什么是等价关系，什么是子句，什么是合取范式 17.什么是二元关系 数据结构与算法： 1.什么是二叉树

2.已知病毒特征码一百万个和文件一个，问用什么查找算法能尽快的检测出该文件是否有病毒？ 3.快排和插入排序那个更高效？ 4.简单描述九宫格算法 5.学数据结构的意义； 6.离散数学的图论和数据结构图论的相同点和不同点 7.堆栈和堆的区别 8.递归变成非递归需要什么（堆栈） 9.堆栈溢出是怎么回事儿 10.算法的几种策略，迪杰斯特拉算法 11.要得到文件的后N行，需要什么数据结构实现 12.数据库中B+树和B-树的区别 13.什么是树？什么是图？树和图有什么区别？ 14.矩阵相乘的时间复杂度是多少？ 15.现在有一未知大小的文件，里面是单词的集合，现要将文件读入内存，问采用什么存储结构较好？ 数据库： 1.数据库查询语句怎样写效率更高 2.使用sql语句实现图的某一顶点可达的该图的其他顶点的查找 3.数据库完整性措施； 4.如何保证数据的一致性

北航最优化方法大作业参考

北航最优化方法大作业参考

1 流量工程问题 1.1 问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5…,5)1 )T， ×13 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1× )。 13 图 1 网络拓扑和流量需求

1.2 7节点算例求解 1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T） 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.2 算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 X2>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.3 算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T 对应的最优值c T x3=40

北航15年3月《数据库原理及应用》试卷

北京航空航天大学现代远程教育 2015年3月份《数据库原理及应用》课程考试试卷 注意事项： 1、本试卷满分100分；考试时间：90分钟；考试形式：开卷 2、请将答案一律写在答题纸上，试卷上作答无效 3、考试结束后，考生将试卷及答题纸一并交回 4、请将条形码贴在答题纸的指定位置 学习中心______________姓名____________学号____________ 一、单项选择题（本大题共20小题，每小题1.5分，共30分） 1、第一代数据模型是指（）。 A．关系模型B．网络模型 C．面向对象模型D．人工智能模型 2、SQL语言中授权的操作是通过（）语句实现的。 A．CREATE B．REVOKE C．GRANT D．INSERT 3、SQL Server是一个基于（）。 A．层次模型的DBMS B．网状模型的DBMS C．关系模型的应用程序D．关系模型的DBMS 4、一个m:n联系转换为一个关系模式。关系的码为（）。 A．某个实体的码B．各实体码的组合 C．n端实体的码D．任意一个实体的码 5、手工处理阶段是（）。 A．计算机数据处理技术发展的初级阶段 B．计算机数据管理技术发展的初级阶段 C．计算机数据处理技术发展的中级阶段 D．计算机数据管理技术发展的中级阶段 6、在DBS中，DBMS和OS之间的关系是（）。 A．相互调用B．DBMS调用OS C．OS调用DBMS D．并发运行7、数据库保护的几个方面中，不包括的是（）。 A．控制数据冗余B．并发控制 C．完整性保护D．故障恢复 8、（）是长期存储在计算机内的有组织、可共享的数据集合。 A．数据库管理系统B．数据库系统 C．数据库D．文件组织 9、数据库系统包括（）。 A．DB、DBMS B．DB、DBA C．DB、DBMS、DBA、计算机硬件 D．DB、DBMS、DBA、OS、计算机硬件 10、SQL语言具有（）的功能。 A．关系规范化、数据操纵、数据控制 B．数据定义、数据操纵、数据控制 C．数据定义、关系规范化、数据控制 D．数据定义、关系规范化、数据操纵 11、部分匹配查询中有关匹配符“_”的正确的叙述是（）。 A．“_”代表任意单个字符 B．“_”可以代表零个或多个字符 C．“_”不能与“%”一同使用 D．“_”代表一个字符 12、规范化过程主要是为了克服数据库逻辑结构中的插入异常、删除异常以及（）的缺陷。 A．数据的不一致性B．结构不合理 C．冗余度大D．数据丢失 13、SQL 语言集数据查询、数据操作、数据定义和数据控制功能于一体，语句INSERT、DELETE、UPDATA实现下列（）功能。 A．数据查询B．数据操纵 C．数据定义D．数据控制 14、下列命题中不正确的是（）。 A．数据库减少了不必要的数据冗余 B．数据库中不存在冗余数据

北航计算机复试面试题

操作系统: 1.文件系统与数据库系统的区别,哪个效率更高,为什么。 2.进程上下文切换具体过程,就是什么实现的 3.BIOS的意思,程序的可移植性 4.、操作系统的基本概念 5.操作系统开机过程; 6.操作系统分哪些部分,进程管理包含什么内容; 7.操作系统我们所学的其她课程有什么关系,还就是操作系统就是个独立的课程 8.什么就是系统调用？它与库函数调用有什么区别？ 计算机网络: 1.数据链路层就是干什么的 2.输入数据在网络层叫什么 3.分组的生命期,为什么要设置这个生命期 4.dns的工作过程 5.点击一个链接的网络过程; 6.网络模型,网络层协议有哪些,应用层协议有哪些 7.两台计算机中的进程进行通信,需要解决什么问题？ 基础数学: 1.什么就是极限,什么就是趋近 2.极值的求法 3. 泰勒级数的展开式;为什么把一个简单的函数表示成那么麻烦的泰勒级数？ 4.信息与数据的区别？ 5.图形与图像有什么区别？ 6.概率的全概率公式,高数的傅立叶级数,现代秩的概念 7.一枚硬币抛三次,至少一次正面的概率 8.什么就是图的同构 9.说一下数理逻辑的定义 10.矩阵的用途 11.线性相关与无关 12.离散数学包含那些部分; 13.集合的势,无限集合的大小比较,偏序,良序,全序,划分,欧拉图,Hamilton图 14.什么就是群 15.谓词逻辑与命题逻辑的区别 16.什么就是等价关系,什么就是子句,什么就是合取范式 17.什么就是二元关系 数据结构与算法: 1.什么就是二叉树 2.已知病毒特征码一百万个与文件一个,问用什么查找算法能尽快的检测出该文件就是否有病毒？ 3.快排与插入排序那个更高效？ 4.简单描述九宫格算法 5.学数据结构的意义; 6.离散数学的图论与数据结构图论的相同点与不同点 7.堆栈与堆的区别

北航最优估计知识点提纲

第一章 1)不同的最优估计准则是否会导致相同的估计结果 2)参数估计与状态估计的区别是什么 3)极大似然估计与极大验后估计的区别、联系是什么； 4)怎样理解极大似然估计； 5)多维随机变量下，对于MMSE，目标函数估计误差协方差阵最小、估计误差分量平 方和最小，是否会导致有相同的估计效果； 6)E{E[x|Z]}的计算过程中对哪一随机变量进行积分？ 7)似然函数的构造思想是什么？最优估计解的求解方法怎样？ 8)多维随机向量的正态分布概率密度计算公式怎样？如何理解； 9)矩阵微分的计算方法是怎样规定的？常用公式都有哪些？ 10)什么是马尔科夫估计？ 11)各种估计准则之间相互关系如何？ 12)造成最小二乘估计误差的主要因素有哪些？ 13)线性最小方差估计与最小方差估计的关系如何？ 第二章 14)若噪声为零均值白噪声，连续线性系统离散化后噪声统计特性有何变化？ 15)离散化噪声统计特性获得的方法是什么？ 16)连续系统离散化的具体计算方法 17)卡尔曼滤波的问题分类有哪些？ 18)卡尔曼滤波中的各种符号~、^、（k|k-1）的具体含义是什么？ 19)卡尔曼滤波的准则是什么？ 20)正交投影的定义是什么？ 21)正交投影的物理意义是什么？ 22)正交定理与正交投影的关系怎样？ 23)正交定理与线性最小方差估计之间的关系如何？ 24)最优预测滤波公式推导的原理与过程怎样 25)最优预测问题滤波公式

26)最优滤波问题公式的推导思路 27)最优预测与最优滤波公式的对比，相同点、不同点以及原因 28)卡尔曼滤波的重要特征或主要优点是什么 29)卡尔曼滤波的通解形式怎样？出于什么样的考虑？关键问题是什么？ 30)最优滤波问题、最优预测问题中什么协方差阵会出现负项？为什么？ 31)最优增益阵与噪声统计特性之间的关系怎样？ 32)理解卡尔曼滤波中协方差阵内各种因素的构成及其原因 33)理解卡尔曼滤波中状态估计值、估计误差与噪声的相关性，考虑不同时刻 34)卡尔曼滤波是否具有无偏性？如果有，需要什么样的条件？ 35)系统、观测噪声相关情况下，卡尔曼滤波算法会发生什么样的变化？ 36)输入对卡尔曼滤波方程的影响怎样？ 37)成型滤波器的思想是什么？ 38)出现有色噪声时怎样进行卡尔曼滤波？ 39)控制系统、观测系统附着不同性质噪声情况下，如何求解？连续系统与离散系统处 理方法是否一样？ 40)卡尔曼滤波中对R k、Q k的理解（统计的对象中的时间） 第三章 41)平滑问题的分类，各自处理的方法如何？ 42)为什么可以用极大验后估计推导卡尔曼平滑问题公式？ 43)平滑处理的意义在哪里？ 44)实际应用中是否平滑处理利用历史观测越多，获得的估计结果会越精确？ 45)平滑算法中平滑协方差在卡尔曼滤波计算上有什么作用？意义如何？ 46)固定区间平滑的解算过程如何？ 47)固定区间平滑算法中用于修正的因素有哪些？ 48)固定点平滑与固定滞后平滑公式的获得思想是什么？解算过程怎样？ 第四章 49)滤波稳定性的意义是什么？ 50)滤波稳定性的判定准则是什么？是否是充要条件？

北航计算机研究生课程-算法设计与分析-HomeWork-1

一、已知下列递推式： C(n) = 1若n =1 = 2C （n/2） + n – 1 若n ≥ 2 请由定理1 导出C(n)的非递归表达式并指出其渐进复杂性。 定理1：设a,c 为非负整数，b,d,x 为非负常数，并对于某个非负整数k, 令n=c k , 则以下递推式 f(n) =d 若 n=1 =af(n/c)+bn x 若 n>=2 的解是 f(n)= bn x log c n + dn x 若 a=c x f(n)= x x x a x x n c a bc n c a bc d c ??? ? ??--???? ??-+log 若 a ≠c x 解：令F(n) = C(n) – 1 则 F(n) = 0 n=1 F(n) = 2C(n/2) + n – 2 n>=2 = 2[F(n/2) + 1] + n – 2 = 2F(n/2) + n 利用定理1，其中： d=0,a=2,c=2,b=1,x=1,并且a=c x 所以 F(n) = nlog 2n 所以 C(n) = F(n) + 1 = nlog 2n + 1 C(n)的渐进复杂性是O(nlog 2n) 二、由于Prim 算法和Kruskal 算法设计思路的不同，导致了其对不同问题实例的效率对比关系的不同。请简要论述： 1、如何将两种算法集成，以适应问题的不同实例输入； 2、你如何评价这一集成的意义？ 答： 1、Prim 算法基于顶点进行搜索，所以适合顶点少边多的情况。 Kruskal 从边集合中进行搜索，所以适合边少的情况。 根据输入的图中的顶点和边的情况，边少的选用kruskal 算法，顶点少的选用prim 算法 2、没有一个算法是万能的，没有一个算法是对所有情况都适合的。这一集成体现了针对具体问题选用最适合的方法，即具体问题具体分析的哲学思想。 三、分析以下生成排列算法的正确性和时间效率： HeapPermute (n ) //实现生成排列的Heap 算法 //输入：一个正正整数n 和一个全局数组A [1..n ] //输出：A 中元素的全排列 if n = 1 write A else for i ←1 to n do HeapPermute (n -1)

16春北航《数据库原理及应用》在线作业

一、单选题（共 25 道试题，共 100 分。）V 1. 数据库物理存储方式的描述称为( ) A. 外模式 B. 内模式 C. 概念模式 D. 逻辑模式 满分：4 分 2. DB、DBMS和DBS三者之间的关系是( ) A. DB包括DBMS和DBS B. DBS包括DB和DBMS C. DBMS包括DB和DBS D. 不能相互包括 满分：4 分 3. 在关系模型中，实现"关系中不允许出现相同的元组"的约束是通过______。 A. 候选键 B. 主键 C. 外键 D. 超键 满分：4 分 4. 数据库中只存放视图的 A. 操作 B. 对应的数据 C. 定义 D. 限制 满分：4 分 5. 从一个数据库文件中取出满足某个条件的所有记录形成一个新的数据库文件的操作是（）操作。 A. 投影 B. 连接 C. 选择 D. 复制 满分：4 分 6. 在SQL中，删除视图用______。 A. DROP SCHEMA命令 B. CREATE TABLE命令 C. DROP VIEW命令 D. DROP INDEX命令 满分：4 分 7. DBAS指的是______。 A. 数据库管理系统 B. 数据库系统 C. 数据库应用系统 D. 数据库服务系统 满分：4 分 8. 设有关系模式W(C,P,S,G,T,R),其中各属性的含义是：C课程,P教师,S学生,G成绩,T

时间,R教室，根据定义有如下数据依赖集：D={C→G，(S,C)→G,(T,R)→C,(T,P)→R,(T,S)→R}关系模式W的一个关键字是__，W的规范化程度最高达到__（）。 A. (S,C),1NF B. (T,R),3NF C. (T,P),4NF D. (T,S),2NF 满分：4 分 9. 设有关系R1和R2，经过关系运算得到结果S，则S是______。 A. 一个关系 B. 一个表单 C. 一个数据库 D. 一个数组 满分：4 分 10. （）是控制数据整体结构的人，负责三级结构定义和修改 A. 专业用户 B. 应用程序员 C. DBA D. 一般用户 满分：4 分 11. 数据库设计属于（）。 A. 程序设计范畴 B. 管理科学范畴 C. 系统工程范畴 D. 软件工程范畴 满分：4 分 12. 下述（）不是DBA数据库管理员的职责。 A. 完整性约束说明 B. 定义数据库模式 C. 数据库安全 D. 数据库管理系统设计 满分：4 分 13. 对象标识具有唯一性，其唯一性的范围是在____ A. 对象内 B. 类内 C. 类层次内 D. 系统内 满分：4 分 14. 已知关系R（P，Q，M，N），F是R上成立的函数依赖集，F={（P→Q，Q→M）}，则R 的侯选码是（）。 A. P B. Q C. PQ D. PN 满分：4 分

北航研究生算法(208精心整理)

一：判断题 1、一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。（对） 2、NP完全问题比其他所有NP问题都要难。（错） 3、回溯法用深度优先法或广度优先法搜索状态空间树。（错，仅深度优先） 4、在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。（错） 5、P类和NP类问题的关系用P?NP来表示是错误的。（错） 6、若近似算法A求解某极小化问题一实例的解为Sa，且已知该问题的最优解为Sa/3，则该近似算法的性能比为3。（错） 7、通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。（对） 8、若P2多项式时间转化为(polynomial transforms to)P1，则P2至少与P1一样难。（错） 9、快速排序算法的平均时间复杂度是O(nlogn)，使用随机化快速排序算法可以将平均时间复杂度降得更低。（错） 10、基于比较的寻找数组A[1,…,n]中最大元素的问题下届是Ω(n/3)。（错） 11、O(f(n))+O(g(n))=O(min{f(n),g(n)})（错） 12、若f(n)=Ω(g(n))，g(n)=Ω(h(n))，则f(n)=Ω(h(n))（对） 13、若f(n)=O(g(n))，则g(n)=Ω(f(n))（对） 14、贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。（错） 15、LasVegas算法只要给出解就是正确的。（对） 16、一个完全多项式近似方案是一个近似方案{Aε}，其中每一个算法Aε在输入实例I的规模的多项式时间内运行。（错） 二：简答 1、二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？此时的查找和插入算法的复杂性如何？ 答：减治策略有3个主要的变种，包括减常量、减常数因子和减可变规模。(1) 二叉查找树属于减可变规模变种的应用。(2) 当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，(3) 查找和插入算法的时间效率都属于Θ(n)。 2、何谓伪多项式算法？如何将一Monte Carlo算法转化为Las Vegas算法？ 答：若一个数值算法的时间复杂度可以表示为输入数值N的多项式，但其运行时间与输入数值N的二进制位数呈指数增长关系，则称其时间复杂度为伪多项式时间。 Las Vegas算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。 Monte Carlo算法每次都能得到问题的解，但不保证所得解的准确性 转化：可以在Monte Carlo算法给出的解上加一个验证算法，如果正确就得到解，如果错误就不能生成问题的解，这样Monte Carlo算法便转化为了Las Vegas算法。 3、构造AVL树和2-3树的主要目的是什么？它们各自有什么样的查找和插入的效率？ 答：(1)当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，为了解决这一问题，可以构造AVL树或2-3树，使树的深度减小。一棵AVL树要求它的每个节点的左右子树的高度差不能超过1。2-3树和2-3-4树允许一棵查找树的单个节点不止包含一个元素。(2) AVL树在最差情况下，查找和插入操作的效率属于Θ(lgn)。2-3树无论在最差还是平均情况下，查找和插入的效率都属于Θ(log n)。 4、写出0/1背包问题的一个多项式等价(Polynomial Equivalent)的判定问题，并说明为什么它们是多项式等价的。 答：0/1背包问题：从M件物品中，取出若干件放在空间为W的背包里，给出一个能获得最大价值的方案。每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。+

北航《算法与数据结构》在线作业一 辅导资料

北航《算法与数据结构》在线作业一 一、单选题（共 25 道试题，共 100 分。） 1. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。 . q->nxt=p->nxt;p->nxt=q; . p->nxt=q->nxt;q=p; . q->nxt=p->nxt;p->nxt=q; . p->nxt=q->nxt;q->nxt=p; 正确答案： 2. 快速排序的记录移动次数（）比较次数，其总执行时间为O(nlog2n)。 . 大于 . 大于等于 . 小于等于 . 小于 正确答案： 3. 下述几种排序方法中,平均查找长度最小的是（） . 插入排序 . 选择排序 . 快速排序 . 归并排序 正确答案： 4. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作 . 条件判断 . 结点移动 . 算术表达式 . 赋值语句 正确答案： 5. 对于含有n个顶点条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。 . O(log2n) . O(n2) . O(n) . O(log2) 正确答案： 6. 下列关于栈的叙述正确的是（）。

. 栈是非线性结构 . 栈是一种树状结构 . 栈具有先进先出的特征 . 栈具有后进先出的特征 正确答案： 7. 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( ) . ki≤k2i≤k2i+1 . ki

15秋北航《算法与数据结构》在线作业二100分答案

北航《算法与数据结构》在线作业二 单选题 一、单选题（共25 道试题，共100 分。） 1. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作 A. 条件判断 B. 结点移动 C. 算术表达式 D. 赋值语句 -----------------选择：B 2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。 A. HL=p;p->next=HL; B. p->next=HL;HL=p; C. p->next=HL;p=HL; D. p->next=HL->next;HL->next=p; -----------------选择：B 3. 线性表是一个具有n个（）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 -----------------选择：C 4. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。 A. 10，15，14，18，20，36，40，21 B. 10，15，14，18，20，40，36，21 C. 10，15，14，20，18，40，36，21 D. 15，10，14，18，20，36，40，21 -----------------选择：A 5. 按照二叉树的定义，具有3个结点的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 -----------------选择：C 6. 下列有关图遍历的说法中不正确的是（）。 A. 连通图的深度优先搜索是个递增过程 B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法 D. 图的遍历要求每个顶点仅被访问一次 -----------------选择：C 7. Substr('DATA STRUCTURE'，5，9)=（）。 A. STRUCTURE' B. 'ASTUCTUR' C. 'DATA STRUCTRUE'

北航2015年961真题

北京航空航天大学2015年 硕士研究生入学考试试题科目代码：961 计算机综合 (共8页) 考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效（本题单不参与评卷） 一、 单项选择（15道小题，每题2分，共30分） 1、常见的几种总线仲裁方式中，对电路最为敏感的方式为（） A、链式查询 B、计数器查询方式 C、独立请求 D、中断查询 2、在常用的I/O控制方式中，要求主存与I/O设备之间有直接数据通路的方式为（） A、程序查询 B、程序中断 C、I/O通道 D、DMA 3、某机器字长为64位，内存容量为256MB，若按字编址，则其寻址空间为（） A、0～8M-1 B、0～16M-1 C、0～32M-1 D、0～64M-1 4、某机器字长为16位，内存按字编址，PC当前值为2000H,当读取一条双字长指令后PC的值为（） A、2000H B、2004H C、2008H D、200AH 5、某程序运行于一个由L1、L2两级cache以及主存组成的存储系统，L1 cache和L2 cache的命中率分别为50%和80%，则整个存储系统cache的命中率为（） A、65% B、80% C、90% D、95% 6、段式存储管理的逻辑地址空间为（） A、一维线性的 B、二维的 C、三维的 D、由操作系统决定的 7、下列选项中，操作系统提供给用户的接口为（） A、库函数 B、中断 C、系统调用 D、驱动程序 8、设某进程的页面走向为：5、4、3、2、4、3、1、4、3、2、1、5，系统中

有3页物理内存，请问采用LRU和FIFO淘汰算法的缺页次数分别为（） A、9和10 B、5和7 C、6和6 D、8和10 9、进程可以使用的最大地址空间受限于（） I.地址位数；II.物理内存大小；III.辅存大小 A、I B、I和II C、II和III D、I，II，III 10、有5个记录A,B,C,D,E存放在某磁盘的某磁道上，假定这个磁道划分为5块，每块存放一个记录，若磁盘旋转一周需要20ms，处理程序每读出一个记录后需要花费6ms进行处理，程序处理这些数据时磁盘照常旋转，按照（）顺序存放这5个记录可以使其按照A,B,C,D,E顺序处理这些记录的时间最少。 A、“A,B,C,E,D” B、“A,C,E,B,D” C、“A,D,E,C,B” D、“A,E,B,C,D” 11、以太网交换机按照自学算法建立转发表，它通过（）进行地址学习 A、ARP协议 B、帧中的源MAC地址和目的MAC地址 C、帧中的目的MAC地址 D、帧中的源MAC地址 12、以太网内某主机甲的IP地址为：211.71.136.23，子网掩码为：255.255.240.0，网关地址为：211.71.136.1，若主机甲向主机乙【IP地址为：211.71.130.25】发送一个IP分组，则（） A、该分组封装成帧后直接发送给乙，帧中目的MAC地址为网关MAC地址 B、该分组封装成帧后直接发送给乙，帧中目的MAC地址为主机乙的MAC 地址 C、该分组封装成帧后交由网关转发，帧中目的MAC地址为网关的MAC地址 D、该分组封装成帧后交由网关转发，帧中目的MAC地址为主机乙的MAC 地址 13、Internet中所有末端系统和路由器都必须实现（）协议以确定网络的连通。 A、IP B、UDP C、TCP D、OSPF 14、主机甲向主机乙发送一个（SYN=1，seq=1000）的TCP段，期望与主机乙

北航14秋《数据库原理及应用》在线作业二答案

北航《数据库原理及应用》在线作业二 单选题 一、单选题（共25 道试题，共100 分。） 1. 若用如下的SQL语句创建了一个表S ：CREATE TABLE S(S# CHAR(6) NOT NULL, SNAME CHAR(8) NOT NULL, SEX CHAR(2), AGE INTEGER) 今向S表插入如下行时，哪一行可以被插入 A. ('991001','李明芳',女，'23') B. ('990746','张为',NULL,NULL) C. (NULL,'陈道一'，'男',32) D. ('992345',NULL,'女',25) -----------------选择：B 2. 下列有关数据库的恢复的说法中不正确的是（） A. 应定期将数据库做成档案文件 B. 在进行事务处理过程时数据库更新的全部内容写入日志文件 C. 发生故障时用当时数据内容和档案文件更新前的映象，将文件恢复到最近的检查点文件状态。 D. 数据库恢复，还可用最新的档案文件和日志文件的更新映象，将文件恢复到最新的检查点文件状态。 -----------------选择：C 3. 在命令窗口执行SQL命令时，若命令要占用多行，续行符是______。 A. 冒号(:) B. 分号(;) C. 逗号(,) D. 连字符(-) -----------------选择：D 4. 事务的执行不被其它事务干扰，这个性质称为事务的（） A. 原子性 B. 隔离性 C. 持久性 D. 一致性 -----------------选择：B 5. 规范化理论是关系数据库进行逻辑设计的理论依据。根据这个理论，关系数据库中的关系必须满足其每一属性都是（） A. 互不相关的 B. 不可分解的 C. 长度可变的 D. 互相关联的 -----------------选择：B 6. SQL语言中，删除一个表的命令是（）。 A. CLEAR TABLE

北航操作系统补考试卷.参考答案.doc

《操作系统》试卷 一、名词解释题（每题5分，共25分） 1、原语 2、快表 3、设备无关性 4、临界资源 5、文件系统 二、判断题（每题1分，共5分） 1、临界区的执行不能被中断。（） 2、资源顺序分配法破坏了死锁发生的循环等待必要条件。（） 3、对磁盘进行磁头调度的目的是为了缩短寻道时间。（） 4、采用页式存储管理时，重定位的工作是由用户完成的。（） 5、与设备相关的中断处理过程由设备驱动程序完成。（） 三、简答题（每题5分，共20分） 1、进程的含义是什么？如何构造和描述进程？ 2、什么是死锁？产生死锁的必要条件是什么？ 3、什么是开中断？什么是关中断？ 4、分页存储管理中有哪几种常用的页面置换算法？ 四、银行家算法（10分） 在银行家算法中，若出现以下资源分配情况： 进程资源最大需求已分配资源 P0 7,5,3 0,1,0 P1 3,2,2 2,1,0 P2 9,0,2 3,0,2 P3 2,2,2 2,1,1 P4 4,3,3 0,0,2

系统剩余资源数量：（3,2,2）。 （1）该状态是否安全（给出详细的检查过程）？ （2）若系统剩余资源数量为（3,1,0），系统是否安全？若系统处于安全状态，请给出安全序列；若系统处于不安全状态，请说明原因。 五、设备管理（10分） 设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个程序同时进入就绪状态，进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图，并说明： （1）开始运行后，CPU有无空闲等待？若有，在哪段时间内等待？计算CPU的利用率。 （2）进程A运行时有无等待现象？若有，在什么时候发生等待现象？ （3）进程B运行时有无等待现象？若有，在什么时候发生等待现象？ 六、进程同步（15分） 桌子上有一只盘子，每次只能放入或者取出一个水果。现有许多苹果与橘子。一家4口人各行其职。爸爸专向盘子中放入苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P操作, V操作来实现4人之间的同步算法。 七、存储管理（15分） 在分页虚拟存储管理系统中，假定系统为某进程分配了四个主存块（将开始4页先装入主存），页的引用顺序为：7,1,2,0,3,0,4,2,3,0,3,2,7,0,1，若采用FIFO调度算法，LUR调度算法时，分别产生多少次缺页中断？一次淘汰的页分别是什么？

北航操作系统试卷参考答案

V操作系统试卷（2010年）参考答案 一、名词解释题（每题4分，共24分） 1、进程控制块 答案：进程控制块是一个与动态过程相联系的数据结构，记载了进程的外部特性（名字、状态等）以及与其他进程的联系（通信关系），还记录了进程所拥有的各种资源。进程控制块是进程存在的标志。 2、原语 答案：原语通常由若干条指令所组成，用来实现某个特定的操作。通过一段不可分割的或不可中断的程序实现其功能。 3、临界区 答案：必须互斥执行的程序段称为相对于临界资源的临界区。 4、虚拟存储器 答案：虚拟存储技术是在主存和辅存之间，增加部分软件及必要的硬件支持，使主、辅之间的信息交换、程序的重定位、地址转换都能自动进行，从而主、辅存形成一个有机的整体，这种存储器的概念成为虚拟存储器。 5、缓冲区 答案：为了解决外部设备和内存或外部设备和CPU之间的数据传送速度不匹配的问题，在系统中引入缓冲区来暂存数据。 6、文件目录 答案：目录是文件系统层次结构的一个非终结节点，一个目录通常包含有许多目录项，每个目录项可能是一个文件或目录。 二、判断题（每题1分，共6分） 1、一个进程可以涉及一个或若干个程序的执行；反之，同一个程序只可以对 应一个进程。（ ） 2、信号量是只允许由P/V操作进行访问和修改的数据结构。（ ） 3、并发是指多个任务在多个处理机上正在同时运行，在微观上看，这些任务 是在各自的物理处理机上分别运行。（ ） 4、进程的同步与互斥可以发生在一个进程之中。（ ） 5、中断方式的数据传送是在中断处理时由CPU控制完成的；DMA方式则不 经过CPU，而是在DMA控制器的控制下完成的。（ ） 6、动态重定位便于程序浮动，其实现时采用的硬件机构是重定位寄存器和加 法器。（ ） 三、简答题（每题4分，共20分） 1、实时系统和分时系统各有什么特点？有什么本质的区别？ 答案：

北航最优化方法大作业参考

1流量工程问题 1.1问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1， 其余元素为0。再令b m =(b m1 ,…,b mN )T，f m =(f m1 ,…,f mE )T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5 (5) 1×13 )T， 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x 12,x 13 ,…,x 75 ) 1×13 )。 图 1 网络拓扑和流量需求

1.27节点算例求解 1.2.1\ T） 1.2.2算例1（b1=[4;-4;0;0;0;0;0] 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.3算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 \ X2>=0利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.4算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T

北航操作系统答案作业4

作业4 单项选择题 第1题在下面解决死锁的方法中，属于死锁预防策略的是：（）。 A、银行家算法 B、资源有序分配法 C、死锁检测法 D、资源分配图化简法 答案：B 第2题原语一般由系统进程所调用，原语常驻内存，具有（）。 A、不可中断性 B、可中断性 C、系统调用的全部特性 答案：A 第3题对进程的管理和控制使用是（）。 A、指令 B、原语 C、信号量 D、信箱通信 答案：B 第4题中断的处理过程大致包括（）几个阶段。 A、关中断并保护现场，分析中断源并转相应处理，恢复现场开中断并返回 B、关中断，处理中断，开中断并返回 C、响应中断，中断处理并返回 答案：A 第5题如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。若要调整中断事件的响应次序，可以利用（）。 A、中断向量 B、中断嵌套 C、中断响应 D、中断屏蔽 答案：D 第6题中断矢量是指（）。 A、中断处理程序的入口地址 B、中断矢量表起始地址 C、中断处理程序入口地址在中断矢量表中的存放地址 D、中断断点的地址 答案：A

第7题中断发生后，应保留（）。 A、缓冲区指针 B、关键寄存器内容 C、被中断的程序 D、页表 答案：B 第8题多道程序环境下，操作系统分配资源以（）为基本单位。 A、程序 B、指令 C、进程 D、作业 答案：C 判断题 第9题所谓直接存取法，就是允许用户随意存取文件中的任何一个逻辑记录。 答案：正确 第10题某一进程被中断，转去执行中断处理程序；中断处理程序结束后，一定返回到被中断的程序。 答案：正确 第11题中断屏蔽是不允许发生中断的。 答案：错误 第12题处于运行状态的进程只能转换为就绪状态或阻塞状态。 答案：错误 填空题 第13题操作系统中，对信号量S的P原语操作定义中，使进程进入相应等待队列等待的条件是___。 答案：S＜0 第14题信号量的物理意义是当信号量值大于0时表示___；当信号量值小于0时，其绝对值表示___。 答案：可用资源的数目；因请求资源而被阻塞的进程的数目 第15题在分页式管理中，页面置换算法常用的是___和___。 答案：先进先出；最近最久未使用 第16题某页式存储管理中，逻辑地址用24位表示，其中页号占8个二进制位，则程序最多占___页。 答案：256