东大19秋学期《数据结构Ⅱ》在线平时作业2

admin

【奥鹏】[东北大学]19秋学期《数据结构Ⅱ》在线平时作业2
试卷总分:100    得分:100
第1题,数据的四种基本存储结构是指
A、顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B、顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C、顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D、顺序存储结构、链式存储结构、树型存储结构、图型存储结构
正确答案:


第2题,若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
A、2，4，3，1，5，6
B、3，2，4，1，6，5
C、4，3，2，1，5，6
D、2，3，5，1，6，4
正确答案:


第3题,有关二叉树下列说法正确的是
A、二叉树的度为2
B、一棵二叉树的度可以小于2
C、二叉树中至少有一个结点的度为2
D、二叉树中任何一个结点的度都为2
正确答案:


第4题,算法分析的目的是
A、辨别数据结构的合理性
B、评价算法的效率
C、研究算法中输入与输出的关系
D、鉴别算法的可读性
正确答案:


第5题,若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A、X的双亲
B、X的右子树中最左的结点
C、X的左子树中最右结点
D、X的左子树中最右叶结点
正确答案:


第6题,在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A、s-next=p-next;p-next=s;
B、s-next=p; q-next=s
C、q-next=s;s-next=p;
D、p-next=s;s-next=q;
正确答案:


第7题,已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为
A、0
B、1
C、48
D、49
正确答案:


第8题,若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A、f,c,b
B、f,d,b
C、g,c,b
D、g,d,b
正确答案:


第9题,对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A、O(1)
B、O(logn)
C、O(n)
D、O(n logn)
正确答案:


第10题,若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是
A、1234
B、4132
C、4231
D、4213
正确答案:


第11题,树的先根序列等同于与该树对应的二叉树的
A、先序序列
B、中序序列
C、后序序列
D、层序序列
正确答案:


第12题,若vi, vj是有向图的一条边，则称
A、vi邻接于vj
B、vj邻接于vi
C、vi和vj相互邻接
D、vi与vj-不相邻接
正确答案:


第13题,已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A、5
B、6
C、16
D、17
正确答案:


第14题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
正确答案:


第15题,导致栈上溢的操作是
A、栈满时执行的出栈
B、栈满时执行的入栈
C、栈空时执行的出栈
D、栈空时执行的入栈
正确答案:


第16题,在下列存储形式中，哪一个不是树的存储形式
A、双亲表示法
B、孩子链表表示法
C、孩子兄弟表示法
D、顺序存储表示法
正确答案:


第17题,文件中，主关键字能唯一标识
A、一个记录
B、一组记录
C、一个类型
D、一个文件
正确答案:


第18题,下面的说法中正确的是    (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。    (2)按二叉树定义，具有三个节点的二叉树共有6种。
A、(1)，(2)
B、(1)
C、(2)
D、(1)，(2)都错
正确答案:


第19题,设给定权值总数有n 个，其哈夫曼树的结点总数为
A、不确定
B、2n
C、2n+1
D、2n-1
正确答案:


第20题,已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t  到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到
A、P=″SCIENCE″
B、P=″STUDY″
C、S=″SCIENCE″
D、S=″STUDY″
正确答案: