16春学期奥鹏东大《数据结构Ⅰ》在线作业1标准答案

奥鹏网院作业

16春学期《数据结构Ⅰ》在线作业1

一、单选题：
1. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别为           (满分:5)
    A. 1和 5
    B. 2和4
    C.  4和2
    D.  5和1
2. 为便于判别有向图中是否存在回路，可借助于          (满分:5)
    A.  广度优先搜索算法
    B.  最小生成树算法  
    C. 最短路径算法
    D. 拓扑排序算法
3. 连通网的最小生成树是其所有生成树中          (满分:5)
    A. 顶点集最小的生成树
    B.  边集最小的生成树
    C.  顶点权值之和最小的生成树
    D. 边的权值之和最小的生成树
4. 上溢现象通常出现在          (满分:5)
    A. 顺序栈的入栈操作过程中
    B. 顺序栈的出栈操作过程中
    C. 链栈的入栈操作过程中
    D. 链栈的出栈操作过程中
5. ALV树是一种平衡的二叉排序树，树中任一结点的          (满分:5)
    A.  左、右子树的高度均相同  
    B.  左、右子树高度差的绝对值不超过1
    C. 左子树的高度均大于右子树的高度
    D.  左子树的高度均小于右子树的高度
6. ISAM文件的周期性整理是为了空出          (满分:5)
    A. 磁道索引
    B. 柱面索引
    C. 柱面基本区
    D. 柱面溢出区
7. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到           (满分:5)
    A. P=″SCIENCE″
    B.  P=″STUDY″
    C.  S=″SCIENCE″
    D.  S=″STUDY″
8. 链栈与顺序栈相比，比较明显的优点是          (满分:5)
    A. 插入操作更加方便
    B.  删除操作更加方便
    C. 不会出现下溢的情况
    D.  不会出现上溢的情况
9. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为          (满分:5)
    A. A．左子树的叶子结点
    B. B．左子树的分支结点
    C. C．右子树的叶子结点
    D. D．右子树的分支结点
10. 高度为5的完全二叉树中含有的结点数至少为           (满分:5)
    A. 16
    B. 17
    C. 31
    D. 32
11. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为          (满分:5)
    A. 0
    B. 1
    C. 48
    D. 49
12. 快速排序在最坏情况下的时间复杂度是          (满分:5)
    A. O(n2log2n)
    B. O(n2)
    C. O(nlog2n)
    D. O(log2n)
13. for（i=0；i；i++） for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为          (满分:5)
    A.  O（m+n×t）
    B.  O（m+n+t）
    C.  O（m×n×t）
    D.  O（m×t+n）
14. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是          (满分:5)
    A.  顺序存储方法
    B. 链式存储方法
    C.  索引存储方法
    D. 散列存储方法
15. 在计算机内实现递归算法时所需的辅助数据结构是          (满分:5)
    A. 栈
    B. 队列
    C. 树
    D. 图
16. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的           (满分:5)
    A. 1/2倍
    B.  1倍  
    C. 2倍
    D. 3倍
17. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是          (满分:5)
    A. 250
    B. 500
    C. 254
    D. 以上答案都不对
18. 若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列           (满分:5)
    A. 一定存在
    B. 一定不存在
    C. 不一定存在
    D. 不确定
19. 以下说法不正确的是          (满分:5)
    A. 无向图中的极大连通子图称为连通分量
    B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
    C.  图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
    D.  有向图的遍历不可采用广度优先搜索
20. 数据元素及其关系在计算机存储器内的表示，称为数据的           (满分:5)
    A. 逻辑结构
    B. 存储结构
    C.  线性结构
    D. 非线性结构