中科大算法导论实验报告
实验一常见排序算法的实现与性能比较
一、实验环境
操作系统：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;
for(k=p;k<=r;k++){
if(L[i]<=R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
j++;
}
}
}
void Merge_sort(float A[],int p,int r){
int q;
if(p q=(p+r)/2; Merge_sort(A,p,q); Merge_sort(A,q+1,r); Merge(A,p,q,r); } } （2）插入排序算法 1）插入排序原理： 依次将待排的数据插入到已经排好的数组中合适的位置，使已排好数组依然是有序的，直到所有待排数据插入完毕。 2）插入排序算法语言描述： void Insertion_sort(float A[],int n){ //要排序得数组A和A的长度n int i,j; float key; for(j=1;j key=A[j]; i=j-1; while(i>=0&&A[i]>key){ A[i+1]=A[i]; i--; } A[i+1]=key; } } （3）希尔排序算法 1）希尔排序原理： 首先取一个小于n的增量d1,将待排数据分成n/d1个组，其中距离 为d1的数据分在同一个组内。现在组内进行直接插入排序，取第二个增量d2 2）希尔排序算法语言描述： Shell_sort(float A[],int n){ //数组A与数组的长度n int i,j,step; float key; for(step=n/2;step>0;step=step/2){ //step为步长，初始为n/2,每次减半 for(i=step;i key=A[i]; j=i-step; while(j>=0&&A[j]>key){ A[j+step]=A[j]; j=j-step; } A[j+step]=key; } } } （4）快速排算法 1）快速排序原理： 任找一个元素作为基准，对待排数组进行分组，使基准元素左边的数据比基准数据要小，右边的数据比基准数据要大，这样基准元素就放在了正确的位置上。然后对基准元素左边和右边的组进行相同的操作，最后将数据排序完成。 2）快速排算法语言描述： void Quick_sort(float A[],int left,int right){ int i,j; float key; i=left; j=right; key=A[i]; while(i while(i j--; } A[i]=A[j]; while(i i++; } A[j]=A[i]; } A[i]=key; if(left Quick_sort(A,left,i-1); } if(right>i+1){ Quick_sort(A,i+1,right); } } （5）冒泡排序算法 1）冒泡排序原理： 两两比较待排序数据元素的大小，若发现两个数据元素的次序相反则进行交换，直到没有反序的数据为止。 2）冒泡排序算法语言描述： void Bubble_sort(float A[],int n){ int i,j; int flag;//作为是否发生变化的标志 float t; for(i=0;i flag=0; for(j=n-1;j>i;j--){ if(A[j] t=A[j-1]; A[j-1]=A[j]; A[j]=t; flag=1; } } if(flag==0){ return; } } } （6）桶排序算法 1）桶排序算法原理： 首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M 的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。 2）桶排序算法语言描述： //桶排序算法思想：设置一个二维数组B[100][],将待排数组A[]中的数据根据小数点后的第一、二位数值0-99存入相应数组B[0-99][]中 //然后在数组B[0-99][]中进行快速排序，排好后再复制回数组A中 void bucket_sort(float A[],int n)//待排数组A和A的长度 { float B[100][2500];//不知道第二维有几个数故设的大了点，谁让c中数组大小不能用变量呢 int index[100]={0};//存放了数组B[0-9][]中的数据个数 int i,j,k; //将待排数组A[]中的数据根据小数点后的第一位数值0-9存入相应数组B[0-9][]中 for(i=0;i k=(int)(A[i]*100); B[k][index[k]]=A[i]; index[k]++; } //在数组B[0-9][]中进行快速排序 for(i=0;i<100;i++){ Quick_sort(B[i],0,index[i]); } //排好后再复制回数组A中 k=0; for(i=0;i<100;i++){ for(j=1;j<=index[i];j++) if(index[i]!=0){ A[k]=B[i][j]; k++; } } } 五、实验内容与结果（程序的输入，输出，结果，演示界面） （1）程序输入： 程序输入包括，10,1000,10000,100000，0，-1。1）如果输入10，则给出各种排序结果；2）如果输入1000,10000,100000，则选择某种算法，观察在该算法下排序所用时间；3）如果输入0，则给出每种排序在6种样本下的排序时间和平均时间；4）如果输入-1程序结束！5）如果输入其它数据则给出错误信息，程序继续执行。 输入数据前界面显示： （2）程序输出结果及界面演示 1）输入10，给出随机生成的10个数据，在各种排序下的结果： 2）输入1000,10000,100000，则选择某种算法，观察在该算法下排序所用时间； 输入1000, 然后输入1、2、3、4、5、6选择各排序算法，观察在各排序算法下对1000个随机产生的数据进行排序所用时间： 输入10000,然后输入1、2、3、4、5、6选择各排序算法，观察在各排序算法下对10000个随机产生的数据进行排序所用时间： 输入100000,然后输入1、2、3、4、5、6选择各排序算法，观察在各排序算法下对100000个随机产生的数据进行排序所用时间： 3）输入0则给出每种排序在6种样本下的排序时间和平均时间： （注：桶排序时有问题，在对数量小时能成功，数据太大时就会出现问题。原因是我用的静态二维数组，所以数据大时堆栈空间中存不下所有二维数组的数据，所以出现问题） 4）如果输入其它数据则给出错误信息，程序继续执行。 六、各种排序算法的性能分析 （1）合并排序算法的性能分析 合并排序是一个时间复杂度为O(n*lgn)的排序算法，而且是一种稳定的排序算法。在最好和最坏情况下的时间复杂度都是O(n*lgn)，而合 并排序的空间复杂度为O(n); 对第五条中的输入0，则给出每种排序在6种样本下的排序时间和平均时间，进行分析可以看出。在数据数量时，合并排序要优于插入排序、和冒泡排序，但是不如快速排序、桶排序和希尔排序性能好。在数据数 量较小时，合并排序不如其他5种排序性能好，这是因为合并排序在最 好和最坏情况下的时间复杂度都是O(n*lgn)。 （2）插入排序算法的性能分析 插入排序是一个时间复杂度为O(n*n)的排序算法，而且是一种稳定的排序算法。插入排序的空间复杂度为O(1)。在最好情况下，待排数据 为升序排列好的数据，此时插入算法只要进行的比较操作需（n-1）次即 可，最坏况下，待排数据为逆序，此时需要进行的比较共有n(n-1)/2 次。 对第五条中的输入0，则给出每种排序在6种样本下的排序时间和平均时间，进行分析可以看出。在数据数量较大时，插入排序只优于冒泡 排序算法。而在数据数量较少时，插入排序要优于合并排序和冒泡排序，但是不如桶排序、快速排序和希尔排序性能好。 （3）希尔排序算法的性能分析 希尔排序算法是一个时间复杂度为O(n*n)的排序算法，但是一种不稳定的排序算法。希尔排序的空间复杂度为O(1)。希尔排序的执行时间依赖于增量序列。 对第五条中的输入0，则给出每种排序在6种样本下的排序时间和平均时间，进行分析可以看出。在数剧数量较大和较小情况下，另外五种算法相 比较，希尔排序要比合并排序、插入排序和冒泡排序算法性能好，但是不如桶排序和快速排序性能好。 （4）快速排序的性能分析 快速排序算是一个时间复杂度为O(n*lgn)的排序算法。空间复杂度为O(n*lgn),而且是一个不稳定的排序算法。快速排序最好时间复杂度 为O(n*lgn),最坏时间复杂度为O(n*n)。 对第五条中的输入0，则给出每种排序在6种样本下的排序时间和平均时间，进行分析可以看出。在数剧数量较大和较小情况下，快速排序 要比插入排序、冒泡排序、希尔排序和合并排序都要好，只比桶排序的 时间复杂度差而已。 （5）冒泡排序算法的性能分析 冒泡排序是一个时间复杂度为O(n*n)的排序算法。在最好情况下时间复杂度为O(n),在最坏情况下时间复杂度为O(n*n)。冒泡排序的空间 复杂度为O(1),而且冒泡排序是一种稳定的排序算法。 对第五条中的输入0，则给出每种排序在6种样本下的排序时间和平均时间，进行分析可以看出。当数据量比较少时，冒泡排序只比合并排 序算法性能好，在数据量较大时冒泡排序比其他性能都差。当数据量特 别大时，冒泡排序性能非常差，无法忍受！ （6）桶排序算法的性能分析 桶排序的平均时间复杂度为O(n+c)，最好情况下时间复杂度为O(n)。 桶排序的空间复杂度为O(m+n)，其中m为桶的数量，c=n*(lgn-lgm)。 桶排序是一种稳定的排序算法。 对第五条中的输入0，则给出每种排序在6种样本下的排序时间和平均时间，进行分析可以看出。桶排序是六种排序算法中性能最好的排序 算法。 总结： 通过上面的分析可以知道，时间复杂度为O(n*n)的排序算法为：插入排、冒泡排序和希尔排序算法，时间复杂度为O(n*lgn)的排序算法为：合并排序和快速排序算法，时间复杂度为O(n+c)的排序算法为桶排序。 稳定的排序算法为：合并排序、插入排序、冒泡排序和桶排序算法。不稳定的排序算法为：希尔排序和快速排序算法。 空间复杂度为O(1)的排序算法为：插入排序、希尔排序和冒泡排序。空间复杂度为O(n)的为合并排序。空间复杂度为O(n*lgn)的是快速排序。空间复杂度为O(m+n)的是桶排序。 在数据量较少时，六种排序算法的性能从高到低依次为：桶排序>快速排序>希尔排序>插入排序>冒泡排序>合并排序。 在数据量较大时，六种排序算法的性能从高到低依次为：桶排序>快速排序>希尔排序>合并排序>插入排序>冒泡排序 实验二红黑树、二叉搜索树的实现和性能比较 一、实验环境 操作系统：Windows XP操作系统 编程语言：C语言 开发工具：Microsoft Visual C++ 6.0 二、问题描述 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 三、实验要求 （1）插入测试，输入 8，11，17，15，6，1，22，25，27，建立红黑树，按照红黑树信息输出方式输出整棵红黑树以及黑高。 （2）删除测试，删除1）中红黑树中Key=15的节点，按照红黑树信息输出方式输出调整后的整棵红黑树以及黑高。 （3）随机产生300,000个不同自然数Key值（1－300,000，每个数出现一次，出现顺序随机），建立红黑树，查找Key=15000的节点，输出查找花费时间。用上面的数据，建立二叉搜索树，查找Key=15000的节点，输出查找花费时间。 （4）重复3－5次3）中操作，求各自平均时间。 （5）在（1）-（4）的红黑树算法基础上修改完成P307 14.1-4算法OS_Key_Rank(T,k). 输入 1,2,3,4,5,6,7,8 建树， k=6, 输出OS_Key_Rank的返回值。 四、红黑树与二叉树算法原理与算法语言描述 （1）二叉树 1）二叉树的结构定义：二叉树的结构包括二叉树节点和二叉树两部分。 分别定义为结构体search_tree_node和search_tree。其中定义二叉树节点包括关键字、左孩子、右孩子、和父节点。二叉树定义为包含一个节点结构的root跟节点。定义如下： struct search_tree_node{//二叉树的节点结构 int key; struct search_tree_node *left; struct search_tree_node *right; struct search_tree_node *p; }; struct search_tree{//二叉树结构 struct search_tree_node * root; }; 2）二叉树插入函数：从二叉树根节点开始依次查找待插入节点在二叉树 中的位置，若该节点的关键字大于待插入关键字则继续向左子树查找，若小于待插入关键字则向右子树查找。直至查找到叶子节点，将待插入节点作为该叶子节点的孩子，插入完毕。算法描述如下： void tree_insert(struct search_tree *T,struct search_tree_node *z){//将新值V插入到二叉树T中 struct search_tree_node * x; struct search_tree_node * y; y=NULL; x=T->root; while(x!=NULL){ y=x; if(z->key x=x->left; else x=x->right; } z->p=y; if(y==NULL){ T->root=z; } else if(z->key y->left=z; else y->right=z; } 3）二叉树查找函数：采用递归算法实现。实现代码如下： //二叉树查找 struct search_tree_node* tree_search(struct search_tree_node *x,int k){//给定指向树根的指针x和关键字k,返回指向k的节点的指针if(x==NULL||k==x->key) return x; if(k return tree_search(x->left,k); else return tree_search(x->right,k); } （2）红黑树 1）红黑树的结构定义：定义红黑树结构为结构体，包括红黑树节点rb_tree_node和红黑树rb_tree。其中红黑树节点结构包括：关键字、左孩子、右孩子、父节点和颜色。红黑树结构体包括：根节点root和空节点nil。具体定义如下： struct rb_tree_node{//红黑树节点 int key; char color; struct rb_tree_node *left; struct rb_tree_node *right; struct rb_tree_node *p; }; struct rb_tree{//红黑树 struct rb_tree_node *root; struct rb_tree_node *nil; }; 2）红黑树插入后修复函数： 红黑树的的插入函数算法与二茶树插入算法类似，这里就不重复讨论了，下面主要关注插入成功后，为保证红黑树的性质而进行的修 复工作。 红黑树插入节点后可能会破坏红黑树的第4条性质，为了回复红黑树的性质而对红黑树进行调整：根据Z的父节点是Z的祖节点的 左子节点还是右子节点，分为两组对称的情况，每组有3种情况。 下面我们只对其中一组进行说明，以Z的父节点是Z祖节点的左子 节点为例。 第一种情况：z的叔父节点是红色的。在这种情况下，将父、叔节点都着为黑色，再将子树根节点着为红色，那么子树的黑高度没 有发生改变，而且红黑性质得得到了调整。此时，再将Z指向子树 的根节点，向上递归恢复红黑特性。 第二种情况：Z的“叔父”节点是黑色的，Z的父节点的左子节点。将Z的父节点与祖节点进行一次右旋，并把父节点着黑色，原 来的祖节点着红色。这些子树的红黑特性得到了恢复，而且子树的 黑高度没有变化。另外，由于子树根节点已经是黑色了（这个节点 不会出现父子同为红色的问题了），所以不必再向上递归了，此时整 个树的红黑特性都已经是正确的了。 第三种情况：Z的“叔父”节点是黑色的，Z的父节点的右子节点。将Z本身与其父节点进行一次左旋，让Z指向原来的父节点， 就可以调整为情况二，而情况二已经得到解决。 红黑树插入后修复函数算法语言描述为： void rb_insert_fixup(struct rb_tree *T,struct rb_tree_node *z){//插入修正红黑树 struct rb_tree_node *y; while(z->p->color=='R'){ if(z->p==z->p->p->left){ y=z->p->p->right; if(y->color=='R'){ z->p->color='B'; y->color='B'; z->p->p->color='R'; z=z->p->p; } else { if(z==z->p->right){ z=z->p; left_rotate(T,z); } z->p->color='B'; z->p->p->color='R'; right_rotate(T,z->p->p); } } else{ //与上述代码类似，将right与left交换即可 } T->root->color='B'; } 3)红黑树删除后修复函数： 红黑树的删除操作比较简单，就不论述了，下面对较为复杂的删除后调整操作进行讨论。 如果Y指向的节点是个红色节点，那么直接删除掉Y以后，红黑性质不会被破坏。操作结束。 下面就具体地分析如何恢复第1、2、4三个可能被破坏的红黑特性：我们知道，如果X指向的节点是有红黑两色，或是X是根节点时，只需要简单的对X进行一些改变就行了。要对除X节点外的其它节 点进行操作时，必定是这样的情况：X节点是双层黑色，且X有父节 点P。由知可知，X必然有兄弟节点W，而且这个W节点必定有两个 子节点。（因为这是原树满足红黑条件要求而自然具备的。X为双黑 色，那么P的另一个子节点以下一定要有至少两层的节点，否则高 黑度不可能和X路径一致）。所以我们就分析这些节点之间如何变形， 把问题限制在比较小的范围内解决。另一个前提是：X在一开始，肯 定是树底的叶节点或是NIL节点，所以在递归向上的过程中，每一 步都保证下一步进行时，至少 X的子树是满足红黑特性的。因此子 树的情况就可以认为是已经正确的了，这样，分析就只限制在X节 点，X的父节点P，X的兄弟节点W，以及W的两个子节点。这些个 节点中。 W以及W的两个子节点C1和C1的一共有五种组合，便有两种情况的处理是一致的，因此调整的过程可以分以下四个情况： 第一种情况：W是红色节点。如果W是红色的，那么B和D节点进行一次左旋，并把D（也就是原来的W）着为黑色，B节点（X的 父节点）着为红色。然后让W指向X的新兄弟。这样，就把这种情 况转化为了W为黑色的情况来解决。在这个变形中，这五个节点之 间保持了红黑性质不变，而X指向的双黑色节点的位置和颜色特性 都没有变化。变形后的情况如何解决呢？下面的都是W为黑色的问 题，因此下面三种中总有一种会合适。 第二种情况：W以及W的两个子节点都是黑色的。这种情况下， 把D节点着成红色。然后把X的一个黑色推到父节点B中去，这时X 就指向B节点了。变形前后，这五个节点间的黑高是没有变化的。 唯一可能产生问题的就是如果B原来是红色，那么B和D两个红色 相邻就破坏了第４个性质，这样新X的子树就有问题了。这本来不 符合我们向上递归的假设。但正好在这种情况下递归就可以结束了。 因为B节点原来是红色，现在双加一层黑色，那么X现在指向的这 个节点就是红黑两色的，直接把X（也就是B）着为黑色。问题就已 经完整解决了。如果B节点现在是双层黑色，那就以B为新的X进 行向上的下一次的递归。 第三种情况：W的左子节点是红色的且右子节点是黑色。把C和D进行一次旋转，改变C和D的颜色变形成新的结构。把问题转化成 W的右子节点为红色的情况来解决。注意，原来C是红色的，所以C 的子节点一定是黑色的，所以旋转中C节点的一个子树挂到之后着 为红色的D节点上不会破坏红黑性质。变形后黑高度不变。 第四种情况：W的右子节点是红色（左子节点可以是红色或黑色）。将B和D进行一次左旋，并交换两者的颜色。再将E着为黑色。 这时，只要将X的一层黑色脱去，整个问题也得到了解决。递归结 束。（在代码上，为了标识递归结束，我们把X指向根节点） 因此，只要按上面四种情况一直递归处理下去，X最终总会指向根结点或一个红色结点，这时我们就可以结束递归并把问题解决 了。 红黑树删除后修复函数的算法描述语言为： void rb_delete_fixup(struct rb_tree *T,struct rb_tree_node *x){//删除后调整 struct rb_tree_node * w; while(x!=T->root&&x->color=='B'){ if(x==x->p->left){ w=x->p->right; if(w->color=='R'){ w->color='B'; x->p->color='R'; left_rotate(T,x->p); w=x->p->right; } if(w->left->color=='B'&&w->right->color=='B'){ w->color='R'; x=x->p; } else{ if(w->right->color=='B'){ w->left->color='B'; w->color='R'; right_rotate(T,w); w=x->p->right; } w->color=x->p->color; x->p->color='B'; w->right->color='B'; left_rotate(T,x->p); x=T->root; } } else{ //与上述代码类似，将right与left交换即可 } x->color='B'; } （3） OS_Key_Rank（T,k）函数： OS_Key_Rank（T,k）主要任务是以一棵顺序统计树T和某个关键字k为输入，返回在由T表示的动态集合中k的秩。 首先对红黑树的数据结构进行扩张。在红黑树的节点的结构体中加入一个整型的size域，其他变量都保持不变。结构定义如下： struct os_rb_tree_node{//扩张后的红黑树节点结构 int key; char color; int size; struct os_rb_tree_node *left; struct os_rb_tree_node *right; struct os_rb_tree_node *p; }; struct os_rb_tree{//扩张后的红黑树结构 struct os_rb_tree_node *root; struct os_rb_tree_node *nil; }; 然后，要在红黑树各个算法的基础上进行修改保持size的值的正确性。 要保证size值的正确性，有对红黑树的四个函数进行修改，包括：左旋函数、右旋函数、插入函数和删除函数。 对于左旋函数os_left_rotate（）和右旋函数os_right_rotate（），只要在函数的结尾处加上以下2句代码就行了： //红黑树扩张设置size值 y->size=x->size; x->size=x->right->size+x->left->size+1; 对于扩张后插入函数的算法描述语言为： void os_rb_insert(struct os_rb_tree *T,struct os_rb_tree_node *z){// 张后插入函数 struct os_rb_tree_node *x; struct os_rb_tree_node *y; struct os_rb_tree_node *k; y=T->nil; x=T->root; while(x!=T->nil){ y=x; if(z->key x=x->left; else x=x->right; } z->p=y; if(y==T->nil) T->root=z; else if(z->key y->left=z; else y->right=z; //红黑树扩张，设置size的值 k=z; while(k!=T->root){ k->p->size=k->p->right->size+k->p->left->size+1; k=k->p; } z->left=T->nil; z->right=T->nil; z->color='R'; os_rb_insert_fixup(T,z); 五、实验内容与结果（程序的输入，输出，结果，演示界面） （1）程序输入 程序输入包括,1、2、3、4、5、6。1）插入测试:输入8,11,17,15,6,1,22,25,27,建立红黑树,输出整棵红黑树以及黑高! 2）删除测试,删除1中红黑树中Key=15的节点,输出调整后的整棵红黑树以及黑高! 3）随机产生300000个不同自然数,建立红黑树和二叉树,输出查找Key=15000节点花费时间! 4）重复3－5次3中操作，求红黑树平均时间! 5）重复3－5次3中操作，求二叉树平均时间! 6）修改完成算法OS_Key_Rank,输入1,2,3,4,5,6,7,8建树,输出k=6时OS_Key_Rank的返回值!\n"); 输入数据前界面显示： （2）程序输出结果及界面演示 1）输入1，插入测试:输入8,11,17,15,6,1,22,25,27,建立红黑树,输出整棵红黑树以及黑高! 2）输入2，删除测试,删除1中红黑树中Key=15的节点,输出调整后的整棵红黑树以及黑高! 《面向对象编程技术》试卷 注：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/bb5121823.html,ponent; import java.awt.Frame; import https://www.sodocs.net/doc/bb5121823.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)中科大软件学院C+考试试卷
中科大软件学院算法复习概念综合题
大数据算法实验教学大纲
中科大软院数据库考试题
动态规划解找零钱问题实验报告
Java弹球游戏实验报告—chen汇总
(完整版)中科大软院常见复试题目.doc
重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码)
算法导论实验
中科大考博辅导班：2019中科大软件学院考博难度解析及经验分享
数据库原理实验报告2012
实验报告
中科大软院金老师的数据库实验一
重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码)
算法导论第二章答案
算法导论学习报告
中科大软件学院算法实验报告
西电算法导论上机实验报告