《数据结构Ⅱ》3. 根据数据元素的关键字直接计算出该元...

奥鹏网院作业

奥鹏东大16秋学期《数据结构Ⅱ》在线作业3标准答案

一、单选题：
1. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为           (满分:5)
    A. 左子树的叶子结点
    B. 左子树的分支结点
    C. 右子树的叶子结点
    D. 右子树的分支结点
2. 稠密索引是在索引表中          (满分:5)
    A.  为每个记录建立一个索引项
    B.  为每个页块建立一个索引项
    C.  为每组记录建立一个索引项
    D. 为每个字段建立一个索引项
3. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是           (满分:5)
    A. 顺序存储方法
    B. 链式存储方法
    C. 索引存储方法
    D. 散列存储方法
4. 采用ISAM或VSAM组织的文件是          (满分:5)
    A.  索引非顺序文件
    B. 顺序文件
    C. 索引顺序文件
    D.  散列文件
5. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为           (满分:5)
    A. 0
    B. 1
    C. 48
    D. 49
6. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是          (满分:5)
    A. A[8，5]
    B. A[3，10]
    C. A[5，8]
    D. A[0，9]
7. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是          (满分:5)
    A. 1234
    B. 4132
    C. 4231
    D. 4213
8. 一棵树高为K的完全二叉树至少的结点是          (满分:5)
    A. 2k –1
    B. 2k-1 –1
    C. 2k-1
    D. 2k
9. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系           (满分:5)
    A. 不一定相同
    B. 都相同  
    C. 都不相同
    D. 互为逆序
10. 以下与数据的存储结构无关的术语是          (满分:5)
    A. 循环队列
    B. 链表
    C. 哈希表
    D. 栈
11. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是          (满分:5)
    A. 空或只有一个结点
    B. 高度等于其结点数
    C. 任一结点无左孩子
    D. 任一结点无右孩子
12. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为           (满分:5)
    A. 4
    B. 5
    C. 8
    D. 9
13. 对长度为n的关键字序列进行堆排序的空间复杂度为          (满分:5)
    A. O（log2n）
    B. O（1）
    C. O（n）
    D. O（n*log2n）
14. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为          (满分:5)
    A. （1，2，3，4，5，6，7，8）
    B. （1，4，3，2，5，7，8，6）
    C. （2，1，4，3，5，7，8，6）
    D. （8，7，6，5，4，3，2，1）
15. 对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为          (满分:5)
    A.  1，2，3
    B.  9，5，2，3
    C. 9，5，3
    D.  9，4，2，3
16. 无向图中一个顶点的度是指图中          (满分:5)
    A.  通过该顶点的简单路径数
    B.  与该顶点相邻接的顶点数  
    C.  通过该顶点的回路数
    D.  与该顶点连通的顶点数
17. 从广义表LS＝（(p, q), r, s）中分解出原子q的运算是          (满分:5)
    A. tail(head(LS))
    B. head(tail(head(LS)))
    C. head(tail(LS))
    D. tail(tail(head(LS)))
18. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是           (满分:5)
    A. G中有弧<Vi，Vj>
    B. G中有一条从Vi到Vj的路径
    C. G中没有弧<Vi
    Vj>
    D. G中有一条从Vj到Vi的路径
19. 下列说法正确的是 (1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值          (满分:5)
    A.(1)(2)(3)
    B.(1)(2)
    C.(1)(3)
    D. 前面的可选答案都不对
20. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是           (满分:5)
    A. O(1)
    B. O(n)
    C. O(nlogn)
    D. O(n2)