当前位置:文档之家› 中科大 算法导论作业答案3

中科大 算法导论作业答案3

中科大 算法导论作业答案3
中科大 算法导论作业答案3

第8次作业答案16.1-1

16.1-2

54

33

16.3-4

16.2-5

参考答案:

16.4-1

证明中要三点:1.有穷非空集合2.遗传性3.交换性

第10次作业参考答案16.5-1

题目表格:

解法1:使用引理16.12性质(2),按wi单调递减顺序逐次将任务添加至Nt(A),每次添加一个元素后,进行计算,{计算方法:Nt(A)中有i个任务时计算N0 (A),…,Ni(A),其中如果存在Nj (A)>j,则表示最近添加的元素是需要放弃的,从集合中删除};最后将未放弃的元素按di递增排序,放弃的任务放在所有未放弃任务后面,放弃任务集合内部排序可随意。

解法2:设所有n个时间空位都是空的。然后按罚款的单调递减顺序对各个子任务逐个作贪心选择。在考虑任务j时,如果有一个恰处于或前于dj的时间空位仍空着,则将任务j赋与最近的这样的空位,并填入; 如果不存在这样的空位,表示放弃。

答案(a1,a2是放弃的):

or 划线部分按上表di递增的顺序排即可,答案不唯一

16.5-2(直接给个计算例子说的不清不楚的请扣分)

题目:

本题的意思是在O(|A|)时间内确定性质2(性质2:对t=0,1,2,…,n,有Nt(A)<=t, Nt(A)表示A中期限不超过t的任务个数)是否成立。

解答示例:

思想:建立数组a[n],a[i]表示截至时间为i的任务个数,对0=i,则说明A不独立,否则A独立。

伪代码:

int temp=0;

for(i=0;i

{

temp+=a[i];//temp就是a[0]+a[1]+…+a[i]

if(temp>i)//Ni(A)>i

A不独立;

}

17.1-1(这题有歧义,不扣分)

a) 如果Stack Operations包括Push Pop MultiPush,答案是可以保持,解释和书上的Push Pop MultiPop差不多.

b) 如果是Stack Operations包括Push Pop MultiPush MultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替的话,平均就是O(K).

17.1-2

本题目只要证明可能性,只要说明一种情况下结论成立即可

17.2-1

第11次作业参考答案

17.3-1

题目:

答案:

备注:最后一句话展开:采用新的势函数后对i 个操作的平摊代价:

)

1()())1(())(()()(1''^

'

-Φ-Φ+=--Φ--Φ+=Φ-Φ+=-Di Di c k Di k Di c D D c c i i i i i i

17.3-2

题目:

答案:

第一步:此题关键是定义势能函数Φ,不管定义成什么首先要满足两个条件 对所有操作i ,)(Di Φ>=0且)(Di Φ>=)(0D Φ

比如令k j

+=2i ,j,k 均为整数且取尽可能大,设势能函数)(Di Φ=2k;

第二步:求平摊代价,公式是)1()(^

-Φ-Φ+=Di Di c c i i 按上面设置的势函数示例:

当k=0,^

i c =…=2

当k !=0, ^

i c =…=3 显然,平摊代价为O(1)

17.3-4

题目:

答案:

结合课本p249,p250页对栈操作的分析很容易有下面结果

17.4-3

题目:

答案:

αα=(第i次循环之后的表中的entry 假设第i个操作是TABLE_DELETE, 考虑装载因子:

i

num size

数)/(第i次循环后的表的大小)=/

i i

第12 次参考答案

19.1.1

题目:

答案:

(1)如果x不是根,则degree[sibling[x]]=degree[child[x]]=degree[x]-1

(2)如果x是根,则sibling为二项堆中下一个二项树的根,因为二项堆中根链是按根的度数

递增排序,因此degree[sibling[x]]>degree[x]

19.1.2

题目:

答案:

(1)如果x是p[x]的最左子节点,则p[x]为根的子树由两个相同的二项树合并而成,以x为

根的子树就是其中一个二项树,另一个以p[x]为根,所以degree[p[x]]=degree[x]+1; (2)如果x不是p[x]的最左子节点,假设x是p[x]的子节点中自左至右的第i个孩子,则去掉

p[x]前i-1个孩子,恰好转换成第一种情况,因而degree[p[x]]=degree[x]+1+(i-1)= degree[x]+i;

综上, degree[p[x]]> degree[x]

19.2.2

题目:

题目:

19.2.5

19.2.6

第13次作业参考答案20.2-1

题目:

解答:

20.2-3 题目:

解答:

20.3-1 题目:

答案:

20.3-2 题目:

答案:

中科大软件学院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)对学术研究有浓厚的兴趣,有较强的创新意识、创新能力和专业能力;

算法导论 第三版 第21章 答案 英

Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1

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

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

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

算法导论 第三版 第六章 答案 英

Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1

算法导论 第三版 第七章 答案 英

Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1

算法导论 第三版 第二章 答案 英

Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i]

算法导论 第三版 第24章 答案 英

Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1

Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v)

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

算法实验报告 快速排序 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 最优子结构性质与重叠子问题性质

相关主题
相关文档 最新文档