东北大学19春学期《数据结构Ⅱ》在线作业3（含答案）

欧阳老师

19春学期《数据结构Ⅱ》在线作业3

奥鹏作业答案
奥鹏东北大学作业

一、单选题：
1.[单选题]  下面的说法中正确的是    (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。    (2)按二叉树定义，具有三个节点的二叉树共有6种。
    A.(1)，(2)                           
    B.(1)   
    C.(2)                                
    D.(1)，(2)都错
    正确答案:——B——
2.[单选题]  n个顶点的有向完全图中含有向边的数目最多为
    A.n-1                                   
    B.n           
    C.n(n-1)/2                             
    D.n(n-1)
    正确答案:——D——
3.[单选题]  深度为h的满m叉树的第k层的结点(1=＜k=＜h)数有  
    A. mk-1                                 
    B. mk-1            
    C.mh-1                                 
    D. mh-1
    正确答案:——A——
4.[单选题]  下面关于线性表的叙述中，错误的是
    A.线性表采用顺序存储，必须占用一片连续的存储单元。
    B.线性表采用顺序存储，便于进行插入和删除操作。
    C.线性表采用链接存储，不必占用一片连续的存储单元。
    D.线性表采用链接存储，便于插入和删除操作。
    正确答案:————
5.[单选题]  在计算机内实现递归算法时所需的辅助数据结构是    易百教育

    A.栈                              
    B.队列
    C.树                              
    D.图
    正确答案:————
6.[单选题]  在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
    A.1
    B.2
    C.3
    D.5
    正确答案:————
7.[单选题]  设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是     
    A.2
    B.3
    C.5
    D.6
    正确答案:————
8.[单选题]  若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为   
    A. O(0)                          
    B.  O(1)              
    C. O(n)                        
    D.  O(n2)
    正确答案:————
9.[单选题]  若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的     
    A. 层次遍历算法                     
    B. 前序遍历算法      
    C.中序遍历算法                     
    D. 后序遍历算法
    正确答案:————
10.[单选题]  一棵树高为K的完全二叉树至少的结点是   
    A. 2k –1                       
    B. 2k-1 –1            
    C. 2k-1                          
    D.2k
    正确答案:————
11.[单选题]  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为   
    A. O(n)                           
    B. O(e)     
    C.O(n+e)                           
    D.O(n2)
    正确答案:————
12.[单选题]   for（i=0；i＜m；i++）        for（j=0；j＜t；j++）c［i］［j］=0；for（i=0；i＜m；i++）for（j=0；j＜t；j++）for（k=0；k＜n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；    上列程序的时间复杂度为   
    A.   O（m+n×t）                  
    B.   O（m+n+t）     
    C.  O（m×n×t）                 
    D.  O（m×t+n）
    正确答案:————
13.[单选题]   若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为     
    A.4
    B.5
    C.8
    D.9
    正确答案:————
14.[单选题]  对于哈希函数H(key)=key%13,被称为同义词的关键字是   
    A.  35和41                       
    B.  23和39   
    C. 15和44                     
    D.  25和51
    正确答案:————
15.[单选题]  已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
    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}
    正确答案:————
16.[单选题]  含n个关键字的二叉排序树的平均查找长度主要取决于      
    A. 关键字的个数                 
    B. 树的形态      
    C. 关键字的取值范围            
    D.关键字的数据类型
    正确答案:————
17.[单选题]  ．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
    A. 逆拓扑有序                     
    B.拓扑有序            
    C. 无序的                     
    D.A和B
    正确答案:————
18.[单选题]  设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为  
    A.5
    B.6
    C.7
    D.8
    正确答案:————
19.[单选题]  某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是  
    A. 空或只有一个结点               
    B.高度等于其结点数  
    C.任一结点无左孩子                 
    D.任一结点无右孩子
    正确答案:————
20.[单选题]  无向图中一个顶点的度是指图中  
    A.   通过该顶点的简单路径数        
    B.   与该顶点相邻接的顶点数     
    C.   通过该顶点的回路数         
    D.  与该顶点连通的顶点数
    正确答案:————
奥鹏作业答案
奥鹏东北大学作业