东北大学18秋学期《数据结构Ⅱ》在线作业3

openhelp100

18秋学期《数据结构Ⅱ》在线作业3

东北大学作业答案咨询QQ515224986


一、单选题：
1.[单选题]下面的说法中正确的是(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。(2)按二叉树定义，具有三个节点的二叉树共有6种。          (满分:)
    A. (1)，(2)
    B. (1)
    C. (2)
    D. (1)，(2)都错]
    正确答案:——B——
2.[单选题]n个顶点的有向完全图中含有向边的数目最多为          (满分:)
    A. n-1
    B. n
    C. n(n-1)/2
    D. n(n-1)]
    正确答案:——D——
3.[单选题]深度为h的满m叉树的第k层的结点(1=<k=<h)数有          (满分:)    奥鹏易百答案

    A. mk-1
    B. mk-1
    C. mh-1
    D. mh-1]
    正确答案:——A——
4.[单选题]下面关于线性表的叙述中，错误的是          (满分:)
    A. 线性表采用顺序存储，必须占用一片连续的存储单元。
    B. 线性表采用顺序存储，便于进行插入和删除操作。
    C. 线性表采用链接存储，不必占用一片连续的存储单元。
    D. 线性表采用链接存储，便于插入和删除操作。]
    正确答案:————
5.[单选题]在计算机内实现递归算法时所需的辅助数据结构是          (满分:)
    A. 栈
    B. 队列
    C. 树
    D. 图]
    正确答案:————
6.[单选题]在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是          (满分:)
    A. 1
    B. 2
    C. 3
    D. 5]
    正确答案:————
7.[单选题]设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是          (满分:)
    A. 2
    B. 3
    C. 5
    D. 6]
    正确答案:————
8.[单选题]若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为          (满分:)
    A. O(0)
    B. O(1)
    C. O(n)
    D. O(n2)]
    正确答案:————
9.[单选题]若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的          (满分:)
    A. 层次遍历算法
    B. 前序遍历算法
    C. 中序遍历算法
    D. 后序遍历算法]
    正确答案:————
10.[单选题]一棵树高为K的完全二叉树至少的结点是          (满分:)
    A. 2k–1
    B. 2k-1–1
    C. 2k-1
    D. 2k]
    正确答案:————
11.[单选题]一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为          (满分:)
    A. O(n)
    B. O(e)
    C. O(n+e)
    D. O(n2)]
    正确答案:————
12.[单选题]for（i=0；i<m；i++）for（j=0；j<t；j++）c［i］［j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为          (满分:)
    A. O（m+n×t）
    B. O（m+n+t）
    C. O（m×n×t）
    D. O（m×t+n）]
    正确答案:————
13.[单选题]若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为          (满分:)
    A. 4
    B. 5
    C. 8
    D. 9]
    正确答案:————
14.[单选题]对于哈希函数H(key)=key%13,被称为同义词的关键字是          (满分:)
    A. 35和41
    B. 23和39
    C. 15和44
    D. 25和51]
    正确答案:————
15.[单选题]已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是          (满分:)
    A. .{25,36,48,72,23,40,79,82,16,35
    B. .{25,36,48,72,16,23,40,79,82,35
    C. .{25,36,48,72,16,23,35,40,79,82
    D. .{16,23,25,35,36,40,48,72,79,82
    正确答案:————
16.[单选题]含n个关键字的二叉排序树的平均查找长度主要取决于          (满分:)
    A. 关键字的个数
    B. 树的形态
    C. 关键字的取值范围
    D. 关键字的数据类型]
    正确答案:————
17.[单选题]．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是          (满分:)
    A. 逆拓扑有序
    B. 拓扑有序
    C. 无序的
    D. A和B]
    正确答案:————
18.[单选题]设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为          (满分:)
    A. 5
    B. 6
    C. 7
    D. 8]
    正确答案:————
19.[单选题]某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是          (满分:)
    A. 空或只有一个结点
    B. 高度等于其结点数
    C. 任一结点无左孩子
    D. 任一结点无右孩子]
    正确答案:————
20.[单选题]无向图中一个顶点的度是指图中          (满分:)
    A. 通过该顶点的简单路径数
    B. 与该顶点相邻接的顶点数
    C. 通过该顶点的回路数
    D. 与该顶点连通的顶点数]
    正确答案:————

奥鹏作业答案