东北大学17秋学期《数据结构Ⅰ》在线作业3参考答案

奥鹏作业答案

17秋学期《数据结构Ⅰ》在线作业3
一、单选题:【20道,总分:100分】


1. 在待排关键字序列基本有序的前提下，效率最高的排序方法是          (满分:5)
    A. 直接插入排序
    B.  快速排序
    C. 直接选择排序
    D.  归并排序
2. 下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。          (满分:5)
    A.(1)，(2)
    B. (1)
    C.(2)
    D. (1)，(2)都错
3. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是           (满分:5)
    A. p=p->next;
    B.  p->next=p->next->next;
    C. p->next=p;
    D. p=p->next->next;
4. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是          (满分:5)
    A. 0
    B. 1
    C. 2
    D. 不确定
5. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为          (满分:5)
    A. (19，23，56，34，78，67，88，92)
    B. (23，56，78，66，88，92，19，34)
    C. (19，23，34，56，67，78，88，92)
    D. (19，23，67，56，34，78，92，88)
6. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为          (满分:5)
    A. O(n)
    B.  O(e)
    C. O(n+e)
    D. O(n2)
7. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为          (满分:5)
    A. （1，2，3，4，5，6，7，8）
    B. （1，4，3，2，5，7，8，6）
    C. （2，1，4，3，5，7，8，6）
    D. （8，7，6，5，4，3，2，1）
8. 上溢现象通常出现在          (满分:5)
    A. 顺序栈的入栈操作过程中
    B. 顺序栈的出栈操作过程中
    C. 链栈的入栈操作过程中
    D. 链栈的出栈操作过程中
9. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在           (满分:5)
    A. BT[i/2]
    B.  BT[2*i-1]
    C.  BT[2*i]
    D.  BT[2*i+1]
10. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是          (满分:5)
    A. 空或只有一个结点
    B. 高度等于其结点数
    C.  任一结点无左孩子
    D.  任一结点无右孩子
11. 若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向          (满分:5)
    A.  各自的头结点
    B. 各自的尾结点  
    C. 各自的第一个元素结点
    D. 一个表的头结点，另一个表的尾结点
12. n个顶点的强连通图中至少含有          (满分:5)
    A.  n-1条有向边
    B.  n条有向边
    C.  n(n-1)/2条有向边
    D. n(n-1)条有向边
13. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则           (满分:5)
    A. p指向头结点
    B. p指向尾结点
    C. p的直接后继是头结点
    D. P的直接后继是尾结点
14. 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是　　　　　s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; s ->data = t;          (满分:5)
    A.  结点p与结点s的数据域互换
    B. 在p所指结点的元素之前插入元素
    C.  在p所指结点的元素之后插入元素  
    D. 在结点p之前插入结点s
15. 在一棵高度为k的满二叉树中，结点总数为          (满分:5)
    A.  2k-1
    B. 2k
    C. 2k-1
    D. log2kû+1
16. 倒排文件的主要优点是          (满分:5)
    A.  便于进行插入和删除运算
    B. 便于进行文件的恢复
    C.  便于进行多关键字查询
    D.  节省存储空间
17. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为          (满分:5)
    A. O(1)
    B.  O(logn)
    C. O(n)
    D. O(n logn)
18. 若要在单链表中的结点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;
19. 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）
20. 算法的时间复杂度主要取决于          (满分:5)
    A. 问题的规模
    B. 待处理数据的初态
    C. 难度
    D. A和B
更多学习资料请登录www.openhelp100.com