东北大学2018秋学期《算法设计与分析》在线作业2参考

2018秋学期《算法设计与分析》在线作业2

东北大学作业答案咨询QQ515224986

一、单选题：
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. 正确]
    正确答案:————
奥鹏作业答案