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

奥鹏网院作业

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

一、单选题：
1. 设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是          (满分:5)
    A. 8
    B. 3
    C. 5
    D. 9
2. 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）
3. 为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为           (满分:5)
    A. 05
    B. 37
    C. 41
    D. 62
4. 已知函数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″
5. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是          (满分:5)
    A. s->next=p->next; p->next=s;
    B.  p->next=s; s->next=p->next;
    C. p->next=s->next; s->next=p;
    D. s->next=p; p->next=s->next;
6.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为          (满分:5)
    A. 4
    B. 5
    C. 6
    D. 7
7. 下述哪一条是顺序存储结构的优点          (满分:5)
    A. 存储密度大
    B. 插入运算方便
    C. 删除运算方便
    D. 可方便地用于各种逻辑结构的存储表示
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为          (满分:5)
    A. 不确定
    B. 2n
    C. 2n+1
    D. 2n-1
9. 二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为          (满分:5)
    A. 470
    B. 471
    C. 472
    D. 473
10. 抽象数据类型的三个组成部分分别为          (满分:5)
    A. 数据对象、数据关系和基本操作  
    B. 数据元素、逻辑结构和存储结构
    C. 数据项、数据元素和数据类型
    D. 数据元素、数据结构和数据类型
11.数据结构中所定义的数据元素，是用于表示数据的          (满分:5)
    A.   最小单位
    B.  最大单位  
    C.  基本单位
    D.  不可分割的单位
12. 以下数据结构中，属于线性结构的是          (满分:5)
    A. 广义表
    B.  二叉树
    C.  稀疏矩阵
    D.  串
13. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为          (满分:5)
    A. 数组的元素处在行和列两个关系中
    B. 数组的元素必须从左到右顺序排列
    C. 数组的元素之间存在次序关系
    D. 数组是多维结构，内存是一维结构
14. 索引非顺序文件的特点是          (满分:5)
    A.  主文件无序，索引表有序
    B.  主文件有序，索引表无序
    C.  主文件有序，索引表有序
    D. 主文件无序，索引表无序
15. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的          (满分:5)
    A.  层次遍历算法
    B. 前序遍历算法
    C.  中序遍历算法
    D. 后序遍历算法
16. 下列编码中属于前缀编码的是          (满分:5)
    A.  {1
    01
    000
    001}
    B.  {1
    01
    011
    010}  
    C. {0
    10
    110
    11}
    D.  {0
    1
    00
    11}
17. 设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是          (满分:5)
    A. (rear-front)%m= =1
    B.  front= =rear  
    C.(rear-front)%m= =m-1
    D. front= =(rear+1)%m
18. 导致栈上溢的操作是          (满分:5)
    A. 栈满时执行的出栈
    B.  栈满时执行的入栈
    C. 栈空时执行的出栈
    D.  栈空时执行的入栈
19. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为          (满分:5)
    A. O(n)
    B.  O(e)
    C. O(n+e)
    D. O(n2)
20. n个顶点的强连通图中至少含有          (满分:5)
    A.  n-1条有向边
    B.  n条有向边
    C.  n(n-1)/2条有向边
    D. n(n-1)条有向边