《数据结构》第2次作业
试卷总分：100
单选题
多选题
判断题
一、单选题（共 25 道试题，共 50 分。）
V
1. 若有序表为（ ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。
A. f,c,b
B. f,d,b
C. g,c,b
D. g,d,b
满分：2 分
2. 若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。
A. 图中每个顶点的入度
B. 图中每个顶点的出度
C. 图中每个顶点的度
D. 图中连通分量的数目
满分：2 分
3. 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。
A. m-n-1
B. n+1
C. m-n+1
D. m-n
此题选: D 满分：2 分
4. 在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。
A. 插入
B. 删除
C. 排序
D. 查找
此题选: D 满分：2 分
5. 对关键字序列（ ）进行增量为3的一趟希尔排序的结果为（ ）。
A. (19, 23, 56, 34, 78, 67, 88, 92)
B. (23, 56, 78, 66, 88, 92, 19, 34)
C. (19, 23, 34, 56, 67, 78, 88, 92)
D. (19, 23, 67, 56, 34, 78, 92, 88)
此题选: D 满分：2 分
6. 已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（ ）3, （ ）5, （ ）8, （ ）10, （ ）6, （ ）15, （ ）12, （ ）9, （ ）4, （ ）20, （ ）18, （ ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（ ）。
A. (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
B. (1,2)3, (4,6)4, (1,3)5, (2,3)6, (1,4)8, (3,6)9
C. (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
D. (1,2)3, (1,3)5, (1,4)8, (2,5)10, (4,6)4, (4,7)20
满分：2 分
7. 设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
满分：2 分
8. 数据的基本单位是（ ）。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
满分：2 分
9. 对线性表进行二分法查找，其前提条件是（ ）。
A. 线性表以链接方式存储，并且按关键码值排好序
B. 线性表以顺序方式存储，并且按关键码值的检索频率排好序
C. 线性表以顺序方式存储，并且按关键码值排好序
D. 线性表以链接方式存储，并且按关键码值的检索频率排好序
满分：2 分
10. 二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ ）。
A. 1207
B. 1209
C. 1211
D. 1213
满分：2 分
11. 对一个算法的评价，不包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
满分：2 分
12. 下列关于数据结构的叙述中，正确的是（ ）。
A. 数组是不同类型值的集合
B. 递归算法的程序结构比迭代算法的程序结构更为精炼
C. 树是一种线性结构
D. 用一维数组存储一棵完全二叉树是有效的存储方法
此题选: D 满分：2 分
13. 含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。
A. 3
B. 4
C. 5
D. 6
满分：2 分
14. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 1
B. 3 2 1
C. 3 1 2
D. 1 2 3
满分：2 分
15. 若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。则该二叉树结点的前序遍历的序列为（ ）。
A. E、G、F、A、C、D、B
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
满分：2 分
16. 从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
满分：2 分
17. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（ ）。
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
此题选: D 满分：2 分
18. 从一个长度为n的顺序表中删除第i个元素（ ）时，需向前移动的元素个数是（ ）。
A. n-i
B. n-i+1
C. n-i-1
D. i
满分：2 分
19. 设Huffman树的叶子结点数为m，则结点总数为（ ）。
A. 2m
B. 2m-1
C. 2m+1
D. m+1
满分：2 分
20. k层（ ）二叉树的结点总数最多为（ ）。
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1
满分：2 分
21. 在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（ ）语句序列。
A. p=q; p- next=q;
B. p- next=q; q- next=p;
C. p- next=q- next; p=q;
D. q- next=p- next; p- next=q;
此题选: D 满分：2 分
22. 在数据结构中，数据元素可由（ ）。
A. 实体
B. 域
C. 数据项
D. 字段
满分：2 分
23. 设有一个二维数组A[m][n] （ ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（ ）。
A. 658
B. 648
C. 633
D. 653
满分：2 分
24. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，则A[3][3]存放位置在（ ）。
A. 688
B. 678
C. 692
D. 696
满分：2 分
25. 以下数据结构中哪一个是非线性结构？（ ）
A. 队列
B. 栈
C. 线性表
D. 二叉树
此题选: D 满分：2 分
《数据结构》第2次作业
试卷总分：100
单选题
多选题
判断题
二、多选题（共 4 道试题，共 20 分。）
V
1. 以下数据结构中哪一个是线性结构？（ ）
A. 有向图
B. 队列
C. 线索二叉树
D. 线性表
E. 栈
满分：5 分
2. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（ ）。
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
E. 6，5，4，3，2，1
满分：5 分
3. 栈和队列的共同特点是（ ）。
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
E. 都可以采用顺序存储方式和链式存储方式
满分：5 分
4. 对一个算法的评价，主要包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
E. 界面友好性
满分：5 分
《数据结构》第2次作业
试卷总分：100
单选题
多选题
判断题
三、判断题（共 15 道试题，共 30 分。）
V
1. 已知指针P指向链表L中的某结点，执行语句P：=P®NEXT不会删除该链表中的结点。
A. 错误
B. 正确
满分：2 分
2. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A. 错误
B. 正确
满分：2 分
3. 一个广义表的表头总是一个广义表。
A. 错误
B. 正确
满分：2 分
4. 若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。
A. 错误
B. 正确
满分：2 分
5. 图G的某一最小生成树的代价一定小于其他生成树的代价。
A. 错误
B. 正确
满分：2 分
6. 线性表的长度是线性表所占用的存储空间的大小。
A. 错误
B. 正确
满分：2 分
7. 有回路的有向图不能完成拓扑排序。
A. 错误
B. 正确
满分：2 分
8. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A. 错误
B. 正确
满分：2 分
9. 一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
A. 错误
B. 正确
满分：2 分
10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
A. 错误
B. 正确
满分：2 分
11. 在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。
A. 错误
B. 正确
满分：2 分
12. 线性表若采用链式存储表示, 在删除时不需要移动元素。
A. 错误
B. 正确
满分：2 分
13. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
A. 错误
B. 正确
满分：2 分
14. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
A. 错误
B. 正确
满分：2 分
15. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A. 错误
B. 正确
满分：2 分
试卷总分：100
单选题
多选题
判断题
一、单选题（共 25 道试题，共 50 分。）
V
1. 若有序表为（ ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。
A. f,c,b
B. f,d,b
C. g,c,b
D. g,d,b
满分：2 分
2. 若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。
A. 图中每个顶点的入度
B. 图中每个顶点的出度
C. 图中每个顶点的度
D. 图中连通分量的数目
满分：2 分
3. 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。
A. m-n-1
B. n+1
C. m-n+1
D. m-n
此题选: D 满分：2 分
4. 在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。
A. 插入
B. 删除
C. 排序
D. 查找
此题选: D 满分：2 分
5. 对关键字序列（ ）进行增量为3的一趟希尔排序的结果为（ ）。
A. (19, 23, 56, 34, 78, 67, 88, 92)
B. (23, 56, 78, 66, 88, 92, 19, 34)
C. (19, 23, 34, 56, 67, 78, 88, 92)
D. (19, 23, 67, 56, 34, 78, 92, 88)
此题选: D 满分：2 分
6. 已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（ ）3, （ ）5, （ ）8, （ ）10, （ ）6, （ ）15, （ ）12, （ ）9, （ ）4, （ ）20, （ ）18, （ ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（ ）。
A. (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
B. (1,2)3, (4,6)4, (1,3)5, (2,3)6, (1,4)8, (3,6)9
C. (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
D. (1,2)3, (1,3)5, (1,4)8, (2,5)10, (4,6)4, (4,7)20
满分：2 分
7. 设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
满分：2 分
8. 数据的基本单位是（ ）。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
满分：2 分
9. 对线性表进行二分法查找，其前提条件是（ ）。
A. 线性表以链接方式存储，并且按关键码值排好序
B. 线性表以顺序方式存储，并且按关键码值的检索频率排好序
C. 线性表以顺序方式存储，并且按关键码值排好序
D. 线性表以链接方式存储，并且按关键码值的检索频率排好序
满分：2 分
10. 二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ ）。
A. 1207
B. 1209
C. 1211
D. 1213
满分：2 分
11. 对一个算法的评价，不包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
满分：2 分
12. 下列关于数据结构的叙述中，正确的是（ ）。
A. 数组是不同类型值的集合
B. 递归算法的程序结构比迭代算法的程序结构更为精炼
C. 树是一种线性结构
D. 用一维数组存储一棵完全二叉树是有效的存储方法
此题选: D 满分：2 分
13. 含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。
A. 3
B. 4
C. 5
D. 6
满分：2 分
14. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 1
B. 3 2 1
C. 3 1 2
D. 1 2 3
满分：2 分
15. 若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。则该二叉树结点的前序遍历的序列为（ ）。
A. E、G、F、A、C、D、B
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
满分：2 分
16. 从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
满分：2 分
17. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（ ）。
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
此题选: D 满分：2 分
18. 从一个长度为n的顺序表中删除第i个元素（ ）时，需向前移动的元素个数是（ ）。
A. n-i
B. n-i+1
C. n-i-1
D. i
满分：2 分
19. 设Huffman树的叶子结点数为m，则结点总数为（ ）。
A. 2m
B. 2m-1
C. 2m+1
D. m+1
满分：2 分
20. k层（ ）二叉树的结点总数最多为（ ）。
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1
满分：2 分
21. 在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（ ）语句序列。
A. p=q; p- next=q;
B. p- next=q; q- next=p;
C. p- next=q- next; p=q;
D. q- next=p- next; p- next=q;
此题选: D 满分：2 分
22. 在数据结构中，数据元素可由（ ）。
A. 实体
B. 域
C. 数据项
D. 字段
满分：2 分
23. 设有一个二维数组A[m][n] （ ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（ ）。
A. 658
B. 648
C. 633
D. 653
满分：2 分
24. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，则A[3][3]存放位置在（ ）。
A. 688
B. 678
C. 692
D. 696
满分：2 分
25. 以下数据结构中哪一个是非线性结构？（ ）
A. 队列
B. 栈
C. 线性表
D. 二叉树
此题选: D 满分：2 分
《数据结构》第2次作业
试卷总分：100
单选题
多选题
判断题
二、多选题（共 4 道试题，共 20 分。）
V
1. 以下数据结构中哪一个是线性结构？（ ）
A. 有向图
B. 队列
C. 线索二叉树
D. 线性表
E. 栈
满分：5 分
2. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（ ）。
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
E. 6，5，4，3，2，1
满分：5 分
3. 栈和队列的共同特点是（ ）。
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
E. 都可以采用顺序存储方式和链式存储方式
满分：5 分
4. 对一个算法的评价，主要包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
E. 界面友好性
满分：5 分
《数据结构》第2次作业
试卷总分：100
单选题
多选题
判断题
三、判断题（共 15 道试题，共 30 分。）
V
1. 已知指针P指向链表L中的某结点，执行语句P：=P®NEXT不会删除该链表中的结点。
A. 错误
B. 正确
满分：2 分
2. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A. 错误
B. 正确
满分：2 分
3. 一个广义表的表头总是一个广义表。
A. 错误
B. 正确
满分：2 分
4. 若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。
A. 错误
B. 正确
满分：2 分
5. 图G的某一最小生成树的代价一定小于其他生成树的代价。
A. 错误
B. 正确
满分：2 分
6. 线性表的长度是线性表所占用的存储空间的大小。
A. 错误
B. 正确
满分：2 分
7. 有回路的有向图不能完成拓扑排序。
A. 错误
B. 正确
满分：2 分
8. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A. 错误
B. 正确
满分：2 分
9. 一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
A. 错误
B. 正确
满分：2 分
10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
A. 错误
B. 正确
满分：2 分
11. 在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。
A. 错误
B. 正确
满分：2 分
12. 线性表若采用链式存储表示, 在删除时不需要移动元素。
A. 错误
B. 正确
满分：2 分
13. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
A. 错误
B. 正确
满分：2 分
14. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
A. 错误
B. 正确
满分：2 分
15. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A. 错误
B. 正确
满分：2 分
版权声明
声明：有的资源均来自网络转载，版权归原作者所有，如有侵犯到您的权益
请联系本站我们将配合处理！