1、数据结构 (第 2 版 )_在线作业 _3 一、单选题 1. (5 分 ) 下述序列中，（ ）是执行第一趟快速排序后所得到的序列。 A. 【 68,11,69,23】【 18,93,73】 B. 【 68,11,69,23,18】【 93,73】 C. 【 68,11,18,69】【 23,93,73】 D. 【 93,73】【 68,11,69,23,18】 纠错 得分： 5 知识点： 7.4 快速排序 展开解析 2. (5 分 ) 下列说法不正确的是（ ）。 A. 图的深度优先遍历不适于用于有向图 B. 遍历的基本算法有两种，深度优先遍历和广度优先遍历 C. 图的遍历是从给定的原点出发，而
2、且每一个顶点仅仅被访问一次 D. 图的深度优先遍历是一个递归过程 纠错 得分： 5 知识点： 5.3 图的遍历 展开解析 3. (5 分 ) 给定一组关键字： 19,1,23,14,55,20,84,27,68,11,10,77 应用散列函数： H（ key） =key%13 采用开放地址法中线性探测法解决冲突，试在 0-18 地址空间中构建散列表，给出散列存储结果，正确的一项是（ ）。 A. B. C. D. 纠错 得分： 5 知识点： 6.2 查找算法 展开解析 4. (5 分 ) 利用 3,7,5,4 这四个值，作为叶子结点的权重，生成一棵 Huffman 树，该树的带权路径长度为（ ）
3、。 A. 55 B. 36 C. 32 D. 38 纠错 得分： 5 知识点： 4.4 Huffman 树及应用 展开解析 5. (5 分 ) 无向图 G=（ V， E）， V=a,b,c,d,e， E=, , , , , , 对该图进行拓扑排序，下列序列中（ ）不是拓扑序列。 A. a,b,c,d,e B. a,d,c,b,e C. d,a,b,c,e D. a,b,d,c,e 纠错 得分： 5 知识点： 5.6 拓扑排序 展开解析 6. (5 分 ) 多种排序方法中：（ ）法从未排序的序列中依次取出元素，与已排序序列（初始为空）中的元素作比较，将其放入已排序序列的正确位置；（ ）法从未排序
4、的序列中挑选元素，并将其依次放入已排序序列的正确位置。 A. 冒泡排序， shell 排序 B. 归并排序，堆排序 C. 插入排序，选择排序 D. 基数排序，快速排序 纠错 得分： 5 知识点： 7 排序 展开解析 7. (5 分 ) 在数据结构中，从逻辑上可以把数据结构分成（ ）。 A. 紧凑结构和非紧凑结构 B. 动态结构和静态结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 纠错 得分： 5 知识点： 1.2 基本概念和术语 展开解析 8. (5 分 ) 已知图如下，若从顶点 a 出发，按深度优先进行遍历，可能得到（ ）序列。 A. a-f-d-b-c-e B. a-c-e-f
5、-d-b C. a-d-f-c-b-e D. a-b-c-d-e-f 纠错 得分： 5 知识点： 5.3 图的遍历 展开解析 9. (5 分 ) 下面的序列中（ ）序列是堆。 A. 9,8,7,6,5,4,3,7 B. 9,8,7,6,4,8,2,1 C. 1,2,8,4,3,9,10,5 D. 1,5,10,6,7,8,9,2 纠错 得分： 5 知识点： 7.3 堆排序 展开解析 10. (5 分 ) 用希尔排序对数据序列 15,9,7,8,20， -1,4进行排序，进行第一趟排序后，数据序列变为 15， -1,4,8， 20,9,7，你认为采用的排序 asp（数据段长度）为（ ）。 A.
6、1 B. 3 C. 4 D. 2 纠错 得分： 5 知识点： 7.2 希尔排序 展开解析 11. (5 分 ) 从二叉树任意结点出发到根结点的路径上所经过的结点序列按其关键字有序，则该二叉树是（ ）。 A. Huffman 树 B. 二叉排序树 C. 堆 纠错 得分： 5 知识点： 7 排序 展开解析 12. (5 分 ) 在规定顺序环形队列一般状态队头指针指向第一个数据元素之前的空位，队尾指针指向末尾元素的前提下，假定一个顺序循环队列的队首和队尾指针分别用 front 和 rear 表示，则判断队空的条件为（ ）。 A. front = rear B. front+1 = rear C. r
7、ear+1 = front D. front = 0 纠错 得分： 5 知识点： 3.1 顺序存储结构队列 展开解析 13. (5 分 ) 除了使用拓扑排序的方法外，利用下面算法中那一种可以判断出一个有向图是否存在环路？（ ） A. 求出最小生成树 B. 深度优先遍历 C. 求最短路径 纠错 得分： 5 知识点： 5.1 图的基本术语与定义 展开解析 14. (5 分 ) 顺序查找法适合于存储结构为（ ）的线性表。 A. 算列存储 B. 压缩存储 C. 顺序存储和链接存储 D. 索引存储 纠错 得分： 5 知识点： 6.2 查找算法 展开解析 15. (5 分 ) 计算机算法必须具备输入、输出
8、、（ ）等 5 个特征。 A. 可行性、确定性和有穷性 B. 可行性、可移植性和可扩展性 C. 易读性、安全性、稳定性 D. 确定性、有穷性和稳定性 纠错 得分： 5 知识点： 1.3 C 程序与例题 展开解析 16. (5 分 ) 设有数据逻辑结构为： Data=(D,R); D=d1,d2,d3,d4,d5,d6,d7 R=, 试分析该数据结构属于哪种逻辑结构？（ ） A. 树结构 B. 图结构 C. 网络结构 D. 线性逻辑结构 纠错 得分： 5 知识点： 1.2 基本概念和术语 展开解析 17. (5 分 ) 对长度为 3 的顺序表进行查找，查找第一个元素的概率是 1/2，查找第二个元素的概率是 1/3，查找第三元素的概率是 1/6，则查找任意元素的平均查找长度为（ ）。 A. 2 B. 7/3 C. 4/3 D. 5/3 纠错 得分： 5 知识点： 6.2 查找算法 展开解析 18. (5 分 ) 有 n 个结点的强连通图的邻接矩阵中至少有（ ）个非零元素。
