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

openhelp100

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


1.树根的层次为1，则有64个结点的完全二叉树的深度为(    )。          (满分:5)
    A. 8
    B. 7
    C. 6
    D. 5
2.下列判断正确的是(    )。          (满分:5)
    A. 二叉树是树的特例。
    B. 具有n个结点的完全二叉树的深度为n/2。
    C. Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
    D. 栈和队列都是限制存取点的线性结构。
3.下列说法正确的是 (    )。          (满分:5)
    A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
    B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
    C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
    D. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
4.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(    )。          (满分:5)
    A. i(i-l)/2+j
    B. j(j-l)/2+i
    C. j(j-l)/2+i-1
    D. i(i-l)/2+j-1
5.关于完全二叉树，不正确的描述是(    )。          (满分:5)
    A. 每个结点必须首先有左儿子，然后才能有右儿子。
    B. 在具有相同结点的所有二叉树中，它的高度最小。
    C. 每个结点的左右子树的高度最多相差为1。
    D. 没有度为1的结点。
6.在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为(    )。          (满分:5)
    A. n-1
    B. 2n-1
    C. n+1
    D. 2n+1
7.假设主串的长度为m，模式串的长度为n，KMP算法的时间复杂度为(    )。          (满分:5)
    A. n+m
    B. n*m
    C. n
    D. m
8.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) = (    )。          (满分:5)
    A. （a）
    B. A
    C.(b)
    D.(A)
9.下面关于完全二叉树的特点叙述不正确的是(    )。          (满分:5)
    A. 只有最后一层是不满的，不满层的结点首先出现在左边
    B. 至多只有最下面的两层结点的度小于2
    C. 左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1
    D. 叶子只能出现在最后两层上；
10.在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序(    )。          (满分:5)
    A. 都不相同
    B. 完全相同
    C. 前序遍历和中序遍历相同，而与后序遍历不同
    D. 前序遍历和后序遍历相同，而与中序遍历不同
11.假设主串的长度为m，模式串的长度为n，BF算法在一般和最坏情况下的时间复杂性分别为 (    )，所以还是一个常用算法。由于有回溯，所以主串输入后必须保存。          (满分:5)
    A. n+m n*m
    B. n m
    C. n*m n+m
    D. m n
12.采用BF算法在主串a a b a a a c a a c b b b中查找子串a a a c a a c b的查找次数为(    )。          (满分:5)
    A. 13
    B. 14
    C. 15
    D. 16
13.一维数组和线性表的区别为 (    ) 。          (满分:5)
    A. 前者长度固定,后者长度可变
    B. 两者长度均固定
    C. 前者长度可变,后者长度固定
    D. 两者长度均可变
14.下面关于数据结构的叙述中，正确的叙述是(    )。          (满分:5)
    A. 顺序存储方式的优点是存储密度大，且插、删除运算效率高
    B. 链表中每个结点都恰好包含一个指针
    C. 包含n个结点的二叉排序树的最大检索长度为log2n
    D. 将一棵树转为二叉树后，根结点无右子树
15.设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A[1,1]的存储地址为base，则A[i,j]的存储地址为(    )。          (满分:5)
    A. base+[(i-1)*m+(j-1)]*w
    B. base+[(j-1)*m+(i-1)]*w
    C. base+（j*m+i）*w
    D. base+（j*m+i）*w
16.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是(    )。          (满分:5)
    A.(c,d )
    B.(d )
    C. b
    D.(b)
17.树最适合用来表示(    )。          (满分:5)
    A. 有序数据元素
    B. 无序数据元素
    C. 元素之间具有分支层次关系的数据
    D. 元素之间无联系的数据
18.某非空二叉树的先序和后序序列正好相反，则二叉树一定是(    )的二叉树。          (满分:5)
    A. 空或只有一个结点
    B. 高度等于其结点数
    C. 任一结点无左孩子
    D. 任一结点无右孩子
19.在线索二叉树中，t 所指结点没有左子树的充要条件是(    )。          (满分:5)
    A. t->lchild!=NULL
    B. t->ltag==1
    C. t->ltag==1且 t->left!=NULL
    D. 以上都不对
20.题目和答案如下图所示：          (满分:5)
    A.
    B.
    C.
    D.
更多学习资料请登录www.openhelp100.com