算法练习题-分章节-带答案
算法练习题---算法概述
一、选择题
1、下面关于算法的描述，正确的是（）
A、一个算法只能有一个输入
B、算法只能用框图来表示
C、一个算法的执行步骤可以是无限的
D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果
2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（）
A、设计算法，编写程序，提出问题，运行程序，得到答案
B、分析问题，编写程序，设计算法，运行程序，得到答案
C、分析问题，设计算法，编写程序，运行程序，得到答案
D、设计算法，提出问题，编写程序，运行程序，得到答案
3、下面说法正确的是（）
A、算法+数据结构=程序
B、算法就是程序
C、数据结构就是程序
D、算法包括数据结构
4、衡量一个算法好坏的标准是（）。
A、运行速度快
B、占用空间少
C、时间复杂度低
D、代码短
5、解决一个问题通常有多种方法。若说一个算法“有效”是指( )。
A、这个算法能在一定的时间和空间资源限制内将问题解决
B、这个算法能在人的反应时间内将问题解决
C、这个算法比其他已知算法都更快地将问题解决
D、A和C
6、算法分析中，记号O表示（），记号Ω表示（）。
A.渐进下界
B.渐进上界
C.非紧上界
D.非紧下界
7、以下关于渐进记号的性质是正确的有：（）
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))
=?=
8、记号O的定义正确的是（）。
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) D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 9、记号Ω的定义正确的是（）。 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) D．O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有： 0 ≤cg(n) < f(n) }； 二、填空题 1、算法的性质包括输入、输出、、、有限性。 4、算法的复杂性是的度量，是评价算法优劣的重要依据。 6、计算机的资源最重要的是时间和空间资源。因而，算法的复杂性有和之分。 7、算法复杂度依赖于三方面：、和算法本身。 8、程序是用某种程序设计语言的具体实现。 9、算法是指解决问题的或步骤的描述。 11、计算一个算法时间复杂度通常可以计算、或计算步。 16、任何可用计算机求解的问题所需的时间都与其有关。 算法练习题---递归与分治策略 一、选择题 10、Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（） 11、二分搜索算法是利用（ ）实现的算法。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 12、以下不可以使用分治法求解的是（ ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 13、实现循环赛日程表利用的算法是（ ）。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 14、实现棋盘覆盖算法利用的算法是（ ）。 A 、分治法 B 、动态规划法 C 、贪心法 D 、回溯法 15、Strassen 矩阵乘法是利用（ ）实现的算法。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 16、使用分治法求解不需要满足的条件是（）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 17、实现合并排序利用的算法是（ ）。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 18、实现大整数的乘法是利用的算法（ ）。 A 、贪心法 B 、动态规划法 C 、分治策略 D 、回溯法 二、填空题 5、分治法的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题互相 且与原问题相同。 10、从分治法的一般设计模式可以看出，用它设计出的程序一般是 。 14、快速排序算法是基于 的一种排序算法。 17、快速排序算法的性能取决于 C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } D. void hanoi(int n, int C, int A, int B) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 三、简答题 3、分治法所能解决的问题一般具有的几个特征是： 答：（1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4、分治法与动态规划法的异同。 答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。 而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 8、老板有一袋金块（共n块，n是2的幂（n>=2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。 答：n≤2 ，识别出最重和最轻的金块，一次比较就足够了。 n＞2， 第一步，把这袋金块平分成两个小袋A和B。 第二步，分别找出在A和B 中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA，以此类推，B中最重和最轻的金块分别为HB和LB。 第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。 9、Tom很顽皮。一天，他把假币投到储钱罐里。之后，他担心爸爸揍它，想从N个钱币里找出那个假币。他知道假币的重量比其他钱币轻，但不知道如何找到它，于是禁不住哭了。也许你能帮他。请描述一个通过使用天平找到假币的算法，并分析你算法的运行时间。 11、对下面的递归算法，写出调用f(4)的执行结果。 void f(int k) { if( k>0 ) { printf("%d\n ",k); f(k-1); f(k-1); } } 四、算法填空 5.快速排序 void QuickSort (int a[], int p, int r) { if (p { int q=Partition(a,p,r); ; //对左半段排序 ; //对右半段排序 } } 6.排列问题 void perm(int list[], int k, int m ) { //产生[list[k:m]的所有排列 if( ) { //只剩下一个元素 for (int i=0;i<=m;i++) cout< cout< } else //还有多个元素待排列，递归产生排列 for ( ) { swap(list[k]，list[i]); ; swap(list[k],list[i]); } } 五、算法题 1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。template int BinarySearch(Type a[], const Type& x, int n) {//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1 Int left=0; int right=n-1; While (left<=right) { int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; } Return -1; } 时间复杂性为O(logn) 2. 利用分治算法写出合并排序的算法，并分析其时间复杂度 void MergeSort(Type a[], int left, int right) { if (left { int i=(left+right)/2; //取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } } 算法在最坏情况下的时间复杂度为O(nlogn)。 算法练习题---动态规划 一、选择题 19、下列不是动态规划算法基本步骤的是（）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 20、最长公共子序列算法利用的算法是（）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 21、动态规划算法的基本要素为（） A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 22、矩阵连乘问题的算法可由（）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D.分治法 23、下列算法中通常以自底向上的方式求解最优解的是（）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 24、应用Johnson法则的流水作业调度采用的算法是（） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 25、下列不是动态规划算法基本步骤的是（）。题目不好 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 二、填空题 2、动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。 3、设计动态规划算法的4个步骤：（1）＿，并刻画其结构特征。 （2）。（3）。（4）根据计算最优值得到的信息，。 12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。 18、下面程序段的所需要的计算时间为。 int MaxSum(int n, int *a, int &besti, int &bestj) { int sum=0; for(int i=1;i<=n;i++) { int thissum=0; for(int j=i;j<=n;j++) { thissum += a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } return sum; } 21、所谓最优子结构性质是指。 三、简答题 1、请叙述动态规划算法与贪心算法的异同。 答：共同点：都需要最优子结构性质， 不同点： （1）动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。 （2）动态规划方法的条件：子问题的重叠性质。 贪心方法的条件：最优子结构性质；贪心选择性质。 （3）动态规划：自底向上求解； 贪心方法：自顶向下求解。 2、设计动态规划算法的主要步骤为： 答：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。 4、分治法与动态规划法的异同。 答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。 而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 四、算法填空 2.最大子段和: 动态规划算法 int MaxSum(int n, int a[]) { int sum=0, b=0； //sum存储当前最大的b[j], b存储b[j] for(int j=1； j<=n； j++) { if (b>0) b += a[j] ； else ； //一旦某个区段和为负，则从下一个位置累和 if(b>sum) sum=b; } return sum； } 算法练习题---贪心算法 一、选择题 26、能采用贪心算法求最优解的问题，一般具有的重要性质为：（） A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 27、贪心算法与动态规划算法的共同点是（）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 28、贪心算法与动态规划算法的主要区别是（ ）。 A 、最优子结构 B 、贪心选择性质 C 、构造最优解 D 、定义最优解 29、哈弗曼编码的贪心算法所需的计算时间为（ ）。 A 、O （n2n ） B 、O （nlogn ） C 、O （2n ） D 、O （n ） 30、下面是贪心算法的基本要素的是（ ）。 A 、重叠子问题 B 、构造最优解 C 、贪心选择性质 D 、定义最优解 31、下面问题（B ）不能使用贪心法解决。 A 单源最短路径问题 B N 皇后问题 C 最小花费生成树问题 D 背包问题 32、背包问题的贪心算法所需的计算时间为（ ） A 、O （n2n ） B 、O （nlogn ） C 、O （2n ） D 、O （n ） 45、下列算法中不能解决0/1背包问题的是（ ） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 二、填空题 19、 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求 解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动 。 20、所谓贪心选择性质是指 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到 。 21、所谓最优子结构性质是指 问题的最优解包含了其子问题的最优解 。 四、算法填空 1.背包问题的贪心算法 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; float c=M; for (i=1;i<=n;i++) x[i]=0; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; 1 11119 8 7 6 5 4 f 12 8 8 6 5 3 5 0 3 1 S 119 8 7 6 5 4 3 2 1 i ; } ; } 3.贪心算法求装载问题 void Loading(int x[], int w[], int c, int n) { int *t = new int [n+1]; ; for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) { x[t[i]] = 1; ; } } 4.贪心算法求活动安排问题 template void GreedySelector(int n, Type s[], Type f[], bool A[]) { ; int j=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { ; ; } else A[i]=false; } } 五、算法题 5、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。 void dicomp(int n,int a[]) { k=1; if(n<3) { a[1]=0; return; } if(n<5) { a[k]=1; a[++k]=n-1; return;} a[1]=2; n-=2; while(n>a[k]) { k++; a[k]=a[k-1]+1; n-=a[k]; } if(n==a[k]) { a[k]++; n--;} for(int i=0;i } 算法练习题—回溯法 一、选择题 33、回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。 A.广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 34、下面哪种函数是回溯法中为避免无效搜索采取的策略（） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数 35、回溯法的效率不依赖于以下哪一个因素？（） A. 产生x[k]的时间； B.满足显式约束的x[k]值的个数； C. 问题的解空间的形式； D.计算上界函数bound的时间； 36、回溯法的效率不依赖于下列哪些因素（） A.满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 37、下列算法中通常以深度优先方式系统搜索问题解的是（）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 38、回溯法搜索状态空间树是按照（）的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 39、程序块（）是回溯法中遍历排列树的算法框架程序。 二、填空题 12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 ，需要排序的是 ， 。 13、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 ，只使用约束条件进行裁剪的是 。 15、回溯法是一种既带有 又带有 的搜索算法。 22、回溯法是指 。 23、用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 。 24、回溯法的算法框架按照问题的解空间一般分为 算法框架与 算法框架。 25、用回溯法解0/1背包问题时，该问题的解空间结构为 结构。 26、用回溯法解批处理作业调度问题时，该问题的解空间结构为 结构。 27、旅行售货员问题的解空间树是 。 28、用回溯法解图的m 着色问题时，使用下面的函数OK 检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限） 。 Bool Color::OK(int k) { C.void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t-1); } } D ．void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); } } for(int j=1;j<=n;j++) if((a[k][j]= =1)&&(x[j]= =x[k])) return false; return true; } 三、简答题 5、分支限界法与回溯法的异同 答：相同点：都是一种在问题的解空间树T中搜索问题解的算法。 不同点：（1）求解目标不同；（2）搜索方式不同； （3）对扩展结点的扩展方式不同；（4）存储空间的要求不同。 四、算法填空 10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容： Typep Knap { Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 结点的上界 // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { ; ; ; } // 装满背包 if (i <= n) return b; } 五、算法题 3.N皇后回溯法 bool Queen::Place(int k) //检查x[k]位置是否合法 { for (int j=1;j if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) { if (t>n) sum++; else for (int i=1;i<=n;i++) { x[t]=i; if ( 约束函数 ) Backtrack(t+1); } } 4. 请写出用回溯法解装载问题的函数。 装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱 i的重量为wi，且 12 1 n i i w c c = ≤+ ∑ 。装载问题要求确定是否有一个合理的装载方案可将这 n个集装箱装上这2艘轮船。如果有，找出一种装载方案。void backtrack (int i) // 搜索第i层结点 { if (i > n) // 到达叶结点 if(cw>bestw) //更新最优解bestx,bestw; return; { for(j=1;j<=n;j++) bestx[j]=x[j]; Bestw=cw; } r -= w[i]; if (cw + w[i] <= c) // 搜索左子树 { x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) // 搜索右子树 { x[i] = 0; backtrack(i + 1); } r += w[i]; } 算法练习题---分支限界法 一、选择题 40、常见的两种分支限界法为（） A. 广度优先分支限界法与深度优先分支限界法； B. 队列式（FIFO）分支限界法与堆栈式分支限界法； C. 排列树法与子集树法； D. 队列式（FIFO）分支限界法与优先队列式分支限界法； 41、分支限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。A．广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 42、下面不是分支界限法搜索方式的是（）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 43、分支限界法解旅行售货员问题时，活结点表的组织形式是（）。 A、最小堆 B、最大堆 C、栈 D、数组 44、优先队列式分支限界法选取扩展结点的原则是（）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 45、下列算法中不能解决0/1背包问题的是（） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 二、填空题 12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。 三、简答题 5、分支限界法与回溯法的异同 答：相同点：都是一种在问题的解空间树T中搜索问题解的算法。 不同点：（1）求解目标不同；（2）搜索方式不同； （3）对扩展结点的扩展方式不同；（4）存储空间的要求不同。 6、用分支限界法设计算法的步骤是： 答：(1)针对所给问题，定义问题的解空间（对解进行编码）；分 (2)确定易于搜索的解空间结构（按树或图组织解）； (3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索。 7、常见的两种分支限界法的算法框架 答：（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 10、用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。 // 检查左儿子结点 Type wt = Ew + w[i]; // 左 儿子结点的重量 if (wt <= c) { // 可 行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 答：斜线标识的部分完成的功能为：提前更新bestw值； 这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。 为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< 全国2011 年10 月高等教育自学考试 票据法试卷 课程代码:00257 一、单项选择题(本大题共30小题，每小题 1 分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1. 票据属于( ) A. 债权证券 B. 证权证券 C. 有因证券 D .商品证券 2. 不属于票据当事人的是( ) A. 银行汇票收款人 B. 银行本票申请人 C. 商业汇票出票人 D .支票背书人 3. 可能享有票据权利的持票人是( ) A. 出票人禁止转让的票据的受让人 B. 金额大小写不一致的票据的持票人 C?偷窃他人票据的持票人 D. 出票原因关系违法的票据的被背书人 4. 不属于票据基础关系的是( ) A. 票据原因关系 B. 票据预约关系 C?票据利益返还关系 D. 票据资金关系 5. 票据权利的内容是( ) A. 请求一定数额的金钱支付 B. 请求付款人承兑 C?转让票据 D.请求返还票据 6. 关于票据权利取得的说法，正确的是( ) A. 只有按照票据法规定的方式取得票据，才能取得票据权利 B. 票据是完全有价证券，持有票据者即享有票据权利 C?以偷盗手段取得票据的，不享有票据权利 D.只有支付对价者才能取得票据权利 7. 无偿取得票据的持票人与其前手的关系是( ) A. 不管前手是否享有票据权利，持票人都享有票据权利 B. 不管前手是否享有票据权利，持票人都不享有票据权利 C?持票人享有的票据权利不得优于其前手 D.持票人是否享有票据权利，与其前手的票据权利状态无关 8. 关于自然人的票据行为能力要求，我国票据法采取( ) A .完全民事行为能力说 B. 限制民事行为能力说 C?自然人当然具有说 D.商人资格说 9. 甲向乙签发支票，因合同总价未确定，故支票金额未填写。甲与乙商定，金额由乙根据实际发货数量补充填写。后来实际发生的货款为21 万元，但乙将金额填为24 万元，并将支票转让给丙。对此，正确的说法是( ) A .乙违反诚信原则填写票据，票据无效 B?乙违反甲之授权，填写无效，应按实际发生的货款确定票据金额 C. 甲可以以乙滥用填充权为由对丙提出抗辩 D. 乙补充填写的支票有效 10. 黄某是某公司普通雇员，盗用公司财务印章签发支票给房产公司，支付自己的购房款。关于此事说法正确的是( ) A. 黄某的行为构成伪造票据 B. 黄某的行为属于票据的无权代理 C. 黄某的行为涉嫌犯罪，支票无效 D. 房产公司未向公司核实，取得票据有重大过失，不享有票据权利 11. 关于票据更改的说法，正确的是( ) A. 只有出票人才有权更改票据 B. 票据上的金额不能更改 C?票据具有要式性，一经填写不得更改 D.票据更改应以红笔标注 12. 甲、乙两公司虚立买卖合同一份，向银行申请银行承兑汇票。银行在汇票上签章承兑。乙将汇票背书转让给丙，获取物资一批。甲、乙的负责人将物资抛售后携款潜逃。丙向银行提示付款时( ) A. 银行应当拒付，理由是甲乙恶意串通损害第三人利益，汇票无效 B. 银行应当拒付，理由是银行承兑是被欺诈而为的行为，应当撤销 C. 银行应当拒付，因为本案涉嫌犯罪，应当先处理刑事部分 D. 银行不能对丙拒付，因为丙是善意持票人 13. 属于票据丧失的情形是( ) A. 持票人故意将票据撕毁 B. 持票人将票据委托他人保管，他人却强占票据不肯返还 3.用梯度法求下列无约束优化问题：MinF(X)=x12+4x22，设初始点取为X(0)={2,2}T，以梯度模为终止迭代准则，其收敛精度为5。 1)求初始点梯度▽F(X) ▽F(X)={2x1,8x2}T▽F(X(0))={4,16}T (2)第一次搜索 |▽F(X(0))|=16.5,S(0)=- ▽F(X(0))/16.5=-{0.243,0.97}T α(0)=2.157 X(1)=X(0)+α(0)S(0)={1.476,-0.923}T ▽F(x(1))={2.952,-0.738}T |▽F(x(1))|=3.043<5.0 故满足要求，停止迭代。 最优点X*={1.476,-0.0923}T 最优值F(X*)=2.21 4. 5. 6. 用外点法求解约束优化问题： ()()12211221min ..0()0 f X x x s t g X x x g X x =+=-≤=-≤ ， 收敛准则：(1) ()0.10.01k k X X εδ+-≤=，约束容限＝ 解：（1）利用外点法惩罚法构造无约束优化问题 () ( ) 12()22()212121(min ,()() k k k x x X r x x r x x r x +??Φ=?++-+-??可行域内）（可行域外） （2）此例只是为了说明外点法的思路，用微分法求解上述无约束优化问题。 用极值条件求解： 在可行域内：偏导数不可能等于0，即可行域内无极值 在可行域外，令： ()2()11211 ()2122 14()2012()0k k k r x x x r x x r x x x ?Φ =+-+=??Φ =--=? 第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n n n n n -+≥-+≥，所以，可选4c =，08n =。对于0n n ≥， 22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。 （3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥， 票据法 一、单选题 1、下列各项中，不符合《票据法》规定的是（）。 A、商业承兑汇票属于商业汇票 B、商业承兑汇票的承兑人是银行以外的付款人 C、银行承兑汇票属于商业汇票 D、银行承兑汇票属于银行汇票 【正确答案】D 【您的答案】 2、在我国，票据金额以中文大写和阿拉伯小写数码同时记载，若两者不一致，则（）。 A、票据无效 B、票据有效 C、以中文大写为准 D、以阿拉伯小写数码为准 【正确答案】A 【您的答案】 3、甲在将一汇票背书转让给乙时，未将乙的XX记载于被背书人栏内。乙发现后将自己的XX填入被背书人栏内。下列关于乙填入自己XX的行为效力的表述中，正确的是（）。 A、无效 B、有效 C、可撤销 D、甲追认后有效 【正确答案】B 【您的答案】 4、下列各项中，属于票据关系中的基本当事人的包括（）。 A、出票人 B、保证人 C、被背书人 D、背书人 【正确答案】A 【您的答案】 5、见票即付汇票的持票人在出票日起（）内提示付款的，才产生法律效力。 A、10日 B、1个月 C、2个月 D、3个月 【正确答案】B 【您的答案】 6、根据《票据法》的规定，背书由背书人签章并记载背书日期。背书未记载日期的，下列处理方式正确的是（）。 A、出票行为无效 B、视为在票据到期日前背书 C、票据无效 D、背书无效 【正确答案】B 【您的答案】 7、出票人在汇票上记载“不得转让”字样的，该记载属于（）。 A、不发生票据法上的效力 B、任意记载事项 C、必须记载事项 D、相对记载事项 【正确答案】B 【您的答案】 8、背书人甲将一X100万元的汇票分别背书转让给乙和丙各50万元，下列有关该背书效力的表述中，正确的是（）。 A、背书无效 B、背书有效 C、背书转让给乙50万元有效，转让给丙50万元无效 D、背书转让给丙50万元无效，转让给乙50万元有效 【正确答案】A 【您的答案】 9、2009年4月1日，甲向乙签发了一X见票后3个月付款的银行承兑汇票，根据票据法律的相关规定，该汇票提示承兑的最后期限是（） A、2009年7月1日 B、2009年4月10日 C、2009年5月1日 现代设计方法试卷1及答案 一、单项选择题 1.属于无约束优化问题求解算法中的直接法是（ C ） A. 梯度法 B.牛顿法 C.POWELL法 D.变尺度法 2.按类型划分，惩罚函数法属于（ D ） A.一维优化方法 B.无约束优化方法 C.直接法 D.约束优化方法 3.对于只含有不等式约束的优化问题，满足每一个设计约束的设计点，称为 （D） A.边界点 B.非可行点 C.外点 D.内点 4.坐标轮换法以为搜索方向。（C） A.梯度方向 B.共轭方向 C.坐标轴方向 D.负梯度方向 5.一个多元函数F（X）在点X*附近偏导数连续，则该点为极小值点的充分条件是（ B ） A.▽F（X*）=0 B. ▽F（X*）=0,H（X*）正定 C. H（X*）=0 D. ▽F（X*）=0,H（X*）负定 6.在有限元分析中，将构件分割成单元的方法称之为( C ) A.有限化 B.单元化 C.网格化 D.分割化 7.平面问题的弹性矩阵与材料的（ D） A.弹性模量有关，泊松比无关 B.弹性模量无关，泊松比有关 C.弹性模量和泊松比都无关 D.弹性模量和泊松比都有关 8.当零件材料的强度均值小于应力均值时，零件的平均安全系数为n，等效概率为F，则（A ） A.n<1，F>50% B. n>1，F>50% C. n<1，F<50% D. n>1，F<50% 9.串联系统的失效模式大多服从（ D ） A.正态分布 B.对数正态分布 C.指数分布 D.威布分布 10.抽取100只灯泡进行实验，灯泡工作到50小时有12只损坏，工作到70小 时又有20只损坏，从50小时到70小时这段时间内灯泡的平均失效密度为（ C ） A. 0.006 B. 0.004 C. 0.01 D. 0.12 二、填空题 11.单元刚度矩阵具有对称性、 分块 性和奇异性。 12.机电产品零件失效曲线分为三个区域，分别为： 早期失效区域 、正常工 作区域和功能失效区域。 13.函数()223212221+-+=x x x x x F 在点（1，0）处的梯度为 [6,-2]T 。 14.组成并联系统的零件的可靠度与该并联系统的可靠度相比较， 并联系统 的可靠度高。 15.一批产品从投入运行到发生失效的平均时间称为 平均寿命 。 16.可靠度是对产品可靠性的 概率 度量。 17.设某系统由10个零件串连组成，每个零件的可靠度均为0.95，系统的可靠度为 0.599 。 18.根据处理约束条件的方式不同，求解约束优化问题的方法分为 直接法 和间接法。 19.根据是否满足约束条件可以将设计点分为：可行点和 不可行点 。 20.利用目标函数的一阶导数或二阶导数信息构成搜索方向的方法称为 导数法 。 三、名词解释 21、（定义）可靠度：指产品在规定的条件下和规定的时间内，完成规定功能的概率，用R 表示。 22、（定义）失效率：又称故障率，产品工作t 时刻时尚未失效（或故障）的产品，在该时刻 第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ，称之为可行域（约束域）。 {}1,,e E m =L ，{}1,,e I m m +=L ，{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ，则问题 可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。 《现代设计方法》课程习题集 西南科技大学成人、网络教育学院 版权所有 习题 【说明】：本课程《现代设计方法》（编号为09021）共有单选题,计算题,简答题, 填空题等多种试题类型，其中，本习题集中有[ 填空题,单选题]等试题类型未进入。 一、计算题 1. 用黄金分割法求解以下问题（缩小区间三次）。 342)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε。 2. 用黄金分割法求解以下问题（缩小区间三次） 32)(m in 2+=x x f ，给定[][],1,2a b =-，取1.0=ε 3. 用黄金分割法求解以下问题（缩小区间三次） 432+=x )x (f min ，给定[][]40,b ,a =，取10.=ε。 4. 用黄金分割法求解以下问题（缩小区间三次）。 12)(m in 3+-=x x x f ，给定初始区间[][]3,0,=b a ，取5.0=ε 5. 用黄金分割法求解以下问题（缩小区间三次）。 107)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε 6. 用梯度法求解无约束优化问题： 168)(m in 22221+-+=x x x X f ，取初始点[]T X 1,1)0(= ，计算精度1.0=ε。 7. 用梯度法求解96)(m in 12221+-+=x x x X f ，[]T X 1,1)0(= ，1.0=ε。 8. 用梯度法求解44)(m in 22221+-+=x x x X f ，[]T X 1,1)0(=，1.0=ε 。 9. 用梯度法求解无约束优化问题：1364)(m in 222 121+-+-=x x x x X f ，取初始点[]T X 1,1)0(=，计算精度1.0=ε。 10. 用梯度法求解1212221422)(m in x x x x x X f --+=,[]T X 1,1)0(=，1.0=ε 。（请迭代两次） 11. 有三个可靠度均为0.9的子系统组成的并联系统，试比较纯并联及2/3[G]表决系统的可靠度。 12. 一个由2个子系统组成的系统，其可靠度指标为0.85，试按等同分配法分配子系统的可靠度：（1）组成串联系统，（2）组成并联系统。 13. 已知某零件的应力和强度均呈正态分布，零件强度：MPa 516=δμ（均值），MPa S 2.24=δ（标准差），应力：MPa 378=σμ（均值），Mpa S 5.41=σ（标准差），试计算零件的可靠度与失效概率。 14. 由应力分析表明，某零件所承受的应力是拉应力，可用正态分布来描述，MPa T 3500=μ，标准差MPa S T 400=。该零件在制造过程中所引起的残余应力也可用正态分布来描述，其均值MPa C 1000=μ，标准差MPa S C 150=。由强度分析表明，该零件的强度也服从正态分布，其均值MPa 5000=δμ。现要求出当保证该零件的可靠度不低0.999时，零件强度的标准差的最低值应为多少? 15. 由应力分析表明，某零件所承受的应力是拉应力，可用正态分布来描述，MPa T 3500=μ，标准差MPa S T 400=。该零件在制造过程中所引起的残余应力也可用正态分布来描述，其均值MPa C 1000=μ，标准差MPa S C 150=。由强度分析表明，该零件的强度也服从正态分布，其均值MPa 5000=δμ。现要求出当保证该零件的可靠度不低0.999时，零件强度的标准差的最低值应为多少? 算法设计与分析习题答案1-6章 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler，1707—1783) 提出并解决了该问题。七桥问题是这样描述的:北区 一个人是否能在一次步行中穿越哥尼斯堡(现在东区叫加里宁格勒，在波罗的海南岸)城中全部的七岛区 座桥后回到起点，且每座桥只经过一次，图1.7 南区是这条河以及河上的两个岛和七座桥的草图。请 图1.7 七桥问题将该问题的数据模型抽象出来，并判断此问题是 否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1，一次步行 2，经过七座桥，且每次只经历过一次 3，回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 2(在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3(设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 #include 票据法测试题及参考答案 一、单项选择题（本大题共30小题，每小题1分，共30分）在每小题列出的四个选项中只 有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1．我国《票据法》规定持票人对定期汇票的出票人和承兑人的票据权利时效，为自汇票到期日起（） A．2年B．6个月C．3个月 D．1年 2．下列关于空白票据转让的表述中，正确的是（） A．空白票据只能依背书方式转让 B．空白票据只能依直接交付方式转让 C．空白票据转让时不受特别限制 D．空白票据不可以转让 3．在涉外票据中，汇票和本票出票行为的记载事项，应当适用（） A．出票人所属国的法律B．付款人所属国的法律 C．出票地的法律D．付款地的法律 4．一般背书的相对必要记载事项是（） A．背书人B．被背书人 C．“不得转让”字样D．背书日期 5．支票出票人的主要票据义务是（） A．直接付款义务B．担保义务 C．背书义务D．承兑义务 6．背书转让与一般债权转让的主要不同在于（） A．背书转让无须通知票据债务人，一般债权转让应当通知债务人 B．背书人转让票据后退出票据关系，一般债权人转让债权后不退出债权债务关系 C．背书转让属于不要式行为，一般的债权转让都是要式行为 D．背书转让的只能是财产权，一般债权转让的既可以是财产权也可以是人身权 7．狭义的票据行为仅指（） A．能够发生票据债务的法律行为 B．能够变更票据债务的法律行为 C．能够消灭票据债务的法律行为 D．能够完成票据债务的法律行为 8．下列票据中，属于涉外票据的是（） A．外国人签发的票据 B．票据行为中有的发生在我国，有的发生在外国 C．所有票据行为都发生在外国的票据 D．我国公司在国外签发、使用的票据 9．导致票据权利消灭的原因是（） A．时效期间经过 B．受欺诈或者受胁迫 环境变量 一．用牛顿法求函数 2214121)2()2(),(x x x x x f -+-= 的极小值点坐标（迭代二次）。 解 初始点T x ]2,3[0 = 则初始点处的函数梯度、海森矩阵及其逆矩阵为 ?? ????=??????---+-=?42)2(4)2(2)2(4)(21213 1 0x x x x x x f ????? ?--=??????--+-=?844148442)2(12)(21 02x x f ???? ??? ???=?=487241241121 )]([1 02x f 代入牛顿法迭代公式，得 T x f x f x x ? ? ? ???=??-=34,38)()]([0 1 2 1 - ??? ?????=??????---+-=?02732)2(4)2(2)2(4)(212 1311x x x x x x f 代入牛顿法迭代公式，得 ?? ? ???=??-=26.152.2)()]([1 1 12 1 2 x f x f x x - 二、分析比较牛顿法、阻尼牛顿法、共轭梯度法、变尺度法和鲍威尔法的特点，找出前四种方法的相互联系。 比较牛顿法：牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。 阻尼牛顿法：可以看出原始牛顿法就相当于阻尼牛顿法的步长因子取成固定值1的情况。阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。 这类方法的主要缺点计算复杂，工作量大，要求计算机存储量大 共轭梯度法：共轭方向主要是针对二次函数的，但也可以用于一般非二次函数。共轭方向法是二次收敛的，计算程序简单，存储量相对较少 变尺度法：只需用到函数的一阶梯度；下降算法，故收敛全局；计算量小（不需要求矩阵逆）；一般可以达到超线性收敛（速度快） 鲍威尔法：多维无约束优化算法是在无约束优化算法之一，首先选取一组共轭方向，从某个初始点出发，求目标函数在这些方向上的极小值点，然后以该点为新的出发点，重复这一过程直到获得满意解，其优点是不必计算目标函数的梯度就可以在有限步内找到极值点。 三、已知约束优化问题minf(x)=(x 1-2)2+(x 2-x 1)2 1．二元可满足性问题 2SAT 例：给定布尔变量的一个有限集合{}n u u u U ,,,21 =及定义其上的子句{}m c c c C ,,,21 =，其中m k c k ,,2,1,2|| ==。 问：是否存在U 的一个真赋值，使得C 中所有的子句均被满足？ 证明： 2SAT 是P －类问题。为叙述方便，采用数理逻辑中的“合取式”表达逻辑命题，于是 ∏∏==+==∧∧∧=m k k k m k k m y x c c c c C 1121)( 其中j i c c ?表示逻辑“与”，k k y x +表示逻辑“或”，k k y x ,是某个j u 或i u 。 考虑表达式∏=+=m k k k y x C 1)(，如果有某个i i k k u u y x +=+，则在乘积式中可以去掉该子句：)(\'i i u u C C +=，可见C 与'C 的可满足性是等价的。所以我们可以假定C 中不含有形如i i u u +的子句。注意到此时C 中的子句个数不会超过)1(-n n 。 如果逻辑变量n u 或它的非n u 在C 的某个子句中出现，我们将C 表示成 )())(()(11h n n k n n z u z u y u y u G C ++++?= （1） 其中G 是C 的一部分子句，而且不出现逻辑变量i u 或它的非i u 。令 ∏≤≤≤≤+? =h j k i j i z y G C 1,1)(' （2） (2)式中不再含有变量n u 和它的非n u 。记{}121,,,'-=n u u u U 。如果存在U 的真赋值，使得C 满足，在'U 也一定满足。 因为如果n u 取真值，则所有的j z 必然取真值；n u 取假值，所有的i y 必然都取真值，不管那中情况，'C 的乘积部分必然取真值。反之，假设存在'U 的真赋值，使得'C 满足。若有某个i y 取假值，则所有的j z 必然取真值，此时令n u 取真值，得到U 的真赋值，使得C 满足。若有某个j z 取假值，则令n u 取假值，得到U 的真赋值，使得C 满足。如果所有的i y 和j z 都取真值，n u 取假值得到U 的真赋值，使得C 满足。 算法设计课程习题答案 第一章 1-1什么是算法？它与计算过程和程序有什么区别？ 算法是指求解一个问题所需要的具体步骤和方法。它是指令的有限序列。算法有一系列明确定义的基本指令序列所描述的，求解特定问题的过程，它能够对合法的输入，在有限时间内产生所要求的输出，取消有穷性限制则是计算过程；而程序是算法的描述。 1-11使用归纳法证明汉诺塔函数的正确性。 用数学归纳法证明汉诺塔函数对任何n （即n 可以是任何正整数）有解。 （1）当盘子数n =1时，只需直接将此盘从A 柱搬到C 柱即可。 （2）现假设n =k 时有解，即可以将k 个盘子（在不违反规则的情况下）从一个源柱，通过一个中间柱移到目的柱上。 （3）现在证明n =k +1时也有解。开始时A 柱上的k +1个盘子可以看成由k 个盘和最底下的一个最大盘组成。根据归纳假设这k 个盘可以（在不违反规则的情况下）通过C 柱移到B 柱上（在这k 个盘的移动过程中，最大盘可以看成不存在）。完成这一大步后，只要将A 柱上的最大盘直接搬到C 柱上。再根据归纳假设B 柱上的这k 个盘可以（在不违反规则的情况下）通过A 柱移到C 柱上。 至此证明结束。 第二章 2-8确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。 （1）程序步为n log 1+画线语句的执行次数为log n ????。(log )n O 。划线语句的执行次数 应该理解为一个整体。 （2）画线语句的执行次数为 111 (1)(2)16 j n i i j k n n n ===++= ∑∑∑。3 ()n O 。 （3）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为 2(2)4 n +。2 ()n O 。 2-11设有)(f n 和)(n g 如下所示，分析)(f n 为))((n g O 、))((n g Ω还是))((n g Θ。 (1) 当3n ≥时，3 log log n n n <<，所以 ()20log 21f n n n n =+<， 3()log 2g n n n n =+>。可选 21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 (2) 当4n ≥ 时，2 log log n n n <<，所以2 2 ()/log f n n n n =<， 2 2 ()log g n n n n =≥。可选 1c =，04n =。对于 0n n ≥，2 ()()f n n cg n <≤，即 ()(())f n g n =O 。 票据法练习题及答案 正误判断题41 1、保证不得附有条件；附有条件的，不影响对汇票的保证责任。（对） 2、汇票上不必记载“无条件支付的委托”的字样。（错） 3、本票的出票人必须具有支付本票金额的可靠资金来源，并保证支付。（对） 4、无民事行为能力人在票据上签章的，其签章无效，而且因此影响其他签章的效力。（错） 5、本票的出票人资格必须由中国人民银行审定。（对） 6、开立支票存款帐户和领用支票，应当有可靠的资信，并存入一定的资金。（对） 7、背书指在票据背面或粘单上记载有关事项并签章的票据行为。（对） 8、汇票是指出票人签发的，委托付款人在见票时或在指定日期无条件支付确定的金额给收款人或持票人的票据。（对） 9、支票记载了有害记载事项的，支票无效。（对） 10、票据抗辩指票据债务人根据法律规定对票据债权人拒绝履行义务的行为。（对） 11、票据权利是指持票人为取得票据金额，依法所附予的可以对票据债务人行使的权利。（对） 12、我国《票据法》将票据分为汇票、本票和支票三种。（对） 13、支票在出票时有三个当事人：出票人，收款人，付款人。（对） 14、票据法是规定票据的种类、签发、转让和票据当事人的权利、义务等内容的法律规范的总称。（对） 15、支票就是出票人委托银行或其他法定金融机构于见票时无条件支付一定金额给收款人的票据。（对） 16、汇票在出票时有三个当事人：出票人，收款人，付款人。（对） 17、票据当事人分为基本当事人与非基本当事人。（对） 18、本票的基本当事人有出票人与收款人。（对） 19、汇票与支票的基本当事人有出票人、付款人与收款人。（对） 20、票据非基本当事人是在票据发出之后通过其他票据行为而加入到票据关系中的当事人。（对） 21、票据的基本当事人是随出票行为而出现的当事人。（对） 22、票据关系是指基于票据行为所产生的债权债务关系，或称权利义务关系。（对） 23、所谓票据关系的当事人，是指享有票据权利，承担义务的法律关系主体。（对） 24、非票据关系分为票据法上的非票据关系与民法上的非票据关系。（对） 25、票据法上的非票据关系是由票据法直接规定的、与票据行为相联系但又不是由票据行为本身所发生的权利义务关系。（对）26、汇票就是出票人委托他人于到期日无条件支付一定金额给收款人的票据。（对） 课程名称： 现代设计方法 一、 单选题 ( 每题1分，共10题，共10分，下列各小题备选答案中，只有一个符合题意的答案。多选、错选、不选均不得分 ) 1. 参数化绘图在定义图形时关键是利用了图形的（ ） A ．相似性 B ．多样性 C ．个别性 D ．特殊性 2. 下列设备不属于CAD 作业输入设备的，有（ ） A ．绘图仪 B ．键盘 C ．数字化仪 D ．光笔 3. 二维图形比例变换矩阵中?? ????=d a T 00，可有（ ） A.a=0,d=1 B. a=1,d=0 C. a=d=1 D. a=d=0 4. 内点罚函数法的特点是（ ） A.能处理等式约束问题 B.初始点必须在可行域内 C. 初始点可以在可行域外 D.后面产生的迭代点序列可以在可行域外 5. 对于极小化F(x)，而受限于约束g μ(x)≤0(μ= 0,1,2,…,m)的优化问题，其内点罚函数表达式为（ ） A.∑=-=Φm k k X g r X F r X 1)()()(/1)(),(μμ B.∑=+=Φm k k X g r X F r X 1)()()(/1)(),(μμ C.∑=-=Φm k k X g r X F r X 1)()()](,0m ax[)(),(μμ D.∑=-=Φm k k X g r X F r X 1)()()](,0m in[)(),(μμ 6. 设F (X )为区间(0,3)上的单峰函数，且F (1)=2、F (2)=1.5，则可将搜索区间(0,3)缩小为（ ） A ．(0,2) B ．(1,2) C ．(2,3) D ．(1,3) 7. 标准正态分布是定义为（ ） A.μ＝1，σ＝0.5的正态分布 B.μ＝1，σ＝1的正态分布 C.μ＝0，σ＝1的正态分布 D.μ＝0.5，σ＝1的正态分布 8. 抽取100只灯泡进行实验，灯泡工作到50小时有12只损坏，工作到70小时有20只损坏，从50小时到70小时这段时间内灯泡的平均失效密度是（ ） A.0.006 B.0.004 C.0.01 D.0.12 9. 当转换开关的可靠度为1时，非工作冗余系统的可靠度为R1, 工作冗余系统的可靠度为R2，则R1与R2之间的关系为（ ） A. R1＜R2 B. R1＞R 2 C. R1= R2 D. R1≤R2 10. 设试验数为N 0，累积失效数为N f (t)，仍正常工作数N s (t)，则存活频率是指（ ） A ．0) (N t N f B ．0)(N t N s C ．)()(t N t N f s D ．) ()(t N t N s f 一、判断题 1、票据是一种特殊有价证券，所以只能适用专门的票据法，证券法的规则对它均不能适用。（错） 2、票据的种类和名称是法定的，任何人不能创设和改变票据法规定之外的票据种类和名称。（对） 3、甲开出一张以乙为收款人，丙为保证人的即期汇票，但甲未在汇票上签章，则乙在付款银行拒绝付款后，亦不得向丙主张票据权利。（对） 4、持票人因超过票据权利时效或者因票据记载事项欠缺而失票据权利的，并不影响其再行向出票人或者承兑人返还和支会票据金额相当的利益。（错） 5、因税收、继承、赠与可以依法无偿取得票据，不受给付对价的限制，但所享有的票据权利不得优于其前手。（对） 二、单项选择题 1、由银行以外的人作为出票人并由银行承兑付款的汇票是( B ) A.银行汇票 B.商业承兑汇票 C.银行本票 D.银行承兑汇票 2、依据票据法原理，票据被称为无因证券，其含义是指（C）。票据的持票人行使票据权利时，无需说明其取得票据的原因，只要占有票据就可以行使票据权利。至于取得票据的原因，持票人无说明的义务，债务人也无审查的权利，即使取得票据的原因关系无效，对票据关系也不发生影响。 A.取得票据无须合法原因 B.转让票据须以向受让方交付票据为先决条件 C.占有票据就能行使票据权利，不问占有原因和资金关系 D.当事人发行、转让、背书等票据行为须依法定形式进行 3、票据的基础关系是指（ C）。 A.交易关系和债务关系 B.出票人与持票人之间基于票据行为而发生的债权债务关系 C.票据收款人与付款人之间的关系 D.票据的签发、取得和转让等当事人之间形成的基本票据关系 4、张某偷盗李某的一张汇票后悔悟，将票据返还给李某，这种关系属于( C) A.票据关系 B.民法上的票据关系 C.非票据关系 D.票据利益返还关系 5、因票据关系违法或违约的持票人是（ B ）。 A.无权利持票人 B.瑕疵权利持票人 C.完整权利持票人 D.票据权利人 6、我国票据法对空白票据采取的立场是（B）。 A.允许商业承兑汇票签发有限空白票据 B.允许支票签发有限空白票据 现代设计方法试题 一、单项选择题(本大题共20小题。每小题1分。共20分) 1．CAD 一词已经成为世界通用的名词，它是指（ A ） A ．计算机辅助工程 B ．计算机辅助制造 C 计算机辅助设计 D ．计算机辅助工艺规程设计 2．实验测试了自变量为3，4，5，6，7，8时的函数值，现要用抛物线插值法计算处的函数值，选择下列哪组自变量及其对应的函数值进行插值计算较为合理（ C ） A ．3，4，5 B ．4，5，6 C ．5，6，7 D ．6，7，8 3．设备坐标系的维数一般为（ B ） A ．一维 B ．二维 C 三维 D ．四维 4．将平面图形沿X 方向平移10个单位，沿Y 方向平移15个单位，其坐标变换矩阵为（ A ） A ．??????? ???11510010001 B ．??????????--11510010001 C ．???? ? ?????101001500010D ．???? ??????10 10015000 1 5．在消阴处理中，进行极大／极小检验，如果两个物体的投影不满足极大／极小条件，则两个物体之间（ D ） A ．相互完全遮挡 B ．部分相互遮挡 C ．相互不遮挡 D ．遮挡关系不确定 6．若函数F(x)在Dl 上具有连续二阶导数(D 是Dl 内部的凸集)，则F(x)为D 上的凸函数的充分必要条件是F(x)的Hessian 矩阵（ C ） A ．半正定 B ．正定 C ．半负定 D ．负定 7．对约束优化问题，设计变量的选择（ C ） A ．可以在可行域中 B ．不允许在可行域中 C ．只允许在可行域中 D ．不一定在可行域中 8．要将一个有约束问题的求解转化为一系列无约束问题的求解，可以选择（ C ） A ．复合形法 B ．简约梯度法 C ．罚函数法 D ．共轭梯度法 9．在解决线性规划问题时，首选的优化方法为（ B ） A ．外点罚函数法 B ．单纯形法 C ．拟牛顿法 D ．变尺度法 10．当目标函势沩凸函数，约『束函彭嘣黜函数时，K —T 条件是约束优化问题取得极值的（ D ） A ．必要条件 B ．充分条件 C ．一般条件 D ．充分必要条件 11．有限元分析中，下列单元属于二维单元的是（ D ） A ．六面体单元 B ．四面体单元 C ．杆单元 D ．三角形单元 12．用有限元方法求解问题获得的解属于（ A ） A ．近似解 B ．精确解 C ．解析解 D ．半解析解 13．采用杆单元进行平面刚架有限元分析，杆单元的一端具有（ B ） A ．两个自由度 B ．三个自由度 C ．四个自由度 D ．六个自由度 14．某刚架单元两节点对应的总体编码为5和3，则局部座标系下的单元刚度系数k 在总体刚度矩阵中的位置为（ D ） A ．第5行第3列 B ．第14行第3列 C ．第5行第14列 D ．第14行第14列 1 5．在平面应变问题中，沿轴线方向（ C ） A ．应变、应力都为零 B ．应力为零，但应变不为零 C ．应变为零，但应力不为零 D ．应变、应力都不为零 16．若产品的平均寿命等于失效率的倒数则产品的寿命服从（ C ） A ．正态分布 B ．泊松分布 C ．指数分布 D ．二项分布 17．在平均安全系数不变的情况下，由于强度(或应力)的分散度增大会使零件的可靠度（ A ） A ．降低 B ．提高 C ．不变 D ．无法确定 18．当系统中任何—个零件发生故障都会导致整个系统失效，该系统是（ A ） A ．串联系统 B ．冗余系统 C ．表决系统 D ．非工作冗余系统 19．并联系统的可靠度比组成该系统的零件的可靠度（ B ） A ．底 B ．高 C ．相等 D ．不确定 20．产品工作到t 时刻后的单位时间内发生失效的概率称为（ D ） A ．平均寿命 B ．平均失效密度 C ．平均可靠度 D ．平均失效率 二、多项选择题(本大题共5小题。每小题2分．共10分) 21．下列设备属于CAD 的输入设备的，有（ BCE ） A ．显示器 B ．扫描仪 C ．键盘 D ．绘图仪 E ．光笔 22．通过矩形窗口与矩形视区的匹配，可以实现图形的（ ABD ） A ．放大 B ．缩小 C ．锗切 D ．摇视 E 平移 23．下列方法中属于利用目标函数的导数构造搜索方向的优化方法有（ BE ） A ．坐标轮换法 B ．梯度法 C ．单纯形 D ．Powell 法 E ．变尺度法 24．单元刚度矩阵具有（ ACE ） A ．奇异性 B ．正定性 C ．分块性 D ．稀疏性 E ．对称性算法设计与分析习题答案1-6章
最新历年票据法自学考试试题及答案
现代设计方法习题答案
算法设计与分析C++语言描述(陈慧南版)课后答案
票据法试题及答案
现代设计方法试卷1及答案
最优化理论与算法(第八章)
现代设计方法-习题集(含答案)
算法设计与分析习题答案1-6章
票据法测试题及参考答案
现代设计方法答案
算法分析习题参考答案第八章
算法设计课程习题答案
票据法练习题及答案
现代设计方法试卷及答案
票据法模拟题及答案
现代设计方法试题及答案
相关主题
文本预览