算法分析第八次作业答案(卜东波)

算法考试题目及答案解析一、单项选择题1. 在算法中，以下哪个选项不是算法的特性？A. 有穷性B. 确定性C. 可行性D. 随机性答案：D解析：算法的特性包括有穷性、确定性和可行性。

有穷性指的是算法必须在执行有限步骤后终止；确定性指的是算法的每一步操作都是明确的，不存在二义性；可行性指的是算法的每一步操作都必须足够基本，以至于可以准确地执行。

随机性并不是算法的特性之一。

2. 以下哪个排序算法的时间复杂度是O(n^2)？A. 快速排序B. 归并排序C. 冒泡排序D. 堆排序答案：C解析：冒泡排序是一种简单的排序算法，其时间复杂度为O(n^2)，在最坏的情况下，需要比较每一对元素。

快速排序的平均时间复杂度为O(n log n)，归并排序的时间复杂度为O(n log n)，堆排序的时间复杂度为O(n log n)。

3. 在图的遍历中，深度优先搜索（DFS）使用的栈是什么类型的栈？A. 后进先出栈B. 先进后出栈C. 先进先出栈D. 随机进随机出栈答案：B解析：深度优先搜索（DFS）使用的数据结构是栈，遵循的是先进后出的原则，即后进先出栈。

4. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 二分查找法答案：D解析：哈希表解决冲突的方法主要包括分离链接法、开放寻址法和链地址法。

二分查找法是一种查找算法，不是用来解决哈希表冲突的方法。

5. 以下哪个算法不是动态规划算法？A. 斐波那契数列B. 0-1背包问题C. 最短路径问题D. 快速排序答案：D解析：斐波那契数列、0-1背包问题和最短路径问题都可以使用动态规划算法来解决。

快速排序是一种排序算法，不属于动态规划算法。

二、多项选择题1. 以下哪些是算法设计中常用的数据结构？A. 数组B. 链表C. 栈D. 队列E. 树答案：ABCDE解析：数组、链表、栈、队列和树都是算法设计中常用的数据结构，它们各自有不同的特点和适用场景。

东北师范大学22春“计算机科学与技术”《算法分析与设计》作业考核题库高频考点版（参考答案）一.综合考核(共50题)1.函数atoi(“1234”)的函数返回值是1234。

()A.错误B.正确参考答案：B2.已知一列数{8，9，7，4，1，2}，使用简单选择排序法对其按照升序进行排列，第0趟比较之后数列为()A.8，9，7，4，1，2B.1，9，7，4，8，2C.8，7，4，1，2，9D.1，2，8，9，7，4参考答案：B3.在C语言中字符串的头文件是string.h。

()A.错误B.正确参考答案：B4.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。

A.编写程序B.调试程序C.执行程序D.编译程序参考答案：B5.下列说法错误的是()A.使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码B.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序C.自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器D.调试器不能解决程序中出现的问题参考答案：D6.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。

()A.错误B.正确参考答案：A7.穷举法，也称辗转法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。

()A.错误B.正确参考答案：A8.例如“DisplayInfo()”和“UserName”这样的命名规则是()。

A.匈牙利命名法B.骆驼命名法C.下划线命名法D.帕斯卡命名法参考答案：D9.图中有关路径的定义是()。

C.由不同边所形成的序列D.上述定义都不是参考答案：A10.字符数组可用字符串来初始化。

()A.错误B.正确参考答案：B11.一个n个顶点的连通无向图，其边的个数至少为()。

A.n-1B.nC.n+1D.nlogn参考答案：A12.在程序调试中，我们需要借助于()来中断程序的运行，查看变量的值。

新数学《算法与框图》专题解析一、选择题1．执行如图所示的程序框图，则输出S 的值为（ ）A ．3B ．32C ．0D ．3-【答案】A 【解析】 【分析】 【详解】试题分析：第一次循环：133,22a S ==,第二次循环：23,32a S ==，第三次循环：30,3a S ==,第四次循环：433,a S =-=,第五次循环：53,0a S =-=,第六次循环：60,0a S ==,第七次循环：733,a S ==,第八次循环：83,3a S ==,第九次循环：90,3a S ==此时98i =>，结束循环，输出3S =，选A.考点：循环结构流程图2．执行如图所示的程序框图，则输出的结果为（ ）A ．40322017 B ．20152016C ．20162017D ．20151008【答案】D 【解析】循环依次为1111,1,2;3,1,3;6,1,4;336s t i s t i s t i =====+===++=L 直至1111,2016;12123122015t i =++++=++++++L L 结束循环，输出1111111112(1)1212312201522320152016t =++++=-+-++-++++++L L L 120152(1)20161008=-=，选D. 点睛：算法与流程图的考查，侧重于对流程图循环结构的考查.先明晰算法及流程图的相关概念，包括选择结构、循环结构、伪代码，其次要重视循环起点条件、循环次数、循环终止条件，更要通过循环规律，明确流程图研究的数学问题，是求和还是求项.3．下列各数中，最小的是( ) A ．101 010(2) B ．111(5)C ．32(8)D ．54(6)【答案】C 【解析】()543221010101202120242=⨯+⨯+⨯+⨯= ()210511115151531=⨯+⨯+⨯= ()10832382826=⨯+⨯= ()10654564634=⨯+⨯=故最小的是()832 故答案选C4．执行如图所示的程序框图，若输出S 的值为43，则输入a 的值可能为（ ）A ．4B ．10C ．79D ．93【答案】D 【解析】 【分析】由题中的程序框图知，该算法是一个以4为周期的函数，若输出S 的值为43，则得出相应的k 值，再由k a >输出，即可得出a 值，再判断选项得出 【详解】程序运行如下：3,1S k ==；4,23S k ==；1,32S k ==； 2,4S k =-=；3,5S k ==；…，此程序的S 值4个一循环.若输出S 的值为43，则相应k 的值为()1142k k N +∈， 因为k a >时，输出S ，则输入a 的值为()1141k k N +∈. 故选：D . 【点睛】本题考查了循环结构的程序框图，根据算法的功能确定S 值的周期规律及跳出循环的k 值是解答本题的关键，属于中档题．5．程大位是明代著名数学家，他的《新编直指算法统宗》是中国历史上一部影响巨大的著作．卷八中第33问：“今有三角果一垛，底阔每面七个．问该若干？”如图是解决该问题的程序框图．执行该程序框图，求得该垛果子的总数S 为（ ）A ．28B ．56C ．84D ．120【答案】C 【解析】 【分析】由已知中的程序可知：该程序的功能是利用循环结构计算并输出变量S 的值，模拟程序运行过程，分析循环中各变量值的变化情况，即可求解. 【详解】模拟程序的运行，可得：0,0,0i n S === 执行循环体，1,1,1i n S ===；不满足判断条件7i ≥，执行循环体，2,3,4i n S ===； 不满足判断条件7i ≥，执行循环体，3,6,10i n S ===； 不满足判断条件7i ≥，执行循环体，4,10,20i n S ===； 不满足判断条件7i ≥，执行循环体，5,15,35i n S ===； 不满足判断条件7i ≥，执行循环体，6,21,56i n S ===； 不满足判断条件7i ≥，执行循环体，7,28,84i n S ===； 满足判断条件7i ≥，退出循环，输出S 的值为84. 故选：C. 【点睛】本题主要考查了循环结构的程序框图的计算与输出问题，其中解答中模拟程序运行的过程，通过逐次计算和找出计算的规律是解答的关键，着重考查了推理与计算能力，属于基础题.6．如图所示的程序框图，若输出的结果为4，则输入的实数的取值范围是（ ）A ．B ．C ．D ．【答案】A 【解析】，，否，； ，否，； ，否，；，，是，即；解不等式，，且满足，，综上所述，若输出的结果为4，则输入的实数的取值范围是，故选．点睛：算法与流程图的考查，侧重于对流程图循环结构的考查.先明晰算法及流程图的相关概念，包括选择结构、循环结构、伪代码，其次要重视循环起点条件、循环次数、循环终止条件，更要通过循环规律，明确流程图研究的数学问题，是求和还是求项.7．执行下面程序框图，若输入的的值分别为0和44，则输出的值为（）A．4 B．7 C．10 D．13【答案】C【解析】【分析】模拟执行程序框图，只要按照程序框图规定的运算方法逐次计算，直到达到输出条件即可得到输出的的值.【详解】第一次循环：，，；第二次循环：，，；第三次循环：，，；第四次循环：，，刚好满足条件，结束循环，此时输出.故选.【点睛】本题主要考查程序框图的循环结构流程图，属于中档题. 解决程序框图问题时一定注意以下几点：(1) 不要混淆处理框和输入框；(2) 注意区分程序框图是条件分支结构还是循环结构；(3) 注意区分当型循环结构和直到型循环结构；(4) 处理循环结构的问题时一定要正确控制循环次数；(5) 要注意各个框的顺序,（6）在给出程序框图求解输出结果的试题中只要按照程序框图规定的运算方法逐次计算，直到达到输出条件即可.，则判断框8．运行如图所示的程序框图，若输入的a的值为2时，输出的S的值为20中可以填（）A ．3?k <B ．4?k <C ．5?k <D ．6?k <【答案】C 【解析】 【分析】模拟执行程序框图的运行过程，即可得出程序运行后输出20S =-时判断框中可以填的条件. 【详解】 运行该程序：第一次循环，2,2,2S a k ==-=； 第二次循环6,2,3S a k =-==； 第三次循环，12,2,4S a k ==-=； 第四次循环，20,2,5S a k =-==，此时输出S 的值，观察可知，仅选项C 符合题意. 故选:C 【点睛】本题主要考查含有当型循环结构的程序框图；考查学生的逻辑推理能力和运算求解能力；熟练掌握含有循环结构的程序框图的运行方法是求解本题的关键；属于中档题、常考题型.9．某程序框图如图所示，若该程序运行后输出的结果为86，则正整数k 的最小值为（ ）A．1 806 B．43 C．48 D．42【答案】B【解析】【分析】根据已知中的程序框图，模拟程序的执行过程，可得答案．【详解】解：开始，n＝1，S＝1，故S＝2×1＋1＝3，n＝1×(1＋1)＝2，S与输出的结果不符，故2≥k不成立．S＝2×3＋2＝8，n＝2×(2＋1)＝6，S与输出的结果不符，故6≥k不成立．S＝2×8＋6＝22，n＝6×(6＋1)＝42，S与输出的结果不相符，故42≥k不成立．S＝2×22＋42＝86，n＝42×(42＋1)＝1 806.S与输出的结果相符，故1 806≥k成立．所以k的最小值为43.故选：B.【点睛】本题考查的知识点是程序框图，难度不大，属于基础题．10．执行如图所示的程序框图，输出的值为（）A．13B．12C．2 D．2-【答案】A【解析】【分析】根据程序框图所示的意义可得a的值，构成周期数列，即可得答案；【详解】1i=，3a=-；2 i=，12a=-；3 i=，13 a=；4i=，2a=；5i=，3a=-，可以看出是周期为4的数列，55 i=，13 a=.56i=，终止循环，输出13 a=.故选：A.【点睛】本题考查算法中程序框图的循环结构，考查函数与方程思想、转化与化归思想，考查逻辑推理能力、运算求解能力，求解时注意与数列的周期性相结合.11．执行如图的程序框图，那么输出S的值是( )A ．-1B ．12C ．2D ．1【答案】C 【解析】判断2014<2017,执行1120141201512S k ==-=+=-， ； 判断2015<2017,执行11201512016112S k ，（）===+=-- ；判断2016<2017,执行12201612017112S k ===+=-， ；判断2017<2017,执行输出S,S=2；故选C点睛：本题考查的是算法与流程图，侧重于对流程图循环结构的考查.解决问题要先明晰算法及流程图的相关概念，包括选择结构、循环结构、伪代码，其次要重视循环起点条件、循环次数、循环终止条件，更要通过循环规律，明确流程图研究的数学问题，是求和还是求项.12．某程序框图如图所示，其中21()g n n n =+，若输出的20192020S =，则判断框内可以填入的条件为（ ）A ．2020?n <B ．2020?n „C ．2020?n >D ．2020?n …【答案】A 【解析】 【分析】 因为()()2111111g n n n n n n n ===-+++，此程序框图是对函数()g n 求和，利用裂项相消法求和，可知201912020n S n ==+，可知2019满足条件进入循环，2020不满足条件没有进入循环，根据选项得到正确结果. 【详解】由2221111111112019(1111222231112020n S n n n n n n ⎫⎛⎫⎛⎫=++⋯+=-+-+⋯+-=-==⎪ ⎪ ⎪++++++⎭⎝⎭⎝⎭，解得2019n =，可得n 的值为2019时.满足判断框内的条件，当n 的值为2020时，不满足判断框内的条件，退出循环，输出S 的值，故判断框内可以填人的条件为“2020n <？”.故选A. 【点睛】本题考查根据循环框图的输出结果填写判断框的内容，关键是分析出满足输出结果时的n 值，再根据选项判断结果.13．执行如图所示的程序框图，则输出的a =（ ）A ．32-B ．13-C ．2D ．2-【答案】A 【解析】 【分析】根据循环程序框图，一次循环后，可知本题循环程序是求一个以3为周期的数列：2，13-，32-，2，13-，32-…，所以当2019i =时，输出结果，根据周期性，即可得出结果.【详解】解：根据程序框图，执行程序得： 2,1a i ==，否， 11,2213a i =-=-=+，否， 13,31213a i =-=-=-+，否， 12,4312a i =-==-+，否， 11,5213a i =-=-=+，否， 13,61213a i =-=-=-+，否， L可知本题循环程序是一个以3为周期的数列：2，13-，32-，2，13-，32-…， 当2019i =时，输出结果，则20193673÷=，即循环673个周期，所以输出结果为32-． 故选：A. 【点睛】本题考查由循环程序框图计算输出结果，理解循环结构框图是关键.14．执行如图所示的程序框图，若输出的结果为11，则图中的判断条件可以为（ ）A ．1?S >-B ．0?S <C ．–1?S <D ．0?S >【答案】B 【解析】 【分析】根据程序框图知当11=i 时，循环终止，此时1lg110S =-<，即可得答案. 【详解】1i =，1S =.运行第一次，11lg 1lg30,33S i =+=->=，不成立，运行第二次，131lg lg 1lg50,535S i =++=->=，不成立，运行第三次，1351lg lg lg 1lg70,7357S i =+++=->=，不成立，运行第四次，13571lg lg lg lg 1lg90,93579S i =++++=->=，不成立，运行第五次，135791lg lg lg lg lg 1lg110,11357911S i =+++++=-<=，成立，输出i 的值为11，结束. 故选：B. 【点睛】本题考查补充程序框图判断框的条件，考查函数与方程思想、转化与化归思想，考查逻辑推理能力和运算求解能力，求解时注意模拟程序一步一步执行的求解策略.15．执行如图所示的程序框图，若输出的结果为48，则输入k 的值可以为A ．6B ．10C ．8D ．4【答案】C 【解析】 【分析】执行如图所示的程序框图，逐次循环，计算其运算的结果，根据选项即可得到答案. 【详解】由题意可知，执行如图所示的程序框图，可知： 第一循环：134,2146n S =+==⨯+=； 第二循环：437,26719n S =+==⨯+=； 第三循环：7310,2191048n S =+==⨯+=， 要使的输出的结果为48，根据选项可知8k =，故选C. 【点睛】本题主要考查了循环结构的计算与输出问题，其中解答中正确理解循环结构的程序框图的计算功能，逐次准确计算是解答的关键，着重考查了运算与求解能力，属于基础题.16．执行如图所示的程序框图，令()y f x =，若()1f a >，则实数a 的取值范围是（ ）A ．(,2)(2,5]-∞⋃B ．(,1)(1,)-∞-+∞UC ．(,2)(2,)-∞⋃+∞D ．(,1)(1,5]-∞-⋃【答案】D 【解析】分析：先根据程序框图得()f x 解析式，再根据分段函数解三个不等式组，求并集得结果.详解：因为2,2()=23,251,5x x f x x x x x ⎧⎪≤⎪-<≤⎨⎪⎪>⎩，所以由()1f a >得25225112311a a a a a a >⎧≤<≤⎧⎧⎪⎨⎨⎨>->>⎩⎩⎪⎩或或 所以11225115a a a a a <-<≤<≤∴<-<≤或或或， 因此选D.点睛：算法与流程图的考查，侧重于对流程图循环结构的考查.先明晰算法及流程图的相关概念，包括选择结构、循环结构、伪代码，其次要重视循环起点条件、循环次数、循环终止条件，更要通过循环规律，明确流程图研究的数学问题，是求和还是求项.17．执行如图所示的程序框图，若输出的S 为154，则输入的n 为（ ）A ．18B ．19C ．20D ．21【答案】B【解析】 【分析】找到输出的S 的规律为等差数列求和，即可算出i ，从而求出n . 【详解】由框图可知，()101231154S i =+++++⋯+-= ， 即()1231153i +++⋯+-=，所以()11532i i -=，解得18i =，故最后一次对条件进行判断时18119i =+=，所以19n =. 故选：B 【点睛】本题考查程序框图，要理解循环结构的程序框图的运行，考查学生的逻辑推理能力.属于简单题目.18．执行如图所示的程序框图，若输入，则输出的S 的值是A ．B ．C ．D ．【答案】B 【解析】 【分析】本题首先可以通过程序框图明确输入的数值以及程序框图中所包含的关系式，然后按照程序框图所包含的关系式进行循环运算，即可得出结果． 【详解】由程序框图可知，输入，，，第一次运算：，；第二次运算：，； 第三次运算：，； 第四次运算：，；第五次运算：，；第六次运算：，；第七次运算：，；第八次运算：，；第九次运算：，；第十次运算：，，综上所述，输出的结果为，故选B．【点睛】本题考查程序框图的相关性质，主要考查程序框图的循环结构以及裂项相消法的使用，考查推理能力，提高了学生从题目中获取信息的能力，体现了综合性，提升了学生的逻辑推理、数学运算等核心素养，是中档题．19．执行如图所示的程序框图，则输出的n值是（）A．5B．7C．9D．11【答案】C【解析】【分析】根据程序框图列出算法循环的每一步，结合判断条件得出输出的n的值.【详解】执行如图所示的程序框图如下：409S =≥不成立，11S 133==⨯，123n =+=； 1439S =≥不成立，1123355S =+=⨯，325n =+=； 2459S =≥不成立，2135577S =+=⨯，527n =+=； 3479S =≥不成立，3147799S =+=⨯，729n =+=. 4499S =≥成立，跳出循环体，输出n 的值为9，故选C. 【点睛】本题考查利用程序框图计算输出结果，对于这类问题，通常利用框图列出算法的每一步，考查计算能力，属于中等题.20．程大位是明代著名数学家，他的《新编直指算法统宗》是中国历史上一部影响巨大的著作.它问世后不久便风行宇内，成为明清之际研习数学者必读的教材，而且传到朝鲜、日本及东南亚地区，对推动汉字文化圈的数学发展起了重要的作用.卷八中第33问是：“今有三角果一垛，底阔每面七个，问该若干？”如图是解决该问题的程序框图.执行该程序框图，求得该垛果子的总数S 为( )A ．84B ．56C ．35D ．28【答案】A 【解析】 【分析】按照程序框图运行程序，直到满足7i ≥时输出结果即可. 【详解】按照程序框图运行程序，输入0i =，0n =，0S =， 则1i =，1n =，1S =，不满足7i ≥，循环；2i =，3n =，4S =，不满足7i ≥，循环；3i =，6n =，10S =，不满足7i ≥，循环；4i =，10n =，20S =，不满足7i ≥，循环； 5i =，15n =，35S =，不满足7i ≥，循环； 6i =，21n =，56S =，不满足7i ≥，循环；7i =，28n =，84S =，满足7i ≥，输出84S =. 故选：A . 【点睛】本题考查根据程序框图循环结构计算输出结果的问题，属于基础题.。

2-34、Gray码是一个长度为2n的序列。

序列中无相同元素。

每个元素都是长度为n位的串。

相邻元素恰好只有一位不同。

用分治策略设计一个算法对任意的n构造相应的Gray码。

答：设序列中元素由0、1组成。

当 n=1 时 Gray码的序列有2个元素〔21=2〕，分别为：0，| 1当 n=2 时 Gray码的序列有4个元素〔22=4〕，分别为：00，10，| 11，01当 n=3 时 Gray码的序列有8个元素〔23=8〕，分别为：000，100，110，010，| 011，111，101，001当 n=4 时 Gray码的序列有16个元素〔24=16〕，分别为：0000，1000、1100、0100，0110，1110，1010，0010，| 0011，1011，1111，0111，0101，1101，1001，0001从上面的列举可得如下规律：n=k时，Gray码的序列有2k个元素，分别为：n=k-1时的Gray码元素正向后加0，得前2k-1个元素，反向后加1的后2k-1个元素。

如 n=2时 Gray码序列的4个元素分别为：00，10， 11，01当 n=3 时 Gray码序列的前4个元素〔23=8〕，分别为：000，100，110，010是n=2时Gray码四个元素正向后加0，即：000，100， 110，010Gray码序列的后4个元素〔23=8〕，分别为：011，111，101，001 是n=2时Gray码四个元素反向后加1，n=2时Gray码四个元素：00，10， 11，01即：011，111，101，001可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-1的Gray码构成。

算法描述：void Gray( type a[],int n){ char a[];if (n==1) { a[0]=’0’;a[1]=’1’;}if (n>1){ Gray(a[],n-1);int k=2n-1-1; //Gray码的个数，因为数组下标从0开始int i=k;for (int x=k;x>=0;x--){char y=a[x];a[x]=y+’0’;a[i+1]=y+’1’; i++;}}}3-7 给定由n个英文单词组成的一段文章，……答：设由n 个单词组成的一段文章可以表示为 A[1:n]，它的“漂亮打印〞方案记为B[1:n]，构成该最优解的最小空格数〔最优值〕记为m[1][n]（1）分析最优解的结构：A[1:n]的最优解B[1:n]，必然在第k个单词处断开，那么A[1:k]是“漂亮打印〞，并且A[k+1:n]也是“漂亮打印〞。

1．二元可满足性问题 2SAT例：给定布尔变量的一个有限集合{}n u u u U ,,,21 =及定义其上的子句{}m c c c C ,,,21 =，其中m k c k ,,2,1,2|| ==。

问：是否存在U 的一个真赋值，使得C 中所有的子句均被满足？证明： 2SAT 是P －类问题。

为叙述方便，采用数理逻辑中的“合取式”表达逻辑命题，于是∏∏==+==∧∧∧=mk k k m k k m y x c c c c C 1121)(其中j i c c ⋅表示逻辑“与”，k k y x +表示逻辑“或”，k k y x ,是某个j u 或i u 。

考虑表达式∏=+=mk k k y x C 1)(，如果有某个i i k k u u y x +=+，则在乘积式中可以去掉该子句：)(\'i i u u C C +=，可见C 与'C 的可满足性是等价的。

所以我们可以假定C 中不含有形如i i u u +的子句。

注意到此时C 中的子句个数不会超过)1(-n n 。

如果逻辑变量n u 或它的非n u 在C 的某个子句中出现，我们将C 表示成)())(()(11h n n k n n z u z u y u y u G C ++++⋅= （1） 其中G 是C 的一部分子句，而且不出现逻辑变量i u 或它的非i u 。

令∏≤≤≤≤+⋅=h j k i j i z y G C 1,1)(' （2）(2)式中不再含有变量n u 和它的非n u 。

记{}121,,,'-=n u u u U 。

如果存在U 的真赋值，使得C 满足，在'U 也一定满足。

因为如果n u 取真值，则所有的j z 必然取真值；n u 取假值，所有的i y 必然都取真值，不管那中情况，'C 的乘积部分必然取真值。

反之，假设存在'U 的真赋值，使得'C 满足。

若有某个i y 取假值，则所有的j z 必然取真值，此时令n u 取真值，得到U 的真赋值，使得C 满足。

第八套模拟试题参考答案及解析1. 计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。

本题答案为C。

2. 栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。

二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种"后进先出"的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种"先进先出"的线性表。

本题答案为C。

3. 依据后序遍历序列可确定根结点为c；再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e，由中序遍历序列可知其左子树为d，右子树由ba构成。

求得该二叉树的前序遍历序列为选项A。

本题答案为A。

4. 快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置），然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组合成一个新的有序表。

本题答案为D。

5. 滥用goto语句将使程序流程无规律，可读性差；添加的注解行有利于对程序的理解，不应减少或取消；程序的长短要依照实际需要而定，并不是越短越好。

本题答案为A。

6. 调试的关键在于推断程序内部的错误位置及原因。

主要的调试方法有强行排错法、回溯法和原因排除法。

本题答案为B。

7. 软件需求规格说明书（SRS，Software Requirement Specification）是需求分析阶段的最后成果，是软件开发中的重要文档之一。

它有以下几个方面的作用：①便于用户、开发人员进行理解和交流；②反映出用户问题的结构，可以作为软件开发工作的基础和依据；③作为确认测试和验收的依据。

2006-2007学年第二学期《计算机算法设计与分析》试题院系：软件学院专业：软件工程年级：2004级一.简答题（共10分）略二.计算题(35分)1. (6 分)对下列各组函数f(n)和g(n),确定f(n)=O(g(n))或f(n)= Q(g(n))或f(n)=8 (g(n))。

(1)f(n)=3n, g(n)=2n2(2)f(n)=log n + 5, g(n)=log n(3)f(n)=log n, g(n尸J n咨：(1)f(n) = Q(g(n)) (2 分)(2)f(n) = 9(g(n)) (2 分)(3)f(n) = O(g(n)) (2 分)2. (8分)采用动态规划策略，计算a= {5,-37-4,-5,9,-2,10,-3,2}的最大子段和, 并给出这个最大子段和的起始下标和终止下标。

[设数组a中的元素下标从1开始。

]要求给出过程。

答：b[1]=5;b[2]=max{b[1]+a[2] , a[2]}=max{2,-3}=2b[3]=max{b[2]+a[3] , a[3]}=max{9,7}=9b[4]=max{b[3]+a[4] , a[4]}=max{5,-4}=5b[5]=max{b[4]+a[5] , a[5]}=max{0,-5}=0b[6]=max{b[5]+a[6] , a[6]}=max{9,9}=9b[7]=max{b[6]+a[7] , a[7]}=max{7,-2}=7b[8]=max{b[7]+a[8] , a[8]}=max{17,10}=17b[9]=max{b[8]+a[9] , a[9]}=max{14,-3}=14b[10]=max{b[9]+a[10] , a[10]}=max{16,2}=16(上述每两行1分，共5分)最大子段和为17 (1分)(若数组下标从1开始)起始下标：6 (1分)，终止下标：8 (1分)(若数组下标从0开始)起始下标：5 ( 0.5分)，终止下标：7 (0.5分)3 .（11分）设有3件工作分配给3个人，将工作i分配给第j个人所花的费用为C ij,现将为每一个人都分配1件不同的工作，并使总费用达到最小。

算法分析与设计基础习题答案[第1版]习题1.15..证明等式gcd(m,n=gcd(n,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:● 如果d整除u和v, 那么d一定能整除u±v;● 如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n和(n,r具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n=gcd(n,r6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m 的一对数字 ,Euclid 算法在第一次叠代时交换 m 和 n, 即gcd(m,n=gcd(n,m并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次gcd(5,8习题1.21.(农夫过河P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x是求平方根的函数算法Quadratic(a,b,c//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D/tempx2←(-b-sqrt(D/tempreturn x1,x2else if D=0 return –b/(2*aelse return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(intn/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略对这个算法做尽可能多的改进.算法 MinDistance(A[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=nb.删除有序数组的第i个元素(依然有序hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers to mark the i th position is empty. (“lazy deletion”第2章习题2.17.对下列断言进行证明:(如果是错误的,请举例a. 如果t(n∈O(g(n,则g(n∈Ω(t(nb.α>0时,Θ(αg(n= Θ(g(n解:a. 这个断言是正确的。

第8 章排序技术课后习题讲解1. 填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。

【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。

⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。

在（）情况下比较次数最多，其比较次数为（）。

【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。

⑷对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。

【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。

【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。

【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。

【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。

2. 选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。

A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。

⑵下列序列中，（）是执行第一趟快速排序的结果。

A [da，ax，eb，de，bb] ff [ha，gc]B [cd，eb，ax，da] ff [ha，gc，bb]C [gc，ax，eb，cd，bb] ff [da，ha]D [ax，bb，cd，da] ff [eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。