电子科大11春学期《数据结构》在线作业二

久爱奥鹏晓林

一、单选题（共 16 道试题，共 48 分。）V 1.  已知函数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″
      满分：3  分
2.  下面程序段的时间复杂度为（ ）。 for (i=0; i<m; i++) for (j=0; j<n; j++) A[i][j]=i*j;
A. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)
      满分：3  分
3.  在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则（ ）。
A. p指向头结点
B. p指向尾结点
C. *p的直接后继是头结点
D. *P的直接后继是尾结点
      满分：3  分
4.  已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）。
A. 5，4，3，2，1，6
B. 2，3，5，6，1，4
C. 3，2，5，4，1，6
D. 1，4，6，5，2，3
      满分：3  分
5.  在计算机内实现递归算法时所需的辅助数据结构是（ ）。
A. 栈
B. 队列
C. 树
D. 图
      满分：3  分
6.  设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。
A. 15
B. 16
C. 17
D. 18
      满分：3  分
7.  若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ）。
A. 4
B. 5
C. 6#7
      满分：3  分
8.  若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为（ ）。
A. O(㏒n)
B. O(n)
C. O(n㏒n)
D. O(㏒2n)
      满分：3  分
9.  数据结构是（ ）。
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
      满分：3  分
10.  栈和队列都是（ ）。
A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
      满分：3  分
11.  在数据结构中，数据的逻辑结构可以分成（ ）。
A. 内部结构和外部结构
B. 线性结构和非线性结构
C. 紧凑结构和非紧揍结构
D. 动态结构和静态结构
      满分：3  分
12.  在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（ ）。
A. p->next==head
B. p->next->next==head
C. p->next==NULL
D. p==head
      满分：3  分
13.  无向图中一个顶点的度是指图中（ ）。
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
      满分：3  分
14.  在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）。
A. Dout
B. Dout-1
C. Dout+1
D. n
      满分：3  分
15.  抽象数据类型的三个组成部分分别为（ ）。
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
      满分：3  分
16.  二叉树中第5层上的结点个数最多为（ ）。
A. 8
B. 15
C. 16
D. 32
      满分：3  分

二、多选题（共 2 道试题，共 8 分。）V 1.  假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（ ）。
A. 12345
B. 54321
C. 43215
D. 14325
      满分：4  分
2.  数据类型按其值能否分解,通常可分为（ ）和（ ）两种类型。
A. 抽象数据类型
B. 原子类型
C. 结构类型
D. 聚合类型
      满分：4  分

三、判断题（共 22 道试题，共 44 分。）V 1.  结点数为20的二叉树可能的最大高度为4。
A. 错误
B. 正确
      满分：2  分
2.  假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是1264。
A. 错误
B. 正确
      满分：2  分
3.  深度为15的满二叉树上，第11层有2^11个结点。
A. 错误
B. 正确
      满分：2  分
4.  深度为k的二叉树至多有2k-1个结点。
A. 错误
B. 正确
      满分：2  分
5.  二叉树是度为2的有序树。
A. 错误
B. 正确
      满分：2  分
6.  抽象数据类型是指数据逻辑结构及与之相关的操作。
A. 错误
B. 正确
      满分：2  分
7.  队列的队尾位置通常是随着入队操作而变化的。
A. 错误
B. 正确
      满分：2  分
8.  在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。
A. 错误
B. 正确
      满分：2  分
9.  如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。
A. 错误
B. 正确
      满分：2  分
10.  队列的000是按先进先出的原则进行的。
A. 错误
B. 正确
      满分：2  分
11.  当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。
A. 错误
B. 正确
      满分：2  分
12.  由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。
A. 错误
B. 正确
      满分：2  分
13.  空串的长度是0。
A. 错误
B. 正确
      满分：2  分
14.  给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
A. 错误
B. 正确
      满分：2  分
15.  在对链队列作出队操作时，不会改变front指针的值。
A. 错误
B. 正确
      满分：2  分
16.  串S=”I am a worker″的长度是10。
A. 错误
B. 正确
      满分：2  分
17.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。
A. 错误
B. 正确
      满分：2  分
18.  字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串.
A. 错误
B. 正确
      满分：2  分
19.  二叉树中结点只有一个孩子时无左右之分。
A. 错误
B. 正确
      满分：2  分
20.  假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100，则元素A[9][8][7]的存储地址是501。
A. 错误
B. 正确
      满分：2  分
21.  含n个顶点的无向连通图中至少含有n条边。
A. 错误
B. 正确
      满分：2  分
22.  一个具有4个顶点的无向完全图有6条边。
A. 错误
B. 正确
      满分：2  分