东师《算法分析与设计16秋在线作业1
东北师范大学东师算法分析与设计16秋在线作业1
一、单选题（共20 道试题，共40 分。）
1. n个结点的完全有向图含有边的数目（）。
A. n*n
B. n（n＋１）
C. n／2
D. n*（n－l）
正确答案：
2. 在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A. 1/2
B. 2
C. 1
D. 4
正确答案：
3. 将递归算法转换成对应的非递归算法时，通常需要使用()。
A. 栈
B. 队列
C. 链表
D. 树
正确答案：
4. 分治法是把一个复杂的问题分成相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题解的()
A. 合并
B. 最大值
C. 最小值
D. 平均值
正确答案：
5. strcmp("a","b")返回的值是（）
A. 2
B. 1
C. 0
D. -1
正确答案：
6. 一个算法中的语句的()被称为语句频度或时间频度。
A. 执行时间
B. 占用空间
D. 执行次数
正确答案：
7. 与二进制数101.01011等值的十六进制数为( )。
A. A.B
B. 5.51
C. A.51
D. 5.58
正确答案：
8. 下面选项中比较著名的命名规则有()。
A. 匈牙利命名法
B. 匈牙利命名法和骆驼命名法
C. 有匈牙利命名法、骆驼命名法和帕斯卡命名法
D. 匈牙利命名法、骆驼命名法、帕斯卡命名法以及下划线命名法
正确答案：
9. 数制中表示基本数值大小的不同数字符号称为（）。
A. 进制
B. 基数
C. 位权
D. 数码
正确答案：
10. ()是用户在程序中使用的名字，它是一种用于命名一些具有特定含义的对象的符号，通常用来标识程序中的变量，常量，函数，语句块。
A. 对象
B. 标识符
C. 符号
D. 命名规则
正确答案：
11. IDE的全程是()。
A. 集成开发环境
B. 集成环境
C. 开发软件
D. 调试过程
正确答案：
12. 有以下程序，程序的运行结果是()。#include
A. 0
B. 9
C. 6
D. 8
正确答案：
13. ()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，因为程序本身就是怎么做。
A. 文件注释
C. 功能注释
D. 程序注释
正确答案：
14. 下列叙述中，正确的是()。
A. 对长度为n 的有序链表进行查找，最坏情况下需要的比较次数为n
B. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)
C. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n) 正确答案：
15. 图中有关路径的定义是（）。
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
正确答案：
16. ()是一个开放源代码的、基于Java的可扩展开发平台。
A. VS
B. Dev-C++
C. Eclipse
D. JDK
正确答案：
17. 设无向图的顶点个数为n，则该图最多有（）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. n2
正确答案：
18. 九进制，就表示某一位置上的数运算时是逢（）进一位。
A. 2
B. 8
C. 9
D. 10
正确答案：
19. 某内排序方法的稳定性是指()。
A. 该排序算法不允许有相同的关键字记录
B. 该排序算法允许有相同的关键字记录
C. 平均时间为0（n log n）的排序方法
D. 以上都不对
正确答案：
20. 递归算法是()。
A. 简单方程
B. 标准方程
C. 简单公式
正确答案：
算法分析与设计16秋在线作业1
二、多选题（共5 道试题，共20 分。）
1. 字符串有关的格式字符有（）。
A. "%c"
B. "%d"
C. "%f"
D. "%s"
正确答案：
2. 高精度运算主要解决（）。
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
正确答案：
3. 设计递归算法有两点最为关键()和()。
A. 确定递推公式
B. 确定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 如果结果已知，那么，不用再重复调用递归
正确答案：
4. 递归算法的执行过程分()和()两个阶段。
A. 递归
B. 递推
C. 回归
D. 回溯
正确答案：
5. 顺序结构、选择结构、循环结构三种结构共同特点是()
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
正确答案：
算法分析与设计16秋在线作业1
三、判断题（共20 道试题，共40 分。）
1. C语言中，字符串作为字符数组来处理。
A. 错误
B. 正确
正确答案：
2. 有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
A. 错误
B. 正确
正确答案：
3. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为n次。
A. 错误
B. 正确
正确答案：
4. C语言允许对数组的大小作动态定义，即定义行中的数组长度能包括变量。
A. 错误
B. 正确
正确答案：
5. 递推就是在函数里调用自身。
A. 错误
B. 正确
正确答案：
6. 一个函数直接或间接调用自己本身，这种函数叫递归函数。
A. 错误
B. 正确
正确答案：
7. 使用冒泡排序法对n个数进行排序必须要进行n趟比较。
A. 错误
B. 正确
正确答案：
8. 一个算法的评价只要考虑时间复杂度。
A. 错误
B. 正确
正确答案：
9. 求n的阶乘的表示方法n!=n*(n-1)! ，其中0!=1，对应的是递归的思想。
A. 错误
正确答案：
10. 在计算机上中有符号整数和无符号整数表示的数值范围是相同的。
A. 错误
B. 正确
正确答案：
11. 在待排数据基本有序的情况下，快速排序效果最好。
A. 错误
B. 正确
正确答案：
12. 高精度计算时可以用数组来存储运算结果。
A. 错误
B. 正确
正确答案：
13. 按“先进后出”原则组织数据的数据结构是队列。
A. 错误
B. 正确
正确答案：
14. 注释内容太多会影响程序的执行效率。
A. 错误
B. 正确
正确答案：
15. 深度为k(k>=1)的二叉树至多有2^k-1个结点。
A. 错误
B. 正确
正确答案：
16. 一个scanf函数输入多个字符串，输入时以“空格”键作为字符串间的分隔。
A. 错误
B. 正确
正确答案：
17. 在顺序表中进行结点的删除操作平均须移动一半结点。
A. 错误
B. 正确
正确答案：
18. 为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。
A. 错误
B. 正确
正确答案：
19. 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
A. 错误
正确答案：
20. 字符串的结束标记在输出时也会被输出。
A. 错误
B. 正确
正确答案：
算法分析与设计16秋在线作业1
一、单选题（共20 道试题，共40 分。）
1. 下列数据结构中，属于非线性结构的是（）。
A. 循环队列
B. 带链队列
C. 二叉树
D. 带链栈
正确答案：
2. tolower（）函数用来（）。
A. 小写字母转换为大写字母
B. 大写字母转换为小写字母
C. 小写字母转换为大写字母，同时大写字母转换为小写字母
D. 判断大小写
正确答案：
3. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆积排序法
正确答案：
4. 排序算法是按照某个或某些关键字的()，递增或递减的排列起来的操作
A. 类别
B. 属性
C. 名称
D. 大小
正确答案：
5. 伪代码是用介于自然语言和()之间的文字和符号来描述算法。
A. 面向过程语言
B. 面向对象语言
C. 编程语言
D. 计算机语言
正确答案：
6. ()是一个开放源代码的、基于Java的可扩展开发平台。
A. VS
B. Dev-C++
C. Eclipse
D. JDK
正确答案：
7. 变量名=属性+ 类型+ 对象描述，其中每个对象的名称都要有明确含义，可以取对象的名字全称或名字的一部分，这种命名规则是()。
A. 匈牙利命名法
B. 骆驼命名法
C. 下划线命名法
D. 帕斯卡命名法
正确答案：
8. 注释从功能上可以分为文件注释、函数注释和()。
A. 程序员注释
B. 功能注释
C. 时间注释
D. 版权注释
正确答案：
9. 二进制的1110，0的位权是（）。
A. 0
B. 1
C. 2
D. 4
正确答案：
10. 广度优先搜索的原则()。
A. 按时间遍历解空间
B. 按代价遍历解空间
C. 按层遍历解空间
D. 按速度遍历解空间
正确答案：
11. 字符数组在初始化时若数据个数少于数组长度,多余元素自动为（）。
A. 空
B. 0
C. null
D. 随机
正确答案：
12. 十六进制数C1B转换为二进制数是（）。
A. 1100101101011
B. 110000011011
C. 10110101010
D. 11101001011
13. 一般情况下，程序中所有注释的行数占到整个源程序的()比较适宜。
A. 1/2到2/3
B. 1/3
C. 1/3到1/2
D. 1/2
正确答案：
14. 下面不是批处理文件的特点是()。
A. 批处理，也称为批处理脚本，其文件扩展名为.bat
B. 它是无格式的文本文件，每一行可视为一个命令，每个命令里可以含多条子命令，从第一行开始执行，直到最后一行结束，它运行的平台是DOS。
C. 在命令提示下键入批处理文件的名称，或者单击该批处理文件，系统就会调用cmd.exe 按照该文件中各个命令出现的顺序来逐个运行它们。
D. 使用批处理文件，可以简化日常或重复性任务，使用方便、灵活，功能强大，自动化程度高
正确答案：
15. 在深度为7的满二叉树中，叶子结点的个数为（）。
A. 32
B. 31
C. 64
D. 63
正确答案：
16. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
A. 35/11
B. 34/11
C. 33/11
D. 32/11
正确答案：
17. 十进制的123，1的位权是（）。
A. 1
B. 2
C. 10
D. 100
正确答案：
18. 使用简单选择排序法对n个数进行排序要进行()趟比较。
A. n
B. n-1
C. n+1
D. 不一定
正确答案：
19. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。
A. 起泡排序
C. Shell排序
D. 直接插入排序
正确答案：
20. 递归函数f(n)=f(n-1)+n(n>1)的递归出口是()。
A. f(1)=0
B. f(1)=1
C. f(0)=1
D. f(n)=n
正确答案：
算法分析与设计16秋在线作业1
二、多选题（共5 道试题，共20 分。）
1. 设计递归算法有两点最为关键()和()。
A. 确定递推公式
B. 确定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 如果结果已知，那么，不用再重复调用递归
正确答案：
2. 高精度运算主要解决（）。
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
正确答案：
3. 顺序结构、选择结构、循环结构三种结构共同特点是()
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
正确答案：
4. 递归算法的执行过程分()和()两个阶段。
A. 递归
B. 递推
C. 回归
D. 回溯
5. 字符串有关的格式字符有（）。
A. "%c"
B. "%d"
C. "%f"
D. "%s"
正确答案：
算法分析与设计16秋在线作业1
三、判断题（共20 道试题，共40 分。）
1. 下列程序段实现的是顺序查找功能（）int Search(int array[], int n, int key) { int i; array[n] = key; for(i=0;key!=array[i];i++); return(i A. 错误 B. 正确 正确答案： 2. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。 A. 错误 B. 正确 正确答案： 3. 字符型和整型一般情况下可以通用。 A. 错误 B. 正确 正确答案： 4. 高精度计算时可以用字符串来存储运算结果。 A. 错误 B. 正确 正确答案： 5. 查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。 A. 错误 B. 正确 正确答案： 6. 快速排序是一种不稳定排序方法。 A. 错误 B. 正确 正确答案： 7. 在C语言中字符串的头文件是string.h。 A. 错误 B. 正确 正确答案： 8. 某二叉树中度为2的结点有18个，则该二叉树中有19个叶子结点。 A. 错误 B. 正确 正确答案： 9. 快速排序总比简单排序快。 A. 错误 B. 正确 正确答案： 10. 使用冒泡排序法对n个数进行排序必须要进行n趟比较。 A. 错误 B. 正确 正确答案： 11. 交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n），而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。 A. 错误 B. 正确 正确答案： 12. 在后序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 A. 错误 B. 正确 正确答案： 13. 外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。 A. 错误 B. 正确 正确答案： 14. 假如用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49,top=30（数组下标），则栈中具有19个元素。 A. 错误 B. 正确 正确答案： 15. 插入排序是一种稳定排序方法。 A. 错误 B. 正确 正确答案： 16. puts不需要格式控制符，且自动换行。 A. 错误 B. 正确 正确答案： 17. 假如A="Jinlin changchun"，B="changchun",则B是A的子串。 A. 错误 B. 正确 正确答案： 18. 一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有24个结点。 A. 错误 B. 正确 正确答案： 19. 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为上溢。 A. 错误 B. 正确 正确答案： 20. 程序调试的作用是将程序测试过程中发现的错误改正过来，程序调试后需要再次进行测试。 A. 错误 B. 正确 正确答案： 算法分析与设计16秋在线作业1 一、单选题（共20 道试题，共40 分。） 1. 十进制，就表示某一位置上的数运算时是逢（）进一位。 A. 2 B. 8 C. 9 D. 10 正确答案： 2. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。 A. 起泡排序 B. 归并排序 C. Shell排序 D. 直接插入排序 正确答案： 3. 下面关于二分查找的叙述正确的是() A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列 C. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 正确答案： 4. 注释从功能上可以分为()。 A. 文件注释 B. 函数注释 C. 功能注释 D. 以上全是 正确答案： 5. 在下面的排序方法中，辅助空间为O（n）的是() 。 A. 希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 正确答案： 6. 下面叙述中正确的是（） A. 栈是“先进先出”的线性表 B. 队列是“先进后出”的线性表 C. 循环队列是非线性结构 D. 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构正确答案： 7. int atoi(char *s)函数的作用是（）。 A. 整数转换为字符串 B. 字符串转换为整数 C. 字符转换为字符串 D. 获取字符个数 正确答案： 8. 下列数据结构中，能用二分法进行查找的是（）。 A. 顺序存储的有序线性表 B. 线性链表 C. 二叉链表 D. 有序线性链表 正确答案： 9. 语句printf("%d\n",strlen("ATS\n012\1\\"));的输出结果是（）。 A. 11 B. 10 C. 9 D. 8 正确答案： 10. char c[6] = "China";哪个语句能输出该字符串（）。 A. printf("%s",c); B. printf("%c",c[0]); C. printf("%s",c[0]); D. printf("%d",c); 正确答案： 11. isdigit（）函数用来（）。 A. 判断字母 B. 判断数字 C. 判断大写 D. 判断小写 正确答案： 12. 一个算法中的语句的()被称为语句频度或时间频度。 A. 执行时间 B. 占用空间 C. 执行速度 D. 执行次数 正确答案： 13. ()是用户在程序中使用的名字，它是一种用于命名一些具有特定含义的对象的符号，通常用来标识程序中的变量，常量，函数，语句块。 A. 对象 B. 符号 C. 标识符 D. 命名规则 正确答案： 14. ()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，因为程序本身就是怎么做。 A. 文件注释 B. 函数注释 C. 功能注释 D. 程序注释 正确答案： 15. isalpha（）函数用来（）。 A. 判断字母 B. 判断数字 C. 判断大写 D. 判断小写 正确答案： 16. 字符数组在进行指定初值时，若未指定数组长度，则长度（）初值个数。 A. 小于 B. 等于 C. 大于 D. 不等于 正确答案： 17. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是()。 A. 选择 B. 冒泡 C. 插入 D. 堆 正确答案： 18. 下面选项中比较著名的命名规则有()。 A. 匈牙利命名法 B. 匈牙利命名法和骆驼命名法 C. 有匈牙利命名法、骆驼命名法和帕斯卡命名法 D. 匈牙利命名法、骆驼命名法、帕斯卡命名法以及下划线命名法正确答案： 19. 二进制数10110.101转换为十进制数是（）。 A. 22.625 B. 20.625 C. 22.725#20.725 正确答案： 20. ()主要是用来显示当前目录的名称或更改当前的目录。 A. dir B. cd C. type D. fc 正确答案： 算法分析与设计16秋在线作业1 二、多选题（共5 道试题，共20 分。） 1. 字符串有关的格式字符有（）。 A. "%c" B. "%d" C. "%f" D. "%s" 正确答案： 2. 顺序结构、选择结构、循环结构三种结构共同特点是() A. 只有一个入口 B. 只有一个出口 C. 结构内的每一部分都有机会被执行到（不存在死语句） D. 结构内不存在死循环（永远执行不完的循环）。 正确答案： 3. 递归算法的执行过程分()和()两个阶段。 A. 递归 B. 递推 C. 回归 D. 回溯 正确答案： 4. 高精度运算主要解决（）。 A. B. 加数 C. 减数 D. 运算结果的输入 E. 运算结果的存储 正确答案： 5. 设计递归算法有两点最为关键()和()。 A. 确定递推公式 B. 确定边界（终了）条件（递归出口） C. 每次递归调用，都必须向基本条件前进 D. 如果结果已知，那么，不用再重复调用递归 正确答案： 算法分析与设计16秋在线作业1 三、判断题（共20 道试题，共40 分。） 1. 快速排序是一种不稳定排序方法。 A. 错误 B. 正确 正确答案： 2. 顺序查找是从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。 A. 错误 B. 正确 正确答案： 3. 求n的阶乘的表示方法n!=n*(n-1)! ，其中0!=1，对应的是递归的思想。 A. 错误 B. 正确 正确答案： 4. 深度为k(k>=1)的二叉树至多有2^k-1个结点。 A. 错误 B. 正确 正确答案： 5. 在使用递归策略时，必须有一个明确的递归结束条件，称为递归入口。 A. 错误 B. 正确 正确答案： 6. 在深度为7的满二叉树中，度为2的结点个数为64。 A. 错误 B. 正确 正确答案： 7. 冒泡排序是一种不稳定排序方法。 A. 错误 B. 正确 正确答案： 8. 下列程序段实现的是顺序查找功能（）int Search(int array[], int n, int key) { int i; array[n] = key; for(i=0;key!=array[i];i++); return(i A. 错误 B. 正确 正确答案： 9. 递推分倒推法和顺推法两种形式。 A. 错误 B. 正确 正确答案： 10. 简单选择排序和冒泡排序都是一种不稳定排序方法。 A. 错误 B. 正确 正确答案： 11. 归并排序是一种稳定的排序方法。 A. 错误 B. 正确 正确答案： 12. 函数atoi("1234")的函数返回值是1234。 A. 错误 B. 正确 正确答案： 13. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。 A. 错误 B. 正确 正确答案： 14. 高精度计算时可以用字符串来存储运算结果。 A. 错误 B. 正确 正确答案： 15. 在深度为7的满二叉树中，度为2的结点个数为63。 A. 错误 B. 正确 正确答案： 16. scanf()、printf()可以输入输出几个字符串。 A. 错误 B. 正确 正确答案： 17. 对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。 A. 错误 B. 正确 正确答案： 18. 快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。 A. 错误 B. 正确 正确答案： 19. 某二叉树中度为2的结点有18个，则该二叉树中有20个叶子结点。 A. 错误 B. 正确 正确答案： 20. 在计算机上中有符号整数和无符号整数表示的数值范围是相同的。 A. 错误 B. 正确 正确答案： 算法分析与设计16秋在线作业1 一、单选题（共20 道试题，共40 分。） 1. 十进制的123，1的位权是（）。 A. 1 B. 2 C. 10 D. 100 正确答案： 2. 用计算机解决问题的过程可以分成哪三个阶段（）。 A. 输入、算法设计和输出 B. 输入、测试和输出 C. 分析问题、设计算法和实现算法 D. 分析问题、测试和实现 正确答案： 3. 二进制，就表示某一位置上的数运算时是逢（）进一位。 A. 2 B. 8 算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月 实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码 《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 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、快速排序算法和线性时间选择算法的随机化版本是: 《数值分析》计算实习题目 第一题： 1. 算法设计方案 （1）1λ，501λ和s λ的值。 1)首先通过幂法求出按模最大的特征值λt1，然后根据λt1进行原点平移求出另一特征值λt2，比较两值大小，数值小的为所求最小特征值λ1，数值大的为是所求最大特征值λ501。 2)使用反幂法求λs ，其中需要解线性方程组。因为A 为带状线性方程组，此处采用LU 分解法解带状方程组。 （2）与140k λλμλ-5011=+k 最接近的特征值λik 。 通过带有原点平移的反幂法求出与数k μ最接近的特征值 λik 。 （3）2cond(A)和det A 。 1）1=n λλ2cond(A)，其中1λ和n λ分别是按模最大和最小特征值。 2）利用步骤（1）中分解矩阵A 得出的LU 矩阵，L 为单位下三角阵,U 为上三角阵，其中U 矩阵的主对角线元素之积即为det A 。 由于A 的元素零元素较多，为节省储存量，将A 的元素存为6×501的数组中，程序中采用get_an_element()函数来从小数组中取出A 中的元素。 2.全部源程序 #include 奥鹏-东北师范大学基础会计学18秋在线作业1 作业试题参考答案 一、单选题共10题，30分 1、某企业本期产品销售收入180万元，产品销售成本85万元，销售税金10万元，发生管理费用20万元、财务费用10万元、销售费用5万元，投资收益15万元，营业外收入8万元，则填入利润表中的营业利润为（）万元 A70 B50 C73 D78 【答案】本题选择：B 2、某企业本期产品销售收入180万元，产品销售成本85万元，销售税金10万元，发生管理费用20万元、财务费用10万元、销售费用6万元，投资收益15万元，营业外收入8万元，则填入利润表中的营业利润为（）万元 A70 B49 C73 D78 【答案】本题选择：B 3、财产清查按清查的对象与范围划分，可分为 A全面清查、定期清查 B全面清查、局部清查 C定期清查、局部清查 D定期清查、不定期清查 【答案】本题选择：B 4、应由本期负担，但本期未支付的费用是 A预提费用 B待摊费用 C计提费用 D已付费用 【答案】本题选择：A 5、某企业3月末的银行存款日记账账面余额为119 200元，从银行获得本月分对账单上的余额为152 700元.经逐笔核对，发现存在以下未达账项：（1）企业收到客户的转账支票一张，金额为8 600元，企业已入账，银行尚未入账；（2）企业开出一张转账支票，金额为2 500元，接收单位尚未到银行支取；（3）银行代付电话费6 000元，企业尚未收到付款通知；（4）银行收到企业托收的销货款49 600，企业尚未收到银行的收款通知；（5）企业将月末多余现金4 000存入银行，银行未及时入账。根据上述资料编制“银行存款余额 A75 700 B174 700 C142 700 D162 800 【答案】本题选择：D 6、填制原始凭证时应做到大小写数字符合规范，填写正确。如大写金额“壹仟零壹元伍角整”，其小写应为 算法设计与分析课程实验项目目录 学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 201 实验项目类型设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要内容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这 里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下： #include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由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、请写出批处理作业调度的回溯算法。 #include 《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1 目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················ 一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。 二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。 (单选题) 1: 默认状态下，“舞台”的宽为550像素，高为（）像素。 A: 400像素 B: 450像素 C: 500像素 D: 550像素 正确答案: (单选题) 2: 命令（）可以为事件添加超级链接。 A: fscommand B: getURL C: loadMovie D: uploadMovie 正确答案: (单选题) 3: （）可以绘制各种各样的线条。 A: 椭圆工具 B: 线条工具 C: 矩形工具 D: 刷子 正确答案: (单选题) 4: 逐帧动画的每一帧都是（）。 A: 空白帧 B: 普通帧 C: 关键帧 D: 过渡帧 正确答案: (单选题) 5: ActionScript中不区分大小写的是（）。 A: 关键字 B: 类名 C: 变量 D: 影片剪辑名 正确答案: (单选题) 6: 场景中输入的文字在Flash中默认是（）. A: 静态文本 B: 动态文本 C: 输入文本 D: 字体元件 正确答案: (单选题) 7: （）可以用于选择形状图形的不规则区域或者相同的颜色区域。A: 套索工具 B: 任意变形工具 C: 选择工具 D: 部分选取工具 正确答案: (单选题) 8: 在ActionScript，点的左侧不可以是（） A: 动画中的对象 B: 实例 C: 时间轴 D: 实例的目标路径 正确答案: (单选题) 9: 在形状补间动画中，（）可以控制变形中间的过程。 A: 关键帧 B: 元件 C: 矢量图形 正确答案: (单选题) 10: ActionScript中用（）表示语句的结束。 A: 句号 B: 逗号 C: 分号 D: 括号 正确答案: (多选题) 1: 下列选项中包含在Flash工具栏中的有（）. A: 工具区域 B: 显示图层 C: 选项区域 D: 图层高度 正确答案: (多选题) 2: 下列选项中是ActionScript关键字的是（）. A: do B: Break C: float D: void 正确答案: (多选题) 3: 在Flash游戏的制作中，响应键盘的方法有（ABCD）. A: 按钮 B: Key对象 C: 键盘侦听 D: 影片剪辑的keyUp和keyDown 正确答案: (多选题) 4: 下列选项中，属于动画设计元素的有（）. A: 矢量图形 B: 位图图像 C: 协议 D: 音频文件 正确答案: (多选题) 5: 动态文本主要应用在（）. A: 显示动画运行时产生的随机文本内容 B: 显示需要动态更新的文本 C: 实现密码输入文本框 D: 实现数字输入文本框 正确答案: (多选题) 6: 下列选项中属于Flash元件类型的有（）. A: 图形 B: 实例 C: 字体 D: 按钮 正确答案: (多选题) 7: 按钮的状态有（）. A: 弹起帧 B: 指针经过帧 C: 按下帧 D: 点击帧 正确答案: (多选题) 8: ActionScript中变量命名必须符合（）. A: 变量名必须以数字开头 B: 变量名必须以英文字母开头 一需求分析 此系统是一个类似于淘宝网的在线衣服销售系统，相当于淘宝网上的一个专门买衣服的网店，它具有用户注册，用户登录，修改密码，显示系统功能，查看订购历史以及订货。 1.1需求列表： （1）用户管理：用户管理的需求包括用户注册，用户登录以及修改密码。 用户注册是添加一个我们网上衣店的新用户；用户登录是用户想要进 入系统时必须采取验证身份的步骤；修改密码是为了用户的安全性考 虑，当密码存在不安全的因素时，适时修改密码。 （2）商品衣服的管理：商品管理包括订购衣服和查看订购衣服的历史。订购衣服是当我们衣店的库存数量不足时必须采取的；查看订购衣服的 历史有助于我们更好地了解衣服的订购情况。 （3）显示系统功能：此功能是用来让用户能很清楚地了解此系统所实现的各种功能。 1.2系统用例图： 1.3用例分析及场景描述： 用户注册用例： 这部分主要是新用户进行注册的过程，首先用户进入到注册页面，填写注册信息并提交，如果无误的话系统会给予注册成功的提示，如果注册失败会提示注册失败信息。 用户登录用例： 此功能模块针对的对象是本网站的会员既已经注册的会员，会员首先填写用户名和密码，然后点击登录按钮，如果网站数据库中存在此会员并且密码正确则提示登录成功提示，如果网站不存在此用户或密码不正确，系统会提示用户登录失败。 修改密码用例： 此用例针对注册会员进行操作。用户登录成功会可以进入网站主页面，如果用户想修改密码的话可以单击修改密码按钮，进行密码修改，用户输入新密码单击修改按钮即可完成密码修改。 显示系统功能用例： 此功能针对注册会员，会员首先登录到网站，进入主页，主页会有相关操作的按钮，显示系统所提供给会员操作的功能，用户可以针对自己的需要选择系统提供的功能。 订货衣服用例： 此功能针对注册登录会员，网站提供两种订购方案：单件订购和定制套装。用户可以根据自己的需求来选择。 单件订购方案：用户选择是上衣还是裤子，并填写订购的数量，确认无误后单击订购按钮即可，如果订购成功，系统会提示订购成功，失败则会提示订购失败。 定制套装方案：用户选择定制套装的档次（高、中、低），并填写订购的数量，确认无误后单击订购按钮即可，如果订购成功，系统会提示订购成功，失败则会提示订购失败。 显示订购历史用例： 此功能针对注册会员，用户登录到系统后，主页显示系统功能中包括历史查看选项，用户可以单击进入历史交易记录页面，页面将显示用户所有的交易记录。 二设计模式 2.1单件模式 2.1.1单件模式的定义 实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组 3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。 1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。 2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。 《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结 1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c]; 昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include 算法分析与设计上机实验报告 课程名称：算法分析与设计班级：实验日期: 姓名：学号：指导教师：许晓华实验名称：最优二叉搜索树实验地点：主楼1114实验成绩：一、实验目的及要求 1．进一步掌握最优二叉树的含义。 2．掌握最优二叉树的结构特征。 3．认真阅读和掌握动态规划法秋最有搜索二叉树实验的程序。 4．上机运行本程序。 5．保存和打印出程序的运行结果，并结合程序进行分析。 6．按照你二叉树的操作需要，可重新改写主程序并运行，请上交文件清单和运行结果 二、实验环境及设备 微机一台：Intel 酷睿2双核 操作系统：Microsoft Windows XP Professional 工具软件：Microsoft Visual C++ 6.0 三、实验内容及实验步骤 动态规划——最优二叉查找树 1，问题描述：给定一个有序序列K={k1 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 深圳大学研究生课程论文 题目大作业：变位词实验成绩 专业计算机与软件学院软件工程 课程名称、代码 年级2015 姓名文成 学号2150230509 时间2015 年12 月任课教师杨烜 一、大作业要求与内容 大作业内容： 在下列问题中挑选一个问题，选用适当的算法进行实现，在课堂上，针对该问题完成一个10分钟的论文演讲与演示，并提交演讲PPT。（30分） 在一个类似英语词典的大文件中找出变位词的所有集合，例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 大作业要求：（70分） （1）要求演示算法解决问题的完整过程，如果我对解这个问题一无所知，看了你的解决过程，就要能理解算法是如何解决问题的； （2）要求交互界面活泼生动，演示速度可控； （3）尽可能提供丰富的功能让我理解你是如何解决这个问题的； （4）提交源程序、大作业报告（介绍详细的算法设计说明和使用说明）； （5）以论文、报告等形式考核专用答题纸写大作业，大作业报告中要分析算法效率，并给出实测效率和理论效率图表； （6）大作业用5号字体，总页数不得少于8页，否则视为无效。 二、大作业步骤 Introduction: 给定一本英语单词词典，找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 Motivating idea: 1.如何判断两个单词是否为变位词。 思路一： 如果两个单词是变位词，那么它们具有相同的长度，且每个英语字母的个数是一样的。我们只需要挨个对各个单词进行比较即可。这个思路容易想，但时间效率太低，还可以继续改进一下，且看下面的思路二。 思路二： 将两个字符串按照字母表顺序排序，看排序后的字符串是否相等，如果相等则是兄弟字符串（变位词）。这种方法的时间效率根据你使用的排序算法不同而不同。这里我采取思路二，我使用的是快速排序。但是依旧有个问题，单词与单词一个一个比较的话效率还是太低了，我们可以再做改进。 2.如何从字典中找出所有变位词的集合。 思路一： 对于这个问题，最快想到的最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。然而，假设一次比较至少花费1微秒的时间，则拥有二十万单词的字典将花费：200000 题目：用动态规划法实现求两序列的最长公共子序列。 程序代码 #include 算法设计与分析期末成绩考核标准 要求：算法设计与分析考试方式为小论文形式。下面给出了小论文的参考模型和参考题目，供大家选择。 1.小作业题目（仅供参考） （题目的难易：●简单10道题★中等11道题▲复杂10道题） ●最佳浏览路线问题 问题描述：某旅游区的街道呈网格状，其中东西向的街道都是旅游街，南向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。 阿隆想到这个旅游区游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路浏览的必要程度，分值从-100到100的整数，所有林荫道不打分，所有分值不可能全是负值。阿隆可以从任一路口开始浏览，在任一路口结束浏览，请写出一个算法，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。（算法设计与分析第二版P190—11题） ●问题描述：某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的，A，B，C个工厂，各工厂在获得这种机器后，可以为国家盈利如图表所示，问：这5台机器如何分配给各工厂，才能使得国家盈利最大？（P190-14题） ●问题描述：编写算法对输入的一个整数，判断他能否被4，7，9整除，并输出一下信息之一， 能同时被4，7，9整除; 能被其中两个数（要指出那两个）整除 能被其中一个数（要指出哪一个）整除 不能被4，7，9任一个整除。（P118-16） ●问题描述：某一印刷厂有6项加工任务，对印刷车间和装订车间所需的时间表如下图：完成每项任务都要先去印刷车间印刷，再到装订车间装订。问咋样安排这6项加工任务的加工工序，使得加工工时最少？（P191-17） ●问题描述：编写用动态规划法求组合数m C的算法(P191-19). n ●问题描述：仿照分治算法中两个大数相乘的算法策略，完成求解两个n*n阶矩阵A和矩阵B的乘积的算法。假设n=2k,要求算法的复杂性要小于O（n3）.(P190-12) ●问题描述：在一个n*m的方格中，m为奇数，放置有n*m个数，方格中间的下方有一人，此人可按照5个方向前进但不能跃出方格，如图所示，人每走过一个方格必须取此方格中的数。要求找到一条路径从低到顶的路径，使其数相加之和为最大，输出最大和的值。（P190-14）●问题描述：N 块银币中有一块不合格，已知不合格的银币比正常的银币重，先用一天平，请利用它找不合格的银币，并且用天平的次数最少。（P-19116） ●问题描述：旅行售货员问题：某售货员要到若干城市去推销商品，已知个城市之间的路线。她要选择一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅行费）最小（P246-6） ●问题描述：54张扑克牌，两个人轮流拿牌，每人每次最少取一张，最多取四张，谁那最后一张谁输。编写模拟计算机先拿牌取且必胜的算法。（P189-3） ★题目一选课方案设计（P290） ★题目二表达式相等判断（P291）算法设计与分析(作业三)
算法分析与设计作业及参考答案样本
北航数值分析大作业第一题幂法与反幂法
东师大学基础会计学18秋在线作业1答案
算法设计与分析实验报告
最新算法分析与设计作业(一)及参考答案讲课讲稿
软件系统分析与设计大作业
东师《Flash动画设计》18秋在线作业1(满分)
软件设计大作业
算法分析与设计实验报告
《算法分析与设计》作业参考答案
算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.
算法分析与设计 实验二 哈夫曼编码
算法分析与设计实验报告 (2)
算法分析与设计(线下作业二)
算法分析大作业 寻找变位词
算法分析与设计实验二：动态规划法
算法分析 期末大作业内容
相关文档
- 5.《算法设计与分析》试题库
- 算法设计与分析考试题及答案
- 算法分析与设计作业(一)与参考答案
- 算法设计与分析报告大作业
- 算法分析与设计作业及参考答案样本
- 《算法设计与分析》实验指导
- 2016年秋学期东北师大算法分析与设计16秋在线作业2满分答案
- 算法分析与设计作业参考答案
- 东师算法分析与设计20秋在线作业2答案_24843
- 《算法分析与设计》作业参考答案
- 算法分析与设计之作业习题答案
- 北师大2018年春算法分析与设计作业(一)及参考答案
- 算法分析与设计(线下作业一)
- 《算法设计与分析》考试题目与答案
- 算法设计与分析(作业三)
- 算法分析与设计：作业
- 算法分析与设计作业(一)及参考答案
- 算法分析与设计在线作业
- 算法设计与分析-作业-第4章-共26页文档
- 东师《算法分析与设计》20春在线作业1答案30728