12秋电大《数据结构》在线作业3

《数据结构》在线作业3
试卷总分：100
单选题
多选题
判断题
一、单选题（共 16 道试题，共 48 分。）
V
1. 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ）。
A. 求一个顶点的邻接点
B. 求一个顶点的度
C. 深度优先遍历
D. 广度优先遍历
满分：3 分
2. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p- next- next= head,则（ ）。
A. p指向头结点
B. p指向尾结点
C. *p的直接后继是头结点
D. *P的直接后继是尾结点
此题选: D 满分：3 分
3. 已知函数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 分
4. 已知指针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
满分：3 分
5. 在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）。
A. Dout
B. Dout-1
C. Dout+1
D. n
满分：3 分
6. 采用两类不同存储结构的字符串可分别简称为（ ）。
A. 主串和子串
B. 顺序串和链串
C. 目标串和模式串
D. 变量串和常量串
满分：3 分
7. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（ ）。
A. 0
B. 2
C. 3
D. 5
满分：3 分
8. 栈和队列都是（ ）。
A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
此题选: D 满分：3 分
9. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）。
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
满分：3 分
10. 数据结构是（ ）。
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
此题选: D 满分：3 分
11. 高度为5的完全二叉树中含有的结点数至少为（ ）。
A. 16
B. 17
C. 31
D. 32
满分：3 分
12. 下面程序段的时间复杂度为（ ）。 for (i=0; i m; i++) for (j=0; j n; j++) A[j]=i*j;
A. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)
满分：3 分
13. 已知栈的最大容量为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 分
14. 已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。
A. 7
B. 8
C. 9
D. 10
满分：3 分
15. 若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ）。
A. 4
B. 5
C. 6#7
满分：3 分
16. 计算机识别、存储和加工处理的对象被统称为（ ）。
A. 数据
B. 数据元素
C. 数据结构
D. 数据类型
满分：3 分
《数据结构》在线作业3
试卷总分：100
单选题
多选题
判断题
二、多选题（共 2 道试题，共 8 分。）
V
1. 构造最小生成树的两个基本算法是（ ）。
A. 普里姆算法
B. 克鲁斯卡尔算法
C. 迪杰斯特拉算法
D. 哈希算法
满分：4 分
2. 假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（ ）。
A. 12345
B. 54321
C. 43215
D. 14325
满分：4 分
《数据结构》在线作业3
试卷总分：100
单选题
多选题
判断题
三、判断题（共 22 道试题，共 44 分。）
V
1. 一个具有4个顶点的无向完全图有6条边。
A. 错误
B. 正确
满分：2 分
2. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p- next- next==null。
A. 错误
B. 正确
满分：2 分
3. 在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。
A. 错误
B. 正确
满分：2 分
4. 一棵树可以只有1个结点。
A. 错误
B. 正确
满分：2 分
5. 不含任何字符的串称为空串。
A. 错误
B. 正确
满分：2 分
6. 设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是”good book” 。
A. 错误
B. 正确
满分：2 分
7. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。
A. 错误
B. 正确
满分：2 分
8. 二叉树中最多只有两棵子树，并且有左右之分。
A. 错误
B. 正确
满分：2 分
9. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。
A. 错误
B. 正确
满分：2 分
10. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。
A. 错误
B. 正确
满分：2 分
11. 两个空串联接得到的串的长度为0。
A. 错误
B. 正确
满分：2 分
12. 在有向图中，以顶点v为终点的边的数目称为v的入度。
A. 错误
B. 正确
满分：2 分
13. 空串的长度是0。
A. 错误
B. 正确
满分：2 分
14. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
A. 错误
B. 正确
满分：2 分
15. 深度为15的满二叉树上，第11层有2^11个结点。
A. 错误
B. 正确
满分：2 分
16. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。
A. 错误
B. 正确
满分：2 分
17. 在二叉树的第i层上至多可以有2i个结点。
A. 错误
B. 正确
满分：2 分
18. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。
A. 错误
B. 正确
满分：2 分
19. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，并且每个元素占2个存储单元，则A[4][3][2]的地址是1264。
A. 错误
B. 正确
满分：2 分
20. 若一棵满三叉树中含有121个结点，则该树的深度为6。
A. 错误
B. 正确
满分：2 分
21. 假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100，则元素A[9][8][7]的存储地址是501。
A. 错误
B. 正确
满分：2 分
22. 队列的修改是按照先进先出的原则进行的。
A. 错误
B. 正确
满分：2 分