中石油(华东)《数据结构》2017年秋学期在线作业（三）答案

openhelp100

《数据结构》2017年秋学期在线作业（三）
一、单选题:【20道,总分:100分】


1.二叉查找树的查找效率与二叉树的树型有关, 在(    )时其查找效率最低。          (满分:5)
    A. 结点太多
    B. 完全二叉树
    C. 呈单枝树
    D. 结点太复杂。
2.希尔排序和快速排序分别属于(    )。          (满分:5)
    A. 交换排序 选择排序
    B. 插入排序 选择排序
    C. 选择排序 归并排序
    D. 交换排序 选择排序
3.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于(    )。          (满分:5)
    A. 1.0
    B. 2.9
    C. 3.4
    D. 5.5
4.n个顶点的有向完全图中含有有向边的数目最多为(    )。          (满分:5)
    A. n-1
    B. n
    C. n(n-1)/2
    D. n(n-1)
5.AVL树是一种平衡的二叉排序树，树中任一结点的(    )。          (满分:5)
    A. 左、右子树的高度均相同
    B. 左、右子树高度差的绝对值不超过1
    C. 左子树的高度均大于右子树的高度
    D. 左子树的高度均小于右子树的高度
6.对于一组结点，从空树开始，把他们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于(    )。          (满分:5)
    A. 结点的输入顺序
    B. 结点的存储结构
    C. 结点的取值范围
    D. 计算机的硬件
7.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行(    )次探测。          (满分:5)
    A. k
    B. k-1
    C. k(k-1)/2
    D. 1+k(k-1)/2
8.以下说法错误的是(    )。          (满分:5)
    A. 散列法存储的基本思想是由关键码的值决定数据的存储地址。
    B. 散列表的结点中只包含数据元素自身的信息，不包含任何指针。
    C. 装填因子是散列法的一个重要参数，它反映散列表的装填程度。
    D. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。
9.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为(    )。          (满分:5)
    A. O(n)
    B. O(e)
    C. O(n+e)
    D. O(n2)
10.下面关于哈希（Hash，杂凑）查找的说法正确的是(    )。          (满分:5)
    A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
    B. 除留余数法是所有哈希函数中最好的
    C. 不存在特别好与坏的哈希函数，要视情况而定
    D. 在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
11.进行二分查找要求查找表必须(    )。          (满分:5)
    A. 以顺序方式存储。
    B. 以链式方式存储。
    C. 以顺序方式存储且数据元素按关键字有序排列。
    D. 以链式方式存储且数据元素按关键字有序排列。
12.图结构的广度优先搜索遍历算法中使用了(    )。          (满分:5)
    A. 堆栈
    B. 队列
    C. 堆栈和队列
    D. 以上都不正确。
13.设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是(    )。          (满分:5)
    A. G’为G 的子图
    B. G’为G 的连通分量
    C. G’为G的极小连通子图且V’=V
    D. G’为G的一个无环子图
14.题目和答案如下图所示：          (满分:5)
    A.
    B.
    C.
    D.
15.在有序表中使用折半查找法的平均时间是(    )。          (满分:5)
    A. O(1)
    B. O(n)
    C. O(log2n)
    D. O(n2)
16.下列说法不正确的是(    )。          (满分:5)
    A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
    B. 图的深度遍历不适用于有向图
    C. 遍历的基本算法有两种：深度遍历和广度遍历
    D. 图的深度遍历是一个递归过程
17.关键路径是事件结点网络中(    )。          (满分:5)
    A. 从源点到汇点的最长路径
    B. 从源点到汇点的最短路径
    C. 最长回路
    D. 最短回路
18.题目和答案如下图所示：          (满分:5)
    A.
    B.
    C.
    D.
19.设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？(    )。          (满分:5)
    A. f->lchild=null
    B. f->lchild=p->lchild
    C. f->lchild=p->rchild
    D. 都不是
20.下面关于图的存储的叙述中正确的是(    )。          (满分:5)
    A. 用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
    B. 用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
    C. 用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
    D. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
更多学习资料请登录www.openhelp100.com