东师《算法分析与设计》20春在线作业1答案30728

算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。

以下是一些典型的算法设计与分析习题及其答案。

习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。

答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

这个过程会不断重复，直到找到目标值或搜索范围为空。

```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。

答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。

```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。

算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。

2.程序：程序是算法⽤某种程序设计语⾔的具体实现。

⼆、简答题：1.算法需要满⾜哪些性质？简述之。

答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。

（2）输出：算法产⽣⾄少⼀个量作为输出。

（3）确定性：组成算法的每条指令清晰、⽆歧义。

（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。

3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。

答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。

该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。

（2）⽤递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。

后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。

三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。

答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。

（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。

A.错误
B.正确
【答案】A
139. strcmp（）函数用来（）。
A.求字符串长度
B.比较字符
C.求子串
D.字符串拷贝
【答案】B
140.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。
A.错误
B.正确
【答案】A
141.采用简单选择排序，比较次数与移动次数分别为()。
A. O(n),O(logn)
A.对象
B.符号
C.标识符
D.命名规则
【答案】C
12.一个算法的评价主要从时间复杂度和()来考虑。
A.空间复杂度
B.算法有效性
C.算法有穷性
D.算法可读性
【答案】A
13. ()是一个开放源代码的、基于Java的可扩展开发平台。
A. VS
B. Dev-C++
C. Eclipse
D. JDK
【答案】C
14.十六进制的213，1的位权是（）。
A. 8,9,7,4,1,2
B. 1,9,7,4,8,2
C. 8,7,4,1,2,9
D. 1,2,8,9,7,4
【答案】B
131.字符数组通过（）来引用其中的某个元素。
A.数组名
B.下标
C.数组名和下标
D.字符串名
【答案】C
132.统计字符串长度时包括字符串结束标志。
A.错误
B.正确
【答案】A
133.字符数组要求其最后一个元素是‘\0’。
A.错误
B.正确
【答案】B
136.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
A.选择排序法
B.插入排序法

算法分析与设计习题集基础篇1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算〔书上定义〕特征：输入、输出、有穷性、明确性、有效性区别：算法是完成特定任务的有限指令集。

程序是用电脑语言编写的写成特定任务的指令序列。

2、算法的时间复杂度指的是什么？如何表示？算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

这是一个关于代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

〔百度百科〕3、算法的空间复杂度指的是什么？如何表示？一个程序的空间复杂度是指运行完一个程序所需内存的大小。

利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。

一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

程序执行时所需存储空间包括以下两部分。

〔1〕固定部分。

这部分空间的大小与输入/输出的数据的个数多少、数值无关。

主要包括指令空间〔即代码空间〕、数据空间〔常量、简单变量〕等所占的空间。

这部分属于静态空间。

〔2〕可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。

这部分的空间大小与算法有关。

一个算法所需的存储空间用f(n)表示。

S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。

答：最坏情况时间复杂性：最好情况时间复杂性：：I*是DN中使T(N, I*)到达Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率10、限界函数的功能是什么？答：用限界函数剪去得不到最优解的子树11、设某一函数定义如下：编写一个递归函数计算给定x的M〔x〕的值。

本函数是一个递归函数，其递归出口是：M〔x〕= x-10x>100递归体是：M〔M〔x+11〕〕x ≤100实现此题功能的递归函数如下：intm ( intx ){ int y;if ( x>100 )return(x-10 );else {y =m(x+11) ;return (m (y ));}procedure M(x)if x>100 thenreturn(x-10)elsereturn M(M(x+11))endifend M12、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。

【奥鹏】-[东北师范大学]算法分析与设计20春在线作业1试卷总分:100 得分:100第1题,按F5开始调试，程序便会直接运行到断点处。

接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。

A、设置断点B、单步调试C、程序编译D、程序调试正确答案:B第2题,()主要是用来显示当前目录的名称或更改当前的目录。

A、dirB、cdC、typeD、fc正确答案:B第3题,输出一个字符串时使用（）格式符。

A、%cB、%sC、%dD、%e正确答案:B第4题,动态规划是一种在数学和计算机科学中使用的，用于求解包含()的最优化问题的方法。

A、重叠子问题B、相似子问题C、互斥子问题D、有序子问题正确答案:A第5题,如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。

A、编写程序B、调试程序C、执行程序D、编译程序正确答案:B第6题,对于循环队列，下列叙述中正确的是（）A、队头指针是固定不变的B、队头指针一定大于队尾指针C、队头指针一定小于队尾指针D、队头指针可以大于队尾指针，也可以小于队尾指针正确答案:D第7题,下列对队列的叙述正确的是（）。

A、队列属于非线性表B、队列按“先进后出”原则组织数据C、队列在队尾删除数据D、队列按“先进先出”原则组织数据正确答案:D第8题,以C语言为例，下列四个选项中，均是不合法的用户标识符的是()。

A、BA、x_0、doB、float、1a0、_YC、x-y、goto、123D、_123、tmp、CHAR正确答案:C第9题,()命令用来显示ASCII码文件的内容。

A、dirB、cdC、typeD、fc正确答案:C第10题,下列排序算法中，其中()是稳定的。

A、堆排序，冒泡排序B、快速排序，堆排序C、直接选择排序，归并排序D、归并排序，冒泡排序正确答案:D第11题,strlen(str)是用来（）。

A、求字符串长度B、比较字符C、求子串D、字符串拷贝正确答案:A第12题,批处理，也称为批处理脚本，其文件扩展名为()。

《算法分析与设计》作业（一）本课程作业由两部分组成。

第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。

第二部分为“主观题部分”，由简答题和论述题组成，共15分。

作业总分30分，将作为平时成绩记入课程总成绩。

客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。

C栈
D循环栈
【答案】：C栈|
3.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。
【选项】：
A不发生改变
B发生改变
C稍有改变
D不能确定
【答案】：A
4.在k叉树中，度为0的结点称为( )。
【选项】：
A根
B叶
C祖先
D子孙
【答案】：B叶|
5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关()。
【选项】：
A空或只有一个结点
B高度等于其结点数
C任一结点无左子女
D任一结点无右子女
【答案】：B
14. n个结点的线索二叉树上含有的线索数为( )。
【选项】：
A n-1
B n
C n +1
D 2n
【答案】：C
15.广义表(( a , b , c , d ) )的表头是()。
【选项】：
A a
B ( )
C ( a , b , c , d )
东北师范大学
东师远程教育
数据结构20春在线作业1
参考答案
试读一页
数据结构20春在线作业1
1个后继，该数据结构是( )
【选项】：
A线性表
B广义表
C树形结构
D图结构
【答案】：A线性表|
2.插入、删除只能在同一端进行的线性表，称为( )。
【选项】：
A队列
B循环队列
C可以链接存储
D数据元素可以是多个字符
【答案】：B
8. head指向的带表头结点的单链表为空的判定条件是( )。
【选项】：
A head = = NULL
B head-&gt;next = = head

(单选题)1: 下列叙述中正确的是（）
A: 在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B: 在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C: 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D: 上述三种说法都不对
正确答案: C
(单选题)2: 十进制算术表达式：3*512+7*64＋4*8＋5的运算结果，用二进制表示为（）。

A: 10111100101
B: 11111100101
C: 11110100101
D: 11111101101
正确答案: B
(单选题)3: 十进制数2014等值于八进制数（）。

A: 4028
B: 3736
C: 2726
D: 2014
正确答案: B
(单选题)4: 下面命名规则中，哪项不是现在比较常用的命名规则()。

A: 匈牙利命名法
B: 骆驼命名法
C: 下划线命名法
D: 图灵命名法
正确答案: D
(单选题)5: 下列叙述中正确的是（）。

A: 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B: 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C: 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D: 上述三种说法都不对
正确答案: B
(单选题)6: 在程序调试中，我们需要借助于()来中断程序的运行，查看变量的值。

A: 变量名
B: 断点
C: 设置断点函数
D: 程序段
正确答案: B
(单选题)7: 十六进制数C1B转换为二进制数是（）。

A: 1100101101011。

算法设计与分析智慧树知到课后章节答案2023年下山东交通学院山东交通学院第一章测试1.解决一个问题通常有多种方法。

若说一个算法“有效”是指( )A:这个算法能在一定的时间和空间资源限制内将问题解决B:这个算法能在人的反应时间内将问题解决C:这个算法比其他已知算法都更快地将问题解决D:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）答案:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）2.农夫带着狼、羊、白菜从河的左岸到河的右岸，农夫每次只能带一样东西过河，而且，没有农夫看管，狼会吃羊，羊会吃白菜。

请问农夫能不能过去？（）A:不一定B:不能过去 C:能过去答案:能过去3.下述（）不是是算法的描述方式。

A:自然语言 B:E-R图 C:程序设计语言 D:伪代码答案:E-R图4.有一个国家只有6元和7元两种纸币，如果你是央行行长，你会设置（）为自动取款机的取款最低限额。

A:40 B:29 C:30 D:42答案:305.算法是一系列解决问题的明确指令。

（）A:对 B:错答案:对6.程序=数据结构+算法（）A:对 B:错答案:对7.同一个问题可以用不同的算法解决，同一个算法也可以解决不同的问题。

（）A:错 B:对答案:对8.算法中的每一条指令不需有确切的含义，对于相同的输入不一定得到相同的输出。

( )A:错 B:对答案:错9.可以用同样的方法证明算法的正确性与错误性 ( )A:错 B:对答案:错10.求解2个数的最大公约数至少有3种方法。

( )A:对 B:错答案:错11.没有好的算法，就编不出好的程序。

（）A:对 B:错答案:对12.算法与程序没有关系。

( )A:错 B:对答案:错13.我将来不进行软件开发，所以学习算法没什么用。

( )A:错 B:对答案:错14.gcd(m,n)=gcd(n,m m od n)并不是对每一对正整数(m,n)都成立。

2020智慧树知到《算法分析与设计》章节测试完整答案智慧树知到《算法分析与设计》章节测试答案第一章1、给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。

答案: 错2、一个问题的同一实例可以有不同的表示形式答案: 对3、同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。

答案: 对4、问题的两个要素是输入和实例。

答案: 错5、算法与程序的区别是()A:输入B:输出C:确定性D:有穷性答案: 有穷性6、解决问题的基本步骤是()。

(1)算法设计(2)算法实现(3)数学建模(4)算法分析(5)正确性证明A:(3)(1)(4)(5)(2)B:(3)(4)(1)(5)(2)C:(3)(1)(5)(4)(2)D:(1)(2)(3)(4)(5)答案: (3)(1)(5)(4)(2)7、下面说法关于算法与问题的说法错误的是()。

A:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。

B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。

C:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。

D:证明算法不正确，需要证明对任意实例算法都不能正确处理。

答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。

8、下面关于程序和算法的说法正确的是()。

A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。

B:程序是算法用某种程序设计语言的具体实现。

C:程序总是在有穷步的运算后终止。

D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。

答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。

,程序是算法用某种程序设计语言的具体实现。

,算法是一个过程，计算机每次求解是针对问题的一个实例求解。

9、最大独立集问题和()问题等价。

A: 最大团B:最小顶点覆盖C:区间调度问题D:稳定匹配问题答案: 最大团,最小顶点覆盖10、给定两张喜欢列表，稳定匹配问题的输出是( ) 。

2020智慧树知到《算法分析与设计》章节测试完整答案智慧树知到《算法分析与设计》章节测试答案第一章1、给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。

答案: 错2、一个问题的同一实例可以有不同的表示形式答案: 对3、同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。

答案: 对4、问题的两个要素是输入和实例。

答案: 错5、算法与程序的区别是()A:输入B:输出C:确定性D:有穷性答案: 有穷性6、解决问题的基本步骤是()。

(1)算法设计(2)算法实现(3)数学建模(4)算法分析(5)正确性证明A:(3)(1)(4)(5)(2)B:(3)(4)(1)(5)(2)C:(3)(1)(5)(4)(2)D:(1)(2)(3)(4)(5)答案: (3)(1)(5)(4)(2)7、下面说法关于算法与问题的说法错误的是()。

A:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。

B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。

C:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。

D:证明算法不正确，需要证明对任意实例算法都不能正确处理。

答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。

8、下面关于程序和算法的说法正确的是()。

A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。

B:程序是算法用某种程序设计语言的具体实现。

C:程序总是在有穷步的运算后终止。

D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。

答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。

,程序是算法用某种程序设计语言的具体实现。

,算法是一个过程，计算机每次求解是针对问题的一个实例求解。

9、最大独立集问题和()问题等价。

A: 最大团B:最小顶点覆盖C:区间调度问题D:稳定匹配问题答案: 最大团,最小顶点覆盖10、给定两张喜欢列表，稳定匹配问题的输出是( ) 。

第3章 动态规划
2. 石子合并问题 问题描述: 在一个圆形操场的四周摆放着n堆石子. 现在要将石子有次序地合并 成一堆. 规定每次只能选相邻的2堆石子合并成一堆, 并将新的一堆石子数记为 该次合并的得分. 试设计一个算法, 计算出将n堆石子合并成一堆的最小得分和 最大得分. 算法设计: 对于给定n堆石子, 计算合并成一堆的最小得分和最大得分. 数据输入: 由文件input.txt提供输入数据. 文件的第1行是正整数n, 1n100, 表 示有n堆石子. 第2行有n个数, 分别表示n堆石子的个数. 结果输出: 将计算结果输出到文件output.txt, 文件第1行是最小得分, 第2行是最 大得分.
第五章 回溯
运动员最佳配对问题
问题描述: 羽毛球队有男女运动员各n人. 给定2个nn矩阵P和Q. P[i][j]是男运 动员i与女运动员j配混合双打的男运动员竞赛优势; Q[i][j]是女运动员i与男运 动员j配混合双打的女运动员竞赛优势. 由于技术配合和心理状态等各种因素 影响, P[i][j]不一定等于Q[j][i]. 男运动员i和女运动员j配对的竞赛优势是 P[i][j]*Q[j][i]. 设计一个算法, 计算男女运动员最佳配对法, 使得各组男女双方 竞赛优势的总和达到最大.
8.
若m[i,j]>t, 则m[i,j]=t; s[i,j]=k;
第3章 动态规划
再讨论圆周上的石子合并问题, 子结构[i:j]稍作修改 • 定义m[i][len]为合并第i堆到第i+len-1堆石子能得到的最少分数 • 当i+len-1>n时, 指跨过第n堆到第(i+len-1)%n堆,
仅sum函数需要修改
第2章 分治
2-8 设n个不同的整数排好序后存于T[1:n]中. 若存在一个下标i， 1 i n, 使得T[i]=i. 设计一个有效算法找到这个下标. 要求算 法在最坏情况下的计算时间O(log n).

《算法分析与设计》练习题一答案1.程序书写格式应该遵循哪四个原则？参考答案：（1）正确使用缩进：一定要有缩进，否则代码的层次不明显。

（2）在一行内只写一条语句。

（3）, '}'位置不可随意放置。

（4）变量和运算符之间最好加1个空格2.什么是算法？参考答案：用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。

算法可以理解为冇基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类屮每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。

或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

3.什么是线性结构？什么是非线性结构？参考答案：线性结构：数据逻辑结构屮的一类。

它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所冇结点都冇R只冇一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

栈、队列、串等都是线性结构。

非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接而趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

4.已知二叉树后序遍丿力序列是DABEC,屮序遍丿力序列是DEBAC,则前序遍历序列是什么？参考答案：前序遍历序列是CEDBA5.什么是数制？参考答案：数制是人们利用符号进行计数的一种科学方法。

数制也称计数制，是用一组固定的符号和统一的规则來表示数值的方法。

6.如果将十进制数106转换为八进制数，结果是多少？参考答案：1527.请问查找算法的效率用什么进行度量？参考答案：平均查找长度ASL：在查找其关键字等于给定值的过程小，需要和给定值进行比较的关键字个数的期望值称为查找成功吋的平均查找长度。

AS厶=£皿/=1其屮，n是结点的个数；是杳找第i个结点的概率,是找到第i个结点所需要的比较次数。

算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。

频率计数是指计算机执行程序中的某一条语句的执行次数。

多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。

指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。

2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。

3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。

4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。

5. 解：①n=11； ②n=12； ③n=982； ④n=39。

第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。

2． 解：通过分治算法的一般设计步骤进行说明。

3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(−−=n n f n② )log *()(n n n f O =6． 解：算法略。

《算法分析与设计》作业1、考虑,10≤≤i x 而不是x i ∈{0，1}的连续背包问题。

一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包内装如此物品的一部分。

(a) 对于n=3，w=[100,10,10]，p=[20,15,15]，以及c=105，上述装入法获得结果是什么？(b)证明这种贪婪算法总能获得最优解。

(c) 用伪代码描述此算法。

答：（a ）利用贪婪算法，按价值密度考察的背包为w2，w3，w1；背包w2和w3重20，还可以容纳85，由于10≤≤i x ，背包w1还可以装入x1=0.85，则背包内物品总价值为15+15+20*0.85＝47.（b ）假设已按价值密度排好序，考察w1,w2,……,wi ，……，对应的价值为p1,p2,……,pi,……如果装到pi-1再装pi 时，恰好要取xi 个wi 。

（,10≤≤i x ） 因为比它价值密度大的都已装载完，所以此时获得的为最优解。

（c ）算法描述如下： template <class T>int ContainerLoading( int x[], T w[], T c, int n ) {int *t = new int[n+1]; IndirectSort(w, t, n); for( int i=1; i<=n; i++) x[i] = 0;for(i=1; i<=n && w[t[i]]<=c; i++){ x[t[i]] = 1; c += w[t[i]]; } delete []t; }2、证明当且仅当二分图没有覆盖时，下述算法找不到覆盖。

m＝0; //当前覆盖的大小对于A中的所有i，New[i]=Degree[i]对于B中的所有i，Cov[i]=falsewhile(对于A中的某些i，New[i]>0) {设v是具有最大的New[i]的顶点；C[m++]=v;for(所有邻接于v的顶点j) {If(!Cov[j]) {Cov[j] = true;对于所有邻接于j的顶点，使其New[k]减1}}}if (有些顶点未被覆盖) 失败else 找到一个覆盖2）给出一个具有覆盖的二分图，使得上述算法找不到最小覆盖。

5..证明等式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,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,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//输出:实根或者无解信息D←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*a)else 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=(int)n/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<=n)b.删除有序数组的第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(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

【选项】：
A错误
B正确
【答案】：B
31.最佳二叉排序树是AVL树(平衡二叉排序树)。
【选项】：
A错误
B正确
【答案】：B
32.用链表( lchild-rchild表示法)存储的包含n个结点的二叉树，结点的2n个指针域中有n + l个空指针。
【选项】：
A错误
B正确
【答案】：B
33.程序一定是算法。
【选项】：
C不同的同义词子表结合在一起
D散列表“溢出”
【答案】：C
11.数组A[6,7]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是()。
【选项】：
A 1165
B 1170
C 1175
D 118
A图的遍历是从给定的源点出发每个顶点仅被访问一次
东北师范大学
东师远程
数据结构20春在线作业1
参考答案
试读一页
数据结构20春在线作业1
1.数据序列( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 )只能是下列排序算法中的()的两趟排序后的结果。
【选项】：
A直接选择排序
B冒泡排序
C直接插入排序
D堆排序
【答案】：C
2.下面关于算法说法错误的是（）。
【答案】：C
15.存放在外存中的数据的组织结构是()。
【选项】：
A数组
B表
C文件
D链表
【答案】：C
16.从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行( )。
【选项】：
A x = top; top = top-&gt;next;