《数据结构Ⅰ》2. 假设一棵完全二叉树按层次遍历的顺序...

奥鹏网院作业

奥鹏东大16秋学期《数据结构Ⅰ》在线作业2标准答案
一、单选题：
1. 下列编码中属于前缀编码的是          (满分:5)
    A.  {1
    01
    000
    001}
    B.  {1
    01
    011
    010}  
    C. {0
    10
    110
    11}
    D.  {0
    1
    00
    11}
2. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在           (满分:5)
    A. BT[i/2]
    B.  BT[2*i-1]
    C.  BT[2*i]
    D.  BT[2*i+1]
3. 上溢现象通常出现在          (满分:5)
    A. 顺序栈的入栈操作过程中
    B. 顺序栈的出栈操作过程中
    C. 链栈的入栈操作过程中
    D. 链栈的出栈操作过程中
4. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为          (满分:5)
    A. 数组的元素处在行和列两个关系中
    B. 数组的元素必须从左到右顺序排列
    C. 数组的元素之间存在次序关系
    D. 数组是多维结构，内存是一维结构
5. 队列和栈的主要区别是           (满分:5)
    A. 逻辑结构不同
    B. 存储结构不同
    C.  所包含的运算个数不同
    D.  限定插入和删除的位置不同
6. 要求具有同一逻辑结构的数据元素具有相同的特性，其含义为          (满分:5)
    A.  数据元素具有同一的特点
    B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
    C. 每个数据元素都一样
    D.  仅需要数据元素包含的数据项的个数相同
7. 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是          (满分:5)
    A. 栈
    B. 线性表
    C. 队列
    D. 二叉排序树
8. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是          (满分:5)
    A. 队列
    B. 栈
    C.  线性表
    D. 有序表
9. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用           (满分:5)
    A. 深度优先搜索算法
    B. 广度优先搜索算法  
    C. 求最小生成树的prim算法
    D. 拓扑排序算法
10. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是           (满分:5)
    A. 有向完全图
    B. 连通图  
    C. 强连通图
    D.  有向无环图
11. 若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为          (满分:5)
    A.  1和n+1
    B. 1和n/2
    C. －1和n
    D. －1和n+1
12. 下列数据结构中，属于非线性数据结构的是          (满分:5)
    A. 栈
    B.  队列
    C.  完全二叉树
    D. 堆
13. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是          (满分:5)
    A. 1
    B. 2
    C. 3
    D. 概念上是错误的
14. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是          (满分:5)
    A. 2，4，3，1，5，6
    B.  3，2，4，1，6，5
    C. 4，3，2，1，5，6
    D. 2，3，5，1，6，4
15. 抽象数据类型的三个组成部分分别为          (满分:5)
    A. 数据对象、数据关系和基本操作  
    B. 数据元素、逻辑结构和存储结构
    C. 数据项、数据元素和数据类型
    D. 数据元素、数据结构和数据类型
16. 快速排序在最坏情况下的时间复杂度是          (满分:5)
    A. O(n2log2n)
    B. O(n2)
    C. O(nlog2n)
    D. O(log2n)
17. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是          (满分:5)
    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}
18. 稠密索引是在索引表中          (满分:5)
    A. 为每个记录建立一个索引项
    B. 为每个页块建立一个索引项
    C. 为每组记录建立一个索引项
    D. 为每个字段建立一个索引项
19. ALV树是一种平衡的二叉排序树，树中任一结点的          (满分:5)
    A.  左、右子树的高度均相同  
    B.  左、右子树高度差的绝对值不超过1
    C. 左子树的高度均大于右子树的高度
    D.  左子树的高度均小于右子树的高度
20. 采用ISAM或VSAM组织的文件是          (满分:5)
    A.  索引非顺序文件
    B.  顺序文件  
    C. 索引顺序文件
    D. 散列文件