重庆大学2018年 数据结构 ( 第2次 )
重庆大学2018年 数据结构 ( 第2次 )一、单项选择题（本大题共60分，共 20 小题，每小题 3 分）
1. 设给定权值总数有n 个，其赫夫曼树的结点总数为( )。
A.
不确定
B.
2n
C.
2n+1
D.
2n-1
2. 有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d.E(G)为{,}，则顶点0到顶点2,3,4,5的最短路径和为（ ）。
A.
140
B.
150
C.
160
D.
170
3. 孩子兄弟表示法中，若要访问结点x的第i个孩子，则要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走（ ）步，便可找到x的第i个孩子。
A.
1
B.
2
C.
i-1
D.
i
4.
以下四个选项中DAG（有向无环图）是（ ）。
A.
B.
C.
5. 由3个结点所构成的二叉树有（ ）种形态。
A.
3
B.
4
C.
5
D.
6
6. 对数据元素序列（49，72，68，13，38，50，97，27）进行排序，如果采用起泡排序方法，则第二趟排序结果是( ）。
A.
49，68，13，38，50，72，27，97
B.
13，38，49，50，27，68，72，97
C.
49，13，38，50，68，27，72，97
D.
13，38，49，27，50，68，72，97
7. 基数排序需要以下数据结构的辅助（ ）。
A.
栈
B.
队列
C.
树
D.
森林
8. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )。
A.
哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B.
除留余数法是所有哈希函数中最好的
C.
删除运算方便
D.
不存在特别好与坏的哈希函数，要视情况而定
9. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为VT为网中任意一点，ET为空，下面步骤重复n-1次: a：选i属于VT，j不属于VT，且（i，j）上的权最小；b：（ ）
A.
顶点i加入VT，（i,j）加入ET
B.
顶点j加入VT，（i,j）加入ET
C.
顶点j加入VT，（i,j）从ET中删去
D.
顶点i,j加入VT，（i,j）加入ET
10. 快速排序在最坏情况下的时间复杂度是 ( )。
A.
O(logn)
B.
O(n)
C.
O(n*logn)
D.
O(n2)
11. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A.
M1
B.
M1+M2
C.
M3
D.
M2+M3
12. 有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，字符c的编码是（ ）。
A.
001
B.
101
C.
010
D.
100
13. 二叉树是非线性数据结构，所以（ ）。
A.
它不能用顺序存储结构存储
B.
它不能用链式存储结构存储
C.
顺序存储结构和链式存储结构都能存储
D.
顺序存储结构和链式存储结构都不能使用
14. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。
A.
求关键路径方法
B.
求最短路径的Dijkstra方法
C.
广度优先遍历算法
D.
深度优先遍历算法
15. 对于一个具有n个顶点e条边的无向图的邻接表的表示，邻接表的边结点个数为（ ）。
A.
2e
B.
n+e
C.
n+2e
D.
n+e+1
16. 下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.
快速排序
B.
shell排序
C.
堆排序
D.
冒泡排序
17. 堆排序的平均时间复杂度为（ ）。
A.
O(logn)
B.
O(n)
C.
O(nlogn)
D.
O(n2)
18. 有一组数，顺序是“4，7，8，1，9”，用冒泡排序法将这组数从小到大排序，第二趟第二次对比的数据两个数是( )。
A.
1、4
B.
4、7
C.
1、7
D.
1、8
19. 快速排序算法是对什么算法的改进？（ ）
A.
直接插入排序
B.
希尔排序
C.
起泡排序
D.
以上答案都不对
20. 基数排序是（ ）。
A.
稳定的
B.
不稳定的
C.
看具体情况
D.
未知
二、判断题（本大题共40分，共 20 小题，每小题 2 分）
1. 对无序表用折半查找比顺序查找快。
2. 对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环。
3. 根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素的过程，称为查找。
4. 若二叉排序树非空，则新结点的值和根结点比较，若小于根结点，则插入到右子树；否则插入到左子树。
5. 克鲁斯卡尔算法适应范围为稀疏图。
6. 二叉树中每个结点有两棵非空子树或有两棵空子树。
7. 有n个数存放在一维数组A中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。
9. 在散列检索中，“比较”操作一般也是不可避免的。
10. 图或网经常用于描述一个城市或城市间的交通运输网络
11. 在AOE网中，从源点到汇点路径上各活动时间总和最短的路径称为关键路径。
12. 若*P结点只有左子树PL或者只有右子树PR，此时只需令PL或PR直接成为其双亲结点*f的右子树即可。
13. 邻接多重表是有向图的另一种链式存储结构。
14. 图的遍历要求从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。
15. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
16. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用求最短路径的Dijkstra方法。
17. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
18. Hash表的平均查找长度与处理冲突的方法无关。
19. 邻接多重表的建立及其各种基本操作的实现和邻接表相似
20. 在待排数据基本有序的情况下，快速排序效果最好。
答案：
一、单项选择题（60分，共 20 题，每小题 3 分）
1. D 2. B 3. C 4. B 5. C 6. C 7. B 8. C 9. B 10. D 11. D 12. A 13. C 14. D 15. A 16. B 17. C 18. C 19. C 20. A
二、判断题（40分，共 20 题，每小题 2 分）
1. × 2. √ 3. √ 4. × 5. √ 6. × 7. × 8. √ 9. √ 10. √ 11. × 12. × 13. × 14. √ 15. × 16. × 17. √ 18. × 19. √ 20. ×
页:
[1]