区间树实验报告
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;
if (tp < xl->max)
tp=xl->max;
if(tp < xr->max)
tp=xr->max;
this->max=tp;
}
在左旋、右旋时调用此方法。
2.3 数据结构设计
基础数据结构选择红黑树,每个结点x 包含一个区间域int[x],x 的关键字为区间的低
端点low[int[x]],对树;进行中序遍历就可按低端点的次序列出个区间,结点还包含一个max[x],即以x 为根的子树中所有区间的端点的最大.
2.4 运行结果
为了增加算法运行时间减少误差,search、insert、delete 的都是树的最小关键字结点,
让查找深度尽可能的深。运行时间如下所示,单位:us:
T(us)
方法
search insert delete
2^4 2.933 14.176 2.933
2^6 3.399 17.098 3.422
2^8 3.422 20.042 3.911
2^10 4.399 17.598 4.547
2^12 3.441 18.087 4.888
运行平台:
2.5 结果分析
根据以上数据作如下t-lg(n)图像:
有图知当n=2^8 时,Insert 操作数据不是很好,出去它可得如下图:
在树规模较小的时候, 会对n 造成比较明显的影响, 3 条测量的曲线中, insert 与lgn 的
曲线增长率最符合,但都大致以lgn 增长。,在n 较小的时候, 算法执行时间受系统本身配置
影响较大, 数据也不会很准确, 这个也可以从表格中看出, 有一些与通常时间偏差较大的记录, 这个应该和系统的任务调度, 和其他程序的影响有关.
2.6 心得体会
由于区间树的很多操作与红黑书相似,此程序最大难点在维护结点的max 值。应仔细
分析左旋、右旋、插入、删除时改变那些结点的max 值、如何改变结点的max 值,这样编程时会事半功倍。
区间树与红黑树差别不是很大,很多操作都相似,可考虑从红黑树继承,实现代码重用。例如:
class ITNode: public RBTNode{
private:
Type NodeMax(ITNode* x);
public:
Type max; //以x 为根的子树中所有区间的端点最大值
Type low;
Type high;
ITNode(Type ilow=0, Type ihigh=0):RBTNode(ilow), low(ilow),
high(ihigh){max=NodeMax(this)}
};
class IntervalTree : public RBTree{
public:
IntervalTree(Type ilow=0, Type ihigh=0):RBTree(ilow){}
void Interval_Insert(ITNode* x){RB_Insert(x);}
void Interval_Insert(Type ilow, Type ihigh){Interval_Insert(new ITNode(ilow,ihigh));} void Interval_Delete(ITNode* x){RB_Delete(x);}
ITNode* Interval_Search(Interval i);
};
《面向对象编程技术》试卷 注: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,此时内结点
《大数据算法》实验教学大纲 大纲制定(修订)时间: 2017 年 11 月课程名称:《大数据算法》课程编码:0 课程类别:专业基础课课程性质:选修 适用专业:通信工程 课程总学时:40 实验(上机)计划学时: 8 开课单位:理学院 一、大纲编写依据 1.信息与计算科学2017-2020版教学计划; 2.信息与计算科学专业《大数据算法》理论教学大纲对实验环节的要求。 二、实验课程地位及相关课程的联系 1.《大数据算法》是信息与计算科学专业的一门专业方向课程;
2.本实验项目是《大数据算法》课程综合知识的运用; 3. 大数据不论在研究还是工程领域都是热点之一,算法是大数据管理与计算的核心主题,通过上机实验,不仅巩固学生在课堂上所学的知识,加深对大数据算法的理解,更重要的是通过实验题目,提高学生的动手能力,增强学生就业的竞争力; 4.本实验为后续的毕业设计有指导意义。 三、本课程实验目的和任务 1.理解大数据算法的基本理论,训练运用大数据思想对实际问题进行分析、设计、实践的基本技术,掌握科学的实验方法; 2.培养学生提炼、分析问题和独立解决问题的能力; 3.通过实验使学生能够正确使用一种大数据算法环境; 4.通过综合性、设计性实验训练,使学生初步掌握简单的概率算法、I/O有效算法、并行算法的设计方法; 5.培养正确记录实验数据和现象,正确分析算法性能的能力,以及正确书写实验报告的能力。 四、实验基本要求 1.实验项目的选定依据教学计划对学生实践能力培养的要求;
2.巩固和加深学生对大数据算法设计与分析方法的理解,提高学生结合运用所学知识解决问题的能力; 3.实验项目要求学生掌握大数据算法基本知识、MapReduce简单编程技术,并运用相关知识自行设计实验方案,完成解决一定问题的小型程序。 4.通过实验,要求学生做到: (1)能够预习实验,自行设计实验方案,并撰写实验报告; (2)学会一种大数据算法开发环境的使用,能利用该环境编制简单的外存有效的算法以及并行算法,验证课程中涉及的知识点,并独立设计算法解决某一实际问题; (3)能够独立分析程序运行结果,分析算法性能。 五、实验内容和学时分配
一、给定关系 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)
一、实验目的 (1)熟练掌握动态规划思想及教材中相关经典算法。 (2)掌握用动态规划解题的基本步骤,能够用动态规划解决一些问题。二、实验内容与实验步骤 (1)仔细阅读备选实验的题目,选择一个(可选多个)作为此次实验题目,设计的程序要满足正确性,代码中有关键的注释,书写格式清晰,简洁易懂,效率较高,利用C++的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示。 (2)可供选择的题目有以下2个: (i)找零钱问题(难度系数为3) ★问题描述 设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱,可以实用的各种面值的硬币个数不限。当只 用硬币面值T[1],T[2],…,T[i]时,可找出钱数j的最少硬币个数记为 C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=∞。 ★编程任务 设计一个动态规划算法,对1≤j≤L,计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的 计算时间复杂性 ★数据输入 由文件input.txt提供输入数据。文件的第1行中有1个正整数n (n<=13),表示有n种硬币可选。接下来的一行是每种硬币的面值。由 用户输入待找钱数j。 ★结果输出 程序运行结束时,将计算出的所需最少硬币个数输出到文件output.txt中。 输入文件示例输出文件示例 input.txt output.txt 3 3 1 2 5 9
三、实验环境 操作系统 Windows 7 调试软件 VC++6.0 上机地点 综合楼211 四、问题分析 (1) 分析要解决的问题,给出你的思路,可以借助图表等辅助表达。 答:这个问题用动态规划来解,归结到动态规划上面就变成了无限背包问题(因为收银台的硬币默认是无穷的,但一种改进版本可以考察有限硬币的情况)。区别在于,现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的,即每次选择都可以选择任何一种硬币。 首先,找零钱问题具有最优子结构性质: 兑换零钱问题的最优子结构表述:对于任意需要找的钱数j ,一个利用T[n]中的n 个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j),P(T(2),j),...,P(T(n),j),即此时的最少钱币个数 ∑==n 1j) P(T (k),),(k j n C ,则 P(T(2),j),...,P(T(n),j)一定是利用T[n]中n 个不同的面值钱币对钱数 j=j-P(T(1),j)* T(1)进行兑换零钱的最佳方案。 其次,找零钱问题具有重叠于问题性质: a)当n=1时,即只能用一种钱币兑换零钱,钱币的面值为T[0],有 b)当n>1时, 若j>T[n],即第n 种钱币面值比所兑换零钱数小,因此有} 1])[,({),(m in 1+-=≤≤k T j n C j n C n k 。当k 为n)i (1k 0≤≤时,C(n,j)达到最小 值,有P(T(k0),j)=P(T(0k ),j-T(0k ))+1 若j=T[n],即用n 种钱币兑换零钱,第n 种钱币面值与兑换零钱数j 相等,此时有C(n,j)=C(n,T[n])=1; { ] [,1] [,0])[,(),(n T i n T i n T i P j i P =≠= = 若j 课程设计报告 题目弹球小游戏 姓名方成 学号20 专业java 指导教师陈华恩 2013年12 月30 目录 一、实验目的 (2) 二、需求分析 (2) 三、实验任务 (2) 1、设计 (3) 2、程序要求: (3) 3、选作题: (3) 四、开发工具与平台 (3) 五、设计思路 (3) 1、界面设计 (3) 2、逻辑设计 (3) 3、程序测试 (4) 六、实验总结 (5) 七、程序代码 (5) 八、参考文献 (11) 1.《疯狂java讲义》 (12) 2.《算法导论》 (12) 3.《java编程思想》 (12) 一、实验目的 1、熟练掌握java面向对象编程。 2、掌握Swing图形用户界面编程以及事件处理等,掌握java绘图技术。 3、掌握timer类的灵活使用 4、培养独立查找资料,并解决问题的能力。 二、需求分析 经典的碰撞球是一个的古老游戏,目的是在训练人的反应能力。只有通过把所有的砖块消除完,才能顺利的完成任务。游戏要求如下: 1、实现球速度的随机性 2、实现球碰撞到边缘或者砖块自动反弹 3、实现游戏可以随时暂停 4、实现游戏结束后能重新开始游戏 三、实验任务 1、设计 设计并编程实现弹球程序:用户能通过菜单或者按钮新增一小球,该小球将从随机的位置出现,并具有随机颜色,随机速度以及随机的运动方向,小球沿初始方向匀速运动,当碰到窗口边缘时,小球将依据受力原理改变运动方向(可简化考虑,受力只改变小球的运动方向,小球仍按照初始速度匀速运动,且不考虑小球之间的碰撞)。 2、程序要求: (1)具备相应界面,并通过事件编程,实现相应的菜单或者按钮功能。(2)使用timer,在程序窗口区域绘制小球,并以线程控制小球的移动,实现动画效果。 3、选作题: (1)实现奖励机制及关卡机制 四、开发工具与平台 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.折半查找调节与时间复杂度 重庆大学项目报告 项目题目:跳桩得珠宝问题 学院: 专业班级:计科 年级:2011级 姓名: 学号: 完成时间:2013 年 6 月7 日指导教师:陈波 重庆大学教务处制 项目报告正文 一.问题描述 有m排n列的柱桩,每一排的柱桩从左向右标号为1,2,…,n,且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃,每次都必须跳到下一排的柱桩上,且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上,那么他可跳到下一排的第j号桩上,也可跳到下一排的第j-1 (if j>1)或者j+1 (if j 《算法导论》课程实验报告 (院)系数理系 _ _____ 专业 ______ _信息与计算科学________ ____ 班级信科1001班 学号_ 20 08 15__ 学生姓名刘俊伟_ 曹玮王舒斌 指导教师_ 阳卫锋 ______ _____ 《算法导论》实验指导书 实验目标 通过实验,使同学掌握并能熟练运用散列表、贪心算法、动态规划算法。 实验三计数排序 实验目的:掌握利用计数排序进行排序。 实验内容:对数组利用计数排序进行排序。 实验要求: 1)利用计数排序法。 2)记录每一步数组的中元素的变化 代码: import java.awt.BorderLayout; import java.awt.Button; import https://www.sodocs.net/doc/f81037035.html,ponent; import java.awt.Frame; import https://www.sodocs.net/doc/f81037035.html,bel; import java.awt.Panel; import java.awt.TextArea; import java.awt.TextField; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.geom.Area; import javax.swing.Box; import javax.swing.JFrame; class CountingSort extends Frame { public static void main(String[] args) { new CountingSort().lauchFrame(); } private void lauchFrame() { Frame f = new JFrame("计数排序"); f.setBounds(350, 150, 600, 300); 中科大考博辅导班: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)对学术研究有浓厚的兴趣,有较强的创新意识、创新能力和专业能力; 《数据库原理》实验报告书 班级: 学号: 姓名: 指导教师: 实验成绩: 中南林业科技大学涉外学院理工系 目录 数据库原理实验安排 (3) 实验一数据库和表的建立、数据操作 (4) 实验二 SQL语言的使用 (9) 实验三完整性、安全性实现 (16) 实验四数据库编程 (18) 附录一SQL Server的安装 (20) 数据库原理实验安排 一、实验目的 通过实验,使学生熟悉并掌握数据库的基本概念、基本原理、和基本技术;能够应用这些理论和技术设计合理的数据库;更重要的是通过教学活动,使学生能够把与数据库相关的先修后继知识融会贯通,初步具有开发完整可用的数据库系统的能力。 二、实验安排 本门课程共分4个实验,8学时 实验一数据库和表的建立、数据操作 2学时 实验二 SQL语言的使用2学时 实验三完整性、安全性实现 2学时 实验四数据库编程 2学时 三、实验考核 实验成绩通过实验报告及每次实验后的验机给出,每次实验结束后都必须写出实验报告。 实验一数据库和表的建立、数据操作 一、实验目的: 掌握使用SQL语言进行数据定义和数据操纵的方法。 二、实验要求: 建立一个数据库stumanage,建立三个关系表students,course,grade。向表中插入数据,然后对数据进行删除、修改等操作,对关系、数据库进行删除操作。 三、实验步骤: 1、在SQL Server中输入本机器的名字,选择“windows身份验证”。点击确定连接SQL Server数据库服务器。 2、新建查询分析器。 3、在查询分析器中输入SQL语句------建立数据库stumanage。然后单击上面的绿色三角形右箭头。下部的空白区显示该语句的运行情况。 4、选择数据库stumanage为当前数据库。 5、如下图建立表students: 列名数据类型允许空主键说明 (1) sno Char(8) 否是学号 (2) sname Varchar(20) 是否姓名 (3) sex Char(2) 是否性别 (4) dept Varchar(20) 是否所在系 如下图建立表:course 列名数据类型允许空主键说明 (1) cno Char(6) 否是课程号 (2) cname Varchar(20) 是否课程名 如下图建立表sc:(注:包括两个外键,sno和cno共同组成主键)列名数据类型允许空主键外键说明 (1) sno Char(8) 否是 students(sno) 学号 (2) cno Char(6) 否是 course(sno) 课程号 (3) grade int 否否否成绩 6、使用SQL语句完成建表操作并以截屏的方式将建表操作过程粘贴在下方表格中。 实验三:苯酚的紫外光谱绘制及定量测定 姓名:黄日权学号:20120010007 一、实验目的 1. 了解紫外可见分光光度计的基本原理; 2. 学习并掌握紫外可见分光光度计的基本操作; 3. 掌握紫外可见吸收光谱的绘制和定量测定方法。 二、实验原理 分子的紫外可见吸收光谱是由于分子中的某些基团吸收了紫外可见辐射光后,发生了电子能级跃迁而产生的吸收光谱。它是带状光谱,反映了分子中某些基团的信息。可以用标准光谱图再结合其它手段进行定性分析。 根据物质对紫外-可见光吸收的吸光度与物质含量符合Lambert-Beer(朗伯—比尔)定律:A=εbc,(A为吸光度,ε为摩尔吸光系数,b为液池厚度,c为溶液浓度),因此,可以对物质进行定量分析。 在紫外-可见吸收分光光度分析中,必须注意溶液的pH 值的影响。因为溶液的pH 值不但有可能影响被测物吸光强度,甚至还可能影响被测物的峰位形状和位置。酚类化合物就有这一现象,例如苯酚在溶液中存在如下电离平衡: 苯酚在紫外区有三个吸收峰,在酸性或中性溶液中,λmax 为196.3nm,210.4nm 和269.8nm;在碱性溶液中λmax 位移至207.1nm,234.8nm 和286.9nm。下图为0.021g/L 的苯酚分别在0.010mol/L 盐酸溶液与氢氧化钠溶液中的紫外吸收光谱。由图可知,在盐酸溶液与氢氧化钠溶液中,苯酚的紫外吸收光谱有很大差别,所以在用紫外可见吸收分光光度分析苯酚时应加缓冲溶液,本实验是通过加氢氧化钠强碱溶液来控制溶液pH 值的。 三、仪器和试剂 1、仪器:(1)UV-1700 型紫外可见分光光度计;(2)1.00cm石英比色皿2个;(3)50mL 容量瓶8 个;(4)5mL、10mL移液管各1 支;(5)100mL、250mL 烧杯各1 个;(6)吸耳球1 个。 2、试剂:(1)苯酚标准溶液: 100mg/L;(2)10% NaOH 溶液 四、实验操作 1、配置系列标准溶液:准确移取100mg/L 的苯酚标准溶液0.00(1 号)、2.00(2 号)、4.00(3 号)、6.00(4 号)、8.00(5 号)、10.00mL(6 号)分别置于50 ml 容量瓶中,各加10 滴10%的NaOH 溶液,并用蒸馏水稀释至刻度,摇匀。 2、绘制吸收曲线:用1cm 石英比色皿,以NaOH 空白溶液为参比,在200~330nm 范围内,测量系列标准溶液中的 3 号(或 4 号)的吸光度A,绘制吸收曲线,找出最大吸收波长λmax 。 3、绘制标准工作曲线:用1cm 石英比色皿,以NaOH 空白溶液为参比,在选定的最大吸收波长λmax 下分别测定标准系列样品的吸光度,绘制标准工作曲线。 4、测定未知溶液:取未知夜10.00mL 置于50.00mL 容量瓶中,加10 滴10%的NaOH 溶液,用蒸馏水稀释至刻度;以NaOH 空白溶液为参比,用1cm 的比色皿在最大吸收波长处测定吸光度A。 5、计算未知溶液的含量(mg/mL)。 6、配制0.1mg/mL 的苯酚水溶液,以空白溶液为参比,用1cm 石英比色皿测定其吸光 度A,绘制吸收曲线,比较其余步骤(2)所得吸收曲线的差别,并说明理由。 五、实验报告及要求 1、绘制苯酚碱性溶液的标准工作曲线; 图一. 苯酚碱性溶液的标准工作曲线 第一次实验报告 1、实验任务 根据下面的需求描述,使用Sybase Power Designer设计相应的数据库概念模型,并转换成Oracle或MS SQL Server上的物理数据库结构: 某银行准备开发一个银行业务管理系统,通过调查,得到以下的主要需求: 银行有多个支行。各个支行位于某个城市,每个支行有唯一的名字。银行要监控每个支行的资产。银行的客户通过其身份证号来标识。银行存储每个客户的姓名及其居住的街道和城市。客户可以有帐户,并且可以贷款。客户可能和某个银行员工发生联系,该员工是此客户的贷款负责人或银行帐户负责人。银行员工也通过身份证号来标识。员工分为部门经理和普通员工,每个部门经理都负责领导其所在部门的员工,并且每个员工只允许在一个部门内工作。每个支行的管理机构存储每个员工的姓名、电话号码、家庭地址及其经理的身份证号。银行还需知道每个员工开始工作的日期,由此日期可以推知员工的雇佣期。银行提供两类帐户——储蓄帐户和支票帐户。帐户可以由2个或2个以上客户所共有,一个客户也可有两个或两个以上的帐户。每个帐户被赋以唯一的帐户号。银行记录每个帐户的余额、开户的支行以及每个帐户所有者访问该帐户的最近日期。另外,每个储蓄帐户有其利率,且每个支票帐户有其透支额。每笔贷款由某个分支机构发放,能被一个或多个客户所共有。每笔贷款用唯一的贷款号标识。银行需要知道每笔贷款所贷金额以及逐次支付的情况(银行将贷款分几次付给客户)。虽然贷款号不能唯一标识银行所有为贷款所付的款项,但可以唯一标识为某贷款所付的款项。对每次的付款需要记录日期和金额。 2、实验过程 (1)确定实体和属性 由上面的需求描述我们可以很容易得出以下几个实体: ●员工(身份证号,姓名,电话号码,家庭地址,开始工作日 期) ●存储账户(账户号,余额,利率) ●支票账户(账户号,余额,透支额) ●客户(身份证号,姓名,街道,城市) ●支行(支行名称,城市,资产) ●贷款(贷款号,总额) ●支付(日期,金额) 图1 PS: 1、在此ER图中我没有设计账户类,然后派生出存储账户和支票账户,因为在客户的需求中,只有两种账户类型,除了支票账户类型就是存储账户类型,没有所谓的“一般的账户”,所以就不 大学项目报告 项目题目:跳桩得珠宝问题 学院: 专业班级:计科 年级:2011级 姓名: 学号: 完成时间:2013 年 6 月7 日指导教师:波 大学教务处制 项目报告正文 一.问题描述 有m排n列的柱桩,每一排的柱桩从左向右标号为1,2,…,n,且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃,每次都必须跳到下一排的柱桩上,且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上,那么他可跳到下一排的第j号桩上,也可跳到下一排的第j-1 (if j>1)或者j+1 (if j 第二章算法入门 由于时间问题有些问题没有写的很仔细,而且估计这里会存在不少不恰当之处。另,思考题2-3 关于霍纳规则,有些部分没有完成,故没把解答写上去,我对其 c 问题有疑问,请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题,没有做优化,请见谅,等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort 算法设计与分析 学 习 报 告 第一部分学习内容归纳 “计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程,或者说,算法是对计算机上执行的计算过程的具体描述。”(参考文献:百度百科)《算法设计与分析》是一门面向设计,在计算机科学中处于核心地位的课程。这门课程主要讲授了在计算机应用中经常遇到的问题和求解的方法,分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法复杂性的分析,以及计算理论简介。 第一部分“概论和数学准备”在简单了解了算法的基本概念和复杂性、研究步骤等几个重要知识点后,着重学习了算法的数学基础,包括生成函数、差方方程的求解等,主要适用于求解算法的时间复杂性。 “任何可以用计算机求解的问题所需要的计算时间都与其规模有关:问题的规模越小,解题所需的计算时间往往也越短,从而也就比较容易处理。”(参考文献:《计算机算法设计与分析(第3版)》)而第二部分介绍的算法常用技术之首——分治法就运用了这样的思想。分治法的要领在于Divide(子问题的划分)-Conquer(子问题的求解)-Combine(子问题解的组合)。由于子问题和原问题是同类的,递归的思想在分治法中显得尤其重要,它们经常同时运用在算法设计中。这部分内容从Select(求第k小元)算法,寻找最近点对算法和快速傅立叶变换FFT等实际应用中深化对分治法思想的理解,同时也强调了平衡思想的重要性。 第三部分“动态规划”与分治法类似,同样是把问题层层分解成规模越来越小的同类型的子问题。但与分治法不同的是,分治法中的子问题通常是相互独立的,而动态规划法中的子问题很多都是重复的,因此通常采用递推的方法以避免重复计算。然而,也不是所有的情况下都采用递推法,当有大量的子问题无需求解时,更好的方式是采用动态规划法的变形——备忘录方法。通常需要用到动态规划法求解的问题都具有子问题的高度重复性和最优子结构性质两大特征,这也是我们分析问题和设计算法时的关键点。最长公共子序列LCS问题和最优二分搜索树就是从动态规划法的两个主要特征角度分析问题,进而设计出相应的解决算法的。而这部分内容中的另一个问题——流水作业调度,则告诉我们采用动态规划时偶尔也得不到高效的算法,我们要学会将已有的知识灵活运用,适当加工。 第四部分“集合算法”中首先介绍了一种分析算法复杂度的手法——平摊分析(Amortized Analysis)。与之前我们所接触的算法分析方法即逐一考虑执行每条指令所需的时间复杂度再进行累加的方法不同,平摊分析是对若干条指令从整体角度考虑其时间复杂度,通过这样的方法获得的时间复杂度更加贴近实际的情况。平摊分析的主要方法有聚集方法,会计方法和势能方法。聚集方法将指令的时间复杂度分类计算再相加;会计方法采用了耗费提前计算的思想;势能方法引入了势函数的概念,从每步操作的数据结构状态和势函数的关系角度分析得出操作的平摊代价。“集合算法”这一部分主要分析了Union(合并集合)和Find (给出元素所在集合名)这两种运算。从上学期的《数据结构》课程的学习中,我们就已经发现集合和树之间的关系是密不可分的,我们经常用树结构来表示集合。而2-3树是一种特殊的每个内结点都只有2个或3个儿子的树,广泛的应用于可实现Member(查找)、Insert(插入)、Delete(删除)操作的数据结构——字典,可实现Insert、Delete、Union和Min(查找最小叶结点)的数据结构——可并堆,可实现Insert、Delete、Find、Concatenate(保序合并)和Split 算法实验报告 快速排序 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),最坏情况是当要排序的数列基本有序的时候。根据快速排序的工作原理我们知道, 算法导论上机实验报告册 班级: xxxxxx 学号: xxxxxxx 姓名: xxxx 教师: xxxxxx 目录 实验一排序算法 (1) 题目一: (1) 1、题目描述: (1) 2、所用算法: (1) 3、算法分析: (1) 4、结果截图: (1) 5、总结: (2) 题目二: (3) 1、题目描述: (3) 2、所用算法: (3) 3、算法分析: (3) 4、结果截图: (3) 5、总结: (4) 题目三: (4) 1、题目描述: (4) 2、所用算法: (4) 3、算法分析: (5) 4、结果截图: (5) 5、总结: (5) 题目四: (6) 1、题目描述: (6) 2、所用策略: (6) 3、算法分析: (6) 4、结果截图: (6) 5、总结: (7) 实验二动态规划 (7) 题目一: (7) 1、题目描述: (7) 2、所用策略: (7) 3、算法分析: (7) 4、结果截图: (8) 5、总结: (8) 题目二: (9) 1、题目描述: (9) 2、所用策略: (9) 3、算法分析: (9) 4、结果截图: (9) 5、总结: (10) 题目三: (10) 1、题目描述: (10) 2、所用策略: (10) 3、算法分析: (10) 5、总结: (11) 题目四: (12) 1、题目描述: (12) 2、所用策略: (12) 3、算法分析: (12) 4、结果截图: (12) 5、总结: (13) 题目五: (13) 1、题目描述: (13) 2、所用策略: (13) 3、算法分析: (13) 4、结果截图: (14) 5、总结: (14) 实验三贪心算法 (14) 题目一: (14) 1、题目描述: (14) 2、所用策略: (14) 3、算法分析: (14) 4、结果截图: (15) 5、总结: (16) 题目二: (16) 1、题目描述: (16) 2、所用策略: (16) 3、算法分析: (16) 4、结果截图: (17) 5、总结: (17) 题目三: (17) 1、题目描述: (17) 2、所用算法: (17) 3、算法分析: (17) 4、结果截图: (18) 5、总结: (18) 题目四: (19) 1、题目描述: (19) 2、所用算法: (19) 3、算法分析: (19) 实验四回溯法 (19) 题目一: (19) 1、题目描述: (19) 2、所用策略: (19) 3、算法分析: (19) 题目二: (21) 1、题目描述: (21)Java弹球游戏实验报告—chen汇总
(完整版)中科大软院常见复试题目.doc
重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码)
算法导论实验
中科大考博辅导班:2019中科大软件学院考博难度解析及经验分享
数据库原理实验报告2012
实验报告
中科大软院金老师的数据库实验一
重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码)
算法导论第二章答案
算法导论学习报告
中科大软件学院算法实验报告
西电算法导论上机实验报告