东大18秋学期《数据结构Ⅱ》在线作业2答案答案
18秋学期《数据结构Ⅱ》在线作业2-0001
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1. 倒排文件的主要优点是
A.便于进行插入和删除运算
B.便于进行文件的恢复
C.便于进行多关键字查询
D.节省存储空间
2. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
head,则
A.p指向头结点
B.p指向尾结点
C.p的直接后继是头结点
D.P的直接后继是尾结点
3.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS))))
D.head(tail(tail(head(LS))))
4. 下列编码中属于前缀编码的是
A.{1,01,000,001}
B.{1,01,011,010}
C.{0,10,110,11}
D.{0,1,00,11}
5. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A.不一定相同
B.都相同
C.都不相同
D.互为逆序
6. 设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
7. 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）
8. 引起循环队列队头位置发生变化的操作是
A.出队
B.入队
C.取队头元素
D.取队尾元素
9. 若<vi, vj>是有向图的一条边，则称
A.vi邻接于vj
B.vj邻接于vi
C.vi和vj相互邻接
D.vi与vj­不相邻接
10. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是
A.1234
B.4132
C.4231
D.4213
11. 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
A.(rear-front-1)％n
B.(rear-front)％n
C.(front-rear+1)％n
D.(rear-front+n)％n
12. 数据的四种基本存储结构是指
A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
13. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A.21
B.23
C.41
D.62
14. 判断两个串大小的基本准则是
A.两个串长度的大小
B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小
15. 下列说法正确的是
(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索
(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前
(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A.(1)(2)(3)
B.(1)(2)
C.(1)(3)
D.前面的可选答案都不对
16. 以下属于逻辑结构的是
A.顺序表
B.哈希表
C.有序表
D.单链表
17. 按排序过程中依据的原则分类，快速排序属于
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.归并类的排序方法
18. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
A.39/15
B.49/15
C.51/15
D.55/15
19. 栈的两种常用存储结构分别为
A.顺序存储结构和链式存储结构
B.顺序存储结构和散列存储结构
C.链式存储结构和索引存储结构
D.链式存储结构和散列存储结构
20. 已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A.5
B.6
C.16
D.17
东大18秋学期《数据结构Ⅱ》在线作业2答案历年真题如下：
