电子科大16秋《数据结构》在线作业1

电子科技大学电子科大16秋《数据结构》在线作业1




一、单选题（共 16 道试题，共 48 分。）

1. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。
A. 15
B. 16
C. 17
D. 18
正确答案：
2. 下面程序段的时间复杂度为（ ）。 for (i=0; iA. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)
正确答案：
3. n个顶点的有向完全图中含有向边的数目最多为（ ）。
A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
正确答案：
4. 在数据结构中，数据的逻辑结构可以分成（ ）。
A. 内部结构和外部结构
B. 线性结构和非线性结构
C. 紧凑结构和非紧揍结构
D. 动态结构和静态结构
正确答案：
5. 逻辑上通常可以将数据结构分为（ ）。
A. 动态结构和静态结构
B. 顺序结构和链式结构
C. 线性结构和非线性结构
D. 初等结构和组合结构
正确答案：
6. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（ ）。
A. 0
B. 2
C. 3
D. 5
正确答案：
7. 已知函数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″
正确答案：
8. 在计算机内实现递归算法时所需的辅助数据结构是（ ）。
A. 栈
B. 队列
C. 树
D. 图
正确答案：
9. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（ ）。
A. n-i+1
B. n-i
C. i
D. i-1
正确答案：
10. 通常将链串的结点大小设置为大于1是为了（ ）。
A. 提高串匹配效率
B. 提高存储密度
C. 便于插入操作
D. 便于删除操作
正确答案：
11. 若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为（ ）。
A. O(㏒n)
B. O(n)
C. O(n㏒n)
D. O(㏒2n)
正确答案：
12. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。
A. 插入
B. 删除
C. 排序
D. 定位
正确答案：
13. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
A. q->next=s->next；s->next=p
B. s->next=p；q->next=s->next
C. p->next=s->next；s->next=q
D. s->next=q；p->next=s->next
正确答案：
14. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则（ ）。
A. p指向头结点
B. p指向尾结点
C. *p的直接后继是头结点
D. *P的直接后继是尾结点
正确答案：
15. 已知在一棵度为3的树中，度为2的

结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ ）。
A. 5
B. 8
C. 11
D. 18
正确答案：
16. 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ）。
A. 求一个顶点的邻接点
B. 求一个顶点的度
C. 深度优先遍历
D. 广度优先遍历
正确答案：



16秋《数据结构》在线作业1




二、多选题（共 2 道试题，共 8 分。）

1. 数据类型按其值能否分解,通常可分为（ ）和（ ）两种类型。
A. 抽象数据类型
B. 原子类型
C. 结构类型
D. 聚合类型
正确答案：
2. 构造最小生成树的两个基本算法是（ ）。
A. 普里姆算法
B. 克鲁斯卡尔算法
C. 迪杰斯特拉算法
D. 哈希算法
正确答案：



16秋《数据结构》在线作业1




三、判断题（共 22 道试题，共 44 分。）

1. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。
A. 错误
B. 正确
正确答案：
2. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。
A. 错误
B. 正确
正确答案：
3. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。
A. 错误
B. 正确
正确答案：
4. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。
A. 错误
B. 正确
正确答案：
5. 设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是”good book” 。
A. 错误
B. 正确
正确答案：
6. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p->next->next==null。
A. 错误
B. 正确
正确答案：
7. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。
A. 错误
B. 正确
正确答案：
8. 二叉树中必有度为2的结点。
A. 错误
B. 正确
正确答案：
9. 空格串的长度是空格的个数。
A. 错误
B. 正确
正确答案：
10. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。
A. 错误
B. 正确
正确答案：
11. 队列的修改是按照先进先出的原则进行的。
A. 错误
B. 正确
正确答案：
12. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。
A. 错误
B. 正确
正确答案：
13. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。
A. 错误
B. 正确
正确答案：
14. 一个具有4个顶点的无向完全图有6条边。
A. 错误
B. 正确
正确答案：
15. 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为15。
A. 错误
B. 正确
正确答案：
16. 删除二叉排序树中一个结点，再重新插入上去，一

定能得到原来的二叉排序树。
A. 错误
B. 正确
正确答案：
17. 在队列中，允许进行删除操作的一端称为队尾。
A. 错误
B. 正确
正确答案：
18. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。
A. 错误
B. 正确
正确答案：
19. 在含100个结点的完全二叉树中，叶子结点的个数为36。
A. 错误
B. 正确
正确答案：
20. 队列的修改是按先进先出的原则进行的。
A. 错误
B. 正确
正确答案：
21. 一棵含999个结点的完全二叉树的深度为6。
A. 错误
B. 正确
正确答案：
22. 字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串.
A. 错误
B. 正确
正确答案：