东大18秋学期《数据结构Ⅰ》在线作业3[答案]满分答案
18秋学期《数据结构Ⅰ》在线作业3-0001
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1. 数据元素及其关系在计算机存储器内的表示，称为数据的
A.逻辑结构
B.存储结构
C.线性结构
D.非线性结构
2. 对于哈希函数H(key)=key%13,被称为同义词的关键字是
A.35和41
B.23和39
C.15和44
D.25和51
3. 二叉树中第5层上的结点个数最多为
A.8
B.15
C.16
D.32
4. 下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
5. 假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A.(rear-length+m+1)％m
B.(rear-length+m)％m
C.(rear-length+m-1)％m
D.(rear-length)％m
6. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
7. 一个具有1025个结点的二叉树的高h为
A.11
B.10
C.11至1025之间
D.10至1024之间
8. 一棵具有 n个结点的完全二叉树的树高度（深度）是
A.ëlognû+1
B.logn+1
C.ëlognû
D.logn-1
9. 倒排文件的主要优点是
A.便于进行插入和删除运算
B.便于进行文件的恢复
C.便于进行多关键字查询
D.节省存储空间
10. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
11. 计算机识别、存储和加工处理的对象被统称为
A.数据
B.数据元素
C.数据结构
D.数据类型
12. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A.n-1
B.n
C.n+1
D.2n
13. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,
<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是
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
14. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A.有向完全图
B.连通图
C.强连通图
D.有向无环图
15. 在一个单链表中，若删除*p结点的后继结点，则执行操作
A.q=p->next;p->next=q->next;free(q);
B.p=p->next;p->next=p->next->next;free(p);
C.p->next=q->next;free(p->next);
D.p=p->next->next;free(p->next);
16. 下列序列中，不构成堆的是
A.（1，2，5，3，4，6，7，8，9，10）
B.（10，5，8，4，2，6，7，1，3）
C.（10，9，8，7，3，5，4，6，2）
D.（1，2，3，4，10，9，8，7，6，5）
17. 用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A.5
B.6
C.8
D.9
18. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为
A.4，4，3
B.4，3，3
C.3，4，4
D.3，3，4
19. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A.O(n) O(n)
B.O(n) O(1)
C.O(1) O(n)
D.O(1) O(1)
20. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A.不一定相同
B.都相同
C.都不相同
D.互为逆序
东大18秋学期《数据结构Ⅰ》在线作业3[答案]历年参考题目如下：
