《数据结构Ⅰ》3. 假设以数组A[m]存放循环队列的元素。已...

奥鹏网院作业

奥鹏东大16秋学期《数据结构Ⅰ》在线作业3标准答案
一、单选题：
1. 若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向          (满分:5)
    A.  各自的头结点
    B. 各自的尾结点  
    C. 各自的第一个元素结点
    D. 一个表的头结点，另一个表的尾结点
2.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为          (满分:5)
    A. 4
    B. 5
    C. 6
    D. 7
3. 假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为          (满分:5)
    A. (rear-length+m+1)％m
    B. (rear-length+m)％m
    C. (rear-length+m-1)％m
    D. (rear-length)％m
4. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为          (满分:5)
    A. n-1
    B. n
    C. n+1
    D. 2n
5. 在待排关键字序列基本有序的前提下，效率最高的排序方法是          (满分:5)
    A. 直接插入排序
    B.  快速排序
    C. 直接选择排序
    D.  归并排序
6. 在下列各种文件中，不能进行顺序查找的文件是           (满分:5)
    A. 顺序文件
    B. 索引文件  
    C. 散列文件
    D. 多重表文件
7. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是           (满分:5)
    A. p=p->next;
    B.  p->next=p->next->next;
    C. p->next=p;
    D. p=p->next->next;
8. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为          (满分:5)
    A. 5
    B. 8
    C. 11
    D. 18
9. 设数组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
10. 下列说法正确的是 (1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值          (满分:5)
    A.(1)(2)(3)
    B.(1)(2)
    C.(1)(3)
    D. 前面的可选答案都不对
11. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有          (满分:5)
    A. 2h
    B. 2h-1
    C. 2h+1
    D. h+1
12. 用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为          (满分:5)
    A. 5
    B. 6
    C. 8
    D. 9
13. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是          (满分:5)
    A. 250
    B. 500
    C. 254
    D. 以上答案都不对
14. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={1,V2>,1,V3>,1,V4>,2,V5>,3,V5>, 3,V6>,4,V6>,5,V7>,6,V7>},G的拓扑序列是          (满分:5)
    A. V1
    V3
    V4
    V6
    V2
    V5
    V7
    B. V1
    V3
    V2
    V6
    V4
    V5
    V7
    C. V1
    V3
    V4
    V5
    V2
    V6
    V7
    D. V1
    V2
    V5
    V3
    V4
    V6
    V7
15. 一个具有1025个结点的二叉树的高h为          (满分:5)
    A. 11
    B. 10
    C.  11至1025之间
    D. 10至1024之间
16. 以下属于逻辑结构的是          (满分:5)
    A. 顺序表
    B. 哈希表
    C. 有序表
    D.  单链表
17. ALV树是一种平衡的二叉排序树，树中任一结点的          (满分:5)
    A.  左、右子树的高度均相同  
    B.  左、右子树高度差的绝对值不超过1
    C. 左子树的高度均大于右子树的高度
    D.  左子树的高度均小于右子树的高度
18. . 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为          (满分:5)
    A. 4
    B. 5
    C. 8
    D. 9
19. ISAM文件和VSAM文件的区别之一是          (满分:5)
    A.  前者是索引顺序文件，后者是索引非顺序文件
    B.  前者只能进行顺序存取，后者只能进行随机存取
    C.  前者建立静态索引结构，后者建立动态索引结构
    D.  前者的存储介质是磁盘，后者的存储介质不是磁盘
20. 十字链表的三元组表是稀疏矩阵的一种          (满分:5)
    A. 顺序存储结构
    B.  链式存储结构  
    C. 索引存储结构
    D. 散列存储结构