《算法分析与设计》期末复习题
一、选择题
1.算法必须具备输入、输出和( D )等4个特性。
A.可行性和安全性 B.确定性和易读性
C.有穷性和安全性 D.有穷性和确定性
2.算法分析中,记号O表示( B ),记号Ω表示( A )
A.渐进下界
B.渐进上界
C.非紧上界
D.紧渐进界
3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台
计算机上实现并完成概算法的时间为t秒。现有另一台计算机,其运行速度为第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?( B )解题方法:3*2^n*64=3*2^x
A.n+8 B.n+6
C.n+7 D.n+5
4.设问题规模为N时,某递归算法的时间复杂度记为T(N),已知
T(1)=1,T(N)=2T(N/2)+N/2,用O表示的时间复杂度为( C )。
A.O(logN) B.O(N)
C.O(NlogN) D.O(N2logN)
5.直接或间接调用自身的算法称为( B )。
A.贪心算法 B.递归算法
C.迭代算法 D.回溯法
6.Fibonacci数列中,第4个和第11个数分别是( D )。
A.5,89 B.3,89
C.5,144 D.3,144
7.在有8个顶点的凸多边形的三角剖分中,恰有( B )。
A.6条弦和7个三角形 B.5条弦和6个三角形
C.6条弦和6个三角形 D.5条弦和5个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的
( B )。
A.重叠子问题 B.最优子结构性质
C.贪心选择性质 D.定义最优解
9.下列哪个问题不用贪心法求解( C )。
A.哈夫曼编码问题 B.单源最短路径问题
C.最大团问题 D.最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是( B )。
A.备忘录法 B.动态规划法
C.贪心法 D.回溯法
11.下列算法中不能解决0/1背包问题的是( A )。
A.贪心法 B.动态规划
C.回溯法 D.分支限界法
12.下列哪个问题可以用贪心算法求解( D )。
A.LCS问题 B.批处理作业问题
C.0-1背包问题 D.哈夫曼编码问题
13.用回溯法求解最优装载问题时,若待选物品为m种,则该问题
的解空间树的结点个数为()。
A.m! B.2m+1
C.2m+1-1 D.2m
14.二分搜索算法是利用( A )实现的算法。
A.分治策略 B.动态规划法
C.贪心法 D.回溯法
15.下列不是动态规划算法基本步骤的是( B )。P44
A.找出最优解的性质 B.构造最优解
C.算出最优解(应该是最优值) D.定义最优解
16.下面问题( B )不能使用贪心法解决。
A.单源最短路径问题 B.N皇后问题
C.最小花费生成树问题 D.背包问题
17.使用二分搜索算法在n个有序元素表中搜索一个特定元素,在
最好情况和最坏情况下搜索的时间复杂性分别为( A )。P17 A.O(1),O(logn) B.O(n),O(logn) C.O(1),O(nlogn) D.O(n),O(nlogn)
18.优先队列式分支限界法选取扩展结点的原则是( C )。
P162
A.先进先出 B.后进先出
C.结点的优先级 D.随机
19.下面不是分支界限法搜索方式的是( D )。P161
A.广度优先 B.最小耗费优先
C.最大效益优先 D.深度优先
20.分支限界法解最大团问题时,活结点表的组织形式是
( B )。
A.最小堆 B.最大堆
C.栈 D.数组
21.下列关于计算机算法的描述不正确的是(C)。P1
A.算法是指解决问题的一种方法或一个过程
B.算法是若干指令的有穷序列
C. 算法必须要有输入和输出
D.算法是编程的思想
22.下列关于凸多边形最优三角剖分问题描述不正确的是
( A )。
A.n+1个矩阵连乘的完全加括号和n个点的凸多边形的三角剖
分对应
B.在有n个顶点的凸多边形的三角剖分中,恰有n-3条弦
C.该问题可以用动态规划法来求解
D.在有n个顶点的凸多边形的三角剖分中,恰有n-2个三角形23.动态规划法求解问题的基本步骤不包括( C )。P44
A.递归地定义最优值
B.分析最优解的性质,并刻画其结构特征
C.根据计算最优值时得到的信息,构造最优解 (可以省去的) D.以自底向上的方式计算出最优值
24.分治法所能解决的问题应具有的关键特征是( C )。P16
A.该问题的规模缩小到一定的程度就可以容易地解决
B.该问题可以分解为若干个规模较小的相同问题
C.利用该问题分解出的子问题的解可以合并为该问题的解
D.该问题所分解出的各个子问题是相互独立的
25.下列关于回溯法的描述不正确的是( D )。P114
A.回溯法也称为试探法
B.回溯法有“通用解题法”之称
C.回溯法是一种能避免不必要搜索的穷举式搜索法
D.用回溯法对解空间作深度优先搜索时只能用递归方法实现
26.常见的两种分支限界法为( D )。P161
A. 广度优先分支限界法与深度优先分支限界法;
B. 队列式(FIFO)分支限界法与堆栈式分支限界法;
C. 排列树法与子集树法;
D. 队列式(FIFO)分支限界法与优先队列式分支限界法;
二、填空题
1.f(n)=3n2+10的渐近性态f(n)= O( n2 ),
g(n)=10log3n的渐近性态g(n)= O( n )。
2.一个“好”的算法应具有正确性、可读性、健壮性
和高效率和低存储量需求等特性。
3.算法的时间复杂性函数表示为 C=F(N,I,A) ,分析算法复杂性
的目的在于比较求解同意问题的两个不同算法的效率的效率。
4.构成递归式的两个基本要素是递归的边界条件和递归的定义。
5.单源最短路径问题可用分支限界法和贪心算法求解。
6.用分治法实现快速排序算法时,最好情况下的时间复杂性为
O(nlogn) ,最坏情况下的时间复杂性为 O(n^2) ,该算法所需的时间与运行时间和划分两方面因素有关。P26
7.0-1背包问题的解空间树为完全二叉树;n后问题的解空间树为排
列树;
8.常见的分支限界法有队列式(FIFO)分支限界法和优先队列式分支限
界法。
9.回溯法搜索解空间树时常用的两种剪枝函数为约束函数和剪枝
函数。
10.分支限界法解最大团问题时,活结点表的组织形式是最大
堆;分支限界法解单源最短路径问题时,活结点表的组织形式是最小堆。
三、算法填空题
1. 递归求解Hanoi 塔问题/阶乘问题。
例1 :阶乘函数n! P12 阶乘的非递归方式定义: 试写出阶乖的递归式及算法。
递归式为: 边界条件 递归方程
递归算法:
int factorial (int n)
{ if (n==0) return 1; 递归出口
return n * factorial (n-1); 递归调用
}
例2:用递归技术求解Hanoi 塔问题,Hanoi 塔的递归算法。P15
其中Hanoi (int n, int a, int c, int b)表示将塔座A 上的n 个盘子移至塔座C ,以塔座B 为辅助。Move(a,c)表示将塔座a 上编号为n 的圆盘移至塔座c 上。
void hanoi (int n, int a, int c, int b)
{
if (n > 0)
{
hanoi(n-1, a, b, c);
move(a,c);
hanoi(n-1, b, c, a);
1
2)2()1(!???-?-?= n n n n 0
0)!1(1!>=???-=n n n n n
}
}
2.用分治法求解快速排序问题。
快速排序算法 P25 、作业、课件第2章(2)42页-50页template
void QuickSort (Type a[], int p, int r)
{
if (p int q=Partition(a,p,r); QuickSort (a,p,q-1); QuickSort (a,q+1,r); } } Partition函数的具体实现 template int Partition (Type a[], int p, int r) { int i = p, j = r + 1; Type x=a[p]; // 将< x的元素交换到左边区域 // 将> x的元素交换到右边区域 while (true) { while (a[++i] while (a[- -j] >x); if (i >= j) break; Swap(a[i], a[j]); } a[p] = a[j]; a[j] = x; return j; } 3.用贪心算法求解最优装载问题。 最优装载问题 P95 课件第4章(2)第3-8页 template void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i <= n; i++) x[i] = 0; for (int j = 1; j <= n && w[t[j]] <= c; j++) {x[t[i]] = 1; c -= w[t[j]];} } 4.用回溯法求解0-1背包/批处理作业调度 /最大团问题,要会画解空间 树。 例1:用回溯法求解0-1背包P133课件第5章(2)第24-38页 template class Knap { private: Typep Bound(int i); //计算上界 void Backtrack(int i); Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最优价值 }; void Knap { if(i>n) { bestp=cp; return; } if(cw+w[i]<=c) //进入左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp) //进入右子树 Backtrack(i+1); } Typep Knap { Typew cleft=c-cw; //剩余的背包容量 Typep b=cp; //b为当前价值 //依次装入单位重量价值高的整个物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } if(i<=n) //装入物品的一部分 b+=p[i]*cleft/w[i]; return b; //返回上界 } class Object //物品类 { friend int Knapsack(int *,int *,int,int); public: int operator <(Object a) const { return (d>=a.d); } int ID; //物品编号 float d; //单位重量价值 }; Typep Knapsack( Typep p[],Typew w[],Typew c,int n) { //为Typep Knapsack初始化 Typew W=0; //总重量 Typep P=0; //总价值 Object* Q=new Object[n]; //创建物品数组,下标从0开始 for(int i=1;i<=n;i++) //初始物品数组数据 { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) //能装入所有物品 return P; if(W<=c) //能装入所有物品 return P; QuickSort(Q,0,n-1); //依物品单位重量价值非增排序 Knap K.p=new Typep[n+1]; K.w=new Typew[n+1]; for(int i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; K.Backtrack(1); delete[] Q; delete[] K.w; delete[] K.p; return K.bestp; } 例2:批处理作业调度课件第5章(2)P2-5问题描述,课本P125-127 解空间:排列树 算法描述: class Flowshop { static int [][] m, // 各作业所需的处理时间 [] x, // 当前作业调度 [] bestx, // 当前最优作业调度 [] f2, // 机器2完成处理时间 f1, // 机器1完成处理时间 f, // 完成时间和 bestf, // 当前最优的完成时间和 n; // 作业数 static void Backtrack(int i) { if (i > n) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; } else for (int j = i; j <= n; j++) { f1+=m[x[j]][1];//第j个作业在第一台机器上所需时间 f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2]; f+=f2[i]; if (f < bestf) //约束函数 { Swap(x[i], x[j]); Backtrack(i+1); Swap(x[i], x[j]); } f1 - =m[x[j]][1]; f - =f2[i]; } } 例3:最大团问题,要会画解空间树。 class Clique { friend int MaxClique(int **,int [],int); public: void Print(); //输出最优解 private: void Backtrack(int i); int **a; //图G的邻接矩阵,下标从1开始 int n; //图G的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前团的顶点数 int bestn; //当前最大团的顶点数 }; void Clique::Backtrack(int i) { if(i>n) { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn; return;} //判断第i个顶点是否与已选顶点都有边相连 int OK=1; for(int j=1;j if(x[j]&&a[i][j]==0) //i与当前团中的顶点无边相连 { OK=0; break; } //只要与当前团中一个顶点无边相连,则中止 if(OK) //进入左子树 { x[i]=1; cn++; Backtrack(i+1); x[i]=0; cn--; } if(cn+n-i>bestn) //如有可能在右子树中找到更大的团,则进入右子树 { x[i]=0; Backtrack(i+1); } } 计算时间:O(n2n) 四、简答题 1.请简述使用动态规划算法解题的基本步骤。P44 动态规划的设计分为以下4个步骤: (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息,构造最优解。 2.简述动态规划方法与分治法的异同。P44 相同点:动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。 不同点:分治法的子问题互相独立且与原问题相同。与分治法不同的是,适合于动态规划求解的问题,经分解得到的子问题往往不是互相独立的。也就是各个子问题包含公共的子子问题。 3.试比较Prim算法与Kruskal算法的异同。105-P107 相同点:Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法都可以看作是应用贪心算法构造最小生成树的例子。利用了最小生成树性质。 不同点: Prim(普里姆)算法:在这个过程中选取到的所有边恰好构成G的一棵最小生成树T,T中包含G的n-1条边,且不形成回路。 Kruskal(克鲁斯卡尔)算法:是构造最小生成树的另一个常用算法。该算法不是通过扩充连通子集来进行贪心选择。而是通过选择具有最小权的边的集合来进行贪心选择。在选择的同时可以进行连通操作以便形成生成树。 4.请简述分支限界法的搜索策略。P161 课件第6章(1)第6页 (1)分支限界法以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 (2)每一个活结点只有一次机会成为扩展结点。 (3)活结点一旦成为扩展结点,就一次性产生其所有儿子结点。 (4)儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。 (5)从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 5.试比较分支限界法与回溯法的异同。P161 课件第6章(1)第5页 不同点: (1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。 (2)搜索方式:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 五、算法应用题 1.用动态规划求解凸多边形最优三角剖分问题。 三角剖分的结构及其相关问题P61 (1)语法树与完全加括号方式 一个表达式的完全加括号方式相应于一棵完全二叉树,称为表达式的语法树。 例如,完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。 (2)语法树与凸多边形三角剖分 凸多边形P={v0,v1,…vn-1}的三角剖分也可以用语法树表示。 如图:根结点是边v0v 6(可以任选)。其他边则是语法树的叶子节点。 v0v 6是三角形v0v3v 6的一条边。 2、三角剖分与矩阵连乘P61 (1)一般来说,凸多边形的三角剖分和有n-1个叶节点的语法树存在一一对应关系。 (2)N个矩阵连乘的完全加括号和有n个叶节点的语法树也存在一一对应关系。 (3)所以,n个矩阵连乘的完全加括号和有n+1个节点的凸多边形的三角剖分也存在一一对应关系。 (4)矩阵连乘积中A1 A2 …An中的每个矩阵Ai对应于凸(n+1)边形中的一 条边vi-1vi。三角剖分中的一条弦vivj,i (5)矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的特殊情况。 课后习题(第3章小结**) 对于如下矩阵链 P={10,100,5,50,30,20,60,45,50},请按照构造其最优完全加括号方式,并列出相应的语法树和最优三角剖分图。 2.用贪心算法求解活动安排问题/最小生成树问题/哈夫曼编码问题。 贪心算法求解活动安排问题 例:设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下: 最小生成树问题 P103-P105 哈夫曼编码问题,前缀码二叉树表示法 例子: 图a:与固定长度编码对应的树(叶子高度一致) 图b:与可变长度编码对应的树(叶子高度不一致) 3.用回溯法求解0-1背包问题/最优装载问题。 用回溯法求0-1背包问题。P133, 实例:n=5,M=50 得 分 阅卷人 2009-2010学年第一学期《电路》期末考试试卷 1、 填空题(每空1分,共20分) 1. 一阶电路的三要素法中的三个要素是:_ ________、_________ _、____________。 2. 理想变压器可以改变:________ __、___________和___ ________。 3. 基尔霍夫电流定律时域形式和相量形式分 别为:_____________、_ _____________。 4. 通过改变_________、____ ______、___________ _可以使RLC 串联电路发生谐振。 5. 对于一个具有n个节点,b条支路的电路, 可写出_____个独立的KCL方程,_ ____个独立的KVL方程。 6. 在分析具有理想运放的电路时,有两个很 重要的规则,分别是_________ 和__________。 7.试指出图1所示元件中电流的真实方向: ,电压的真实方向 ,功率 。 8.图2所示电路中a 点的电压(位)为 V 。 图1 图2 9.含源电阻二端网络N 及其伏安特性如图3所示,其戴维南等效电路中U s =_____V,R s =______Ω。 得分阅卷 人图3 10.图4所示电路中,电压源、受控源、2Ω电阻所吸收的功率依次 为:_________、__________、______ ______。 图4 2、 选择题(3×7=21分) 1.图5所示电路在t = 0时,开关打开,电路的 时间常数为( )。 A.2s B. 3s C. 1/2s D. 1/3s 图5 图6 图7 2.图6所示电路中,,当()时获得最大功率。 A. B. C. D. 3.图7所示电路中的U为( ) A. 14V B. 10V C. 20V D. 12V 4.已知一个Ω的阻抗上流过电流,则其电压为( )V。 A. B. C. D. 5.受控源k中,k为() A.电压转移比 B.电流转移比C.转移电导 D.转移电阻 6.关联参考方向时,线性电感的韦安特性曲线为( )。 A.过一、四象限的直线 B.过二、三象限的直线 C.过一、三 象限的直线 D.过一、二象限的直线 7.恒定电流2A流过初始储能为零的1F电容,历时5s,则在这段时 间内电容获得能量为( )。 c期末考试试题及答案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 AutoCAD 试卷 一、 单项选择 1、AutoCAD 默认扩展名是 A 、dwt B 、dwg C 、bak D 、dxf 答案:B 2、在CAD 中,以下哪个命令可用来绘制横 平竖直的直线 A 、栅格 B 、捕捉 C 、正交 D 、对象捕捉答案:C 3、按哪个键可切换文本窗口和绘图窗口 A 、F2 B 、F8 C 、F3 D 、F5答案:A 4、默认情况下,命令提示行显示为几行 A 、3 B 、5 C 、2 D 、8答案:A 5、在CAD 中为一条直线制作平行线用什么命令 A 、移动 B 、镜像 C 、偏移 D 、旋转答案:C 6、在图层特性管理器中不可以设定哪项 A 、颜色 B 、页面设置 C 、线 宽 D 、是否打印答案:B 7、绘制建筑图步骤为 A 、墙线、轴线、门窗 B 、墙线、 门窗、轴线 C 、轴线、门窗、墙线 D 、轴线、 墙线、门窗答案:D 8、哪个命令可用于绘制直线与圆弧的复合 体 A 、圆弧 B 、构造线 C 、多段线 D 、样条曲线答案:C 9、如何在图中输入“直径”符号 A 、%%P B 、%%C C 、%%D D 、%%U 答案:B 10、如果要在一个圆的圆心写一个“A”字,应使用以下哪种对正方式 A、中间 B、对齐 C、中心 D、调整答案:A 11、在哪个层创建的块可在插入时与当前层特性一致 A、0层 B、在所有自动产生的层 C、所有图层 D、新建的图层答案:A 12、一个完整的尺寸由几部分组成 A、尺寸线、文本、箭头 B、尺寸线、尺寸界线、文本、标记 C、基线、尺寸界线、文本、箭头 D、尺寸线、尺寸界线、文本、箭头 答案:D 13、要将图形中的所有尺寸都为原有尺寸的2倍,应设定以下哪项A、文字高度 B、使用全局比例 C、测量单位比例 D、换算单位 答案:B 14、三维模型中哪种模型可以进行布尔运算 A、线框模型 B、实心体模型 C、表面体模型答案:B 15、渲染三维模型时,哪种类型可以渲染出物体的所有效果 A、一般渲染 B、普通渲染 C、照片级真实感渲染 D、照片级光线跟踪渲染答案:D 16、样板文件的括展名是 A、BAK B、SVS C、DWT D、DWG 答案:C 17、以下哪种相对坐标的输入方法是画8个单位的线长 A.8, 0 B.@0,8 C.@0<8 人教版小学一年级数学下册期末 一、填空 学生 1.( )里最大能填几? 10+5>( ) 20+( )<28 69+( ) >60 50-( )<41 23+9>( ) 81+( ) <85 88-( )>79 90+( )<100 45-( ) >40 2.(1)100里面有( )个十,( )个一。 (2)从( )到( )是两位数。 (3)从最大的两位数中减去最大的一位数,差是( )。 (4)6个十2个一再添( )个( )是70。 3、填出各物品的价钱。( 3.50元 5.30元 0.50元 35.00元 ( )元( )角 ( )元( )角 ( )角 ( )元( )角 4、9比59小( ) 78比70大( ) 58比9大( ) 9比80小( ) 5、一个足球40元,一个排球30元,一个足球比一个排球贵( )元。 6、80里面有( )个十;由4个十和8个一组成的数是( )。 十位是5,个位是0,这个数是( )。( )个十是100。 34的十位上是( ),表示( ).个位上是( ),表示( )。 从右边起,第一位是( )位,第( )位是十位,第三位是( )位。 74前面的一个数是( ),后面的一个数是( )。 把这些数从大到小排一排:76,25,60,19,100,82,46 。 ( )>( )> ( )>( )> ( )>( )>( ) 7、用 做成一个 ,数字“6”的对面是数字“( )。”用( ) 个这样的 可以拼出一个大 。 8、5、18个小朋友排队做操,从左数起,小芳排在第9位,从右数起,她排在第( )位。 9、写出78后面连续的四个数:( )、( )、( )、( )。 10、写出4个十位上是5的两位数: 、 、 、 。 11、按顺序填数 二、在合适的答案下面画“√”。 (1)书包的价钱接近30元,足球比30元多得多。 书包的价钱可能是多少元? 足球的价钱可能是多少元? (2) 梨有40个,苹果的个数比梨少得多,苹果苹果可能有多少个? 18个 28个 48个 (3)三(5)班有47人去春游,坐哪辆汽车比较合适? 3 1 6 28元 50元 21元 25元 35元 65元 小明捧一捧花生米,数一数共有 18粒。又捧了一捧黄豆,你猜一猜可能有多少粒? 16粒 20粒 72粒电路期末考试试卷
c期末考试试题及答案完整版
小学一年级下册数学期末复习考试试题
2016矩阵论试题