重庆大学网院数据结构数据结构第2次作业答案
重庆大学网院数据结构数据结构第2次作业答案一、单项选择题（本大题共60分，共 20 小题，每小题 3 分）
1. 按克鲁斯卡尔算法建的最小生成树（ ）。
A. 只有一种
B. 有多种
C. 不确定
2. 以下关于单链表的叙述中，错误的是（ ）。
A. 在单链表中插入一个结点必须先找到其前驱结点
B. 在单链表中删除一个结点必须先找到其前驱结点
C. 在单链表中只能通过结点的next指针向后查找结点
D. 在单链表中查找第i个结点的时间复杂度是O(1)
3. 输入序列为ABC，可以变为CBA时，经过的栈操作为（）。
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
4. 如图所示，可得到一个拓扑排序序列（）。
file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg
A. v1,v6,v4,v3,v2,v5
B. v1,v2,v6,v4,v3,v5
C. v1,v2,v6,v3,v4,v5
D. v1,v4,v6,v3,v2,v5
5. 下列排序方法中，哪一个是稳定的排序方法？（ ）
A. 简单选择排序
B. 堆排序
C. 希尔排序
D. 快速排序
6. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（ ）结点。
A. 2h
B. 2h-1
C. 2h+1
D. h+1
7. 平衡二叉树的平衡因子的取值可能是（ ）。
A. 1
B. 2
C. 3
D. 4
8. 一个有n个顶点的无向图最多有（ ）条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
9. 在迷宫求解问题中，用（）作为转换过程中的数据存储结构。
A. 线性表
B. 栈
C. 队列
D. 单链表
10. 计算机算法指的是（ ）。
A. 计算方法
B. 排序方法
C. 解决问题的步骤序列
D. 调度方法
11. 基数排序是（ ）。
A. 稳定的
B. 不稳定的
C. 看具体情况
D. 未知
12. 对（70.83.100.65.10.32.7.9）进行简单选择排序，排序后第一趟结果为（）。
A. 7.83.100.65.10.32.70.9
B. 7.9.100.65.10.32.70.83
C. 7.9.10.65.100.32.70.83
D. 7.9.10.32.100.65.70.83
13. 对于一个有向图的逆邻接链表表示，第i 个链表中有x个结点，则顶点i的出度为（ ）。
A. x
B. x+1
C. x+i
D. 无法确定
14. 1348转化为8进制结果是（ ）。
A. 2504
B. 2405
C. 4052
D. 2054
15. 二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（ ）。
A. 700
B. 1120
C. 1180
D. 1140
16. 已知Head(Tail())=，广义表S满足上式，则S为（ ）(其中，方括号表示广义表，圆括号表示函数，如表示由a,b 构成的广义表，而Head()表示取广义表的头部）。
A. [,b,a]
B. [,,]
C. [,,]
D. [,,]
17. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（ ）。
A. X的双亲
B. X的右子树中最左的结点
C. X的左子树中最右结点
D. X的左子树中最右叶结点
18. 在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找30需要进行多少次比较。（ ）
A. 1
B. 2
C. 3
D. 4
19. 对长度为155的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ）。
A. 78
B. 77.5
C. 155
D. 156
20. 对于三个结点的二叉树有多少种形态？ （ ）
A. 3
B. 4
C. 5
D. 6
二、判断题（本大题共40分，共 20 小题，每小题 2 分）
1. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用求最短路径的Dijkstra方法。
2. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。
3. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
4. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
5. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
6. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
7. Hash表的平均查找长度与处理冲突的方法无关。
8. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。
9. 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
10. 图的遍历要求从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。
11. 迷宫求解问题中经常用到顺序表来存储数据。
12. 邻接多重表的建立及其各种基本操作的实现和邻接表相似
13. 建立十字链表和建立邻接表的时间复杂度是相同的。
14. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。
15. 表达式求值问题中经常用到顺序表来存储数据。
16. 在待排数据基本有序的情况下，快速排序效果最好。
17. 括号匹配的检验中经常用到单链表来存储数据。
18. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。
19. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。
20. 最佳二叉树是AVL树（平衡二叉树）
答案：
页:
[1]