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

《数据结构》在线作业2
试卷总分：100
单选题
多选题
判断题
一、单选题（共 16 道试题，共 48 分。）
V
1. 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ）。
A. 求一个顶点的邻接点
B. 求一个顶点的度
C. 深度优先遍历
D. 广度优先遍历
满分：3 分
2. 在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）。
A. Dout
B. Dout-1
C. Dout+1
D. n
满分：3 分
3. 与线性表相比，串的插入和删除操作的特点是（ ）。
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C. 算法的时间复杂度较高
D. 涉及移动的元素更多
满分：3 分
4. 无向图中一个顶点的度是指图中（ ）。
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：3 分
5. 已知指针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 分
6. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）。
A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
满分：3 分
7. 采用两类不同存储结构的字符串可分别简称为（ ）。
A. 主串和子串
B. 顺序串和链串
C. 目标串和模式串
D. 变量串和常量串
满分：3 分
8. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ ）。
A. 5
B. 8
C. 11
D. 18
满分：3 分
9. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）。
A. O(1)
B. O(n)
C. O(nn)
D. O(n2)
满分：3 分
10. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（ ）。
A. n-i+1
B. n-i
C. i
D. i-1
满分：3 分
11. 逻辑上通常可以将数据结构分为（ ）。
A. 动态结构和静态结构
B. 顺序结构和链式结构
C. 线性结构和非线性结构
D. 初等结构和组合结构
满分：3 分
12. 数据结构是（ ）。
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
此题选: D 满分：3 分
13. 算法分析的目的是（ ）。
A. 辨别数据结构的合理性
B. 评价算法的效率
C. 研究算法中输入与输出的关系
D. 鉴别算法的可读性
满分：3 分
14. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）。
A. p=p- next
B. p- next=p- next- next
C. p- next=p
D. p=p- next- next;
满分：3 分
15. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（ ）。
A. p- next==head
B. p- next- next==head
C. p- next==NULL
D. p==head
满分：3 分
16. 已知栈的最大容量为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 分
《数据结构》在线作业2
试卷总分：100
单选题
多选题
判断题
二、多选题（共 2 道试题，共 8 分。）
V
1. 假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（ ）。
A. 12345
B. 54321
C. 43215
D. 14325
满分：4 分
2. 一个好的算法有（ ）设计要求。
A. 正确性
B. 可读性
C. 健壮性
D. 效率与低存储量要求
满分：4 分
《数据结构》在线作业2
试卷总分：100
单选题
多选题
判断题
三、判断题（共 22 道试题，共 44 分。）
V
1. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。
A. 错误
B. 正确
满分：2 分
2. 抽象数据类型是指数据逻辑结构及与之相关的操作。
A. 错误
B. 正确
满分：2 分
3. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 a b b c c d d e d c 。
A. 错误
B. 正确
满分：2 分
4. 栈下溢是指在栈空时进行出栈操作
A. 错误
B. 正确
满分：2 分
5. 若一棵满三叉树中含有121个结点，则该树的深度为6。
A. 错误
B. 正确
满分：2 分
6. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。
A. 错误
B. 正确
满分：2 分
7. 在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。
A. 错误
B. 正确
满分：2 分
8. 设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是”good book” 。
A. 错误
B. 正确
满分：2 分
9. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序。
A. 错误
B. 正确
满分：2 分
10. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
A. 错误
B. 正确
满分：2 分
11. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是1264。
A. 错误
B. 正确
满分：2 分
12. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。
A. 错误
B. 正确
满分：2 分
13. 假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是501。
A. 错误
B. 正确
满分：2 分
14. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。
A. 错误
B. 正确
满分：2 分
15. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。
A. 错误
B. 正确
满分：2 分
16. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。
A. 错误
B. 正确
满分：2 分
17. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。
A. 错误
B. 正确
满分：2 分
18. 一棵含999个结点的完全二叉树的深度为6。
A. 错误
B. 正确
满分：2 分
19. 一棵树可以只有1个结点。
A. 错误
B. 正确
满分：2 分
20. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。
A. 错误
B. 正确
满分：2 分
21. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
A. 错误
B. 正确
满分：2 分
22. 一棵含999个结点的完全二叉树的深度为12。
A. 错误
B. 正确
满分：2 分