《数据结构》3.从顺序表中删除一个元素时，表中所有在被...

奥鹏网院作业

电科17春《数据结构》在线作业3
一、单选题：
1.在线性表的下列运算中，不改变数据元素之间结构关系的运算是(    )。          (满分:3)
    A. 插入
    B. 删除
    C. 排序
    D. 定位
2.设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为(    )。          (满分:3)
    A. 15
    B. 16
    C. 17
    D. 18
3.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需(    )。          (满分:3)
    A. 前移一个位置
    B. 后移一个位置
    C. 不动
    D. 视情况而定
4.下面程序段的时间复杂度为(    )。for(i=0; i<m; i++)for(j=0; j<n; j++)A[i][j]=i*j;          (满分:3)
    A. O(m2)
    B. O(n2)
    C. O(m*n)
    D. O(m+n)
5.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则(    )。          (满分:3)
    A. p指向头结点
    B. p指向尾结点
    C. *p的直接后继是头结点
    D. *P的直接后继是尾结点
6.在数据结构中，数据的逻辑结构可以分成(    )。          (满分:3)
    A. 内部结构和外部结构
    B. 线性结构和非线性结构
    C. 紧凑结构和非紧揍结构
    D. 动态结构和静态结构
7.下面程序段的时间复杂度是(    )。for(i=0;i<n;i++)   for(j=1;j<m;j++)     A[i][j]=0；          (满分:3)
    A. O(n)
    B. O(m+n+1)
    C. O(m+n)
    D. O(m*n)
8.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(    )。          (满分:3)
    A. 顺序表
    B. 用头指针表示的单循环链表
    C. 用尾指针表示的单循环链表
    D. 单链表
9.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为(    )。          (满分:3)
    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
10.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是(    )。          (满分:3)
    A. 10
    B. 11
    C. 12
    D. 不确定的
11.在计算机内实现递归算法时所需的辅助数据结构是(    )。          (满分:3)
    A. 栈
    B. 队列
    C. 树
    D. 图
12.判断两个串大小的基本准则是(    )。          (满分:3)
    A. 两个串长度的大小
    B. 两个串中首字符的大小
    C. 两个串中大写字母的多少
    D. 对应的第一个不等字符的大小
13.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(    )。          (满分:3)
    A. P=″SCIENCE″
    B. P=″STUDY″
    C. S=″SCIENCE″
    D. S=″STUDY″
14.栈是一种操作受限的线性结构，其操作的主要特征是(    )。          (满分:3)
    A. 先进先出
    B. 后进先出
    C. 进优于出
    D. 出优于进
15.若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为(    )。          (满分:3)
    A. O(㏒n)
    B. O(n)
    C. O(n㏒n)
    D. O(㏒2n)
16.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为(    )。          (满分:3)
    A. 3，2，6，1，4，5
    B. 3，4，2，1，6，5
    C. 1，2，5，3，4，6
    D. 5，6，4，2，3，1
二、多选题：
1.一个好的算法有(    )设计要求。          (满分:4)
    A. 正确性
    B. 可读性
    C. 健壮性
    D. 效率与低存储量要求
2.构造最小生成树的两个基本算法是(    )。          (满分:4)
    A. 普里姆算法
    B. 克鲁斯卡尔算法
    C. 迪杰斯特拉算法
    D. 哈希算法
三、判断题：
1.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。          (满分:2)
    A. 错误
    B. 正确
2.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是基数排序。          (满分:2)
    A. 错误
    B. 正确
3.在有向图中，以顶点v为终点的边的数目称为v的入度。          (满分:2)
    A. 错误
    B. 正确
4.深度为k的二叉树至多有2k-1个结点。          (满分:2)
    A. 错误
    B. 正确
5.设S1="good",S2="  ",S3="book"，则S1，S2和S3依次联接后的结果是”good book” 。          (满分:2)
    A. 错误
    B. 正确
6.二叉树是度为2的有序树。          (满分:2)
    A. 错误
    B. 正确
7.队列的队尾位置通常是随着入队操作而变化的。          (满分:2)
    A. 错误
    B. 正确
8.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。          (满分:2)
    A. 错误
    B. 正确
9.串S=”I am a worker″的长度是10。          (满分:2)
    A. 错误
    B. 正确
10.不含任何字符的串称为空串。          (满分:2)
    A. 错误
    B. 正确
11.栈下溢是指在栈空时进行出栈操作          (满分:2)
    A. 错误
    B. 正确
12.在二叉树的第i层上至多可以有2i个结点。          (满分:2)
    A. 错误
    B. 正确
13.二叉树中的叶子结点就是二叉树中没有左右子树的结点。          (满分:2)
    A. 错误
    B. 正确
14.已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。          (满分:2)
    A. 错误
    B. 正确
15.一棵树可以只有1个结点。          (满分:2)
    A. 错误
    B. 正确
16.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 a b b c c d d e d c 。          (满分:2)
    A. 错误
    B. 正确
17.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。          (满分:2)
    A. 错误
    B. 正确
18.结点数为20的二叉树可能的最大高度为4。          (满分:2)
    A. 错误
    B. 正确
19.字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串.          (满分:2)
    A. 错误
    B. 正确
20.一个具有4个顶点的无向完全图有6条边。          (满分:2)
    A. 错误
    B. 正确
21.在对链队列作出队操作时，不会改变front指针的值。          (满分:2)
    A. 错误
    B. 正确
22.空格串的长度是空格的个数。          (满分:2)
    A. 错误
    B. 正确