2024年大学试题(计算机科学)-算法设计与分析笔试历年真题荟萃含答案

2024年大学试题(计算机科学)-算法设计与分析笔试历年真题荟萃含答案（图片大小可自由调整）答案解析附后卷I一.参考题库(共25题)1.Dijkstra算法求单源最短路径。2.青蛙过河问题中，如果河中没有石柱，有x片荷叶的话，那么从左岸到右岸可以过去（）只青蛙A、x+1只B、x+2只C、x+3只D、x+4只3.希尔排序的时间复杂度是O（n*n）。4.一个算法应该包含如下几条性质，除了（）A、二义性B、有限性C、正确性D、可终止性5.请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。6.数据结构与算法里，完数又称完美数，它等于所有因子之和。7.数据结构与算法里，次关键字能唯一标识一条记录。8.最优子结构性质的含义是（）。9.青蛙过河案例中，如果河中有2根石柱，有3片荷叶，则可以过多少只青蛙（）。A、16只B、32只C、8只D、4只10.整数7和9的最小公倍数是（）。A、7B、9C、21D、6311.数据结构与算法里，不是插入排序的有（）。A、直接插入排序B、希尔排序C、冒泡排序D、快速排序12.回溯法的效率不依赖于下列哪些因素（）A、满足显约束的值的个数B、计算约束函数的时间C、计算限界函数的时间D、确定解空间的时间13.设f（N），g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≤Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）∈○（g（N）），即f（N）的阶（）g（N）的阶。A、不高于B、不低于C、等价于D、逼近14.一根绳子有320米长，每天截取12米，问多少天后绳子长度不足40米？其代码编写如下：则填空处应该填写的语句序列是（） A、len=len-12；B、len=len+12；C、len*=12；D、len-1215.循环控制组成要素包含有（）A、循环起始条件（循环初值）B、循环控制条件C、循环控制变量（步长值）D、循环执行时间16.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下（）说法不正确。A、让水桶大的人先打水，可以使得每个人排队时间之和最小B、让水桶小的人先打水，可以使得每个人排队时间之和最小C、让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D、若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样17.数据结构与算法里，比荷兰国旗算法时间复杂度低的是（）。A、O（n*n）B、O（nlog2n）C、O（log2n）D、O（2^n）18.数据结构与算法里，可以使用两个下标定义的数组，称为二维数组。19.数据结构与算法中，负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度，该值越大则发生冲突可能性越大。20.可以通过赋初值的方式确定数组元素的个数。21.一维数组的定义的形式始下：类型说明符数组名[常量表达式]；*下面关于数组概念描述说法正确的是（）A、数组名应符合标识符的命名规则，正式应用中第一个字符应为英文。B、一维数组就是用一个下标定义的数组，可以存同类型也可以存不同类型数据。C、常量表达式定义了数组元素的个数D、数组下标从0开始22.设散列表中有m个存储单元，散列函数H（key）=key%p，则p最好选择（）。A、小于等于m的最大奇数B、小于等于m的最大素数C、小于等于m的最大偶数D、小于等于m的最大合数23.数据结构与算法里，指针做参数时，属于（）。A、值传递B、地址传递C、函数传递D、递归调用24.设有n个活动的集合s={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si，fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si>=fj或者sj>=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（）。A、最早结束的活动优先安排B、最先开始的活动优先安排C、占用资源时间最少的活动优先安排D、占用资源时间最长的活动优先安排25.以下排序算法中，属于交换排序的算法有（）A、希尔排序B、冒泡排序C、快速排序D、简单选择排序卷II一.参考题库(共25题)1.请画出用回溯法解4皇后问题的解空间树和搜索空间树。2.break语句可以用于下列那些语法中（）A、ifB、switchC、forD、while3.采用高级程序设计语言表达算法，主要好处是什么？4.定义二维数组intarr[3][5]如果全部元素输入，共需要输入15个元素5.投点法是（）的一种。A、分支界限算法B、概率算法C、贪心算法D、回溯算法6.数据结构与算法里，简单选择排序，每趟最多进行（）次交换。A、1B、2C、3D、47.ACM算法的素数算法可以（）来完成。A、使用for循环B、只用switch语句C、只用if语句D、只用printf语句8.数据结构中，关于关键字，下列选项中说法正确的是（）。A、次关键字是可以唯一标识一条记录的关键字B、次关键字是可以识别若干记录的关键字C、次关键字是在表中出现的次数最少的关键字D、无正确答案9.数据结构与算法里，用穷举法逐一列举可能是解决鸡兔同笼问题的办法之一。10.continue是可以用于switch语句中11.数据结构与算法里，属于不稳定排序的是（）。A、快速排序B、冒泡排序C、直接插入排序D、希尔排序12.与顺序查找算法相比，折半查找算法的时间复杂性有多大程度的降低？它是如何提高算法的效率的？13.数据结构与算法里，快速排序的时间复杂度是O（log2n）。14.θ记号在算法复杂性的表示法中表示（）15.小明的烦恼问题，电话号存储的字符是使用（）存储的。A、一维数组B、二维数组C、指针变量D、整型变量16.数据结构与算法里，查找表分为哪几种（）。A、静态查找表B、动态查找表C、混合查找表D、逻辑查找表17.折纸问题算法的代码如下：问该算法的时间复杂度是（） A、O（1）B、O（log2n）C、O（nlog2n）D、O（n）18.希尔排序又叫缩小增量排序，属于交换排序的一种。19.数据结构与算法里，素数是只能被1和本身整除的数，以下是素数的是（）A、7B、11C、13D、1720.数据结构与算法里，从大类上讲，简单选择排序是（）。A、插入排序B、选择排序C、交换排序D、归并排序21.数据结构与算法里，顺序表的查找有（）A、顺序查找B、折半查找C、随机查找D、索引查找22.哪种排序可能发生：在最后一趟排序开始之前，所有记录均不在其最终位置上（）。A、直接插入排序B、简单选择排序C、冒泡排序D、快速排序23.优先队列通常用（）数据结构来实现。A、栈B、堆C、队列D、二叉查找树24.数据结构与算法里，在C语言中，有以下二维数组的定义inta[4][5]；如想引用第五个元素，则书写（）。A、a[4]B、a[5]C、a[0][4]D、a[1][5]25.数据结构与算法里，如果待排序序列是完全有序的，使用改进的冒泡排序，只需要（）趟排序。A、一B、二C、三D、四卷III一.参考题库(共25题)1.排序和查找是常用的计算机算法。按照要求完成下题： （1）对数组A={15，9，115，118，3，90，27，25，5}，使用合并排序方法将其排成递减序。 （2）若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z，先与元素比较，若比较，若，则在前面[n/3]个元素中寻找Z；否则与比较，总之使余下的序列为[n/3]个元素。给出该方法的伪代码描述。 （3）使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：118，31，25。2.循环跳转指的是在循环结构当中，出现的强制终止循环或跳过某些次的循环的一种操作。3.冒泡排序N个记录需要N-1趟排序，就可以完成排序。4.两个整数的最小公倍数的求解一般以先求出它们的最大公约数，计算方法是两数相乘除以最大公约数。5.冒泡排序和（）都属于交换排序。A、快速排序B、直接插入排序C、简单选择排序D、希尔排序6.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是（）A、T（n）=T（n–1）+1，T（1）=1B、T（n）=2n2C、T（n）=T（n/2）+1，T（1）=1D、T（n）=3nlog2n7.下面程序执行后的结果是（） A、28B、34C、40D、108.已知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的最佳求积顺序。（要求：给出计算步骤）9.当输入规模为n时，算法增长率最小的是（）。A、5nB、20log2nC、2n2D、3nlog3n10.用动态规划算法解0-1背包问题：n=5，w=[2，9，4，6，7]，p=[6，10，12，8，13]，c=15。11.数据结构与算法里，O（n）是以下哪种算法的复杂度（）。A、顺序查找B、顺序表删除元素C、顺序表插入元素D、单链表查找第i个元素12.对于下列二分搜索算法，正确的是（）A、B、C、D、13.数据结构与算法里，对不同的关键字可能得到同一哈希地址，即key≠key2面f（key1）=f（key2）这种现象称冲突（collision）。具有相同函数值的关键词对该哈希函数来说乘坐同义词。14.数据结构与算法里，快速排序是（）的一种。A、插入排序B、选择排序C、交换排序D、归并排序15.贪心算法的基本要素是（）和最优子结构性质。16.用for循环实现输出1-100的结构也可以用while结构替换实现该功能17.数据结构与算法里，属于交换排序的有（）。A、快速排序B、冒泡排序C、直接插入排序D、希尔排序18.数据结构与算法里，算法的特性包括（）A、有穷性B、正确性C、可读性D、健壮性19.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（），需要排序的是（），（）。20.数据结构与算法里，完数N的因子一定包括1和N-1这两个数。21.运算符/和%的计算：表达式9/3和3%9的结果分别是（）A、3，3B、3.0，0C、3，3.0D、3，022.数据结构与算法里，循环结构是用来描述可以重复执行的程序。23.以下不是汉诺塔问题的时间复杂度的是（）。A、O（1）B、O（n）C、O（n*n）D、O（2的n次幂）24.把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？请设计一个算法计算K值（只需要计算K值，不用把具体的分法输出）。注意：5，1，1和1，5，1是同一种分法。25.折纸问题属于迭代算法解决的一类问题。卷I参考答案一.参考题库1.参考答案:2.参考答案:A3.参考答案:错误4.参考答案:A5.参考答案:6.参考答案:正确7.参考答案:错误8.参考答案:问题最优解包含其子问题最优解9.参考答案:A10.参考答案:D11.参考答案:C,D12.参考答案:D13.参考答案:A14.参考答案:A15.参考答案:A,B,C16.参考答案:A17.参考答案:C18.参考答案:正确19.参考答案:正确20.参考答案:正确21.参考答案:A,C,D22.参考答案:B23.参考答案:B24.参考答案:C25.参考答案:B,C卷II参考答案一.参考题库1.参考答案: 解空间树： 用回溯法的搜索空间树： 2.参考答案:B,C,D3.参考答案: 高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。4.参考答案:正确5.参考答案:B6.参考答案:A7.参考答案:A8.参考答案:B9.参考答案:正确10.参考答案:错误11.参考答案:A,D12.参考答案: 顺序查找的时间是O（n），折半查找O（logn）降低了一个数量级。 采用分治策略，每一次比较可以排除一半的数据。13.参考答案:错误14.参考答案:紧致界15.参考答案:B16.参考答案:A,B17.参考答案:B18.参考答案:错误19.参考答案:A,B,C,D20.参考答案:B21.参考答案:A,B22.参考答案:A23.参考答案:B24.参考答案:C25.参考答案:A卷III参考答案一.参考题库1.参考答案: （3）搜索118：118>27，所以right＝3；118>115，所以right＝1；118＝118，找到。 搜索31：31>27，所以right＝3；31<90，所以left=4，结束，未找到。 搜索25：9<25<27，所以left=5，right=6；25＝25，找到。2.参考答案:正确3.参考答案:正确4.参考答案:正确5.参考答案:A6.参考答案:C7.参考答案