东大19春学期《数据结构Ⅱ》在线作业123答案.docx
《东大19春学期《数据结构Ⅱ》在线作业123答案.docx》由会员分享，可在线阅读，更多相关《东大19春学期《数据结构Ⅱ》在线作业123答案.docx（14页珍藏版）》请在冰点文库上搜索。
东大19春学期《数据结构Ⅱ》在线作业123答案
19春学期《数据结构Ⅱ》在线作业1
设哈希表长为14，哈希函数H（key）=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A.8
B.3
C.5
D.9
正确答案:
A
带行表的三元组表是稀疏矩阵的一种
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
正确答案:
A
引起循环队列队头位置发生变化的操作是
A.出队
B.入队
C.取队头元素
D.取队尾元素
正确答案:
A
在下列各种文件中，不能进行顺序查找的文件是
A.顺序文件
B.索引文件
C.散列文件
D.多重表文件
正确答案:
C
一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是
A.0
B.1
C.2
D.3
正确答案:
B
在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是
A.p=p-next;
B.p-next=p-next-next;
C.p-next=p;
D.p=p-next-next;
正确答案:
B
计算机识别、存储和加工处理的对象被统称为
A.数据
B.数据元素
C.数据结构
D.数据类型
正确答案:
B
有关二叉树下列说法正确的是
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
正确答案:
B
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为
A.5
B.6
C.7
D.8
正确答案:
D
从广义表LS＝（（p,q）,r,s）中分解出原子q的运算是
A.tail（head（LS））
B.head（tail（head（LS）））
C.head（tail（LS））
D.tail（tail（head（LS）））
正确答案:
A
在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A.1
B.2
C.3
D.5
正确答案:
C
已知一个散列表如图所示，其散列函数为H（key）=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为
A.2
B.3
C.8
D.9
正确答案:
C
ISAM文件的周期性整理是为了空出
A.磁道索引
B.柱面索引
C.柱面基本区
D.柱面溢出区
正确答案:
D
在长度为n的顺序表中删除第i个元素（1in）时，元素移动的次数为
A.n-i+1
B.i
C.i+1
D.n-i
正确答案:
D
某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A.head==NULL
B.head-next==NULL
C.head!
=NULL
D.head-next!
=NULL
正确答案:
B
在VSAM文件的控制区间中，记录的存储方式为
A.无序顺序
B.有序顺序
C.无序链接
D.有序链接
正确答案:
B
下列程序段for（i=1;i=n;i++）A[I,j]=0;的时间复杂度是
A.O
（1）
B.O（0）
C.O（1+n）
D.O（n）
正确答案:
D
下列序列中，不构成堆的是
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）
正确答案:
D
在下列对顺序表进行的操作中，算法时间复杂度为O
（1）的是
A.访问第i个元素的前驱
B.在第i个元素之后插入一个新元素
C.删除第i个元素
D.对顺序表中元素进行排序
正确答案:
A
在待排关键字序列基本有序的前提下，效率最高的排序方法是
A.直接插入排序
B.快速排序
C.直接选择排序
D.归并排序
正确答案:
A
19春学期《数据结构Ⅱ》在线作业2
倒排文件的主要优点是
A.便于进行插入和删除运算
B.便于进行文件的恢复
C.便于进行多关键字查询
D.节省存储空间
正确答案:
C
在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head,则
A.p指向头结点
B.p指向尾结点
C.p的直接后继是头结点
D.P的直接后继是尾结点
正确答案:
D
已知广义表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））））
正确答案:
C
下列编码中属于前缀编码的是
A.{1,01,000,001}
B.{1,01,011,010}
C.{0,10,110,11}
D.{0,1,00,11}
正确答案:
A
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A.不一定相同
B.都相同
C.都不相同
D.互为逆序
正确答案:
B
设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
正确答案:
A
for（i=0；im；i++）for（j=0；jt；j++）c［i］［j］=0；for（i=0；im；i++）for（j=0；jt；j++）for（k=0；kn；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为
A.O（m+nt）
B.O（m+n+t）
C.O（mnt）
D.O（mt+n）
正确答案:
C
引起循环队列队头位置发生变化的操作是
A.出队
B.入队
C.取队头元素
D.取队尾元素
正确答案:
A
若vi,vj是有向图的一条边，则称
A.vi邻接于vj
B.vj邻接于vi
C.vi和vj相互邻接
D.vi与vj不相邻接
正确答案:
B
若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是
A.1234
B.4132
C.4231
D.4213
正确答案:
C
假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。
若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
A.（rear-front-1）％n
B.（rear-front）％n
C.（front-rear+1）％n
D.（rear-front+n）％n
正确答案:
D
数据的四种基本存储结构是指
A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
正确答案:
B
设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。
若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A.21
B.23
C.41
D.62
正确答案:
C
判断两个串大小的基本准则是
A.两个串长度的大小
B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小
正确答案:
D
下列说法正确的是
（1）二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索
（2）二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前（3）二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A.
（1）
（2）（3）
B.
（1）
（2）
C.
（1）（3）
D.前面的可选答案都不对
正确答案:
D
以下属于逻辑结构的是
A.顺序表
B.哈希表
C.有序表
D.单链表
正确答案:
C
按排序过程中依据的原则分类，快速排序属于
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.归并类的排序方法
正确答案:
C
对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
A.39/15
B.49/15
C.51/15
D.55/15
正确答案:
B
栈的两种常用存储结构分别为
A.顺序存储结构和链式存储结构
B.顺序存储结构和散列存储结构
C.链式存储结构和索引存储结构
D.链式存储结构和散列存储结构
正确答案:
A
已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A.5
B.6
C.16
D.17
正确答案:
C
19春学期《数据结构Ⅱ》在线作业3
下面的说法中正确的是
（1）任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
（2）按二叉树定义，具有三个节点的二叉树共有6种。
A.
（1），
（2）
B.
（1）
C.
（2）
D.
（1），
（2）都错
正确答案:
B
n个顶点的有向完全图中含有向边的数目最多为
A.n-1
B.n
C.n（n-1）/2
D.n（n-1）
正确答案:
D
深度为h的满m叉树的第k层的结点（1=k=h）数有
A.mk-1
B.mk-1
C.mh-1
D.mh-1
正确答案:
A
下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
正确答案:
B
在计算机内实现递归算法时所需的辅助数据结构是
A.栈
B.队列
C.树
D.图
正确答案:
A
在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A.1
B.2
C.3
D.5
正确答案:
C
设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A.2
B.3
C.5
D.6
正确答案:
B
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O（0）
B.O
（1）
C.O（n）
D.O（n2）
正确答案:
C
若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A.层次遍历算法
B.前序遍历算法
C.中序遍历算法
D.后序遍历算法
正确答案:
C
一棵树高为K的完全二叉树至少的结点是
A.2k1
B.2k-11
C.2k-1
D.2k
正确答案:
C
一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A.O（n）
B.O（e）
C.O（n+e）
D.O（n2）
正确答案:
A
for（i=0；im；i++）for（j=0；jt；j++）c［i］［j］=0；for（i=0；im；i++）for（j=0；jt；j++）for（k=0；kn；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为
A.O（m+nt）
B.O（m+n+t）
C.O（mnt）
D.O（mt+n）
正确答案:
C
若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A.4
B.5
C.8
D.9
正确答案:
C
对于哈希函数H（key）=key%13,被称为同义词的关键字是
A.35和41
B.23和39
C.15和44
D.25和51
正确答案:
D
已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。
对这些子序列进行一趟两两归并的结果是
A..{25,36,48,72,23,40,79,82,16,35}
B..{25,36,48,72,16,23,40,79,82,35}
C..{25,36,48,72,16,23,35,40,79,82}
D..{16,23,25,35,36,40,48,72,79,82}
正确答案:
D
含n个关键字的二叉排序树的平均查找长度主要取决于
A.关键字的个数
B.树的形态
C.关键字的取值范围
D.关键字的数据类型
正确答案:
A
．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.逆拓扑有序
B.拓扑有序
C.无序的
D.A和B
正确答案:
A
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为
A.5
B.6
C.7
D.8
正确答案:
D
某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
正确答案:
B
无向图中一个顶点的度是指图中
A.通过该顶点的简单路径数
B.与该顶点相邻接的顶点数
C.通过该顶点的回路数
D.与该顶点连通的顶点数
正确答案:
D
升级会员 