湘潭大学2016年算法试卷解析：是非题与选择题详解

湘潭大学2016年上学期的算法试卷主要考察了学生们对算法基础理论的理解和应用能力。试卷分为两部分，一是是非题和选择题，涵盖了算法的关键概念和设计原则。 1. 是非题部分（每题2分，共16分）： - 第1题探讨了常数因子对时间复杂度的影响，指出若c为正常数，O(cf(n))仍然属于O(f(n))的大致时间复杂度范围，这反映了算法分析中的基本性质。 - 第2题强调了时间复杂度评估中的实际价值，认为在最好、最坏和平均情况中，最坏情况的时间复杂度往往更具指导意义，因为它是衡量算法稳定性的重要指标。 - 第3题说明了数据结构对于算法效率的重要性，好的数据结构能提升算法的性能。 - 第4题区分了迭代模型和递归算法，迭代模型通常用于解决规模逐渐减小的问题，而递归则是处理规模不变或增大问题。 - 第5题关于贪婪算法的表述不完全准确，虽然贪婪算法在某些情况下可以找到局部最优解，但并非总是能找到全局最优解。 - 第6题测试了动态规划算法的两个关键特性：最优化原理（寻找全局最优解）和子问题重叠（避免重复计算）。 - 第7题关于深度优先搜索（DFS），它是一种用于遍历或搜索树或图的算法，但不一定能找到所有可能的解，而是先尽可能深地探索一条路径。 - 第8题介绍了分支限界法的目标，即找到满足约束条件的解，或是找到最优解，这涉及到优化目标函数。 2. 选择题部分（每题2分，共10分）： - 第1题考核动态规划算法的核心特征，正确答案是C，最优子结构性质与重叠子问题性质，这是动态规划问题分解和记忆化的关键。 - 第2题提问的是贪心算法的适用性，贪心算法通常适用于具有最优子结构和贪心选择性质的问题，因此正确答案是A。 - 第3题涉及搜索策略，分支限界法通常按活结点优先（也称启发式搜索）进行，因此答案是B。 - 第4题询问NP类语言的定义，正确答案是B，表示能在多项式时间内被一台NDTM（非确定型图灵机）接受的语言。 - 第5题是关于渐进上界符号的定义，即[pic]表示一个函数集合，其中f(n)的渐进上界是g(n)，正确答案涉及上界限制，即存在c和n0。 通过这些题目，试卷旨在考察学生对算法概念的掌握程度，如时间复杂度、数据结构、贪心算法、动态规划、搜索算法以及计算机科学的基础理论知识。