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