四川大学《数据结构2264》17春在线作业1 2辅导资料

奥鹏在线作业

一、单选题（共 25 道试题，共 50 分。）  V 1.  在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。
A. 插入
B. 删除
C. 排序
D. 查找

2.  中缀表达式2+X*（ ）的后缀形式是（ ）。
A. 3 Y X 2 + * +
B. Y 3 + X * 2 +
C. 2 X Y 3 * + +
D. 2 X Y 3 + * +

3.  若某二叉树结点的中序遍历的序列为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

4.  以下数据结构中哪一个是非线性结构？（ ）
A. 队列
B. 栈
C. 线性表
D. 二叉树

5.  数据的基本单位是（ ）。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量

6.  设Huffman树的叶子结点数为m，则结点总数为（ ）。
A. 2m
B. 2m-1
C. 2m+1
D. m+1

7.  一散列表长度m为100，采用除留余数法构造散列函数，即H（ ）=K%P （ ）,，为使散列函数具有较好的性能，P的选择应是（ ）。
A. 99
B. 100
C. 97
D. 93

8.  在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）
A. 都不相同
B. 完全相同
C. 先序和中序相同，而与后序不同
D. 中序和后序相同，而与先序不同

9.  设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8

10.  由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。
A. 11
B. 35
C. 19
D. 53

11.  假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
A. K-1次
B. K次
C. K＋l次
D. K(K+1)/2次

12.  已知一个图的顶点集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

13.  设有一个二维数组A[m][n] （ ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（ ）。
A. 658
B. 648
C. 633
D. 653

14.  采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
A. 低于链接法处理冲突
B. 高于链接法处理冲突
C. 与链接法处理冲突相同
D. 高于二分查找

15.  下面关于广义表的叙述中，不正确的是（ ）。
A. 广义表可以是一个多层次的结构
B. 广义表至少有一个元素
C. 广义表可以被其他广义表所共享
D. 广义表可以是一个递归表

16.  下面关于图的存储的叙述中正确的是（ ）。
A. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

17.  对关键字序列（ ）进行增量为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)

18.  k层（ ）二叉树的结点总数最多为（ ）。
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1

19.  下列关于数据结构的叙述中，正确的是（ ）。
A. 数组是不同类型值的集合
B. 递归算法的程序结构比迭代算法的程序结构更为精炼
C. 树是一种线性结构
D. 用一维数组存储一棵完全二叉树是有效的存储方法

20.  若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。
A. 图中每个顶点的入度
B. 图中每个顶点的出度
C. 图中每个顶点的度
D. 图中连通分量的数目

21.  对一个算法的评价，不包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度

22.  一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 1
B. 3 2 1
C. 3 1 2
D. 1 2 3

23.  在数据结构中，数据元素可由（ ）。
A. 实体
B. 域
C. 数据项
D. 字段

24.  对n个记录进行堆排序，所需要的辅助存储空间为（ ）。
A. O（1og2n
B. O（n）
C. O（1）
D. O（n2）

25.  若有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



二、多选题（共 4 道试题，共 20 分。）  V 1.  以下序列中，是堆（ ）的有（ ）。
A. {15,26,38,49,27,51,39,62}
B. {15,23,71,94,72,68,26,73}
C. {15,27,26,49,38,62,39,51}
D. {15,23,26,68,94,72,71,73}
E. {94,72,73,26,71,23,68,15}
CDE
2.  下述（ ）是顺序存储方式的优点。
A. 存储密度大
B. 插入和删除运算方便
C. 获取符合某种条件的元素方便
D. 查找运算速度快
E. 可以很方便地存取第i个元素
E
3.  若进栈序列为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
CD
4.  以下数据结构中哪一个是线性结构？（ ）
A. 有向图
B. 队列
C. 线索二叉树
D. 线性表
E. 栈
DE


三、判断题（共 15 道试题，共 30 分。）  V 1.  邻接矩阵适用于稠密图（ ），邻接表适用于稀疏图（ ）。
A. 错误
B. 正确

2.  快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。
A. 错误
B. 正确

3.  一个广义表的表头总是一个广义表。
A. 错误
B. 正确

4.  若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。
A. 错误
B. 正确

5.  用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
A. 错误
B. 正确

6.  一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
A. 错误
B. 正确

7.  图G的某一最小生成树的代价一定小于其他生成树的代价。
A. 错误
B. 正确

8.  数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
A. 错误
B. 正确

9.  进行折半搜索的表必须是顺序存储的有序表。
A. 错误
B. 正确

10.  存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（ ）三角部分。
A. 错误
B. 正确

11.  在线性链表中删除某个结点时，只需将被删结点释放。
A. 错误
B. 正确

12.  链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A. 错误
B. 正确

13.  线性表若采用链式存储表示, 在删除时不需要移动元素。
A. 错误
B. 正确

14.  在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。
A. 错误
B. 正确

15.  邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
A. 错误
B. 正确
















                                  谋学网www.mouxue.com