《数据结构Ⅰ》1. 对长度为n的关键字序列进行堆排序的空...

奥鹏网院作业

奥鹏东大16秋学期《数据结构Ⅰ》在线作业1标准答案
一、单选题：
1. 对长度为n的关键字序列进行堆排序的空间复杂度为          (满分:5)
    A. O（log2n）
    B.  O（1）
    C. O（n）
    D. O（n*log2n）
2. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是          (满分:5)
    A. 10
    B. 11
    C. 12
    D. 不确定的
3. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为          (满分:5)
    A. 0
    B. 1
    C. 48
    D. 49
4. 要求具有同一逻辑结构的数据元素具有相同的特性，其含义为          (满分:5)
    A.  数据元素具有同一的特点
    B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
    C. 每个数据元素都一样
    D.  仅需要数据元素包含的数据项的个数相同
5. 一棵具有 n个结点的完全二叉树的树高度（深度）是          (满分:5)
    A.  ëlognû+1
    B.  logn+1
    C. ëlognû
    D. logn-1
6. 若某线性表最常用的操作是存取任一指定序号的元素和在表尾进行插入和删除运算，则节省时间的存储方式是          (满分:5)
    A. 顺序表
    B. 双链表
    C. 带头结点的双循环链表
    D. 单循环链表
7. 下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。          (满分:5)
    A.(1)，(2)
    B. (1)
    C.(2)
    D. (1)，(2)都错
8. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是           (满分:5)
    A. 有向完全图
    B. 连通图  
    C. 强连通图
    D.  有向无环图
9. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为          (满分:5)
    A. A．左子树的叶子结点
    B. B．左子树的分支结点
    C. C．右子树的叶子结点
    D. D．右子树的分支结点
10. 下面关于数据结构正确的说法是           (满分:5)
    A. 一种数据类型
    B. 数据的存储结构
    C. 一组性质相同的数据元素的集合
    D. 相互之间存在一种或多种特定关系的数据元素的集合
11. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为          (满分:5)
    A.  f
    c
    b
    B. f
    d
    b
    C. g
    c
    b
    D. g
    d
    b
12. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是          (满分:5)
    A. A，B，C，D
    B. D，C，B，A
    C.  A，C，D，B
    D.  D，A，B，C
13. n个顶点的强连通图中至少含有          (满分:5)
    A.  n-1条有向边
    B.  n条有向边
    C.  n(n-1)/2条有向边
    D. n(n-1)条有向边
14. 导致栈上溢的操作是          (满分:5)
    A. 栈满时执行的出栈
    B.  栈满时执行的入栈
    C. 栈空时执行的出栈
    D.  栈空时执行的入栈
15. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于          (满分:5)
    A. 1.0
    B. 2.9
    C. 3.4
    D. 5.5
16. 采用ISAM或VSAM组织的文件是          (满分:5)
    A.  索引非顺序文件
    B.  顺序文件  
    C. 索引顺序文件
    D. 散列文件
17. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是          (满分:5)
    A. 1
    B. 2
    C. 3
    D. 概念上是错误的
18. 引入二叉线索树的目的是          (满分:5)
    A. 加快查找结点的前驱或后继的速度  
    B. 为了能在二叉树中方便的进行插入与删除
    C. 为了能方便的找到双亲
    D. 使二叉树的遍历结果唯一
19. 栈的两种常用存储结构分别为          (满分:5)
    A. 顺序存储结构和链式存储结构
    B. 顺序存储结构和散列存储结构
    C. 链式存储结构和索引存储结构
    D. 链式存储结构和散列存储结构
20. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用           (满分:5)
    A. 深度优先搜索算法
    B. 广度优先搜索算法  
    C. 求最小生成树的prim算法
    D. 拓扑排序算法