东北大学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中，其中根结点存放在BT，若BT中的结点有左孩子，则左孩子存放在 (满分:5)
A. BT
B.BT
C.BT
D.BT
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
页:
[1]