算法试卷二

05－06学年度第一学期期末考试试卷

1.（30分）证明题：

（1）证明：一个算法在平均情况下的计算时间复杂度为Θ(f(n))，则该算法在最坏情况下所需的计算时间为Ω(f(n))。

（2）;

（3）.

2．（25分）用熟悉的语言描述二分检索算法BINSRCH，并证明BINSRCH的平均计算时间是Θ(log n)。

3．（10分）考虑下列背包问题：

n=7,M=15,(p1,p2,p3,…,p7)=(10,5,15,7,6,18,3),(w1,w2,w3,…,w7)=(2,3,5,7,1,4,1),利用贪心策略求该背包问题的最优解，并计算此时背包中物品的总效益值。4．（10分）设解用定长的元组表示：利用回溯方法求解4皇后问题，并画出求解过程中生成的状态空间树。

5．（15分）设带期限的作业调度问题，作业数n=4,作业罚款值：（p1,p2,p3,p4）=(5,10,6,3),作业截止期限：(d1,d2,d3,d4)=(1,3,2,1),作业处理时间：(t1,,t2,t3,t4)=(1,2,1,1),求这4个作业的一个子集j，使得j中作业都在其截止期限内完成，并使不在j中的作业总的罚款值最小，设解用不定长的元组表示，定义结点的成本和成本的上下界，利用LC分枝限界法求最优解j，画出求解过程中生成的状态空间树，并求出对应于最优解的罚款值。

6．（10分）设有n种不同面值的硬币，各硬币的面值存于数组T(L:n)中,现要用这些面值的硬币找钱，可以使用的各种面值的硬币个数。

（1）当只硬币面值T(1),T(2),…,T(L)时，可找出钱数j的最小硬币个数记为C(i,j),若只用这些硬币面值，找不出钱数j时,可记C(i,j)＝x，给出C(i,j)

的递推及初始化条件，1i n,1j L。

（2）设计一个动态规划算法，对于1j L，计算出所有的C(n,j)：算法中只

允许使用一个长度为L的数组，用L作为变量表示算法的计算时间复

杂性。

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10

0 0 10 10 10 15 15 15 15 15 15 15 15 15 15 15

0 0 10 10 10 15 15 25 25 25 30 30 30 30 30 30

0 0 10 10 10 15 15 25 25 25 30 30 30 30 32 32

0 0 10 10 10 15 15 25 31 31 31 36 36 36 36 38

0 0 10 10 18 18 28 28 31 33 33 43 49 49 49 54

0 0 10 10 18 21 28 31 31 34 36 43 49 52 52 54

07－08学年第一学期05级期中试题

1．（10分）证明：.

2．（10

T(n)=

3．（10分）利用二分检索算法BINSRCH ，分别检索元素x=101，－14是否在数组A ＝(-15,-6,0,7,9,23,54,82,101)中出现，详细描述检索的过程。

4．（10分）给定8个集合

{1},{2},{3},{4},{5},{6},{7},{8},画出执行下列运算后所得到的树表示：

Union(1,2),Union(2,3),Union(4,5),Find(1),Union(2,5),Union(6,7),Union(7,8),

Find(3),Union(3,7)

5．（10分）图示说明寻找多数元素算法对下列数组的执行过程：

（1）（12，4，1，4，4，4，6，4）

（2）（5，7，5，4，8）

6．（10

7．（10分）考虑将MATCHAIN 算法应用于下述5个矩阵链相乘的问题：

M1:2*3 M2:3*6 M3:6*4 M4:4*2 M5:2*7

找出这五个矩阵链相乘最少的标量乘的次数，要求写出过程。

8．（10分）设计一个分治算法，判断两个二叉树是否相等。先用文字描述算法的基本思想，再写出包括输入，输出在内的算法流程。

2010年1月数量方法试题及答案

2010年1月高等教育自学考试中英合作商务管理专业与金融管理专业考试 数量方法 试题 （课程代码：00799） 第一部分 必答题（满分60分） 一、 单项选择题（每小题1分，共20分） 1、2008年某唱歌比赛，九位评委给歌手甲打分如下：8，7.9，7.8，9.5，8.1，7.9，7.8，8，7.9，，则该歌手得 分的众数为 A 、7.8 B 、7.9 C 、8 D 、9.5 2、琼海市在一条高速公路建造的招标过程中共有六个投标，其投标金额（万元）分别为98；100；105；112；130；107，则这些投标金额的极差为 A 、10 B 、15 C 、32 D 、40 3、某交通管理局选择6辆汽车行驶本作样本，得到这些汽车的使用年限为：1；6；3；8；9；3，则汽车使用年限（单位：年）的中位数为 A 、1 B 、3 C 、4.5 D 、5 4、某公司员工的年龄在23-50岁之间，其中年龄在20-30岁之间的员工占全部职工的32%，30-40岁的占40%，则年龄在40岁以上的职工占全部职工的比重为 A 、15% B 、20% C 、25% D 、28% 5、设A 、B 、是两个相互独立的随机事件，若P(A)=0.6，P(AB)=0.3，则P （B ）等于 A 、0.3 B 、0.5 C 、0.7 D 、0.9 6、某全国性杂志社给每个订户邮寄一本广告小册子，并随附一份问卷，杂志社在寄回的问卷中随机抽选50人发给奖品。这家杂志社共收到10000份有效问卷，则某一特定参加者获奖的几率为 A 、0.005 B 、0.04 C 、0.05 D 、0.06 7、离散型随机变量X 的分布率为 则a 等于 A 、1/4 B 、1/3 C 、1/2 D 、2/3 8 A 、0.25 B 、0.26 C 、0.27 D 、0.28 9、若顾客到亚东银行办理储蓄业务所花费的时间（单位：分钟）服从正态分布N （3,1），则一个顾客办理储蓄业务所花费时间不超过5分钟的概率为（用0()φ?表示） A 、0(0.5)φ B 、0(1)φ C 、0(2)φ D 、0(5)φ 10、假定到达某车道入口处的汽车服从泊松分布，每小时到达的汽车平均数为5，则在给定的一小时内，没有汽车到达该入口处的概率为 A 、e-5 B 、e-4 C 、e4 D 、e5 11、设X 与Y 为两个随机变量，则E(X)=6，()1 E Y =-,则(2)E X Y +等于

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分，共20 分)

《算法设计与分析》试卷A

《算法设计与分析》试卷 一．计算题（共25分） 1. 用表示函数f与g之间的关系。（10分，每小题2分） (1) f(n)=10000n g(n)=n-10000 (2) f(n)=2n g(n)=3n/n (3) f(n)=n3log2n g(n)=n2log3n (4) f(n)=log2n g(n)=log3n (5) f(n)=100n+n100 g(n)=n! 2.估计下列算法的时间复杂性的阶。(10分，每小题5分) (1)算法A的时间复杂性为， (2)算法B的时间复杂性为 3. 计算下面算法中count=count+1的执行次数（5分） 算法 COUNT count=0 for i=1 to for j=i to i+5 for k=1 to i2 count=count+1 end for end for end for 二．简答题（共15分） 1. 随机算法分成那几类，各有什么特点？（7分） 2．最大k乘积问题：设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。对于给定的I和k，求出I的最大k乘积。当用动态规划求解该问题时，最优子结构是什么？递归关系式是什么？（8分） 三．算法填空题（共45分，每空3分） 1. 以下是计算x m的值的过程 power ( x, m ) if m=0 then y=_____ (1)_______ else y=_____ (2)_______

装订 线 y=y*y if m 为奇数 then y=x*y

C=multiply( A , B) //计算两个矩阵乘积C=AB。 return C end if end matchain_product 3. 以下是迷宫问题的算法 算法 MAZE 输入：正整数m, n，表示迷宫的数组M[0..m+1, 0..n+1] (迷宫数据存于M[1..m, 1..n]中)，迷宫的入口位置(ix, iy),出口位置(ox, oy)。 输出：迷宫中入口至出口的一条通路，若无通路，则输出no solution。 M[0, 0..n+1]=M[m+1, 0..n+1]=1

数量方法期末试题7卷

绝密★启用前 学院 学年第二学期期末考试 级 专业（ ）《数量方法》试卷 1.受极端值影响最小的离散趋势度量是（ ） A.四分位极差 B.极差 C.标准差 D.变异系数 2.一般用来描述和表现各成分占全体的百分比的图形是（ ） A.条形图 B.饼形图 C.柱形图 D.百分比图 3.将一枚硬币连续抛两次观察正反面出现情况，则样本空间为（ ） A.{正，反} B.{正正，反反，正反} C.{正正，反反，正反，反正} D.{反正，正正，反反} 4.某夫妇按国家规定，可以生两胎。如果他们每胎只生一个孩子，则两胎全是女孩的概率为 （ ） A.16 1 B.81 C.4 1 D.2 1 5.若随机变量Y 与X 的关系为Y=2X+2，如果随机变量X 的数学期望为2，则随机变量Y 的数学期望为（ ） A.4 B.6 C.8 D.10 6.从研究对象的全部单元中抽取一部分单元进行观察研究取得数据，并从这些数据中获得信息，以此来推断全体，称此过程为（ ） A.随机抽样 B.分层抽样 C.系统抽样 D.抽样推断 7.已知变量x 与y 之间存在着正相关关系，则其回归方程可能是（ ） A.x y 85.010?--= B.x y 5.1200?-= C.x y 76.0140?+-= D.x y 08.025?-= 8.由两个不同时期的总量对比形成的相对数称为（ ） A.数量指数 B.质量指数 C.零售价格指数 D.总量指数 9.某足球运动员罚点球的命中率是90％，若让他罚10次点球，他罚中球数的期望值是 （ ） A.1 B.3 C.7 D.9 10.事件A 、B 相互独立，P (A )=0.3，P (B |A )=0.6，则P (A )+P (B )=（ ） A.0. B.0.3 C.0.9 D.1 11.协方差的取值范围是（ ） A.[-1，0] B.[-1，1] C.正数 D.实数 12.设随机变量X 服从二项分布B(20，0.6)，则X 的方差为（ ） A.3.6 B.4.8 C.6.0 D.7.2 13.设X 1，X 2……X 10为来自正态总体N(100，100)的样本，则其样本均值X 服从（ ） A.N(100，100) B.N(10，10) C.N(10，100) D.N(100，10) 14.对于成对观测的两个正态总体均值差的区间估计，可以采用的统计量是（ ） A.t 统计量 B.Z 统计量 C.2χ统计量 D.F 统计量 15.当抽样方式与样本容量不变时，置信区间愈大，则（ ） A.可靠性愈大 B.可靠性愈小 C.估计的效率愈高 D.估计的效率愈低 16.显著性水平α是指（ ） A.原假设为假时，决策判定为假的概率 B.原假设为假时，决策判定为真的概率 C.原假设为真时，决策判定为假的概率 D.原假设为真时，决策判定为真的概率

算法分析与设计试卷

《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。

数量方法试题

数量方法试题 1在一次《数量方法》考试中，某班的平均成绩是80分，标准差是4分，则该班考试成绩的变异系数是 A. 0.05 B. 0.2 C. 5 D. 20 2.对于峰值偏向右边的单峰非对称直方图，一般来说 A. 平均数>中位数>众数 B. 平均数<中位数<众数 C. 平均数>众数>中位数 D. 平均数<众数<中位数 3.将一枚硬币抛掷两次的样本空间Ω={00，01，10 ,11}（用0表示出现正面，用1表示出现反面）。“第一次出现正面”可以表示为 A. {01,11} B. {10,11} C. {00,01} D. {00,11} 4.某夫妇按照国家规定，可以生两胎。如果他们每胎只生一个孩子，则他们有一个男孩和一个女孩的概率为 A. 1/2 B. 1/4 C. 1/8 D. 1/6 5.设A、B、C为任意三个事件，则“这三个事件都发生”可表示为 A. ABC B. ABC C. A∪B∪C D. ABC 6.事件A、B相互对立，P(A)=0.3，P(B –A)= 0.7，则P(AB)= A. 0 B. 0.3 C. 0.4 D. 1 7、2008年某唱歌比赛，九位评委给歌手甲打分如下：8，7.9，7.8，9.5，8.1，7.9，7.8，8， 7.9，，则该歌手得分的众数为 A、7.8 B、7.9 C、8 D、9.5 8、琼海市在一条高速公路建造的招标过程中共有六个投标，其投标金额（万元）分别为98； 100；105；112；130；107，则这些投标金额的极差为 A、10 B、15 C、32 D、40 9、某交通管理局选择6辆汽车行驶本作样本，得到这些汽车的使用年限为：1；6；3；8；9； 3，则汽车使用年限（单位：年）的中位数为 A、1 B、3 C、4.5 D、5 10、某公司员工的年龄在23-50岁之间，其中年龄在20-30岁之间的员工占全部职工的32%， 30-40岁的占40%，则年龄在40岁以上的职工占全部职工的比重为 A、15% B、20% C、25% D、28% 11、设A、B、是两个相互独立的随机事件，若P(A)=0.6，P(AB)=0.3，则P（B）等于 A、0.3 B、0.5 C、0.7 D、0.9 12、某全国性杂志社给每个订户邮寄一本广告小册子，并随附一份问卷，杂志社在寄回的问 卷中随机抽选50人发给奖品。这家杂志社共收到10000份有效问卷，则某一特定参加者获奖的几率为 A、0.005 B、0.04 C、0.05 D、0.06 13 则a等于 A、1/4 B、1/3 C、1/2 D、2/3

2010年04月自考00994《数量方法(二)》历年真题及答案整理版

考试学习软件商城（https://www.wendangku.net/doc/9f12206742.html, ）出品
自考笔记、真题及答案、题库软件、录音课件！
全国 2010 年 4 月自学考试数量方法（二）试题
课程代码：00994
一、单项选择题(本大题共 20 小题，每小题 2 分，共 40 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号 内。错选、多选或未选均无分。 1．有一组数据 99，97，98，101，100，98，100，它们的平均数是( A．98 C．99 B．98.5 D．99.2 C )1-24 C )1-16
2．一组数据中最大值与最小值之差，称为( A．方差 B．标准差 C．全距 D．离差
3．袋中有红、黄、蓝球各一个，每一次从袋中任取一球，看过颜色后再放回袋中，共取球 三次，颜色全相同的概率为( A A．1／9 B．1／3 C．5／9 D．8／9 4．设 A、B、C 为任意三事件，事件 A、B、C 至少有一个发生被表示为( A．A C． B． D．A+B+C D )2-38 )2-53
5．掷一枚骰子，观察出现的点数，记事件 A={1，3，5}，B={4，5，6}，C={1，6}则 C—A=( D )2-39 B．{3，5}
A．{3，5，6} C．{1} D．{6}
自 考 备 考 三 件 宝 ： 自 考 笔 记 、 真 题 及 答 案 、 录 音 课 件 ！
6．已知 100 个产品中有 2 个废品，采用放回随机抽样，连续两次，两次都抽中废品的概率 为( A )2-课本无明确答案
A．
B．
C．
D．
本文档资源由考试真题软件网（https://www.wendangku.net/doc/9f12206742.html,）搜集整理二次制作！

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

自考数量方法(二)历年试题及答案(DOC)

全国2010年4月自考数量方法（二）试题 1．有一组数据99，97，98，101，100，98，100，它们的平均数是( ) A ．98 B ．98.5 C ．99 D ．99.2 2．一组数据中最大值与最小值之差，称为( ) A ．方差 B ．标准差 C ．全距 D ．离差 3．袋中有红、黄、蓝球各一个，每一次从袋中任取一球，看过颜色后再放回袋中，共取球三次，颜色全相同的概率为( ) A ．1／9 B ．1／3 C ．5／9 D ．8／9 4．设A 、B 、C 为任意三事件，事件A 、B 、C 至少有一个发生被表示为( ) A ．A B B ． C B A C ．ABC D ．A+B+C 5．掷一枚骰子，观察出现的点数，记事件A={1，3，5}，B={4，5，6}，C={1，6}则C —A=( ) A ．{3，5，6} B ．{3，5} C ．{1} D ．{6} 6．已知100个产品中有2个废品，采用放回随机抽样，连续两次，两次都抽中废品的概率为( ) A ． 10021002? B ．9911002? C ．1002 D ． 10021002+ 7．随机变量X 服从一般正态分布N(2,σμ)，则随着σ的减小，概率P(|X —μ|<σ)将会( ) A ．增加 B ．减少 C ．不变 D ．增减不定 8．随机变量的取值一定是( ) A ．整数 B ．实数 C ．正数 D ．非负数 9．服从正态分布的随机变量X 的可能取值为( ) A ．负数 B ．任意数 C ．正数 D ．整数 10．设X 1，……X n 为取自总体N(2,σμ)的样本，X 和S 2分别为样本均值和样本方差，则统计量1n S X -服从的分布为( ) A ．N(0，1) B ．2χ (n-1) C ．F(1，n-1) D ．t(n-1) 11．将总体单元在抽样之前按某种顺序排列，并按照设计的规则确定一个随机起点，然后每隔一定的间隔逐个抽取样本单元的抽选方法被称为( ) A ．系统抽样 B ．随机抽样 C ．分层抽样 D ．整群抽样 12．估计量的无偏性是指估计量抽样分布的数学期望等于总体的( ) A ．样本 B ．总量 C ．参数 D ．误差 13．总体比例P 的90％置信区间的意义是( ) A ．这个区间平均含总体90％的值

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

算法分析与设计模拟试卷A

算法设计与分析期末考试模拟试卷 A卷 考试说明： 承诺： 本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。 承诺人：学号：班号： 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。注：本试卷共三大题，共 6 页，满分100分，考试时答案请写在试卷空白处。 一、算法时间复杂性问题（共30分） Part 1. The Time Complexity Of the Algorithm Test 1、试证明下面的定理：[12分] (1) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n)) (2) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n)) 1. Prove the following Theorem [12 marks] (1) if f(n)=O(s(n)) and g(n)=O(r(n)), to prove f(n)+g(n)=O(s(n)+r(n)) (2) if f(n)=O(s(n)) and g(n)=O(r(n))，to prove f(n)*g(n)=O(s(n)*r(n))

2、已知有如下的断言： f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n)) 请你举出一个反例。[8分] 2. Known as the following assertion If f(n)=O(s(n)) and g(n)=O(r(n))，then f(n)-g(n)=O(s(n)-r(n)) 。 Please cite a counter-example [8 marks] 3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A 型计算机的256倍。试求出若在先进的B型机上运行同一算法则在t秒内能求解输入规模为多大的问题？[10分] 3. Assume that in the case of the input size is n, the computing time of the algorithm required is T（n）=3*2n. It would take t seconds to implement the algorithm on Computer A. Computer B is more advanced. The operation ability of Computer B is 256 times of Computer A. If the same algorithm running on Computer B, please find out the input size so that the algorithm would solve in t seconds.[10 marks]

2011年1月数量方法试题及答案

2011年1月高等教育自学考试中英合作商务管理专业与金融管理专业考试 数量方法 试题 （课程代码 00799） （考试时间165分钟，满分100分） 注意事项： 1. 试题包括必答题与选答题两部分，必答题满分60分，选答题满分40分。必答题为一、二、三题，每题20分。选答题为四、五、六、七题，每题20分，任选两题回答，不得多选，多选者只按选答的前两题计分。60分为及格线。 2. 答案全部答在答题卡上。 3. 可使用计算器、直尺等文具。 4. 计算题应写出公式、计算过程；计算过程保留4位小数，结果保留2位小数。 第一部分 必答题（满分60分） （本部分包括第一、二、三题，每题20分，共60分） 一、本题包括1——20二十个小题，每小题1分，共20分。在每小题给出的四个选项中，只有一项符合题目要求，把所选项前的字母填写在括号内。 1. 对于数据6，8，8，9，7，13，8，9，5，12，其众数和中位数之差为 A.-1 B.0 C.1 D.7 2.如果一组全为正值的数据依次为15，20，30和x ，并且这组数据的极差是30，那么x 值应为 A.20 B.25 C.35 D.45 3.下面是一组数据的茎叶图 1 ︱ 8 2 ︱ 2 4 5 3 ︱ 1 该数据组的中位数为 A. 2 B. 4 C. 22 D. 24 4.对于峰值偏向左边的非对称分布，平均数、中位数和众数的大到小关系是 A.平均数、中位数和众数 B.众数、中位数和平均数 C.三者相等 D.中位数、平均数和众数 5.独立抛掷一枚均匀硬币2次，两次都出现国徽的概率是 A. 0 B. 1 C. 21 D.4 1 6.设两点分布的随机变量X ～B （1，0.5），则其方差为 A.0.5 B.0.25 C.0.75 D.1 7.如果随机变量X 的数学期望为2，则Y=3X+4的数学期望为 A.3 B.4 C.7 D.10 8.若~ θ是θ的无偏估计，那么~ θ应满足

2006年1月数量方法真题和答案

2006年1月自考数量方法试题答案 115 2006年1月自考数量方法试题答案 第一部分 必答题（满分60分） 一、本题包括1－20题共二十个小题，每小题1分，共20分。 1． 某公司最近发出了10张订单订购零件，这10张订单的零件数（单位：个）分别为80,100,125,150,180， 则这组数据的中位数是 A ．100 B ．125 C ．150 D ．180 解答：中位数是将一组数按从小到大顺序排列好后恰好居中的一个数，若中间有两个数则求这两个数的平均数。 选：B (本题有些问题!明明只有5个数，确说10张订单!一般来说，如果题目出错了，那么无论回答如何都会得分的!!!) 2． 从某公司随机抽取5个员工，他们的月工资收入（单位：元）分别为：1500,2200, 2300,3600,5400，则他们的平均月工资收入是 A ．2000 B ．2500 C ．3000 D ．3500 解答：平均值问题，将所有的数相加，然后再被5除。 选：C 3． 从某银行随机抽取10个储户，他们的存款总额（单位：万元）分别是：3,7，12,16,17,21,27,29,32,43， 则存款总额的极差是 A ．40 B ．25 C ．17 D ．11 解答：极差是最大值与最小值之差。 选：A 4． 某大学法律专业今年招收10名硕士研究生，他们的年龄分别为21,22,22,23,23,23,23,24,28,31，则入学 年龄的众数是 A ．22 B ．23 C ．24 D ．25 解答：众数是出现次数最多的数。 选：B 5． 某事件发生的概率为 10 1 ，如果试验10次，则该事件 A ．一定会发生1次 B ．一定会发生10次 C ．至少会发生1次 D ．发生的次数是不确定的 解答：选：D 概率的发生总是不确定的。这是练习册上的题。05刚刚考过 6． 一所大学的学生中有35%是一年级学生，26%是二年级学生。若随机抽取一人，该学生不是一年级学 生的概率为 A ．0.26 B ．0.35 C ．0.65 D ．0.74 解答：是一年级学生的概率为 35%，则不是一年级学生的概率为1－35%＝0.65 选：C 7． 某银行有男性职工280人，女性职工220人，从中随机抽取1人是女职工的概率为 8． 某一零件的直径规定为10厘米，但实际生产零件的直径可能有的超过10厘米，有的不足10厘米。在 正常生产情况下，其误差通常服从 A ．二项分布 B ．正态分布 C ．均匀分布 D ．泊松分布 解答： 选：B 练习册上的题。 9． 如果随机变量X 的方差为2，则Y ＝2X －2的方差为 A ．2 B ．4 C ．6 D ．8

数量方法期末试题与答案1卷

绝密★启用前 学院 学年第二学期期末考试 级 专业（ ）《数量方法》试卷 一、 单选题（每小题1分，共20分） 1．8位学生五月份的伙食费分别为（单位：元）： 360 400 290 310 450 410 240 420 则这8位学生五月份的伙食费的中数为 A ．360 B ．380 C ．400 D ．420 解答：将所给数据按升序排好：240 290 310 360 400 410 420 450 则中位数为 3802 400 360=+，故选B 2．某航班的飞机每次乘満可以乘坐80名旅客，现随机抽取了10次航班，获得乘坐人数资料如下： 76 62 80 52 27 72 71 77 65 58 这10次航班的平均乘坐率为 A ．64% B ．80% C ．66% D ．85% 解答：10个数据的平均值为：6410 58 657771722752806276=+++++++++ 所以平均乘坐率为： %8080 64 =，故选B 3．某超市在过去80天的销售额数据如下： 销售额 天数 10万元以下 5 10万元－20万元以下 17 20万元－30万元以下 30 30万元－40万元以下 23 40万元以上 5 若随机抽取一天，其销售额在30万元以上的概率为 A ．0.35 B ．0.28 C ．0.58 D ．0.22 解答：其销售额在30万元以上的概率为 35.080 5 23=+，选A 4．设A ，B 是两个事件，则“这两个事件至少有一个发生”可以表示为： 则α等于 B A B A C B A B A B AB A . D ... ?? 解答：A 表示A ，B 两个事件同时发生 B 表示只有一个发生 C 表示至少有一个发生 D 表示两上都不发生 故选C 5．已知 4.0)(6.0)( 5.0)(===AB p B p A p ，则=?)(B A p A ．0.6 B ．0.7 C ．0.8 D ．0.9 解答： )()()()(AB p B p A p B A p -+=? 于是， )()()()()()()()(B p A p B p A p AB p B p A p B A p -+=-+=? 选B 6．设离散型随机变量的分布律为 X －1 0 1 P 0.3 0.5 0.2 则X 的数学期望E （X ）＝ A ．0.2 B ．-0.1 C ． 0.1 D ．-0.2 解答：数学期望的定义∑=i i p x X E )(，所以1.02.015.003.01)(-=?+?+?-=X E 选B 。 7．一大批计算机元件的正品率为80%，随机地抽取n 个为样本，其中X 个为正品，X 的分布服从 A ．正态分布 B ．二项分布 C ．泊松分布 D ．均匀分布 解答： 元件只有正品和非正品两种情况，这是典型的两点分布。将其独立地重复n 次，这是贝努利概型，或称二项分布。选B 8．比较两个总体均值是否相同的假设检验中，采用t 检验的条件是 A ．总体为正态分布，方差已知 B ．总体为正态分布，方差未知 C ．总体为非正态分布，方差已知 D ．总体为非正态分布，方差未知 解答：选B 。 9．若随机变量服从正态分布N(0,4),则随机变量Y=X-2的分布为： A ．N(-2,4) B ．N(2,4) C ．N(0,2) D ．N(-2,2) 解答：)()(,)()(2X D a b aX D b X aE b aX E =++=+,所以选择A 10．采用随机抽样的正确理由是 A ．使样本更精确 B ．使样本更具代表性 C ．使样本的效率更高 D ．使抽样误差可以控制 解答：选C 11．某调查公司接受委托对某种化妆品的满意程度进行调查，评分在值在0分（完全不满意）和20分（非常满意）之间，随机抽取36名消费者，其平均值为12分，标准差为3分，根据调查结果对总体均值进行置信度为95%的区间估计，其结果应该是（z 0.025≈2） A ．9-15分 B ．6－18分 C ．11－13分 D ．12－14分 解答：置信区间为n z x σ α 2 ± ，所以36 32 12±，选C 。 12．假设检验中第二类错误是指 A ．错误接受原假设的概率 B ．错误接受备择假设的概率 C ．错误接受这两种假设的概率 D ．错误拒绝原假设的概率 解答：第一类错误是所谓的弃真，当拒绝时所犯的错误是第一类错误；第二类错误是取伪，当接受时所犯的错误是第二类错误。选A 13．为了测试喝啤酒与人体血液中酒精含量之间的关系，随机抽取了16人作试验，令x 表示喝啤酒的杯数，y 表示血液中酒精含量，对x 与y 做线性回归分析，获得下列数据 变量 系数 标准差

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do

管理数量方法与分析复习资料-试题带答案版本

管理数量方法与分析复习资料-试题带答案版 本 https://www.wendangku.net/doc/9f12206742.html,work Information Technology Company.2020YEAR

1.在测量了变量的分布特征之后，测度变量之间的相关程度有何意义测量指标有哪些 答：有时候掌握了变量的分布特征之后还不够，还需要了解变量之间相互影响的变动规律，以便对变量之间的相对关系进行深入研究。测度指标有协方差和相关系数。 2.简述数学期望和方差各描述的是随机变量的什么特征。 答：随机变量的期望值也称为平均值，它是随机变量取值的一种加权平均数，是随机变量分布的中心，它描述了随机变量取值的平均水平，而方差是各个数据与平均值之差的平方的平均数，方差用来衡量随机变量对其数学期望的偏离程度。 3.在数据分布中离散程度测度的引入有何意义？ 答：研究变量的次数分布特征出来考察其取值的一般水平的高低外，还需要进一步考察其各个取值的离散程度。它是变量次数分布的另外一个重要特征。对其进行测定在实际研究中十分重要的意义：首先通过对变量取值之间离散程度的测定可以反映各个变量值之间的差异大小，从而也就可以反映分布中心指标对各个变量值代表性的高低。其次，通过对变量取值之间离散程度的测定，可以大致反映变量次数分布密度曲线的形状。 4．在变量数列中引入偏度与峰度的概念有何意义？答：对变量次数分布的偏斜程度和峰尖程度进行测度，一方面可以加深人们对变量取值的分布情况的认识；另一方面人们可以将所关心的变量的偏度标值和峰度指标值与某种理论分布的偏度标值和峰度指标值进行比较，以判断所关心的变量与某种理论分布的近似程度，为进一步的推断分析奠定基础。 5．什么是变量数列？ 答：在对变量取值进行分组的基础上，将各组不同变量值与其变量值出现的次数排列成的数列，就称为变量数列。 1.（1）运用算术平均数应注意什么问题？在实际应用中如何有效地避免（1）中的问题。 答：（1）运用算术平均数应注意： ①算术平均数容易受到极端变量的影响。这是由于算术平均数是根据一个变量的全部变量值计算的，当一个变量的取值出现极小或者极大值，都将影响其计算结果的代表性。 ②权数对平均数大小起着权衡轻重的作用，但不取决于它的绝对值的大小，而是取决于它的比重。 ③根据组距数列求加权算术平均数时，需用组中值作为各组变量值的代表，它是假定各组内部的所有变量值是均匀分布的。 （2）①为了提高算术平均数的代表性，需要剔除极增值，即对变量中的极大值或极小值进行剔除。 ②采用比重权数更能反映权数的实质，因为各组绝对数权数按统一比例变化，则不会影响平均数的大小。 ③注意组距数列计算的平均数在一般情况下只是一个近似值。 2.（1）什么是洛伦茨曲线图其主要用途有哪些 （2）简述洛伦茨曲线图的绘制方法。 答：（1）累计频数（或频率）分布曲线；用来研究财富、土地和工资收入的分配是否公平。（2）首先，将分配的对象和接受分配者的数量均化成结构相对数并进行向上累计；其次，纵轴和横轴均为百分比尺度，纵轴自下而上，用以测定分配的对象，横轴由左向右用以测定接受分配者；最后，根据计算所得的分配对象和接受分配者的累计百分数，在图中标出相应的绘示点，连接各点并使之平滑化，所得曲线即所要求的洛伦茨曲线。 3.（1）简述分布中心的概念及其意义。 （2）分布中心的测度指标有哪些这些指标是否存在缺陷

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]