东师数据结构2022年秋学期在线作业2【标准答案】

数据结构19春在线作业2-0002

试卷总分:100 得分:100

一、单选题 (共 20 道试题,共 60 分)

1.判别头绪二叉树中某结点p有右后代的条件是 ( )。

A.p->rtag = = 0

B.p->rtag = = 1

C.p ! = NULL

D.p->lchild ! = NULL



2.选用次序查找方法查找长度为n的线性表时，每个元素的均匀查找长度为 ()。

A.n

B.(n-1)/2

C.n/2

D.(n+1)/2



3.用ISAM安排文件合适于 ()。

A.磁带

B.磁盘

C.光盘

D.外存储器



4.在k叉树中，无爸爸妈妈的结点称为 ( )。

A.根

B.叶

C.先人

D.后代



5.一棵摆布子树均不空的二叉树在前序头绪化后，其间空的链域的个数是：( )。

A.不断定

B.0

C.1

D.2



6.设二维数组A[0..m-1][0..n-1]按行优先次序存储且每个元素占c个单元，则元素A[i][j]的地址为 ()。

A.LOC(A[0][0]) + (j*m+i)*c

B.LOC(A[0][0]) + (i*n+j)*c

C.LOC(A[0][0]) + [(j-1)*m+i-1]*c

D.LOC(A[0][0]) + [(i-1)*n+j-1]*c



7.下面关于串的叙说中，哪一个是不正确的? ( )

A.串是字符的有限序列

B.空串是由空格构成的串

C.形式匹配是串的一种重要运算

D.串既能够选用次序存储，也能够选用链式存储



8.广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作成果是 ()。

A.( c , d )

B.c , d

C.( ( c , d ) )

D.d



9.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前刺进s所指结点，则履行 ( )。

A.p->next = s; s->next = q;

B.s->next = p->next; p->next = s;

C.p->next = s->next; s->next = p;

D.q->next = s; s->next = p;



10.若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。

A.存在

B.不存在

C.纷歧定存在

D.能够不存在



11.下列排序算法中，在每一趟都能选出一个元素放到其终究方位上，而且当时间功能受数据初始特性影响的是 ()。

A.直接刺进排序

B.疾速排序

C.直接挑选排序

D.堆排序



12.设s1 = "abc" ，则strlen(s1) = ( )。

A.0

B.1

C.2

D.3



13.B+ 树应用在 () 文件系统中。

A.ISAM

B.VSAM

C.次序

D.散列



14.四个元素进入行列QU的次序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。

A.U

B.V

C.X

D.Y



15.串是一种特别的线性表，其特别性表现在 ( )。

A.能够次序存储

B.数据元素是一个字符

C.能够连接存储

D.数据元素能够是多个字符



16.稀少矩阵常用的紧缩存储方法有两种，它们是 ()。

A.二维数组和三维数组

B.三元组和散列

C.三元组和十字链表

D.散列和十字链表



17.假如要求一个线性表既能较快地查找、又能习惯动态改变的要求，则可选用的查找方法是 ()。

A.次序查找

B.减半查找

C.分块查找

D.根据特点的查找



18.下列描绘中正确的是 ( )。

A.线性表的逻辑次序与存储次序老是共同的

B.每种数据结构都具有查找、刺进和删去三种根本运算

C.数据结构本质上包含逻辑结构和存储结构两方面的内容

D.挑选适宜的数据结构是处理应用疑问的要害过程



19.散列函数有一个一起的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。

A.平等概率

B.最大约率

C.最小概率

D.均匀概率



20.关于3个结点a、b、c，可构成不一样的二叉树的棵数为 ( )。

A.24

B.28

C.30

D.32



二、判别题 (共 20 道试题,共 40 分)

21.二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树必定是二叉排序树。



22.对无序表用减半查找比次序查找快。



23.最小生成树疑问是结构带权连通图 ( 网 ) 的最小价值生成树。



24.结构的存储密度界说为数据自身所占的存储量与整个结构所占的存储量之比。



25.连接存储结构属静态存储方法。



26.分块查找在等概率查找状况下，其均匀查找长度不只与表中元素个数有关，并且与每块中的元素个数有关。



27.链表与次序存储结构比较，在链表中进行刺进、删去操作的功率高。



28.栈和行列都是约束存取点的线性结构。



29.数组是同类型值的调集。



30.归并排序的辅助存储空间价值为O(1 )。



31.在二叉树中刺进结点，则此二叉树便不再是二叉树了。



32.将森树转成二叉树，根结点没有右子树。



33.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能运用邻接表存储方式来存储它。



34.强健的算法不会因不合法的输人数据而呈现不可思议的状况。



35.在指定结点之后刺进新结点时，双链表比单链表更便利。



36.无向图的邻接矩阵可用一维数组存储。



37.若一个广义表的表头为空表，则此广义表亦为空表。



38.稀少矩阵紧缩存储后，必会失掉随机存取功用。



39.程序必定是算法。



40.广义表中的元素或许是一个不可以切割的原子，或许是一个非空的广义表。