东北大学19春学期《数据结构Ⅱ》在线作业3

作业辅导

[东北大学]19春学期《数据结构Ⅱ》在线作业3（答案）
【奥鹏】[东北大学]19春学期《数据结构Ⅱ》在线作业3
奥鹏作业答案
奥鹏东北大学作业

试卷总分100得分100
第1题下面的说法中正确的是(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。(2)按二叉树定义，具有三个节点的二叉树共有6种。
A、(1)，(2)
B、(1)
C、(2)
D、(1)，(2)都错
正确答案B
第2题n个顶点的有向完全图中含有向边的数目最多为    易百教育
A、n1
B、n
C、n(n1)/2
D、n(n1)
正确答案
第3题深度为h的满m叉树的第k层的结点(1=k=h)数有
A、mk1
B、mk1
C、mh1
D、mh1
正确答案A
第4题下面关于线性表的叙述中，错误的是
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
正确答案B
第5题在计算机内实现递归算法时所需的辅助数据结构是
A、栈
B、队列
C、树
D、图
正确答案A
第6题在目标串T［0..n1］=″xwxxyxy″中，对模式串P［0..m1］=″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、2k1–1
C、2k1
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+nt）
B、O（m+n+t）
C、O（mnt）
D、O（mt+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题已知一组关键字为{25483672798223401635}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A、.{25364872234079821635}
B、.{25364872162340798235}
C、.{25364872162335407982}
D、.{16232535364048727982}
正确答案
第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、与该顶点连通的顶点数
正确答案

奥鹏作业答案
奥鹏东北大学作业