《算法分析与设计》试卷(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)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。
西南交通大学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 分)
《算法设计与分析》试卷 一．计算题（共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
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =
中国药科大学工业药剂学试卷3答案 一．名词解释 1．1．剂型与制剂 剂型：药物不能直接供患者用于疾病的防治，必须制成适合于患者应用的最佳给药形式，即药物剂型或称剂型 制剂：根据药典和部颁标准，将药物制成适合临床需要并符合一定质量标准的药剂称为制剂 2．2．GLP 与GCP GLP：药品安全试验规范(Good Laboratory Practice，简称GLP)，是在新药研制的实验中，进行动物药理试验(包括体内和体外试验)的准则，如急性、亚急性、慢性毒性试验、生殖试验、致癌、致畸、致突变以及其它毒性试验等都有十 分具体的规定，是保证药品研制过程安全准确有效的法规。 GCP：药品临床试验管理规范（Good Clinical Practice，简称GCP)，是临床试验全过程的标准规定，包括方案设计、组织、实施、监查、稽查、记录、分析总结和报告。 3．3．Isoosmotic Solution 与Isotonic solution Isoosmotic Solution：等渗溶液是指渗透压与血浆相等的溶液，是物理化学的概念 Isotonic solution：等张溶液是指与红细胞张力相等，也就是与细胞接触时使细胞功能和结构保持正常的溶液，是生物学的概念 4．4．F0与F值 Fo值表示一定灭菌温度(T)，Z值为10℃时，一定灭菌温度(T)产生的灭菌效果与121℃，Z值为10℃产生的灭菌效力相同时所相当的时间(min)。即将被灭菌物品各不同受热温度均所达到与湿热灭菌121℃产生的灭菌效力相同时所相当的灭菌时间 F值为在一定温度（T），给Z值所产生的灭菌效力与参比温度（To）给定Z值所
《算法分析与设计》试题库 （一） 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上，并 D.动态规划算法
3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质
D.预排序与递归调用 4. 算法分析中，记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有：(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中，按(D)策略，从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先
内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(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
广西中医药大学成教院##级##专升本专业考试试卷1 课程名称:药剂学考试形式：闭卷 适用专业年级:########专业考试时间：2小时 姓名年级专业学号 一、以下每一道题下面有A.B.C.D四个备选答案。请从中选择一个最佳答案。每题1分，共15分。 1、药剂学概念正确的表述是（ B ）。 A、研究药物制剂的处方理论、制备工艺和合理应用的综合性技术科学 B、研究药物制剂的基本理论、处方设计、制备工艺和合理应用的综合性技术科学 C、研究药物制剂的处方设计、基本理论和应用的技术科学 D、研究药物制剂的处方设计、基本理论和应用的科学 2、中国药典中关于筛号的叙述，哪一个是正确的（ B ）。 A、筛号是以每一英寸筛目表示 B、一号筛孔最大，九号筛孔最小 C、最大筛孔为十号筛 D、二号筛相当于工业200目筛 3、下列关于胶囊剂的叙述哪一条不正确（C ）。 A、吸收好，生物利用度高 B、可提高药物的稳定性 C、可避免肝的首过效应 D、可掩盖药物的不良嗅味 4、配制含毒剧药物散剂时，为使其均匀混合应采用（D ）。 A、过筛法 B、振摇法 C、搅拌法 D、等量递增法 5、不能制成胶囊剂的药物是（B）。 A、牡荆油 B、芸香油乳剂 C、维生素AD D、对乙酰氨基酚 6、关于液体药剂优点的叙述错误的是（ D ） A．药物分散度大、吸收快 B．刺激性药物宜制成液体药剂 C．给药途径广泛 D．化学稳定性较好 E．便于分剂量 7、药物制成以下剂型后哪种服用后起效最快（ B ）。 A、颗粒剂 B、散剂 C、胶囊剂 D、片剂 8、下列哪一条不符合散剂制法的一般规律（B ）。 A．各组分比例量差异大者，采用等量递加法 B．各组分比例量差异大者，体积小的先放入容器中，体积大的后放入容器中 C．含低共熔成分，应避免共熔 D．剂量小的毒剧药，应先制成倍散 9、泡腾颗粒剂遇水产生大量气泡，是由于颗粒剂中酸与碱发生反应所放出的气体是（ C ）。 A、氢气 B、二氧化碳 C、氧气 D、氮气 10、以下关于乳剂类型鉴别的说法，正确的是（D ） A、加纯化水稀释不分层的是W/O B、加油溶性染料染色，内相染色的是W/O C、加水溶性染料染色，外相染色的是O/W D、加水溶性染料染色，外相染色的是W/O E、以上都不对 11.关于软膏剂的制备方法，错误的叙述有（ D ） A、依照形成的软膏类型、制备量及设备条件不同、采用的方法不同 B、溶液型或混悬型软膏常采用研磨法或熔融法。 C、乳剂型软膏常用乳化法。 D、在形成乳剂型基质后加入的药物为不溶性微细粉末的不属于混悬型软膏。
湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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卷 考试说明： 承诺： 本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。 承诺人：学号：班号： 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。注：本试卷共三大题，共 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]
算法分析与设计复习题及答案一、单选题 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
《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 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] 广西中医药大学成教院##级##专升本专业考试试卷4 课程名称:药剂学考试形式：闭卷 适用专业年级: ########专业考试时间：2小时 姓名年级专业学号 一、以下每一道题下面有A.B.C.D四个备选答案。请从中选择一个最佳答案。每题1分，共40分。 1. 以下缩写中表示临界胶束浓度的是（ c ） A.HLB B.GMP C.CMC D.MAC 2. 关于休止角表述正确的是（ c ） A.休止角越大，物料的流动性越好 B.粒子表面粗糙的物料休止角小 C.休止角小于30o，物料流动性好 D.粒径大的物料休止角大 3. 根据Stock定律，混悬微粒的沉降速度与下列哪一个因素成正比（ b ） A.混悬微粒的半径 B.混悬微粒半径的平方 C.混悬微粒的粒度 D.混悬微粒的粘度 4. 片剂包糖衣工序的先后顺序为（ a ） A.隔离层.粉衣层.糖衣层.有色糖衣层 B.隔离层.糖衣层.粉衣层.有色糖衣层 C.粉衣层.隔离层.糖衣层.有色糖衣层 D.粉衣层.糖衣层.隔离层.有色糖衣层 5. 碘酊属于哪一种剂型液体制剂（d ） A.胶体溶液型 B.混悬液型 C.乳浊液型 D.溶液型 6. 全身作用的直肠栓剂在应用时适宜的用药部位是（ b ） A.距肛门口6cm处 B.距肛门口2cm处 C.接近肛门 D.接近直肠上静脉 7.《中国药典》规定的注射用水属于哪种类型注射剂（d） A.纯净水 B.蒸馏水 C.去离子水 D.蒸馏水或去离子水再经蒸馏而制得的水 8. 下列哪些制片法不适用于对湿热敏感的药物（ d ） A.空白颗粒制片法 B.粉末直接压片法 C.干法制粒压片法 D.软材过筛制粒压片法 9.下列哪种方法不能增加药物的溶解度（d ） A.加入助溶剂 B.加入表面活性剂 C.制成盐类 《算法分析与设计》期末复习题 一、选择题 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．定义最优解 一选择题 1.以下哪个不是生物信息的特征 D A级联反应B网络结构C多样性D不可逆性 2.体内信号转导的主体是 A A 蛋白质 B 小分子物质 C 多糖 D 脂质 3．凡是由细胞分泌的，能够调节特定靶细胞生理活动的化学物质都称为细胞间物质，称为第一信使，它属于 D A 物理信号B机械力 C生物体外信号D化学信号 3.下列哪个不是细胞间化学信号分子的特点 B A特异性B持续性 C时间效应各异 D 复杂性 4.第三信使是下列哪种物质 C A 花生四烯酸 B 二十碳酸类 C DNA结合蛋白D磷脂酰肌醇 5.基于调节第二信使的药物设计不是 A A 维生素D受体配体的药物设计 B 调节cAMP和cGMP信号通路的药物设计 C 调节激酶系统的药物设计 D调节钙的药物设计 6.下列哪个是基于调节第三信使的药物设计 A A 过氧化物酶体增殖因子活化受体配体的药物设计 B 磷酸二酯酶抑制剂活化受体配体的药物设计 C 磷酸二酯酶V的抑制剂活化受体配体的药物设计 D 糖原合成激酶-3抑制剂活化受体配体的药物设计 7.不是对信号转导系统的药物干预的选项是 A 影响信号分子的药物 B 影响信号接受系统的药物 C 影响信号传输系统的药物 D 影响细胞内信号转导系统的药物 1.生物体内嘌呤核苷酸的合成除了补救合成外，还有（） A.从头合成 B.中间合成 C.最后合成 D.中间体合成 2.（）是嘧啶生物合成的重要中间体 A.天冬氨酸 B.氨甲酰磷酸 C.乳清苷酸 D.谷氨酰胺 3.既是核酸生物合成的代谢产物，也是红细胞发育生长的重要因子的是（） A.核苷 B.磷酸 C.戊糖D叶酸 4.氨基嘌呤和甲氨嘌呤是最早用于肿瘤临床治疗的（）还原酶抑制剂 A.血清铁蛋白 B.黏蛋白 C.二氢叶酸 D.甲胎蛋白 5.（）可以影响IMP、AMP或GMP的形成，从而抑制DNA和RNA 的合成 A.次黄嘌呤 B.鸟嘌呤 C.腺甘酸 D.巯嘌呤核苷酸 一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai 福建医科大学2013年《药物设计学》考试试卷 年级______专业_______姓名__________学号___________命题人：刘洋 单项选择填空题（每空3分，共24分） 1.由实验方法，可以求得药物分子的三维结构，并与生物条件下体液中的分子状态 较为接近。 A．X-射线晶体学 B. 核磁共振技术 C. 质谱技术 D. DNA重组技术 2.靶点结构未知时，可以用方法设计新的药物分子。 A．直接药物设计 B. 间接药物设计 C. 全新药物设计 3.比较分子力场分析（CoMFA）方法属于方法。 A．2D-QSAR B. 3D-QSAR C. 全新药物设计 D. 三维结构搜寻 4.可以用方法计算分子的结构、总能量、分子轨道形状、能量和电势；方法 计算分子的构象和能量；方法计算分子的能量最低构象和运动轨迹。 A．量子化学 B. 分子力学 C. 分子动力学 D. 拓朴学 E. 计算机分子图形学5.用方法设计出的药物，是已知化学结构的化合物。 A．动力学算法 B. 模板定位法 C. 分子碎片法 D. 三维结构搜寻法 6.靶点结构已知时，可以直接考虑采用方法来设计新的药物分子。 A．对接法 B. 比较分子力场分析（CoMFA）方法 C. 活性类似物法（AAA法） D. 分子形状分析（MSA） 7.方法适用于靶点结构未知时设计新的药物分子。 A．直接药物设计 B. 间接药物设计 C. 全新药物设计 D、分子生长法 8.药物与受体间相互作用的主要因素是。 A．分子间的空间识别 B、分子间的离子键结合 C、分子间的非共价键结合 D分子间的共价键结合 多项选择填空题（每题3分，共6分） 1. 药物与受体结合的作用有。 A、氢键作用 B、疏水作用 C、静电作用 D、共轭作用 E、诱导作用 2. 影响药物与受体结合的立体因素有。 A、光学异构 B、顺反异构 C、构象异构 D、互变异构 问答题（20分） 试以辣椒素（结构见下图）为先导物分别运用前药原理、生物电子等排原理、拼合原理三种方法进行优化，并将优化后的结构画出来。 N H O H3CO HO 一、选择题（20分） 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 3.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 4.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 5.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数6．采用最大效益优先搜索方式的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法7．贪心算法与动态规划算法的主要区别是（ B ）。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解 8. 实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 10.下列算法中通常以广度优先方式系统搜索问题解的是（ A ）。 A、分支限界法 B、动态规划法 C、贪心法 D、回溯法 二、填空题（22分每空2分） 1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。 2、大整数乘积算法是用分治法来设计的。 3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。 4、舍伍德算法总能求得问题的一个解。 5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 6.快速排序 template药剂学试卷有答案
《算法分析与设计》期末考试复习题纲(完整版)
(完整版)药物设计学考试题库及答案
《算法分析与设计》期末复习题
算法设计与分析试题与答案
2013药物设计学考卷
算法分析与设计试题
相关主题
文本预览