2024年大学试题(计算机科学)-算法设计与分析考试近5年真题集锦（频考类试题）带答案

（图片大小可自由调整）2024年大学试题(计算机科学)-算法设计与分析考试近5年真题集锦（频考类试题）带答案第I卷一.参考题库(共100题)1.函数自身调用自身，称之为递归调用。2.voidprint（inta[]，intlen）是打印数组所有元素功能的函数头，则其参数是（）。A、数组B、指针C、普通整型变量D、字符串3.简单选择排序的时间复杂度与快速排序的不一样。4.数据结构与算法里，循环语句中加break的作用的是（）A、break用于循环语句的作用是结束本层循环B、break用于循环语句的作用是结束本次循环，继续下一下循环C、break不能用于switch语句D、break语句不能用do-while语句开会5.设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为（）A、B、C、D、6.在流程图中，圆角矩形表示开始或结束。7.分支限界法主要有（）分支限界法和（）分支限界法。8.（）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质9.利用迭代算法解决问题，需要做好哪几个方面的工作？10.以下代码求和结果应该是：（） A、以上三项都不对B、2550C、2500D、505011.下列算法中不能解决0/1背包问题的是（）A、贪心法B、动态规划C、回溯法D、分支限界法12.数据结构中，下列选项中是顺序查找的时间复杂度的是（）。A、O（1）B、O（n）C、O（n*n）D、O（log2n）13.用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。14.数据结构与算法里，荷兰国旗算法要用循环嵌套来解决问题。15.由分治法产生的子问题往往是（），这就为使用（）提供了方便。16.Dijkstra算法求单源最短路径。17.数据结构与算法里，快速排序的时间复杂度是O（log2n）。18.快速排序是稳定排序。19.回文字符串的非递归算法：用系统函数解决的方式，需要用到哪些系统函数（）。A、strcpyB、strcatC、strcmpD、strrev20.数据结构与算法里，比孙子算经中的双层循环解决的鸡兔同笼问题的时间复杂度高的是（）A、O（n*n*n）B、O（2^n）^表示幂C、O（n!）D、O（n^n）^表示幂21.试比较回溯法与分支限界算法，分别谈谈这两个算法比较适合的问题？22.回文字符串是正反都一样的英文字符串，那么下面不属于回文字符串的是（）。A、aabbB、aabbccddC、ABCABCD、AABBB23.数据结构中，顺序查找即用逐一比较的办法顺序查找关键字。24.静态查找表中，不是对顺序表的查找方式有（）A、顺序查找B、折半查找C、无序查找D、随机查找25.已知一个分治算法耗费的计算时间T（n），T（n）满足如下递归方程： 解得此递归方可得T（n）=O（）。26.数据结构与算法里，简单选择排序的时间复杂度是（）A、O（n*n）B、O（nlog2n）C、O（1）D、都不对27.数据结构与算法里，小明的烦恼问题的算法使用下列哪些技术项（）。A、二维数组B、循环嵌套C、分支判断D、递归28.汉诺塔问题可以用递归解决，以下也可用递归实现的是（）A、求1-n的和B、求n的阶乘C、斐波那契数列D、n^k（^表示幂）29.数据结构与算法中，查找哈希表，解决冲突的方法包括（）。A、数字分析法B、除留余数法C、直接地址法D、线性探测再散列法30.if语句有三种形态，分别是（）A、单分支ifB、双分支ifC、多分支ifD、无分支if31.分治法所能解决的问题一般具有什么特征？32.算法的复杂性有（）复杂性和（）复杂性之分。33.递归通常用（）来实现。A、有序的线性表B、队列C、栈D、数组34.小明的烦恼核心代码是使用（）实现的。A、递归算法B、循环嵌套C、单层循环D、只用了分支结构35.FIFO是（）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法36.简述舍伍德算法的特点。37.数据结构中，二叉排序树的右子树也应该一定是棵二叉排序树。38.直接插入排序是不稳定排序。39.数据结构中，折半查找需要记录是链式存储并且有序。40.以下代码求和结果应该是：（） A、以上三项都不对B、2550C、2500D、505041.数据结构与算法里，排序是（）A、排将一批无序的记录（数据）重新排列成按关键字有序的记录序列的过程B、将正序的记录（数据）排成倒序的即记录C、将倒序的记录（数据）排成正序的即记录D、以上都不对42.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解43.如《孙子算经》中描述的鸡兔同笼问题之穷举算法的时间复杂度是（）A、O（n）B、O（n*n）C、O（nlog2n）D、O（1）44.鸡兔同笼算法属于算法的一种，按照算法的特性来讲应具有（）A、正确性B、健壮性C、可读性D、可行性45.从排序的稳定性来看，快速排序是（）。A、不稳定排序B、稳定排序C、不确定D、都不对46.数据结构与算法里，冒泡排序和（）都属于交换排序。A、快速排序B、直接插入排序C、简单选择排序D、希尔排序47.数据结构与算法里，动态查找的典型工具是（），请将不是这个答案的选项选上。A、二叉排序树B、栈C、数组D、队列48.把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？请设计一个算法计算K值（只需要计算K值，不用把具体的分法输出）。注意：5，1，1和1，5，1是同一种分法。49.一个算法应该包含如下几条性质，除了（）A、二义性B、有限性C、正确性D、可终止性50.数据结构中，O（n）是以下哪种算法的复杂度（）。A、顺序查找B、顺序表删除元素C、顺序表插入元素D、单链表查找第i个元素51.有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？52.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（） A、B、C、D、53.Strassen矩阵乘法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法54.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。 55.数据结构与算法里，返回值是char*的字符串处理函数有（）。A、strlenB、strcpyC、strcatD、strcmp56.ACM算法的素数和计算中，sum变量用于累加素数之和，那么它的初值应赋值为（）A、0B、1C、100D、不赋初值57.定义一维数组正确的是（）A、int[]age；B、double[3]ageC、intage[3]D、doubleage[3]58.希尔排序是一种不稳定排序，那么原因是（）。A、存在不相邻记录的交换B、存在相邻记录的交换C、存在相同关键字的记录D、存在着记录顺序的一次调换59.数据结构中，动态查找表：边查找，边改变集合中的元素，改变的方式可以是（）。A、增加B、删除C、交换D、移动60.设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。61.计算一个算法时间复杂度通常可以计算（）、（）或计算步骤。62.关于装填因子，以下说法正确的是（）。A、哈希表的平均查找长度与处理冲突的方法无关。B、若散列表的负载因子（装填因子）α63.数据结构与算法里，字符串处理函数是字符串拷贝的是（）。A、strcatB、strcpyC、strcmpD、strlen64.数据结构与算法中，就排序记录所在位置而言，希尔排序排序属于（）。A、外排序B、内排序C、稳定排序D、交换排序65.数据结构与算法里，鸡兔同笼也是算法的一种，具有算法的特性（）A、正确性B、可读性C、可行性D、健壮性66.数据结构与算法里，鸡兔同笼算法具有的特性包括（）A、有穷性B、确定性C、可行性D、正确性67.荷兰国旗算法是数组的移动问题，需要遍历一维数组（）次，因此时间复杂度为线性阶。A、1（一）B、2C、3D、0（零）68.在C语言中若有定义语句inta[6]按在内存中的存放顺序，a数组的第3个元素是（）A、[4]B、a[1]C、a[3]D、a[2]69.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）A、问题规模相同，问题性质相同B、问题规模相同，问题性质不同C、问题规模不同，问题性质相同D、问题规模不同，问题性质不同70.冒泡排序是交换排序的一种。71.在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况下，O、Ω、Θ分别提供了算法运行时间的什么界？72.8个记录待排序，使用冒泡排序可能进行的趟数最少情况是（）。A、1B、2C、7D、873.写出0/1背包问题的动态规划方程，并简要说明。74.已知Ak=（aij（k））ri*ri+1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）75.数据结构与算法里，下列数字不是完数的是（）A、7B、6C、28D、9976.数据结构中，关于查找表的分类，下列选项中说法正确的是（）。A、查找表有静态查找表法B、查找表有动态查找表法C、查找表分为混合查找表D、查找表分为物理查找表77.数据结构与算法里，冒泡排序的每一趟的过程是要比较（）元素，如果逆序进行交换。A、相邻B、不相邻C、首尾D、都不对78.数据结构与算法里，研究完数最早的是中国的《九章算术》。79.一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件满足时，递归（）A、进行运算B、返回C、前进D、结束条件80.求证：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。81.数据结构与算法中，在排序中，对于关键字相等的记录，排序前后相对位置不变。这时称排序为（）。A、稳定排序B、不稳定排序C、不确定是稳定排序还是不稳定排序D、基数排序82.装填因子的计算方法是（）。A、1-（表中未填入记录的数目/哈希表的总长度）B、表中未填入记录的数目/哈希表的总长度C、（表中未填入的记录数-1）/哈希表的总长度D、表中填入的记录数/哈希表的总长83.快速排序的时间复杂度是O（n*n）。84.改进的冒泡排序的任一趟排序过程中，如果没有发生（），则说明已经有序；排序完毕。A、数据交换B、数据删除C、数据增加D、都不对85.下列数组定义、初始化或赋值语句中，正确的是：（）A、intx[5]={1，2，3，4，5，6}；B、intn=8；intscore[n]；C、inta[8]；a[8]=100；D、intx[]={1，2，3，4，5，6}；86.数据结构与算法里，汉诺塔是一类递归的算法，也应具有算法的特性（）A、有穷性B、模糊性C、二义性D、正确性87.下列算法中通常以深度优先方式系统搜索问题解的是（）。A、备忘录法B、动态规划法C、贪心法D、回溯法88.数据结构与算法里，装填因子又称为（）。A、负载因子B、平衡因子C、外力因子D、合力因子89.数据结构中，查找的结果可能在集合中也可能不在集合中，分别称为（）。A、查找失败B、查找成功C、不确定D、都不对90.设T（n）=n，根据T（n）=O（f（n））的定义，T（n）=O（n）*O（logn）。91.数据结构与算法里，顺序表的查找有（）A、顺序查找B、折半查找C、随机查找D、索引查找92.请画出用回溯法解4皇后问题的解空间树和搜索空间树。93.数据结构与算法里，for循环的小括号第一个表达式是（）A、初值B、条件C、增量D、循环体94.在C语言中，系统函数strcmp的参数个数是（）。A、2B、1C、3D、495.以下能正确定义一维数组的选项是（）A、intnum[]；B、intnum[0..100]；C、#defineN5intnum[N]；D、ntN=100；intnum[N]；96.蒙特卡罗算法是（）的一种。A、分支界限算法B、概率算法C、贪心算法D、回溯算法97.数据结构与算法里，希尔排序与直接插入排序相同之处是（）。A、它们都是稳定排序B、它们的时间复杂度是一样的C、它们都是插入排序大类里的D、它们都是缩小增量排序98.穷举法求解问题的两个基本要素（）A、确定穷举对象和穷举范围B、确定判定条件C、确定穷举所需要的时间D、确定列举穷举的地点99.数据结构与算法中，在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。A、希尔排序B、冒泡排序C、直接插入排序D、简单选择排序100.数据结构与算法里，鸡兔同笼是（）经典算法解决的一类问题。A、穷举法B、递推法C、分治法D、迭代法第I卷参考答案一.参考题库1.参考答案：正确2.参考答案：A3.参考答案：正确4.参考答案：A5.参考答案：B6.参考答案：正确7.参考答案：队列式（FIFO）；优先队列式8.参考答案：D9.参考答案： 1）确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 2）建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 3）对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。10.参考答案：D11.参考答案：A12.参考答案：B13.参考答案：至少需要对每个元素进行一次比较运算，运算时间是O（n）。14.参考答案：错误15.参考答案：原问题较小模式；递归技术16.参考答案：17.参考答案：错误18.参考答案：错误19.参考答案：A,C,D20.参考答案：A,B,C,D21.参考答案： 不同点：求解目标，搜索方式，空间消耗。 回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 搜索方式：回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。 回溯法：以深度优先方式系统搜索问题解的算法为回溯法，适合解组合数较大的问题。 分支限界法适合解决大量离散最优化的问题。22.参考答案：A,B,C,D23.参考答案：正确24.参考答案：C,D25.参考答案：nlogn26.参考答案：A27.参考答案：A,B,C28.参考答案：A,B,C,D29.参考答案：D30.参考答案：A,B,C31.参考答案： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。32.参考答案：时间；空间33.参考答案：C34.参考答案：B35.参考答案：A36.参考答案：总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。37.参考答案：正确38.参考答案：错误39.参考答案：错误40.参考答案：D41.参考答案：A42.参考答案：B43.参考答案：B44.参考答案：D45.参考答案：A46.参考答案：A47.参考答案：B,C,D48.参考答案： 例：M=7，N=3则有K=8 可能的分法为： 7，0，0 6，1，0 5，2，0 4，3，0 5，1，1 4，2，1 3，3，1 3，2，2 设f（m，n）为m个苹果，n个盘子的放法数目，则先对n作讨论，如果n>m，必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if（n>m）f（m，n）=f（m，m）当n49.参考答案：A50.参考答案：A,B,C,D51.参考答案： 因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。52.参考答案：B53.参考答案：A54.参考答案：贪心算法： （1）标准：重量、价值和单位价值。 （2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。 使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。 使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。 （3）显然使用单位价值作为标准得到的是最优解。 回溯法：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得： 在Q1处获得该问题的最优解为（1，1，1，1，0，0，1），背包效益为1