中石油华东18秋《算法设计与分析》在线作业（全）
2018秋学期《算法设计与分析》在线作业1核对题目下载答案，转载请注明无忧答案网
一、单选题：1.[单选题]在对一些问题进行分析或建立数学模型时，若从前向后分析问题感到比较棘手，则使问题容易理解和解决，可采用 (满分:)
A. 正推法 B. 循环法
C. 迭代法 D. 倒推法]
正确答案:——D——
2.[单选题]算法每条语句的执行时间应该是执行该语句一次所需的时间与该语句执行的次数的乘积，称为 (满分:)
A. 语句频度
B. 执行次数
C. 基本操作
D. A和B]
正确答案:——A——
3.[单选题]某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。不同的钥匙数至少是 (满分:)
A. 11
B. 28
C. 35
D. 40]
正确答案:——C——
4.[单选题]图论问题主要是研究数据结构是图形结构或树形结构的 (满分:)
A. 结构
B. 定义
C. 算法
D. 数据元素]
正确答案:————
5.[单选题]下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是 (满分:)
A. 堆排序
B. 冒泡排序
C. 直接选择排序
D. 快速排序]
正确答案:————
6.[单选题]设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为 (满分:)
A. 5
B. 6
C. 7
D. 8]
正确答案:————
7.[单选题]对一个线性表中的无序数据进行顺序查找，表中的数据量越大，则查找的时间就越长。因此，决定算法的运行时间是 (满分:)
A. 程序数据量
B. 输出数据
C. .处理环境
D. 问题规模]
正确答案:————
8.[单选题]某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则该二叉树对应的森林包括的树的棵树是 (满分:)
A. 1
B. 2
C. 3
D. 4]
正确答案:————
9.[单选题]含n个关键字的二叉排序树的平均查找长度主要取决于 (满分:)
A. 关键字的个数
B. 树的形态
C. 关键字的取值范围
D. 关键字的数据类型]
正确答案:————
10.[单选题]而解递归方程的最直接方法，就是采用 (满分:)
A. 递推法
B. 穷举法
C. 搜索法
D. 贪心法]
正确答案:————
11.[单选题]当采用分快查找时，数据的组织方式为 (满分:)
A. 数据分成若干块，每块内数据有序 辅导联系q或微信761296021
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同]
正确答案:————
12.[单选题]由2个a，1个b，2个c组成的不同排列总数是 (满分:)
A. 11
B. 20
C. 28
D. 30]
正确答案:————
13.[单选题]某班选修企业管理的有18人，不选的有10人，则该班共有人数是 (满分:)
A. 8
B. 10
C. 18
D. 28]
正确答案:————
14.[单选题]如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为 (满分:)
A. 插入排序
B. 归并排序
C. 冒泡排序
D. 堆排序]
正确答案:————
15.[单选题]对于输入的任何数据，贪心策略都是适用的，因此我们称它们为“可绝对贪心问题”。货币找零问题是 (满分:)
A. 可贪心问题
B. 不可贪心问题
C. 绝对贪心问题
D. 相对贪心问题]
正确答案:————
三、判断题：
16.[判断题]倒推法是对某些特殊问题所采用的从前向后推解问题的方法。 (满分:)
A. 错误
B. 正确]
正确答案:————
17.[判断题]一个递推算法总可以转换为一个递归算法。 (满分:)
A. 错误
B. 正确]
正确答案:————
18.[判断题]在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。 (满分:)
A. 错误
B. 正确]
正确答案:————
19.[判断题]克鲁斯卡尔算法的时间复杂度为O(eloge）,它对稀疏图较为适合。 (满分:)
A. 错误
B. 正确]
正确答案:————
20.[判断题]用冒泡排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：20，12，25，15，47，30，76，8312，20，15，25，30，47，76，8312，15，20，25，30，47，76，83 (满分:)
A. 错误
B. 正确]
正确答案:————
2018秋学期《算法设计与分析》在线作业2
一、单选题：
1.[单选题]在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为 (满分:)
A. 4，4，3
B. 4，3，3
C. 3，4，4
D. 3，3，4]
正确答案:——B——
2.[单选题]对于输入的任何数据，贪心策略都是适用的，因此我们称它们为“可绝对贪心问题”。货币找零问题是 (满分:)
A. 可贪心问题
B. 不可贪心问题
C. 绝对贪心问题
D. 相对贪心问题]
正确答案:——D——
3.[单选题]在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 (满分:)
A. 不一定相同
B. 都相同
C. 都不相同
D. 互为逆序]
正确答案:——B——
4.[单选题]下面的叙述不正确的是 (满分:)
A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i的值成反比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关]
正确答案:————
5.[单选题]n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排。下面属于123的错排是 (满分:)
A. 132
B. 321
C. 312
D. 213]
正确答案:————
6.[单选题]下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是 (满分:)
A. 分块查找
B. 顺序查找
C. 二分查找
D. 散列查找]
正确答案:————
7.[单选题]有5本不同的日文书，7本不同的英文书，10本不同的中文书。取2本相同文字的书种数是 (满分:)
A. 22
B. 35
C. 76
D. 155]
正确答案:————
8.[单选题]为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为 (满分:)
A. 05
B. 37
C. 41
D. 62]
正确答案:————
9.[单选题]若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是 (满分:)
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表]
正确答案:————
10.[单选题]一个有向无环图的拓扑排序序列是 (满分:)
A. 一定唯一的
B. 一定不唯一的
C. 不一定唯一的
D. 都不对]
正确答案:————
11.[单选题]在分块索引的在顺序表中查找，算法中采用的最佳技术是 (满分:)
A. 穷举法
B. 贪心法
C. 分治法
D. 分支限界法]
正确答案:————
12.[单选题]所谓搜索问题，就是在给定的数据集合中寻找满足条件的 (满分:)
A. 动态结构
B. 顺序结构
C. 数据对象
D. 数据类型]
正确答案:————
13.[单选题]用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为 (满分:)
A. 5
B. 6
C. 8
D. 9]
正确答案:————
14.[单选题]对n个关键字的序列进行快速排序，平均情况下的空间复杂度为 (满分:)
A. O(1)
B. O(logn)
C. O(n)
D. O(nlogn)]
正确答案:————
15.[单选题]在一个带权连通图G中，权值最小的边一定包含在G的 (满分:)
A. 最小生成树中
B. 深度优先生成树中
C. 广度优先生成树中
D. 深度优先生成森林中]
正确答案:————
三、判断题：
16.[判断题]通常深度优先搜索法全部保留结点，扩展完的结点从数据存储结构栈中弹出删去。 (满分:)
A. 错误
B. 正确]
正确答案:————
17.[判断题]用计算机对问题求解，问题的本质是算法设计问题。 (满分:)
A. 错误
B. 正确]
正确答案:————
18.[判断题]可以在多项式时间内解决的判定性问题属于NP类问题。 (满分:)
A. 错误
B. 正确]
正确答案:————
19.[判断题]将有序表中n个元素依次插入到一棵空的二叉排序树中，则在等概率查找的情况下，该二叉排序树在查找成功时的平均查找长度是O(n)。 (满分:)
A. 错误
B. 正确]
正确答案:————
20.[判断题]Hanoi问题的递归算法的时间复杂度为O（n）。算法的空间度杂度为O（(n)）。 (满分:)
A. 错误
B. 正确]
正确答案:————
2018秋学期《算法设计与分析》在线作业3
一、单选题：
1.[单选题]下面哪一方法可以判断出一个有向图是否有回路 (满分:)
A. 深度优先遍历
B. 求关键路径
C. 求最短路径
D. A和C]
正确答案:——A——
2.[单选题]某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有的个数是 (满分:)
A. 3
B. 5
C. 8
D. 15]
正确答案:——D——
3.[单选题]若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为 (满分:)
A. f,c,b
B. f,d,b
C. g,c,b
D. g,d,b]
正确答案:——A——
4.[单选题]无向图中一个顶点的度是指图中 (满分:)
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数]
正确答案:————
5.[单选题]如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 (满分:)
A. 栈
B. 队列
C. 树
D. 图]
正确答案:————
6.[单选题]若<vi,vj>是有向图的一条边，则称 (满分:)
A. vi邻接于vj
B. vj邻接于vi
C. vi和vj相互邻接
D. vi与vj不相邻接]
正确答案:————
7.[单选题]设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是 (满分:)
A. 2
B. 3
C. 5
D. 6]
正确答案:————
8.[单选题]算法分析的目的是 (满分:)
A. 辨别数据结构的合理性
B. 评价算法的效率
C. 研究算法中输入与输出的关系
D. 鉴别算法的可读性]
正确答案:————
9.[单选题]设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 (满分:)
A. A，B，C，D
B. D，C，B，A
C. A，C，D，B
D. D，A，B，C]
正确答案:————
10.[单选题]如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用 (满分:)
A. 深度优先搜索算法
B. 广度优先搜索算法
C. 求最小生成树的prim算法
D. 拓扑排序算法]
正确答案:————
11.[单选题]三维数组A按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］的存储地址为 (满分:)
A. 356
B. 358
C. 360
D. .362]
正确答案:————
12.[单选题]在分块索引的在顺序表中查找，算法中采用的最佳技术是 (满分:)
A. 穷举法
B. 贪心法
C. 分治法
D. 分支限界法]
正确答案:————
13.[单选题]栈是一种操作受限的线性结构，其操作的主要特征是 (满分:)
A. 先进先出
B. 后进先出
C. 进优于出
D. 出优于进]
正确答案:————
14.[单选题]在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为 (满分:)
A. i
B. i+1
C. n-i
D. n-i+1]
正确答案:————
15.[单选题]在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是 (满分:)
A. G中有弧<Vi，Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有弧<Vi,Vj>
D. G中有一条从Vj到Vi的路径]
正确答案:————
三、判断题：
16.[判断题]假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为cdba，不可能得到的出栈序列为cdab。 (满分:)
A. 错误
B. 正确]
正确答案:————
17.[判断题]用冒泡排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：20，12，25，15，47，30，76，8312，20，15，25，30，47，76，8312，15，20，25，30，47，76，83 (满分:)
A. 错误
B. 正确]
正确答案:————
18.[判断题]杨辉三角形是队列应用的一个典型例子。 (满分:)
A. 错误
B. 正确]
正确答案:————
19.[判断题]倒推法是对某些特殊问题所采用的从前向后推解问题的方法。 (满分:)
A. 错误
B. 正确]
正确答案:————
20.[判断题]对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于结点高度。 (满分:)
A. 错误
B. 正确]
正确答案:————
附件是答案，需要的核对题目，自助下载，q761296021
页:
[1]