中科大软院算法导论最近点对算法_C++

中科大软件学院C+考试试卷

《面向对象编程技术》试卷 注：1）请将答案写在答题纸上，写在试卷上不算分。答题纸在试卷的最后页。 2）交卷时,试卷和答题纸一起交。 一、单选题 (每小题1.5分，共30分) 1. C++中，以下有关构造函数的叙述不正确的是 ______ 。 A. 构造函数名必须和类名一致 B. 构造函数在定义对象时自动执行 C. 构造函数无任何函数类型 D. 在一个类中构造函数有且仅有一个 2．以下叙述不正确的是 ______ 。 A. 在类的定义中，通常是成员变量描述对象的属性；用成员函数描述对象的行为 B. 类的一个成员只能具有一种访问控制属性 C. 构造函数和析构函数是特殊的成员函数，因此不允许重载 D. 通过对象只能访问类的公有成员 3. 以下关于虚函数的叙述不正确的是 ______ 。 A. 虚函数属于成员函数 B. 虚函数不允许说明成静态的 C. 凡是虚函数必须用virtual说明 D. 虚函数可以被继承 4. cout是I0流库预定义的______ 。 A．类 B. 对象 C. 包含文件 D. 常量 5．面向对象程序设计中的数据隐藏指的是______ 。 A．输入数据必须输入保密口令 B．数据经过加密处理 C. 对象内部数据结构上建有防火墙D．对象内部数据结构的不可访问性6．拷贝（复制）构造函数的作用是______ 。 A．进行数据类型的转换 B．用对象调用成员函数 C．用对象初始化对象D．用一般类型的数据初始化对象 7. 下列不是描述类的成员函数的是______ 。 A.构造函数 B.析构函数 C.友元函数 D.拷贝构造函数 8. 如果类A被说明成类B的友元，则______ 。 A. 类A的成员即类B的成员 B. 类B的成员即类A的成员 C. 类A的成员函数不得访问类B的成员 D. 类B不一定是类A的友元 9. 对于任何一个类，析构函数最多有______ 个。 A. 0 B. 1 C. 2 D. n 10. 下列特性中，C与C++共有的是______ 。 A.继承 B.封装 C.多态性 D.函数定义不能嵌套 11. 在公有继承的情况下，基类公有和保护成员在派生类中的访问权限______ 。 A. 受限制 B. 保持不变 C. 受保护 D. 不受保护 12. 通过______ 调用虚函数时，采用动态束定。 A. 对象指针 B. 对象名 C. 成员名限定 D. 派生类名 13. C++ 类体系中，不能被派生类继承的有______ 。 A. 成员转换函数 B. 构造函数 C. 虚函数 D. 静态成员函数 14. 假定 ab 为一个类，则执行 ab x；语句时将自动调用该类的______ 。 A. 有参构造函数 B. 无参构造函数 C. 拷贝构造函数 D. 赋值构造函数 15. 静态成员函数不能说明为______ 。 A. 整型函数 B. 浮点函数 C. 虚函数 D. 字符型函数 16. 在 C++ 中，数据封装要解决的问题是______ 。 A. 数据规范化排列 B. 数据高速转换 C. 避免数据丢失 D. 保证数据完整性

中科大软件学院算法复习概念综合题

一、概念题： （1）排序算法时间复杂度： 排序算法最好最坏平均 插入O(n)O(n2)O(n2) 归并O(nlogn)O(nlogn)O(nlogn) 快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度： 1、所有简单排序和堆排序都是0(1) 2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间 3、归并排序和基数排序所需辅助空间最多，为O(n) （2）渐近记号 1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n>= n0，都有0<=c1g(n)<=f(n)<=c2g(n)}。大Θ记号给出函数的渐进确界。 2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=cg(n)<=f(n)}。大Ω记号给出函数的渐进下界。 3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=f(n)<=cg(n)}。大O记号给出函数的渐进上界。 （3）二叉查找树： 执行基本操作的时间与树的高度成正比。搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表） （4）红黑树： 1、时间复杂度： 基本动态集合操作：O(log n)，n是树中元素的数目。 2、性质： 1)节点是红色或黑色。 2)根节点是黑色。 3)每个叶节点（NIL节点）是黑色的。 4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续 红结点） 5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。 3、相关概念，定理： 1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。红黑树的黑高度定义为其根节点的黑高度。 2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。(用2-3-4树理解) 3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点

中科大软院数据库考试题

一、给定关系 R(A,B) 和 S(B,C) ，将下面的关系代数表达式转换为相应的SQL语句： π (attribute-list) [ (condition) [ R ? S ] ] 二、Megatron 747 磁盘具有以下特性： 1）有8个盘面和8192个柱面 2）盘面直径为英寸，内圈直径为英寸 3）每磁道平均有256个扇区，每个扇区512字节 4）每个磁道10％被用于间隙 5）磁盘转速为 7200 RPM 6）磁头启动到停止需要1ms，每移动500个柱面另加1ms 回答下列有关Megatron 747的问题（要求写出式子并且计算出结果，精确到小数点后两位）： 1）磁盘容量是多少GB 2）如果一个块是8KB，那么一个块的传输时间是多少ms 3）平均寻道时间是多少ms 4）平均旋转等待时间是多少ms 三、下面是一个数据库系统开始运行后的undo/redo日志记录，该数据库系统支持simple checkpoint （1）（2）（3） 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 设日志修改记录的格式为 ，（1）、（2）、（3）为三种故障情形下磁盘日志内容，请分别给出这三种情况下数据库系统的恢复过程以及数据元素A, B, C, D, E, F和G 在执行了恢复过程后的值。

(完整版)中科大软院常见复试题目.doc

1.ipv4 的替代方案； 2.单链表原地逆向转置； 3.折半查找算法 4.简述操作系统中系统调用过程； 5.在数据库中什么是关系，它和普通二维表啥区别； 6.什么是原子操作； 7.路由协议有哪些； 8.进程的三种状态，以及之间转换的过程； 9.快速排序的基本过程； 10.什么叫视图？视图在数据库的第几层； 11.二叉树的搜索； 12.什么叫冲突？解决冲突的办法都有哪些； 13.java 与 C++区别； 14.深度、广度搜索的过程； 15.迪杰斯克拉算法的过程； 16.关系模式和关系； 17.数据链路停发协议，就是流量控制； 18.虚拟存储器及相关算法；段存储器； 19.进程线程树图； 20.传输等待协议； 21.堆栈排序及其与快速排序的不同； 22.386 的保护模式是什么； 23.页表； 24.ER图； 25.关系范式 26.链表查询某个元素，平均时间复杂度是多少； 27.路由协议有哪些； 28.网络服务质量包括哪些方面； 29.并发控制是为了保证事务的？； 30.什么是 DMA； 31.两个时钟不同步的设备怎么通信； 32.操作系统的调度算法有哪些； 33.单链表的原地逆置算法 34.数据库的两级模式以及它们的关系和作用（貌似是这样） 35.操作系统的进程调度算法有哪些，并介绍其中两种 36.计算机的一条指令有几个机器周期，为什么 37.原子操作， pv 操作的要点和注意事项 38.内核、芯片（记不清了） 39.DMA控制器的组成和工作原理 40.简述最短路径的迪杰斯特拉算法 41.什么是 P 操作与 V 操作。 42.一个深度为 N的满二叉树有多少个结点。 43.实现一个队列的方法 44.折半查找调节与时间复杂度

中科大考博辅导班：2019中科大软件学院考博难度解析及经验分享

中科大考博辅导班：2019中科大软件学院考博难度解析及经验分享中国科学院大学2019年博士研究生招生统一实行网上报名。报考者须符合《中国科学院大学2019年招收攻读博士学位研究生简章》规定的报考条件。考生在报考前请联系所报考的研究所(指招收博士生的中科院各研究院、所、中心、园、台、站)或校部相关院系，了解具体的报考规定。 下面是启道考博辅导班整理的关于中国科学技术大学软件学院考博相关内容。 一、院系简介 中国科学技术大学是中国科学院直属的唯一院校，是一所以前沿科学和高新技术为主、科技人文与科技管理兼备的综合性全国名校，为国家教育重点建设的9所世界知名高水平研究型大学之一，在国际上享有较高的声誉。学校力争在2018年建校60周年前后，把学校建设成为“规模适度、质量优异、结构合理、特色鲜明”的世界知名的高水平研究型大学。目前，校本部共有10个学院、25个系和少年班，43个本科专业；一级学科博士学位授权点17个，国家重点学科19个，二级学科博士学位授权点89个，二级学科硕士学位授权点105个，有工商管理（MBA）、公共管理（MPA）和工程硕士3个专业硕士学位授权点；17个博士后流动站，45个博士后流动站专业，具备培养学士、硕士、博士的完整教育体系。其严谨务实的学风、创新探索的精神、高水平级的成果、国际化办学的追求，都使得这所年轻的研究型大学受到国际社会越来越强的关注 二、招生信息 中国科学技术大学软件学院博士招生专业有1个： 085271电子与信息 研究方向：不区分研究方向 三、报考条件 （1）中华人民共和国公民；拥护中国共产党的领导，愿意为祖国社会主义现代化建设服务；品德良好，遵纪守法，学风端正，无任何考试作弊、学术剽窃及其它违法违纪行为； （2）身体健康状况符合我校规定的体检要求，心理正常； （3）申请者原则上应来自国内重点院校或所在高校学习专业为重点学科； （4）专业基础好、科研能力强，在某一领域或某些方面有特殊学术专长及突出学术成果； （5）对学术研究有浓厚的兴趣，有较强的创新意识、创新能力和专业能力；

中科大软院金老师的数据库实验一

第一次实验报告 1、实验任务 根据下面的需求描述，使用Sybase Power Designer设计相应的数据库概念模型，并转换成Oracle或MS SQL Server上的物理数据库结构： 某银行准备开发一个银行业务管理系统，通过调查，得到以下的主要需求： 银行有多个支行。各个支行位于某个城市，每个支行有唯一的名字。银行要监控每个支行的资产。银行的客户通过其身份证号来标识。银行存储每个客户的姓名及其居住的街道和城市。客户可以有帐户，并且可以贷款。客户可能和某个银行员工发生联系，该员工是此客户的贷款负责人或银行帐户负责人。银行员工也通过身份证号来标识。员工分为部门经理和普通员工，每个部门经理都负责领导其所在部门的员工，并且每个员工只允许在一个部门内工作。每个支行的管理机构存储每个员工的姓名、电话号码、家庭地址及其经理的身份证号。银行还需知道每个员工开始工作的日期，由此日期可以推知员工的雇佣期。银行提供两类帐户——储蓄帐户和支票帐户。帐户可以由2个或2个以上客户所共有，一个客户也可有两个或两个以上的帐户。每个帐户被赋以唯一的帐户号。银行记录每个帐户的余额、开户的支行以及每个帐户所有者访问该帐户的最近日期。另外，每个储蓄帐户有其利率，且每个支票帐户有其透支额。每笔贷款由某个分支机构发放，能被一个或多个客户所共有。每笔贷款用唯一的贷款号标识。银行需要知道每笔贷款所贷金额以及逐次支付的情况（银行将贷款分几次付给客户）。虽然贷款号不能唯一标识银行所有为贷款所付的款项，但可以唯一标识为某贷款所付的款项。对每次的付款需要记录日期和金额。

2、实验过程 （1）确定实体和属性 由上面的需求描述我们可以很容易得出以下几个实体: ●员工（身份证号，姓名，电话号码，家庭地址，开始工作日 期） ●存储账户（账户号，余额，利率） ●支票账户（账户号，余额，透支额） ●客户（身份证号，姓名，街道，城市） ●支行（支行名称，城市，资产） ●贷款（贷款号，总额） ●支付（日期，金额） 图1 PS: 1、在此ER图中我没有设计账户类，然后派生出存储账户和支票账户，因为在客户的需求中，只有两种账户类型，除了支票账户类型就是存储账户类型，没有所谓的“一般的账户”，所以就不

中科大软件学院算法实验报告

算法实验报告 快速排序 1. 问题描述： 实现对数组的普通快速排序与随机快速排序 (1)实现上述两个算法 (2)统计算法的运行时间 (3)分析性能差异，作出总结 2. 算法原理： 2.1快速排序 快速排序是对冒泡排序的一种改进。它的基本思想是：选取一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准元素小，另外一部分的所有数据都要比基准元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 设要排序的数组是A[0]……A[N-1]，首先选取一个数据（普通快速排序选择的是最后一个元素, 随机快速排序是随机选择一个元素）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。 一趟快速排序的算法是： 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]； 4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]； 5）重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这

一过程一定正好是i+或j-完成的时候，此时令循环结束）。 2.2随机快速排序 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个或者最后一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。 3. 实验数据 本实验采用对80,000个随机数据进行十次排序，并取出平均值。分别用普通快速排序和随机快速排序对数据排序。用毫秒作为运行计数单位，观测两种算法所用的时间的不同。 4. 实验截图 如下图所示的时间，普通快速排序所用的平均时间为181毫秒，而随机化版本的快速排序所用时间仅仅为119毫秒。 5. 结果分析 5.1 时间分析 从实验截图得到的结果来看，随机化版本的快速排序所用时间比普通快速排序所用的平均时间少。 快速排序的平均时间复杂度为O(nlogn)，最坏时间时间可达到O(n^2)，最坏情况是当要排序的数列基本有序的时候。根据快速排序的工作原理我们知道，

中科大软件学院第一学期总结

考研究生调剂到了中科大软件学院，现在看来是一件让我觉得十分幸运的事情。中科大的学习气氛非常的浓，课程的内容也十分有新意，虽然有新意，但是又都是很基础的内容，让我收获很大，很多课程给我带来了很大的启发。直到过年时候，才腾出时间来写上一篇总结，记录我这一学期的生活和学习。我一直是一个地地道道的北方人，生在北京，长在北京，却跑到哈尔滨读了四年书。哈工大学习负担不轻，假期也很短，一直没有时间到处玩玩，再加上自己比较懒，大学期间也就去了趟长春。这次考到了中科大苏州研究院，心中对于南方的风土人情很是期待，内心中也不乏有些忐忑。 开学前，我直接跑到了南京玩了一周，玩的十分痛快，题外话暂且不提，然后从南京坐高铁到了苏州。中科大苏州研究院地处独墅湖高教园区，正巧高铁有工业园区一站，我就在工业园区站下了车。人生地不熟找不到合适的公交，直接拦下一辆出租车奔着学校这边就来了。苏州的出租车司机素质感觉比较高，礼让行人等做的都很不错，开车也很规矩。出租车司机还很健谈，就像北京的老师傅一样，听说我是来上学的，给我说了很多苏州的情况。我是提前一天前来报道的，物业态度很不好，不过好在顺利办理了入住手续，搬进了宿舍。宿舍两人寝，上床下桌，屋子不小，但是什么都没有，不过比较干净，我开学前几天都在置备东西。苏州的空气很好，略显湿润但却不潮湿，气温跟北京差不多，略高3℃左右，我很适应。住宿的地方离学校不近，走路30分钟左右，不过每天都有班车。中科大开的课程都很有意思，很多课程我遗憾的没有抢到，不过幸好没有全抢到我喜欢的课程，不然估计得累到爆。曾经我很不理解哈佛的学生为什么一学期只有8门课程还累得要死，知道我来到了号称不要命的来科大的中科大，才彻底理解了原因。中科大的课很有意思，难度也颇高，想要学好，就要付出150%的努力，而且基本上我学的所有的课都需要这种程度的努力。 下面说说我都上了些什么课，都有什么好玩的内容。英语免修过关考试侥幸水过，让我能够选一些其他我感兴趣的课程。一开始我选的是实用算法设计一课，第一节课时，老师负责任的指出此课程针对于没有算法基础的同学，恰巧此时算法分析与设计一课有一个空位，我就改选了算法分析与设计。实用算法设计一课使用的是《程序员实用算法》一书，说实在的，里面的例子都是经过精心编写的算法，非常优美，很多细节处理的十分精妙，可惜我还是更喜欢算法分析与设计一课。算法分析与设计使用的教材是经典的《算法导论》一书，整个课程跳过了一些简单的章节，但是覆盖到了算法导论中的大部分章节(不含第七部分和第八部分)。这课说实在的，超赞啊!我本科学的算法课用的是《算法概论》一书，比较偏重于算法设计，《算法导论》则是设计与分析并重。自己看《算法导论》的时候真心看不进去，这门课程一口气跟下来觉得并不吃力，而且有一种融会贯通的感觉。发现很多的时候，一个算法的时间复杂度暗示了其设计思想。上这门课的感觉还是很多问题都似曾相识，比如说经典的八皇后问题，这些问题以前在遇到的时候都是采用一些固定的策略来进行处理，并不知道为什么要采用这样的策略。这门课程让我认识到了三类基本问题：组合计数、组合优化、组合设计，每一类问题都有很多数学工具来对其进行分析和解决。顺便说一下，书中对于如何构造GF(pk)讲解的实在是让人有点稀里糊涂的，恰巧我另一门课程密码学及其应用中讲到了这些内容，让我在这点上没有稀里糊涂的跳过去。随机过程是一门神奇的课，说实在的，我一直都挺怕概率论的，我觉得概率论十分的违反直觉，很多时候得出的答案都令我十分费解，也不能够肯定是否正确。这有助于我们抛弃一些不必要的tricks，在关键的时候进行优化。(这也是CSAPP所需要达到的一个目标之一) 说完这两门课程，不妨看看上面提到过的密码学及其应用一课。在上这门课程以前，我一直认为密码学领域主要是一些数学问题，程序员需要关注的内容很少;上了这门课程后，我发现，所有的程序员都应该学习一下密码学的基本知识，走出密码学的误区。在这门课程上，我了解了，即便是有了安全的加密方式，如果使用不当的话，仍然可能会泄密或收到被攻击者伪装成正常消息而受到欺骗，非对称加密并不比对称加密更安全，反而，非对称加密方式由于加密速度较慢，使用范围会受到限制。有些不

北京航空航天大学 《算法导论》期末参考题(有一部分考到了)

一、选择题 1.算法分析中，记号O表示（B），记号?标售（A）,记号Θ表示（D） A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界 2.以下关于渐进记号的性质是正确的有：（A） A f(n) =Θ(g(n)),g(n) =Θ(h(n))?f(n) =Θ(h(n)) B f(n) =O(g(n)),g(n) =O(h(n)) ?h(n) =O(f(n)) C O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D f(n) = O(g(n)) ?g(n) = O(f(n)) 3. 记号O的定义正确的是（A）。 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }； B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤ f(n) }； C O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 4. 记号?的定义正确的是（B）。 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }； B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；

C (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 5. T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是( C ) A T（n）= T（n – 1）+1，T（1）=1 B T（n）= 2n2 C T（n）= T（n/2）+1，T（1）=1 D T（n）= 3nlog2n 6. 动态规划算法的基本要素为（C） A 最优子结构性质与贪心选择性质 B 重叠子问题性质与贪心选择性质 C 最优子结构性质与重叠子问题性质 D 预排序与递归调用 7.下列不是动态规划算法基本步骤的是（ A ）。 A 找出最优解的性质 B 构造最优解 C 算出最优解 D 定义最优解 8.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A 最优子结构性质与贪心选择性质 B 重叠子问题性质与贪心选择性质 C 最优子结构性质与重叠子问题性质

中科大算法导论实验报告

实验一常见排序算法的实现与性能比较 一、实验环境 操作系统：Windows XP操作系统 编程语言：C语言 开发工具：Microsoft Visual C++ 6.0 二、问题描述 实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法 三、实验要求 A．在随机产生的空间大小分别为 N = 10， 1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。 B．结果输出: 1） N=10时，排序结果。 2） N=1000，10000，100000时，对同一个样本实例，不同排序完 成所需的时间。 3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。 四、各种排序算法的原理及算法语言描述 （1）合并排序算法 1）合并排序的原理： 采用分治法。分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括n/2 个元素。治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。合并: 合并两个排好序的子序列,生成排序结果。 2）合并排序算法语言描述： void Merge(float A[],int p,int q,int r){ int n1,n2,i,j,k; float L[10],R[10]; n1=q-p+1; n2=r-q; for(i=1;i<=n1;i++){ L[i]=A[p+i-1]; } for(j=1;j<=n2;j++){ R[j]=A[q+j]; } L[n1+1]=MAX; R[n2+1]=MAX; i=1; j=1;

中科大软院嵌入式期末总结

复习提纲：（C语言翻译汇编） 一、概述 1. 嵌入式系统是“用于控制、监视或者辅助操作机器和设备的装置 国内普遍认同的嵌入式系统定义为： 以应用为中心、以计算机技术为基础、软硬件可裁剪、适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。 2.嵌入式系统的几个重要特征（简述5特征） (1) 嵌入式系统工业是不可垄断的高度分散的工业 从某种意义上来说,通用计算机行业的技术是垄断的。 嵌入式系统则不同,它是一个分散的工业,充满了竞争、机遇与创新,没有哪一个系列的处理器和操作系统能够垄断全部市场。 （2）操作系统内核小 由于嵌入式系统一般是应用于小型电子装置的，系统资源相对有限，所以内核较之传统的操作系统要小得多。 比如ENEA公司的OSE分布式系统，内核只有5K，而Windows的内核则要大得多。 （3）专用性强 嵌入式系统的个性化很强，其中的软件系统和硬件的结合非常紧密，一般要针对硬件进行系统的移植。 即使在同一品牌、同一系列的产品中也需要根据系统硬件的变化和增减不断进行修改。 同时针对不同的任务，往往需要对系统进行较大更改，程序的编译下载要和系统相结合，这种修改和通用软件的“升级”是完全不同的概念。 （4）系统精简 嵌入式系统一般没有系统软件和应用软件的明显区分，不要求其功能设计及实现上过于复杂，这样一方面利于控制系统成本，同时也利于实现系统安全。（5）高实时性OS 这是嵌入式软件的基本要求，而且软件要求固态存储，以提高速度。软件代码要求高质量和高可靠性、实时性。 6）嵌入式软件开发走向标准化 嵌入式系统的应用程序可以没有操作系统直接在芯片上运行。 为了合理地调度多任务、利用系统资源、系统函数以及和专家库函数接口，用户必须自行选配RTOS（Real－Time Operating System）开发平台，这样才能保证程序执行的实时性、可靠性，并减少开发时间，保障软件质量。 （7）嵌入式系统开发需要开发工具和环境 由于其本身不具备自主开发能力，即使设计完成以后，用户通常也是不能对其中的程序功能进行修改，必须有一套开发工具和环境才能进行开发。 这些工具和环境一般是基于通用计算机上的软硬件设备以及各种逻辑分析仪、混合信号示波器等。 开发时往往有主机和目标机的概念，主机用于程序的开发，目标机作为最后的执行机，开发时需要交替结合进行。

中科大软院算法导论区间树实验报告

区间树实验报告 1.区间树的实验源码见另外一个文件 2.区间树实验分析 2.1 需求分析 基础数据结构选择红黑树，每个结点x 包含一个区间域int[x]，x 的关键字为区间的低端点low[int[x]]，对树；进行中序遍历就可按低端点的次序列出个区间，结点还包含一个max[x]，即以x 为根的子树中所有区间的端点的最大值。如： 实验要求：将红黑树扩展为区间树 (1)区间的端点为正整数，随机生成； (2)内部节点数为n：2^4，2^6,2^8,2^10,2^12； (3)测试插入，删除，查找的时间并绘出曲线，运行次数为10 次； 2.2 程序设计 区间树的操作基本和红黑树的相同，在其基础上增加了一个新方法： INTERVAL_SEARCH(T,i）；它用来找出树中覆盖区间i 的那个结点。如果树中不存在，则返回nil[T]指针。代码如下： ITNode* IntervalTree::Interval_Search(Interval i){ ITNode* x=root; while(x!=Nil && !x->Overlap(i)){ // x != nil and i doesn't overlap int[x] if (x->left!=Nil && x->left->max>=i.low) x=x->left; else x=x->right; } return x; } 区间树的插入、删除除了有可能改变红黑树性质，还有可能改变结点的max 值。前者向红黑树那样处理就可以了，又 max[x] = max(high[int[x]], max[left[x]], max[right[x]]) 为解决后者，增加一方法Nodemax（），让它来维护结点的max 值。Nodemax()如下：void ITNode::NodeMax(ITNode* xl, ITNode* xr){ Type tp=this->interval->high;

中科大软院数据库考试题

一、给定关系R(A,B) 和S(B,C) ，将下面的关系代数表达式转换为相应的SQL语句： π (attribute-list) [ (condition) [ R ? S ] ] 二、Megatron 747 磁盘具有以下特性： 1）有8个盘面和8192个柱面 2）盘面直径为3.5英寸，内圈直径为1.5英寸 3）每磁道平均有256个扇区，每个扇区512字节 4）每个磁道10％被用于间隙 5）磁盘转速为7200 RPM 6）磁头启动到停止需要1ms，每移动500个柱面另加1ms 回答下列有关Megatron 747的问题（要求写出式子并且计算出结果，精确到小数点后两位）： 1）磁盘容量是多少GB？ 2）如果一个块是8KB，那么一个块的传输时间是多少ms？ 3）平均寻道时间是多少ms？ 4）平均旋转等待时间是多少ms？ 三、下面是一个数据库系统开始运行后的undo/redo日志记录，该数据库系统支持simple checkpoint 设日志修改记录的格式为，（1）、（2）、（3）为三种故障情形下磁盘日志内容，请分别给出这三种情况下数据库系统的恢复过程以及数据元素A, B, C, D, E, F和G在执行了恢复过程后的值。

四、查询处理器在回答涉及R(A, B)和S(B, C)的查询“Select * From R, S Where R.B=S.B and R.B=10”时，生成了下面的逻辑查询计划：() ()S R B S B R 10.10.==σσ，已知有关参数为： ● R 和S 的元组都是定长的，在磁盘块中连续存放 ● T(R) = 60000，V(R, B) = 12，B(R) = 6000，T(S) =30000， V(S, B) = 5，B(S) = 1000 我们假设： 1）此查询计划中的连接实现时采用散列连接算法（非“混合散列连接”） 2）中间结果不写回磁盘 3）散列的桶存储在磁盘上 4）最终结果存放在内存中 5）有足够的内存可以执行散列连接算法 请估计此查询计划的I/O 代价。 五、我们想将关系R 按某个字段排序。已知R 的下列信息： ? R 包含 100000 个元组，即 T(R) = 100000. ? 一个磁盘块大小为 4000 bytes. ? R 的元组大小为 400 bytes ，即S(R) ＝ 400. ? 关系R 在磁盘上是连续（contiguous ）存放的，并且每个磁盘块中仅存放R 的记录 ? 排序字段的大小为 32 bytes. ? 记录指针的大小为 8 bytes. 回答下面的问题： （1） 如果使用两阶段归并排序，要求的最小内存是多少 （用块数表示）？ （2） 使用两阶段归并排序需要多少次磁盘I/O ？（包括最后将排序文件写回磁盘的代价） （3） 考虑下面改进的归并排序算法。原来的两阶段归并排序的第一阶段是将排序后的整个元组写到 chunk 中，现在我们仅将排序后的 写出。第一阶段，我们在内存中将记录按 排序，当记录填满内存时将其写到chunk 中。第二阶段，读入各个chunk 中的 并在内存中归并。通过记录指针(recordPointer)我们可以读取记录的其它部分(从R 的存储块中)，并将排好序的记录写回磁盘。这一改进的排序算法要求的最小内存是多少（用块数表示）? 排序需要多少次磁盘I/O? 在其他参数不变的情况下，当R 的元组多大时这个改进算法的I/O 代价要优于原来的归并排序算法？ ?

中科大软院软测期末复习提纲知识点

一.软件质莹 1?软件二程序（敷据）?文档+服务 软件产品组成部分：程用代码?帮助文件、用戶手册.样本和示例、标签■产品支持信息、图表和标志、错误信息.广 倂与宜传材料.软件的安装、软件说明文件、测试锚谊提示信息. 2 ?软件开发过程凋求分析（可行性报乩 项目初步开发汁划.需求规格说明?用户手册概要?测试讣划）；设汁複耍：建立系统 总体结构.划分功能模块：定义备功能模块接口：数据库设计：播定组袋测试计划.详细:设汁备模块八体实现以法:确定模块间 的详细接口 ：折定模块测试方案）［设计说明忱测试计划〕编码（編祝，进行模块调试和测试，编写用戶手册）［调试报俗，用户手 册］测试.錐护（纠错、适应.增强、预防）。 3. 软件测试与软件开发过程的关系： 1）项目规划阶段：员贵从单元测试到系统测试的整个测试阶段的监控。2）需求分析阶段：确定测试需求分析、系统测试il ?划 的制定.评审后成为管理项目。3）详细设计和概耍设il ?阶段：确保集成测试计划和单元测试汁划完成。1）綁码阶段：由开发 人员进行自己负贵部分的测试代码。在项目较人时?由专人进行編码阶段的测试任务。引测试阶段（单元、集成、系统測 试）：依据测试代码进行测试.井捉交相应的测试状态报倂和测试结束报乩 4. 软件虜量的定义："徹件产品满足规定的和隐含需求的能力冇关的特件 质量模型包括质fit 要素、准則.度酣三层次: 1） McCall^*模型软件质童要素（11个分为3类） 1. 产品修正，吋维护性、町测试性.灵活性 2. 产品转移：互联性■可移植性.复用性 3. 产品运行，正确性?叮使用性、完整性.叮绥性.效率 2） 质量要素评价准則1〉对审査性2）准确性3〉通信通用性4）完全性5）简明 性6） 一致性7）数据通用性S ）客钳性9>执行效率10）对扩充性11〉通用性 15） 作性16）安全性17）子文档化18）简单性19）软件系统独立性20） nf 追踪性21）易培训性3）软件质童的度量:1）确定软件质需求2）确定?ft 3）分析度就结果1）确认质fit 度it 软件质量模型:包播SQRC （软件质fit 需求评价准則）、SQDC （软件质壇设计评价准则）、SQMC （软件质试度猷评价准则几对应干McCall 质扯模型的质：K 要素、准则、度扯。 1） 8个要素：止确性.町容性、效率、安全性、可用性.可维 护性.适应性.连接性2）23个评价准鹏 McCall-样 3） 6个质量特性（左图）4）贞量特性使用：定文软件质母盂 求、 评价软件产品。软件质址观点（用户.开发者.管理者〉 5）质最评价?目的：1?确定产品足否通过峻收2与其他类似 产品相比较选择3.评估产品正面和奂面越啊4.确定何时优化 步探：1?质虽要求定义：据软件需求定义软件质址特性和可能 的子特性.将用户的质扯要求转化为软件开发不同阶段的质址要求. 并及时分解为软件产品组成部分的质fit 要求。2.评价准备： <1）选择质敞度fit （2）定义等级：（3）定义评估准则：3.评价过程：（1）测敞：把选定的度址应用到秋件产品上<2）评级 <3）评估。 7-软件质童管理： 1） IS09000： 2000：本标准浪述了质蛍沽理体系的基础。1质址管理体系的理论说明2质址管理体系要求与产品要求3质fit 骨理体系方法\过程方法5质fit 方针和质敬目标6恿岛管理者?在质飛管理体系中的作用7文件S 质就管理体系评价9 持续改进10统计技术的作用11质蛾骨理体系与其他骨理体系的关注点12质1ft 骨理体系与优秀枳式之闻的关系 2） 3（能力成熟度模型）： 二.软件测试 1?软件缺陷： 1）定义：软件岀惜机理叮描述为:软件错気软件缺陷?软件故障?软件失效。 1 依从" 安金H 衣曲怜 it 迢皈tl ?am 12）硕件独立性13）检测ft 14）枳块化 KiMIttVCA^aiSII McCI 诚悄度IK 檢中*:

中科大软院算法导论-第五次实验报告-最长公共子序列实验报告

第五次实验报告 ——最长公共子序列的生成算法 1.1算法应用背景 最长公共子序列是一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。 最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。 1.2算法原理 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 例：∑= {x, y, z} ，A = x y z y x z x z x x x 是长度为3 的子序列 x z y z x 是长度为5 的子序列 例：A = x y z y x z x z，B = x z y x x y z x x x x是长度为3 的公共子序列 x z y z 是长度为4 的公共子序列 x z y x x z 是长度为6 的最长公共子序列 1.3算法描述 记L n,m为序列A n和B m的最长公共子序列长度，则L i,j为序列A i和Bj的最长公共子序列的长度。根据最长公共子序列的性质，则得到：

阶段的划分和最长公共子序列长度的获取 第一阶段：计算A1和Bj的最长公共子序列的长度L1,j ,j=1,2,…m 第二阶段：计算A2和B j的最长公共子序列的长度L2,j, j=1,2,…m 第n 阶段：计算A n和B j的最长公共子序列的长度L n,j, j=1,2,…m 第n 阶段的L m,n便是序列A n和B m的最长公共子序列的长度 为了得到A n和B m最长公共子序列，设置一个二维的状态字数组s i，j，在上述每一个阶段计算L n,j过程中，根据公共子序列的性质则有按照如下方法把搜索状态登记于状态字s i，j中：s i，j =1 a i=b j s i，j =2 a i≠b j L i-1,j>= L i,j-1 s i，j =3 a i≠b j L i-1,j< L i,j-1 设L n,m=k,S k=c1c2……c k是序列A n和B m的长度为k的最长公共子序列。最长公共子序列的搜索过程为状态字s n，m开始。搜索过程如下： S m,n =1 a n=b m c k=a n下一个搜索方向是S n-1,m-1 S m,n =2 a i≠b j L i-1,j>= L i,j-1下一个搜索方向是S n-1,m S m,n =3 a i≠b j L i-1,j< L i,j-1 下一个搜索方向是S n,m-1 递推关系： 若s i，j =1 则c k=a i，i=i-1，j=j-1，k=k-1 s i，j =2 a i≠b j 则i=i-1 s i，j =3 a i≠b j 则j=j-1 从i=n，j=m开始搜索，直到i=0或j=0结束，即可得到A n和B m的最长公共子序列。1.4程序实现及程序截图 1.4.1程序源码 #include #include #define MAXLEN 100 void LCSLength(char *x, char *y, char *z,int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i,j,k,len; for(i = 0; i <= m; i++) c[i][0] = 0; for(j = 1; j <= n; j++)

中科大软院软测期末复习提纲知识点

一、软件质量 1.软件= 程序(数据) + 文档+ 服务 软件产品组成部分：程序代码、帮助文件、用户手册、样本和示例、标签、产品支持信息、图表和标志、错误信息、广告与宣传材料、软件的安装、软件说明文件、测试错误提示信息。 2.软件开发过程:需求分析(可行性报告，项目初步开发计划，需求规格说明，用户手册概要，测试计划);设计(概要：建立系统总体结构，划分功能模块；定义各功能模块接口；数据库设计；指定组装测试计划.详细:设计各模块具体实现算法;确定模块间的详细接口;指定模块测试方案)[设计说明书,测试计划]编码(编程,进行模块调试和测试,编写用户手册)[调试报告,用户手册]测试、维护(纠错、适应、增强、预防)。 3.软件测试与软件开发过程的关系： 1）项目规划阶段：负责从单元测试到系统测试的整个测试阶段的监控。2）需求分析阶段：确定测试需求分析、系统测试计划的制定，评审后成为管理项目。3）详细设计和概要设计阶段：确保集成测试计划和单元测试计划完成。4）编码阶段：由开发人员进行自己负责部分的测试代码。在项目较大时，由专人进行编码阶段的测试任务。5）测试阶段（单元、集成、系统测试）：依据测试代码进行测试，并提交相应的测试状态报告和测试结束报告。 4.软件质量的定义:与软件产品满足规定的和隐含需求的能力有关的特性 5.McCall质量模型包括质量要素、准则、度量三层次: 1)McCall质量模型软件质量要素（11个分为3类） 1.产品修正：可维护性、可测试性、灵活性 2.产品转移：互联性、可移植性、复用性 3.产品运行：正确性、可使用性、完整性、可靠性、效率 2) 质量要素评价准则1）可审查性2）准确性3）通信通用性4)完全性5）简明 性6）一致性7）数据通用性8）容错性9）执行效率10）可扩充性11）通用性12）硬件独立性13）检测性14）模块化15）可操作性16）安全性17）子文档化18）简单性19）软件系统独立性20）可追踪性21）易培训性3)软件质量的度量: 1）确定软件质量需求2）确定度量3）分析度量结果4）确认质量度量 6.ISO-9126软件质量模型：包括SQRC(软件质量需求评价准则)、SQDC(软件质量设计评价准则)、SQMC(软件质量度量评价准则)，对应于McCall质量模型的质量要素、准则、度量。 1)8个要素：正确性、可容性、效率、安全性、可用性、可维护 性、适应性、连接性2）23个评价准则：和McCall一样 3）6个质量特性(左图)4)质量特性使用：定义软件质量需求、 评价软件产品。软件质量观点（用户、开发者、管理者）5）质 量评价。目的：1.确定产品是否通过验收2.与其他类似产品相 比较选择3.评估产品正面和负面影响4.确定何时优化。步骤： 1.质量要求定义：据软件需求定义软件质量特性和可能的子特性，将用户的质量要求转化为软件开发不同阶段的质量要求，并及时分解为软件产品组成部分的质量要求。 2.评价准备：（1）选择质量度量；（2）定义等级；（3）定义评估准则； 3.评价过程：（1）测量：把选定的度量应用到软件产品上（2）评级（3）评估。 7.软件质量管理: 1）ISO9000：2000：本标准表述了质量管理体系的基础。1 质量管理体系的理论说明2 质量管理体系要求与产品要求3 质量管理体系方法4 过程方法5 质量方针和质量目标6 最高管理者在质量管理体系中的作用7 文件8 质量管理体系评价9 持续改进10 统计技术的作用11 质量管理体系与其他管理体系的关注点12 质量管理体系与优秀模式之间的关系 2）CMM(能力成熟度模型)： 二、软件测试 1.软件缺陷： 1）定义：软件出错机理可描述为:软件错误，软件缺陷，软件故障，软件失效。 1. 软件错误(error) ：是指在软件生存期内的不希望或不可接受的人为错误，其结果是导致软件缺陷的产生。 2. 软件缺陷(bug) ：是存在于软件（文档、数据、程序）之中的那些不希望或不可接受的偏差。其结果是软件运行于某一特定条件时出现软件故障，