2024年大学试题(计算机科学)-算法设计与分析历年考试高频考点试题附带答案VIP

2024年大学试题(计算机科学)-算法设计与分析历年考试高频考点试题附带答案（图片大小可自由调整）第1卷一.参考题库(共25题)1.下面程序执行后输出的结果是（）。 A、123B、1230C、12356789D、1230567892.从排序大类上看，属于选择排序的是（）。A、简单选择排序B、堆排序C、快速排序D、冒泡排序3.下列不是基本计算模型的是（）。A、RAMB、ROMC、RASPD、TM4.该程序是计算1-100以内的素数之和，则填空处应填（） A、i%j==0B、j%i==0C、i+j==0D、i/j==05.在一个空间安排n=5个活动，开始时间和结束时间分别为[8，10），[12，14），[9，11：30），[11：40，13），[13：30，15）。写出活动安排贪心算法的运行结果。6.背包问题的贪心算法所需的计算时间为（）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）7.数据结构中，二叉排序的的哪些遍历序列，不能得到一个升序序列，或非递减有序序列。（）A、先序序列B、中序遍历C、后序遍历D、按层次遍历序列8.定义二维数组intarr[4][2]如果全部元素输出，共需要输出6个元素9.蜗牛爬井问题不属于（）类型算法解决的问题。A、迭代问题B、递归问题C、分治问题D、穷举问题10.数据结构与算法中，在排序中，对于关键字相等的记录，排序前后相对位置不变。这时称排序为（）。A、稳定排序B、不稳定排序C、不确定是稳定排序还是不稳定排序D、基数排序11.最优子结构性质的含义是（）。12.用分支限界法设计算法的步骤是什么？13.以下是计算xm的值的过程。横线处填（） 14.关于二维数组初始化描述正确的是（）。A、二维数组，即可以按元素初始化，也可以按行初始化B、二维数组当初始化列表给出数组全部元素的初值时，第一维的长度声明可以省略，此时，系统将按初始化列表中提供的初值个数来定义数组的大小。C、二维数组按行初始化时，即使初始化列表中提供的初值个数可以少于数组元素的个数，第一维的长度声明也可以省略，此时系统自动给后面的元素初始化为0。D、二维数组初始化时可以省略第二维的长度15.C语言中，定义一维数组intarr[3]={1，1，1}输出第三个元素可以使用语句printf（"%d"，arr）；。16.数据结构与算法里，查找表是（）类型的逻辑结构。A、集合B、线性C、树形D、图形17.数据结构与算法里，用穷举法逐一列举可能是解决鸡兔同笼问题的办法之一。18.数据结构与算法里，关于循环语句描述正确的是（）A、for循环完全可以取代while循环B、while循环是先执行后判断C、do-while循环和for循环语法一样D、for循环不能嵌套do-while循环19.对于符号三角问题，符号三角形的第一行有n个符号。符号可以为“＋”或“－”，以下每一行的符号由上行得到，2个同号下面都是“+”，2个异号下面都是“－”。如下图所示（第一行有4个符号的符号三角中的其中的一个）： 请画出使用回溯法求解第一行有4个符号（即n＝4）时，解空间树的形状。20.鸡兔同笼问题可以使用for循环嵌套for循环完成，那么循环嵌套for可以嵌套（）A、while语句B、for语句C、do-while语句D、都不对21.荷兰国旗问题，定义交换两个元素的函数，参数为指针，请问当参数为指针类型的函数，其传递属于（）。A、值传递B、地址传递C、形参传递D、实参传递22.数据结构与算法里，属于稳定排序的有（）。A、冒泡排序B、直接插入排序C、希尔排序D、改进的冒泡排序23.continue语句一般只用于循环结构，用来提前退出循环24.当输入规模为n时，算法增长率最快的是（）A、12nB、100log2nC、2n2D、3nlog3n25.有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适（）A、作业从小到大依次分配给空闲的机器B、作业从大到小依次分配给空闲的机器C、每个机器分配一样的作业数D、使用以上几种贪心策略都能找到最优解，所以都合适第2卷一.参考题库(共25题)1.数据结构与算法中，递归概念指的是（）。A、程序调用自身的编程技巧B、特定功能的模块C、相同数据类型的有序的集合D、从小到大进行排列2.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是（）A、（4k–1）/3B、2k/3C、4kD、2k3.鸡兔同笼问题可以是很多实际的问题如（）A、孙子算经中的鸡兔同笼问题B、大人小孩吃面包问题C、大小油瓶装油问题D、计算素数和问题4.比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？5.以下代码的功能是：（） A、其他三项都不对B、求1--100的和C、求1--100的奇数和D、求1--100的偶数和6.数据结构与算法中，从排序大类上看，属于选择排序的是（）。A、简单选择排序B、堆排序C、快速排序D、冒泡排序7.概率算法大致分为哪几类？8.冒泡排序，交换的是相邻元素，因此（）。A、不存在不相邻的记录的交换，属于稳定排序B、仍然可能存在不相邻的记录之间的交换C、是不稳定排序D、是外排序的一种9. 上述算法的时间复杂度为（）A、O（2n）B、O（nlogn）C、Θ（n！）D、Θ（nn）10.下图是由14个“+”和14个“－”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“－”。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“－”的个数相同。请针对符号三角形问题设计一个尽可能高效的算法。11.数据结构与算法里，荷兰国旗算法应具有的算法的设计要求有（）。A、正确性B、可读性C、健壮性D、效率与低存储量需求12.数据结构中，n个记录的某顺序表，查找某关键字，采用顺序查找，最好的情况是比较多少次（）。A、nB、1C、n-1D、n+113.数据结构与算法里，查找哈希表，不是解决冲突的方法包括（）。A、数字分析法B、除留余数法C、直接地址法D、线性探测再散列法14.定义一维数组，[]内必须是常量表达式。15.采用简单选择排序，共有N个记录，每趟最多进行（）次交换。A、1B、2C、N-2D、N-116.修公路问题算法：则填空处可以填写（） A、h-=55B、h=h-55C、h=h*2D、h*=217.矩阵连乘问题的算法可由（）设计实现。18.for循环的嵌套经常用于穷举法算法的实现，那么关于循环嵌套的说法正确的是（）A、for循环不能嵌套while循环B、while循环可以嵌套for循环C、do-while循环不能嵌套for循环D、for循环不能嵌套do-while循环19.该程序输出的图形是（） A、三行四列的矩形方阵B、三行三列的矩形方阵C、三行的直角三角形D、四行的直角三角形20.函数调用的一种特殊，即自己调用自己称为（）。A、嵌套调用B、循环调用C、连续调用D、递归调用21.数据结构与算法里，返回值是char*的字符串处理函数有（）。A、strlenB、strcpyC、strcatD、strcmp22.冒泡排序属于（）A、插入排序B、选择排序C、交换排序D、归并排序23.下面不是分支界限法搜索方式的是（）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先24.数据结构与算法里，希尔排序又称为（）。A、缩小增量排序B、二分插入排序C、多路归并排序D、锦标赛排序25.数据结构中，在顺序表的查找中，若记录是有序的，可以使用（）方式查找效率更高A、顺序查找B、折半查找C、分块查找D、随机查找第3卷一.参考题库(共25题)1.现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他选手各赛一次； （2）每个选手一天只能赛一次； （3）循环赛一共进行n–1天。 请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。2.数据结构与算法里，for循环嵌套for循环可解决孙子算经中提到的鸡兔同笼问题。3.有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 4.分治法的基本思想是什么？5.用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。 6.数据结构与算法里，折半查找的时间复杂度是（）。A、O（1）B、O（log2n）C、O（n*n）D、O（n）7.数据结构与算法里，以下算法时间复杂度是O（n*n）的是（）。A、冒泡排序B、直接插入排序C、折半查找D、希尔排序8.考虑背包问题：n=6，物品重量W=（1，5，2，3，6，1），价值P=（15，59，21，30，60，5），背包载重量C＝10。能放进背包的物品价值最大为（）。A、101B、110C、115D、1209.50个记录，采用简单选择排序，每趟最多进行（）次交换。A、1B、2C、50D、4910.使用分治法求解不需要满足的条件是（）。A、子问题必须是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题使用相同的方法解11.将一个正整数n表示成一系列正整数之和，n=n1+n2+…+nk（其中，n1≥n2≥…≥nk≥1，k≥1）正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数总和称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）=（）。A、q（8，8）B、1+q（9，9）C、2+q（10，8）D、ABC都正确12.利用概率的性质计算近似值的随机算法是（），运行时以一定的概率得到正确解的随机算法是（）。13.数据结构与算法里，交换排序和插入排序是没有什么区别的。14.数据结构与算法里，从时间复杂度的角度来看，快速排序的时间复杂度是（）。A、O（n*n）B、O（nlog2n）C、O（1）D、都不对15.算法的定义是什么？16.回溯法中常见的两类典型的解空间树是什么？并简述其定义。17.数据结构与算法中，装填因子的计算方法是（）。A、1-（表中未填入记录的数目/哈希表的总长度）B、表中未填入记录的数目/哈希表的总长度C、（表中未填入的记录数-1）/哈希表的总长度D、表中填入的记录数/哈希表的总长18.数据结构与算法里，28是完数，除了1，2，4，14以外，因子还有（）A、21B、7C、6D、2819.冒泡排序在一趟排序中没有记录交换，则说明记录已经有序，停止排序。20.数据结构与算法里，冒泡排序和（）都属于交换排序。A、快速排序B、直接插入排序C、简单选择排序D、希尔排序21.关于循环结构说法正确的是（）A、循环控制表达式是进入循环控制操作的必要条件，程序流程只有满足循环控制表达式，才能进入循环B、循环体语句是循环控制结构的执行主体C、在循环控制结构中，循环开始执行时，只有使循环控制表达式的运算值为假，才能终止并跳出循环控制结构，因此循环控制变量要在循环体中做增量运算。D、循环结构都是对循环条件行判断如果为真才能执行循环体语句22.采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是（）A、最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同B、最佳情况的渐进代价要好于最差情况和平均情况的渐进代价C、最佳情况和平均情况的渐进代价要好于最差情况的渐进代价D、最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价23.Strassen矩阵乘法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法24.数据结构与算法里，字符串和字符数组是一回事。25.数据结构与算法里，是不稳定排序的有（）。A、简单选择排序B、直接插入排序C、快速排序D、希尔排序第1卷参考答案一.参考题库1.参考答案:D2.参考答案:A,B3.参考答案:B4.参考答案:A5.参考答案: 1）按照结束时间排序 [8，10）1，[9，11：30）3，[11：40，13）4，[12，14）2，[13：30，15）5 2）可行解1，4，56.参考答案:B7.参考答案:A,C,D8.参考答案:错误9.参考答案:B,C,D10.参考答案:A11.参考答案:问题最优解包含其子问题最优解12.参考答案: （1）针对所给问题，定义问题的解空间（对解进行编码）； （2）确定易于搜索的解空间结构（按树或图组织解）； （3）以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。13.参考答案: 1；；14.参考答案:A,B,C15.参考答案:错误16.参考答案:A17.参考答案:正确18.参考答案:A19.参考答案: 第一行4个符号（即n＝4）时，解空间树是一棵完全二叉树。 20.参考答案:D21.参考答案:B22.参考答案:A,B,D23.参考答案:错误24.参考答案:C25.参考答案:B第2卷参考答案一.参考题库1.参考答案:A2.参考答案:A3.参考答案:A,B,C4.参考答案: 1）回溯法是在约束下带跳跃的深度优先搜索。 2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。 3）分枝限界法更适合找最优解。5.参考答案:D6.参考答案:A,B7.参考答案:数值概率算法，蒙特卡罗（MonteCarlo）算法，拉斯维加斯（LasVegas）算法和舍伍德（Sherwood）算法。8.参考答案:A9.参考答案:A10.参考答案: 回溯法实现 对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x=1时，表示符号三角形的第一行的第i个符号为“+”号；当x=0时，表示符号三角形的第一行的第i个符号为“-”号；1≤i≤n。由于x是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x[1：i]确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1：i+1]所相应的符号三角形。最终由x[1：n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束，用于剪去不满足约束的子树。 对于给定的n，当n*（n+1）/2为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。 复杂度分析 计算可行性约束需要O（n）时间，在最坏情况下有O（2n）个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为O（n2n）。11.参考答案:A,B,C,D12.参考答案:B13.参考答案:A,B,C14.参考答案:正确15.参考答案:A16.参考答案:A,B17.参考答案:动态规划18.参考答案:B19.参考答案:B20.参考答案:D21.参考答案:B,C22.参考答案:C23.参考答案:D24.参考答案:A25.参考答案:B第3卷参考答案一.参考题库1.参考答案: 2.参考答案:正确3.参考答案:4.参考答案:将一个规模为n的问题分解为k个规模较小的子问题，这些子