2024年大学试题(计算机科学)-算法设计与分析笔试参考题库含答案

“人人文库”水印下载源文件后可一键去除，请放心下载！（图片大小可任意调节）2024年大学试题(计算机科学)-算法设计与分析笔试参考题库含答案“人人文库”水印下载源文件后可一键去除，请放心下载！第1卷一.参考题库(共75题)1.关于装填因子，以下说法正确的是（）。A、哈希表的平均查找长度与处理冲突的方法无关。B、若散列表的负载因子（装填因子）α2.以下英文字符串中是回文字符串的应该是（）。A、123321B、11223311C、123213D、1231233.一根绳子有320米长，每天截取12米，问多少天后绳子长度不足40米？其代码编写如下：则填空处应该填写的语句序列是（） A、len=len-12；B、len=len+12；C、len*=12；D、len-124.数据结构与算法里，荷兰国旗算法的基本写法循环中套分支结构。5.运算符%的计算：表达式3%7和7%3的结果分别是（）A、11B、24C、31D、736.羽毛球队有男女运动员各n人。给定两个n×n的矩阵P和Q。P[i][j]是男运动员i和女运动员j配合组成混合双打的竞赛优势，Q[i][j]是女运动员i和男运动员j配合的竞赛优势。由于技术配合或心理状况等各种因素的影响，P[i][j]并不一定等于Q[j][i]。 采用回溯法设计一个算法，计算男女运动员最佳搭配的配对法，使得各组男女双方竞赛优势乘积的总和达到最大。7.哪种排序可能发生：在最后一趟排序开始之前，所有记录均不在其最终位置上（）。A、直接插入排序B、简单选择排序C、冒泡排序D、快速排序8.荷兰国旗问题，定义交换两个元素的函数，参数为指针，请问当参数为指针类型的函数，其传递属于（）。A、值传递B、地址传递C、形参传递D、实参传递9.数据结构中，O（n）是以下哪种算法的复杂度（）。A、顺序查找B、顺序表删除元素C、顺序表插入元素D、单链表查找第i个元素10.下列算法中通常以自顶向下的方式求解最优解的是（）。A、分治法B、动态规划法C、贪心法D、回溯法11.在一个6×6的棋盘上，共放置12颗棋子，每个格子最多只能放一个棋子，要求每一行，每一列以及两条主对角线上恰好都是两颗棋子。请用回溯法输出所有可能的布局。在不考虑对称的情况下，共有多少种布局？12.利用概率的性质计算近似值的随机算法是（），运行时以一定的概率得到正确解的随机算法是（）。13.数据结构与算法里，二叉排序树的右子树也应该是棵二叉排序树14.算法是由若干条指令组成的有穷序列，且要满足输入、（）、确定性和（）四条性质。15.数据结构与算法中，属于插入排序的有（）。A、希尔排序B、直接插入排序C、冒泡排序D、简单选择排序16.数据结构与算法里，简单选择排序的时间复杂度是（）A、O（n*n）B、O（nlog2n）C、O（1）D、都不对17.数据结构与算法里，循环结构是用来描述可以重复执行的程序。18.scanf语句用于格式化输出的，例如%d是输出整型数据的。19.数据结构与算法里，O（n）是以下哪种算法的复杂度（）。A、顺序查找B、顺序表删除元素C、顺序表插入元素D、单链表查找第i个元素20.若有说明：inta[3][4]；，则对a数组元素的非法引用是：（）A、a[0][2*1]B、a[1][3]C、a[4-2][0]D、a[0][4]21.数据结构与算法里，动态查找的典型工具是（），请将不是这个答案的选项选上。A、二叉排序树B、栈C、数组D、队列22.数据结构中，二叉排序的的哪些遍历序列，不能得到一个升序序列，或非递减有序序列。（）A、先序序列B、中序遍历C、后序遍历D、按层次遍历序列23.数据结构与算法里，快速排序在（）情况下，不利于发挥其长处。A、完全乱序B、基本有序C、杂乱无章D、都不对24.C语言中，continue的作用是（）A、结束本次循环，继续下一次循环B、结束本层循环C、结束本次循环，不继续下一次循环D、与case搭档，跳出switch语句25.概率算法有数值概率算法、舍伍德算法和（）、（）。26.用回溯法解布线问题时，求最优解的主要程序段如下：如果布线区域划分为n×m的方格阵列，扩展每个结点需O（1）的时间，L为最短布线路径的长度，则算法共耗时（O（mn）），构造相应的最短距离需要（O（L））时间。27.下列各步骤的先后顺序是（）。 ①调试程序 ②分析问题 ③设计算法 ④编写程序28.以下代码的执行结果是：（） A、是0B、是24C、是6D、是12029.冒泡排序按照各种分类可以是（）。A、稳定排序B、交换排序C、内排序30.分支限界法是一种既带有（）又带有（）的搜索算法。31.数据结构与算法里，下列选项中关于稳定排序说法正确的是（）。A、稳定排序是指对于关键字相等的记录，排序前后相对位置不变B、稳定排序是指对于关键字相等的记录，排序前后相对位置可以变化C、稳定排序是指排序是指将记录变成无序的32.有若干只鸡兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。求笼中各有几只鸡和兔？（）A、鸡有23只，兔有12只B、鸡有12只，兔有23只C、鸡有20只，兔有15只D、鸡有15只，兔有20只33.一个人有一捆草，一只羊，一头老虎。他想把草、羊、老虎运过河。但是老虎要吃羊，羊要吃草。他要羊不吃草，虎不吃羊。完整运过去。请问应怎样运？试写出完整的搬运步骤。34.设散列表中有m个存储单元，散列函数H（key）=key%p，则p最好选择（）。A、小于等于m的最大奇数B、小于等于m的最大素数C、小于等于m的最大偶数D、小于等于m的最大合数35.希尔排序就分类而言属于（）A、归并排序B、选择排序C、交换排序D、插入排序36.有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适（）A、作业从小到大依次分配给空闲的机器B、作业从大到小依次分配给空闲的机器C、每个机器分配一样的作业数D、使用以上几种贪心策略都能找到最优解，所以都合适37.定义二维数组intarr[4][2]如果全部元素输出，共需要输出6个元素38.回文字符串算法，不可以判断一串汉字字符串是否是回文。39.最大效益优先是（）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法40.Olay教授正在为一家石油公司咨询，该公司正在计划建造一条由东向西的石油主管道，该管道要穿过一片有n口井的油田，从每口井中都有一条喷油管沿最短路径与主管道直接相连（喷油管道为南北方向）。 给定各个井的X坐标和Y坐标，Olay教授要如何才能选择最佳主管道的位置（即：使各喷油管长度之和最小）？ 41.什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。42.数据结构与算法里，冒泡排序N个记录需要N-1趟排序，就可以完成排序。43.排序和查找是经常遇到的问题。按照要求完成下题： （1）对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序； （2）请描述递减数组进行二分搜索的基本思想，并给出非递归算法； （3）给出上述算法的递归算法； （4）使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。44.数据结构中，动态查找的常用方法是二叉排序树。45.数据结构与算法里，属于先预测型的循环有，即先判断决定是否去循环（）A、whileB、do-whileC、forD、switch46.数据结构与算法里，希尔排序又称为（）。A、缩小增量排序B、二分插入排序C、多路归并排序D、锦标赛排序47.数据结构与算法里，在C语言中，有以下二维数组的定义inta[4][5]；如想引用第五个元素，则书写（）。A、a[4]B、a[5]C、a[0][4]D、a[1][5]48.属于1-10000以内的完数的是（）A、13B、28C、7D、49849.N个记录是有序的使用什么查找效率更高（）A、顺序查找B、折半查找C、分块查找D、随机查找50.chars1[100]="ABC"，s2[100]="abc"；则strcmp（s1，s2）的结果是（）。A、是0B、是1C、是-1D、不确定51.哈夫曼编码可利用（）算法实现。A、分治策略B、动态规划法C、贪心法D、回溯法52.数据结构与算法里，若有函数定义如下：则以下涉及上述函数的说明语句错误的（） A、doublefun（intx）；B、doublefun（inty）；C、intfun（intx，inty）；D、doublefun（inta，intb）；53.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M=150，使用回溯方法求解此背包问题。请写出状态空间搜索树并计算各个节点处的界限函数值，最后给出装载方案及背包中物品的重量和价值。 54.数据结构与算法里，若查找表中不存在特定元素，称（）。A、查找失败B、查找成功C、不确定D、都不对55.二叉排序树是否可能是一棵完全二叉树（）。A、不可能B、可能C、不确定能不能D、都不对56.数据结构与算法里，A函数调用B函数，B函数又调用了A函数，这种调用是（），下列选项不是正确答案的是（）。A、直接递归B、间接递归C、非递归D、嵌套调用57.数据结构与算法里，斐波那契数列的第5项的值是（）。A、1B、2C、5D、858.对于如下描述的背包问题，请计算最终装入背包的最大价值和以及各个物品装入背包的数量。 背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。59.对以下代码描述正确的是（） A、循环执行4次B、循环条件第1次就不成立，所以循环体一次也不执行C、循环执行5次D、循环次数不确定60.若哈希表的装填因子α<1，则可避免冲突的产生。61.请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。62.数据结构与算法里，散列表的地址区间为0-17，散列函数为H（K）=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则元素59存放在散列表中的地址是（）A、8B、9C、10D、1163.数据结构与算法中，设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。A、8B、9C、5D、364.求证：log（n!）=Θ（nlogn）。65.分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。66.负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度，该值越大则发生冲突可能性越大。67.给定已按升序排好序的n个元素a[0：n-1]，现要在这n个元素中找出一特定元素x。 据此容易设计出二分搜索算法，横线处填（） 68.简单选择排序、快速排序都是不稳定排序。69.优先队列通常用（）数据结构来实现。A、栈B、堆C、队列D、二叉查找树70.简单选择排序每趟排序可能出现多次记录交换。71.数据结构中，由同一类型的数据元素（或记录）构成的集合称为（）。A、数据库B、查找表C、检索器72.数据结构与算法中，希尔排序就稳定性和内外排序而言，属于（）。A、稳定排序B、不稳定排序C、内排序D、外排序73.以下能正确定义一维数组的选项是（）A、intnum[]；B、intnum[0..100]；C、#defineN5intnum[N]；D、ntN=100；intnum[N]；74.求证：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。75.回溯法是一种既带有（）又带有（）的搜索算法。第2卷一.参考题库(共75题)1.数据结构与算法里，鸡兔同笼算法具有的特性包括（）A、有穷性B、确定性C、可行性D、正确性2.对于一维数组，访问其中的元素时，可随机访问，只要制定的下标不越界即可3.穷举法也称枚举法列举所有可能，逐一试探。4.数据结构与算法里，从排序的稳定性来看，快速排序是（）。A、不稳定排序B、稳定排序C、不确定D、都不对5.用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。6.一定范围内的完数求和的求解过程使用循环嵌套完成，其时间复杂度是（）A、O（1）B、O（n）C、O（log2n）D、O（n*n）7.程序调用自身的编程技巧称为递归，递归的英文是（）。A、returnB、recursionC、restartD、reverse8.数据结构中，二叉排序树是（）经常使用的方式。A、静态查找B、动态查找C、随机查找D、跳跃查找9.有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在（）才能使到邮局到这9个村庄的总距离和最短。A、（4.5，0）B、（4.5，4.5）C、（5，5）D、（5，0）10.数据结构与算法里，属于内排序的包含（）。A、快速排序B、冒泡排序C、直接插入排序D、希尔排序11.数据结构与算法里，希尔排序又叫缩小增量排序，属于基数排序的一种。12.简述动态规划算法的基本步骤。13.设函数f1、f2和f3的处理时间分别为O（n）、O（n2）和O（1），分析下列流程的时间复杂性： 14.数据结构与算法中，查找哈希表，解决冲突的方法包括（）。A、数字分析法B、除留余数法C、直接地址法D、线性探测再散列法15.编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。16.冒泡排序的每一趟的过程是要比较（）元素，如果逆序进行交换。A、相邻B、不相邻C、首尾D、都不对17.数据结构与算法里，冒泡排序是不稳定的排序。18.数据结构与算法里，查找的结果可能在集合中也可能不在集合中，分别称为（）。A、查找失败B、查找成功C、不确定D、都不对19.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）=3nlog2n20.一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件满足时，递归（）A、进行运算B、返回C、前进D、结束条件21.ACM算法的素数算法可以（）来完成。A、使用for循环B、只用switch语句C、只用if语句D、只用printf语句22.int型数据与float型数据可以互相进行强制转换。23.实现合并排序利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法24.使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是（），只使用约束条件进行裁剪的是（）。25.二叉排序树的（）上结点的值都小于根结点的值。A、左子树B、右子树C、左子树和右子树D、都不对26.给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。27.请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20，15，10}，价值为{20，30，25}，背包容量为25时搜索空间树。28.请画出用回溯法解4皇后问题的解空间树和搜索空间树。29.可以通过赋初值的方式确定数组元素的个数。30.Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的无向图，Prim算法和Dijkstra算法还能保证获得最优解吗？31.有4个矩阵{A1，A2，A3，A4}，其中Ai与Ai＋1是可乘的，i=1，2，3，连乘积为A1A2A3A4。在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个，并请把所有的子问题列出来。32.引用数组元素时，其数组下标的数据类型允许的是：整型常量或整型表达式33.下面关于NP问题说法正确的是（）A、NP问题都是不可能解决的问题B、P类问题包含在NP类问题中C、NP完全问题是P类问题的子集D、NP类问题包含在P类问题中34.下面关于break与continue描述正确的是。（）A、continue与break具有相同的效果B、continue在循环语句中具有中断循环的作用C、continue语句可以在switch语句中使用D、continue与break都可以用于循环结构中35.数据结构与算法里，较孙子算经中的双层循环解决的鸡兔同笼问题的时间复杂度低的是（）A、O（n*n）B、O（nlog2n）C、O（n*n*n）D、O（2^n）^表示幂36.算法设计的质量指标有哪些？37.数据结构与算法内，就性能而言，希尔排序的时间复杂度是（）。A、O（n*n）B、O（nlog2n）C、O（n）D、O（n3/2）38.对布线问题，以下（）是不正确描述。A、布线问题的解空间是一个图B、可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定C、采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的D、采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件39.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，请问他们怎样排队，才能使得总的排队时间最短。（）A、水桶大的人先打水B、水桶小的人先打水C、按照什么顺序都一样D、先到的人先打水40.数据结构中，下列选项中符合折半查找的前提的是（）。A、顺序存储B、记录有序C、记录无序D、链式存储41.数据结构与算法里，装填因子又称为（）。A、负载因子B、平衡因子C、外力因子D、合力因子42.数据结构与算法里，改进的冒泡排序最好的情况是（），只需要一趟，发现无数据交换，就可以停止，排序完毕。A、记录完全逆序B、记录完全有序C、记录杂乱无序D、都不对43.下列随机算法中运行时有时候成功有时候失败的是（）A、数值概率算法B、舍伍德算法C、拉斯维加斯算法D、蒙特卡罗算法44.函数的这种调用方式属于（） A、穷举B、递归C、迭代D、分治45.数据结构中，下列选项中是折半查找的时间复杂度的是（）。A、O（1）B、O（log2n）C、O（n*n）D、O（n）46.数据结构与算法里，与i=i*2；等价的语句是（）A、i+=2；B、i++；C、i=i*2；D、i**47.与顺序查找算法相比，折半查找算法的时间复杂性有多大程度的降低？它是如何提高算法的效率的？48.数据结构与算法里，while循环属于当型循环，其循环变量的初值写在（）A、while语句{}中的第一句B、while语句{}中的最后一句C、while语句的上面D、while语句的下面49.一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？50.数据结构与算法里，变量height要比原来少15，则应写成（）A、height-15B、height=15C、height=-15D、height-=1551.do..while条件为假时一次也不执行循环体语句52.循环语句中，循环执行次数是（） A、5B、100C、3D、453.30个记录进行冒泡排序，使用未改进的冒泡排序，则需要（）趟排序才能完成排序。A、29B、30C、28D、2754.汉诺塔问题是古老的问题，不可以使用递归解决，最初是原型是印度的僧人移动盘子的故事。55.数据结构与算法里，计算完数和，有累加器名为sum，应如何赋初值（）A、sum=0B、sum==0C、sum+=0；D、sum=1；56.贪心算法的基本要素是（）质和（）性质。57.在C语言中若有定义语句inta[6]按在内存中的存放顺序，a数组的第3个元素是（）A、[4]B、a[1]C、a[3]D、a[2]58.给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1]=1，m[i]（1A、m[i]=1+max{0，m[k]（A[k]B、m[i]=1+m[k]（k=i-1&&i>1）C、m[i]=1+max{0，m[k]（A[k]≤A[i]，1≤k<i）}D、m[i]=max{0，m[k]（A[k]59.对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（）A、n!B、2nC、2n+1-1D、60.哈弗曼编码的贪心算法所需的计算时间为（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）61.数据结构与算法里，交换排序和插入排序是没有什么区别的。62.舍伍德算法总能求得问题的（）。63.break语句格式中，使用正确的是（）A、while（条件）{break；}B、其它三项都不对C、for（；；）{break；}D、do{break；}while（条件）；64.数据结构与算法里，从算法的设计要求上讲，汉诺塔应具有（）。A、有穷性B、确定性C、可行性D、可读性65.若变量inti，intsum=0，要求程序段完成求1加到100的和的，能完成此操作的程序段不正确的是（）A、for（i=1；i66.数据结构与算法里，顺序表的查找有顺序查找和（）。A、折半查找B、线性查找C、随机查找D、索引查找67.数据结构与算法里，循环语句中加break的作用的是（）A、break用于循环语句的作用是结束本层循环B、break用于循环语句的作用是结束本次循环，继续下一下循环C、break不能用于switch语句D、break语句不能用do-while语句开会68.鸡兔同笼不仅仅限于孙子算经中描述，也可以其它类似问题，如大人小孩吃面包的问题，或者是大小油瓶的问题。69.比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？70.数据结构与算法里，属于不稳定排序的是（）。A、快速排序B、冒泡排序C、直接插入排序D、希尔排序71.冒泡排序的时间复杂度是O（n*n）。72.实现循环赛日程表利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法73.希尔排序属于不稳定排序，而直接插入排序是稳定排序。74.下述表达不正确的是（）A、n2/2+2n的渐进表达式上界函数是O（2n）B、n2/2+2n的渐进表达式下界函数是Ω（2n）C、logn3的渐进表达式上界函数是O（logn）D、logn3的渐进表达式下界函数是Ω（n3）75.冒泡排序的时间复杂度（）。A、O（n）B、O（n*n）C、O（1）D、都不对第1卷参考答案一.参考题库1.参考答案：C,D2.参考答案：A3.参考答案：A4.参考答案：正确5.参考答案：C6.参考答案： 对于这个问题，解空间如下： 在这个解空间中采用回溯方法，由于一个男队员只能和一个女队员搭档，反之也同理，因此，对于搜索的第一步选定某男和某女，那么第二个男队员就不能和第一个男队员的女搭档组合，因此，剪去改女队员的分枝。 将男女队员的竞赛优势乘积计算出来，然后将各组男女的优势乘积进行相加。找出最大值。7.参考答案：A8.参考答案：B9.参考答案：A,B,C,D10.参考答案：C11.参考答案：12.参考答案：数值概率算法；蒙特卡罗算法13.参考答案：正确14.参考答案：输出；有限性15.参考答案：A,B16.参考答案：A17.参考答案：正确18.参考答案：错误19.参考答案：A,B,C,D20.参考答案：D21.参考答案：B,C,D22.参考答案：A,C,D23.参考答案：B24.参考答案：A25.参考答案：拉斯维加斯；蒙特卡罗26.参考答案：27.参考答案：②③④①28.参考答案：A29.参考答案：A,B,C30.参考答案：系统性；跳跃性31.参考答案：A32.参考答案：A33.参考答案： 1、运羊； 2、运草；把羊带回。 3、运虎； 4、运羊。34.参考答案：B35.参考答案：D36.参考答案：B37.参考答案：错误38.参考答案：正确39.参考答案：A40.参考答案： 这是中位数的应用问题。在顺序统计的问题中，中位数的应用最广，例如在X轴上有n个点，由左到右依次排列为X1，X2，…，Xn。 我们希望在x轴上寻找一点Xp，使得Xp与各点距离之和最小。这个问题可以归结为中位数问题。即： 当n为奇数时，Xp为X（n+1）/2，否则，Xp为 从这个例子出发，本题求主油管道的问题也是类似的。 由于主管道由东向西，因此，要使连接油井和主油管道的喷井管道最短，喷井管道必须南北走向，与主管道垂直，即主管道的最优位置应为一条Y＝Yk的水平线，问题是Yk如何确定。 为了使Yk与各油井的Y坐标Y1，Y2，…，Yn间的距离和最短，我们将Y1，…，Yn由小到大排序，选择最中间的那个点作为Yk，（若油井为奇数，则取第（n+1）/2小的Y坐标作为Yk，若油井为偶数，则取第n/2小的Y坐标值与第（n/2+1）小的Y坐标值的平均数作为Yk的值。 显然，确定主油管道的最佳位置，实际上就是求n个油井的Y坐标的中位数。41.参考答案：用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。 用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。 集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。42.参考答案：正确43.参考答案： （4）搜索18：首先与27比较，1827，在前半部分搜索；再次32比较，3129，此时只有一个元素，未找到，返回-1。 搜索135：首先与27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；与135比较，相同，返回0。44.参考答案：正确45.参考答案：A,C46.参考答案：A47.参考答案：C48.参考答案：B49.参考答案：B50.参考答案：C51.参考答案：C52.参考答案：A,B,D53.参考答案： 按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得： 在Q1处获得该问题的最优解为（1，1，1，1，0，0，1），背包效益为170。即在背包中装入物品F，B，G，D，A时达到最大效益，为170，重量为150。 54.参考答案：A55.参考答案：B56.参考答案：A,C,D57.参考答案：C58.参考答案： 物品1的单位重量价值为50元/千克；物品2的单位重量价值为60元/千克；物品3的单位重量价值为30元/千克。采用贪心算法解此背包问题。 此时，贪心的策略是：每次选择单位重量价值最大的物品。因此，首先选择物品2，然后是物品1，最后是物品3，直至将背包装满。 物品2全部装入背包，当前背包中价值120元，背包占用20千克，剩余30千克； 物品1全部装入背包，当前背包中价值220元（120元＋100元），背包占用40千克，剩余10千克； 物品3的1/3被装入背包，当前背包中价值250元（120元＋100元＋90元×1/3），背包占用50千克（装满）。 因此，最终装入背包的最大价值为250元，物品1和物品2都全部装入，分别是20千克和20千克，物品3装入1/3，是10千克。59.参考答案：C60.参考答案：错误61.参考答案：62.参考答案：D63.参考答案：B64.参考答案：65.参考答案：（1）贪心算法O（nlog（n）） 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下： （2）动态规划法O（nc） M（i，j）是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m（i，j）的递归式如下。 （3）回溯法O（2n） 66.参考答案：正确67.参考答案： ；；68.参考答案：正确69.参考答案：B70.参考答案：错误71.参考答案：B72.参考答案：B,C73.参考答案：C74.参考答案：对于任意f1（n）∈O（f（n）），存在正常数c1和自然数n1，使得对所有≥n1，有f1（n）≤c1f（n）。 类似地，对于任意g1（n）∈O（g（n）），存在正常数c2和自然数n2，使得对所有n≥n2，有g1（n）≤c2g（n）。 75.参考答案：系统性；跳跃性第2卷参考答案一.参考题库1.参考答案：A,B,C2.参考答案：正确3.参考答案：正确4.参考答案：A5.参考答案：至少需要对每个元素进行一次比较运算，运算时间是O（n）。6.参考答案：D7.参考答案：B8.参考答案：B9.参考答案：C10.参考答案：A,B,C,D11.参考答案：错误12.参考答案： 设计一个标准的动态规划算法，通常可按以下几个步骤进行： （1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。 （2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 （3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 （4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。 一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的主要难点在于理论上的设计，一旦设计完