《东大19春学期《数据结构Ⅱ》在线作业2满分哦》由会员分享，可在线阅读，更多相关《东大19春学期《数据结构Ⅱ》在线作业2满分哦（5页珍藏版）》请在金锄头文库上搜索。
1、东大19春学期数据结构在线作业2-0001试卷总分:100 得分:100一、 单选题 (共 20 道试题,共 100 分)1. 倒排文件的主要优点是 A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间正确答案:C2. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next= head,则 A.p指向头结点B.p指向尾结点C.p的直接后继是头结点D.P的直接后继是尾结点正确答案:D3.已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是A.head(tail(LS)B.tail(
2、head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)正确答案:C4. 下列编码中属于前缀编码的是 A.1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,11正确答案:A5. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 A.不一定相同B.都相同C.都不相同D.互为逆序正确答案:B6. 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是s - next = p - next; p - next = s; t = p - data; p - data
3、= s - data; s -data = t; A.结点p与结点s的数据域互换B.在p所指结点的元素之前插入元素C.在p所指结点的元素之后插入元素D.在结点p之前插入结点s正确答案:A7. for（i=0；im；i+） for（j=0；jt；j+）cij=0；for（i=0；im；i+）for（j=0；jt；j+）for（k=0；kn；k+）cij=cij+aik*bkj； 上列程序的时间复杂度为 A.O（m+nt）B.O（m+n+t）C.O（mnt）D.O（mt+n）正确答案:C8. 引起循环队列队头位置发生变化的操作是 A.出队B.入队C.取队头元素D.取队尾元素正确答案:A9. 若是有
4、向图的一条边，则称 A.vi邻接于vjB.vj邻接于viC.vi和vj相互邻接D.vi与vj不相邻接正确答案:B10. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A.1234B.4132C.4231D.4213正确答案:C11. 假设以数组An存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-
5、front+n)n正确答案:D12. 数据的四种基本存储结构是指 A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构正确答案:B13. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为 A.21B.23C.41D.62正确答案:C14. 判断两个串大小的基本准则是A.两个串长度的大小
6、B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小正确答案:D15. 下列说法正确的是 (1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值A.(1)(2)(3)B.(1)(2)C.(1)(3)D.前面的可选答案都不对正确答案:D16. 以下属于逻辑结构的是A.顺序表B.哈希表C.有序表D.单链表正确答案:C17. 按排序过程中依据的原则分类，快速排序属于A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法正确答案:C18. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为 A.39/15B.49/15C.51/15D.55/15正确答案:B19. 栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构正确答案:A20. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为 A.5B.6C.16D.17正确答案:C
