四川大学《数据结构2264》13春在线作业2

川大《数据结构2264》13春在线作业2
试卷总分：100
单选题
多选题
判断题
一、单选题（共 25 道试题，共 50 分。）
V
1. 设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
满分：2 分
2. 如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。
A. 直接插入排序
B. 快速排序
C. 归并排序
D. 选择排序
满分：2 分
3. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）
A. 都不相同
B. 完全相同
C. 先序和中序相同，而与后序不同
D. 中序和后序相同，而与先序不同
满分：2 分
4. 由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。
A. 11
B. 35
C. 19
D. 53
满分：2 分
5. 对线性表，在下列哪种情况下应当采用链表表示？（ ）
A. 经常需要随机地存取元素
B. 经常需要进行插入和删除操作
C. 表中元素需要占据一片连续的存储空间
D. 表中元素的个数不变
满分：2 分
6. 对广义表L=（ ）,（ ）,（ ）执行操作tail（ ）的结果是（ ）。
A. (e,f)
B. ((e,f))
C. (f)
D. ( )
满分：2 分
7. 设有一个二维数组A[m][n] （ ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（ ）。
A. 658
B. 648
C. 633
D. 653
满分：2 分
8. 含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。
A. 3
B. 4
C. 5
D. 6
满分：2 分
9. 以下数据结构中哪一个是非线性结构？（ ）
A. 队列
B. 栈
C. 线性表
D. 二叉树
此题选: D 满分：2 分
10. 对于线性表（ ）进行散列存储时，若选用H（ ）=K % 9作为散列函数，则散列地址为1的元素有（ ）个。
A. 1
B. 2
C. 3
D. 4
此题选: D 满分：2 分
11. 下面关于图的存储的叙述中正确的是（ ）。
A. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
满分：2 分
12. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
此题选: D 满分：2 分
13. 对一个算法的评价，不包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
满分：2 分
14. 在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。
A. i
B. i+1
C. n-i
D. n-i+1
满分：2 分
15. 假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
A. K-1次
B. K次
C. K＋l次
D. K(K+1)/2次
此题选: D 满分：2 分
16. 对于关键字序列（ ）进行散列存储时，若选用H（ ）=K%7作为散列函数，则散列地址为0的元素有（ ）个。
A. 1
B. 2
C. 3
D. 4
此题选: D 满分：2 分
17. 带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（ ）。
A. head= =NUL
B. head- next= =NULL
C. head!=NULL
D. head- next= =head
此题选: D 满分：2 分
18. 从L=（ ）,（ ）)中，取出banana元素的表达式为（ ）。
A. head(tail(L))
B. head(head(tail(L)))
C. tail(head(tail(L)))
D. head(tail(head(tail(L))))
此题选: D 满分：2 分
19. 队列的特点是（ ）。
A. 先进后出
B. 先进先出
C. 任意位置进出
D. 前面都不正确
满分：2 分
20. 对n个记录进行堆排序，所需要的辅助存储空间为（ ）。
A. O（1og2n
B. O（n）
C. O（1）
D. O（n2）
满分：2 分
21. 若某二叉树结点的中序遍历的序列为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 分
22. 采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
A. 低于链接法处理冲突
B. 高于链接法处理冲突
C. 与链接法处理冲突相同
D. 高于二分查找
满分：2 分
23. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，则A[3][3]存放位置在（ ）。
A. 688
B. 678
C. 692
D. 696
满分：2 分
24. 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
A. HL=p; p- next=HL;
B. p- next=HL- next; HL- next=p;
C. p- next=HL; p=HL;
D. p- next=HL; HL=p;
满分：2 分
25. 中缀表达式2+X*（ ）的后缀形式是（ ）。
A. 3 Y X 2 + * +
B. Y 3 + X * 2 +
C. 2 X Y 3 * + +
D. 2 X Y 3 + * +
此题选: D 满分：2 分
川大《数据结构2264》13春在线作业2
试卷总分：100
单选题
多选题
判断题
二、多选题（共 4 道试题，共 20 分。）
V
1. 若进栈序列为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 分
2. 以下序列中，是堆（ ）的有（ ）。
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}
满分：5 分
3. 对一个算法的评价，主要包括如下（ ）方面的内容。
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
E. 界面友好性
满分：5 分
4. 下述（ ）是顺序存储方式的优点。
A. 存储密度大
B. 插入和删除运算方便
C. 获取符合某种条件的元素方便
D. 查找运算速度快
E. 可以很方便地存取第i个元素
满分：5 分
川大《数据结构2264》13春在线作业2
试卷总分：100
单选题
多选题
判断题
三、判断题（共 15 道试题，共 30 分。）
V
1. 顺序表用一维数组作为存储结构，因此顺序表是一维数组。
A. 错误
B. 正确
满分：2 分
2. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
A. 错误
B. 正确
满分：2 分
3. 二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
A. 错误
B. 正确
满分：2 分
4. 一个广义表的表头总是一个广义表。
A. 错误
B. 正确
满分：2 分
5. 线性表若采用链式存储表示, 在删除时不需要移动元素。
A. 错误
B. 正确
满分：2 分
6. 若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。
A. 错误
B. 正确
满分：2 分
7. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
A. 错误
B. 正确
满分：2 分
8. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A. 错误
B. 正确
满分：2 分
9. 图G的某一最小生成树的代价一定小于其他生成树的代价。
A. 错误
B. 正确
满分：2 分
10. 为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
A. 错误
B. 正确
满分：2 分
11. 一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
A. 错误
B. 正确
满分：2 分
12. 有回路的有向图不能完成拓扑排序。
A. 错误
B. 正确
满分：2 分
13. 存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（ ）三角部分。
A. 错误
B. 正确
满分：2 分
14. 对任何用顶点表示活动的网络（ ）进行拓扑排序的结果都是唯一的。
A. 错误
B. 正确
满分：2 分
15. 进行折半搜索的表必须是顺序存储的有序表。
A. 错误
B. 正确
满分：2 分