[东北大学]19春学期《数据结构Ⅱ》在线作业3（答案）
【奥鹏】[东北大学]19春学期《数据结构Ⅱ》在线作业3试卷总分:100 得分:100
第1题,下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A、(1)，(2)
B、(1)
C、(2)
D、(1)，(2)都错
正确答案:B
第2题,n个顶点的有向完全图中含有向边的数目最多为
A、n-1
B、n
C、n(n-1)/2
D、n(n-1)
正确答案
第3题,深度为h的满m叉树的第k层的结点(1=k=h)数有
A、mk-1
B、mk-1
C、mh-1
D、mh-1
正确答案:A
第4题,下面关于线性表的叙述中，错误的是
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
正确答案:B
第5题,在计算机内实现递归算法时所需的辅助数据结构是
A、栈
B、队列
C、树
D、图
正确答案:A
第6题,在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A、1
B、2
C、3
D、5
正确答案:C
第7题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A、2
B、3
C、5
D、6
正确答案:B
第8题,若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A、O(0)
B、O(1)
C、O(n)
D、O(n2)
正确答案:C
第9题,若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A、层次遍历算法
B、前序遍历算法
C、中序遍历算法
D、后序遍历算法
正确答案:C
第10题,一棵树高为K的完全二叉树至少的结点是
A、2k –1
B、2k-1 –1
C、2k-1
D、2k
正确答案:C
第11题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
正确答案:A
第12题,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+n×t）
B、O（m+n+t）
C、O（m×n×t）
D、O（m×t+n）
正确答案:C
第13题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A、4
B、5
C、8
D、9
正确答案:C
第14题,对于哈希函数H(key)=key%13,被称为同义词的关键字是
A、35和41
B、23和39
C、15和44
D、25和51
正确答案
第15题,已知一组关键字为{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}
正确答案
第16题,含n个关键字的二叉排序树的平均查找长度主要取决于
A、关键字的个数
B、树的形态
C、关键字的取值范围
D、关键字的数据类型
正确答案:A
第17题,．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A、逆拓扑有序
B、拓扑有序
C、无序的
D、A和B
正确答案:A
第18题,设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为
A、5
B、6
C、7
D、8
正确答案
第19题,某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
正确答案:B
第20题,无向图中一个顶点的度是指图中
A、通过该顶点的简单路径数
B、与该顶点相邻接的顶点数
C、通过该顶点的回路数
D、与该顶点连通的顶点数
正确答案
页:
[1]