东大19春学期《数据结构Ⅱ》在线作业123答案.docx

1、东大19春学期数据结构在线作业123答案19春学期数据结构在线作业1设哈希表长为14，哈希函数H(key)=key11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A.8B.3C.5D.9正确答案:A带行表的三元组表是稀疏矩阵的一种A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构正确答案:A引起循环队列队头位置发生变化的操作是A.出队B.入队C.取队头元素D.取队尾元素正确答案:A在下列各种文件中，不能进行顺序查找的文件是A.顺序文件B.索引文件C.散列文件D.多重表文件正确答案:C一棵左右子树均

2、不空的二叉树在先序线索化后，其中空的链域的个数是A.0B.1C.2D.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.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2正确答案:B设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的

3、叶子数为A.5B.6C.7D.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在目标串T0.n-1=″xwxxyxy″中，对模式串P0.m-1=″xy″进行子串定位操作的结果是A.1B.2C.3D.5正确答案:C已知一个散列表如图所示，其散列函数为H(key)=key11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为A.2B.3C.8D.9正确答案:CISAM文件

4、的周期性整理是为了空出A.磁道索引B.柱面索引C.柱面基本区D.柱面溢出区正确答案:D在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为A.n-i+1B.iC.i+1D.n-i正确答案:D某带头结点的单链表的头指针为head，判定该链表为非空的条件是A.head=NULLB.head-next=NULLC.head!=NULLD.head-next!=NULL正确答案:B在VSAM文件的控制区间中，记录的存储方式为A.无序顺序B.有序顺序C.无序链接D.有序链接正确答案:B下列程序段for(i=1;i=n;i+)AI,j=0;的时间复杂度是A.O(1)B.O(0)C.O(1+n)

5、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.归并排序正确答案:A19春学期数据结构在线作业2倒排文件的主要优点是A.便于进行插入

6、和删除运算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,00

7、1B.1,01,011,010C.0,10,110,11D.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正确答案:Afor（i=0；im；i+）for（j=0；jt；j+）cij=0；fo

8、r（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）正确答案:C引起循环队列队头位置发生变化的操作是A.出队B.入队C.取队头元素D.取队尾元素正确答案:A若vi,vj是有向图的一条边，则称A.vi邻接于vjB.vj邻接于viC.vi和vj相互邻接D.vi与vj不相邻接正确答案:B若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A.1234B.4132C.4231D.4213正确

9、答案:C假设以数组An存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n正确答案:D数据的四种基本存储结构是指A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构正确答案:B设

10、顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为A.21B.23C.41D.62正确答案:C判断两个串大小的基本准则是A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小正确答案:D下列说法正确的是(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值A.(1)(2)(3)B.(1)(2)

11、C.(1)(3)D.前面的可选答案都不对正确答案:D以下属于逻辑结构的是A.顺序表B.哈希表C.有序表D.单链表正确答案:C按排序过程中依据的原则分类，快速排序属于A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法正确答案:C对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为A.39/15B.49/15C.51/15D.55/15正确答案:B栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构正确答案:A已

12、知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为A.5B.6C.16D.17正确答案:C19春学期数据结构在线作业3下面的说法中正确的是(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。(2)按二叉树定义，具有三个节点的二叉树共有6种。A.(1)，(2)B.(1)C.(2)D.(1)，(2)都错正确答案:Bn个顶点的有向完全图中含有向边的数目最多为A.n-1B.nC.n(n-1)/2D.n(n-1)正确答案:D深度为h的满m叉树的第k层的结点(1=k=h)数有A.mk-1B.mk-1C.mh-1D.mh-1正确答案:A下面关于线性

13、表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。正确答案:B在计算机内实现递归算法时所需的辅助数据结构是A.栈B.队列C.树D.图正确答案:A在目标串T0.n-1=″xwxxyxy″中，对模式串P0.m-1=″xy″进行子串定位操作的结果是A.1B.2C.3D.5正确答案:C设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈

14、的容量至少应该是A.2B.3C.5D.6正确答案:B若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A.O(0)B.O(1)C.O(n)D.O(n2)正确答案:C若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法正确答案:C一棵树高为K的完全二叉树至少的结点是A.2k1B.2k-11C.2k-1D.2k正确答案:C一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为A.O(n)B.O(e)C.O(n+e)D.O(n2)正确答案:Afo

15、r（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）正确答案:C若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.4B.5C.8D.9正确答案:C对于哈希函数H(key)=key%13,被称为同义词的关键字是A.35和41B.23和39C.15和44D.25和51正确答案:D已知一组关键字为25,48,36,72,79,82,23,40,16,35

16、，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82D.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.5B.6C.7D.8正确答案:D某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子正确答案:B无向图中一个顶点的度是指图中A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数正确答案:D