《2018年数据结构第2次作业》由会员分享，可在线阅读，更多相关《2018年数据结构第2次作业（11页珍藏版）》请在金锄头文库上搜索。
1、第第 2 2 次作业次作业 一、单项选择题（本大题共一、单项选择题（本大题共 6060 分，共分，共 2020 小题，每小题小题，每小题 3 3 分）分） 1. 已知图 G 的邻接表如图所示，其从 v1 顶点出发的广度优先搜索序列为（）。A. 1、2、5、4、3、6B. 1、2、3、6、5、4C. 1、4、3、6、2、5D. 1、2、6、5、4、32. 在数制转换中，用（ ）作为转换过程中的数据存储结构。 A. 线性表B. 栈C. 队列D. 单链表3. 下面程序段的时间复杂度是（ ）。 i 0； while（inext=L。 2. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利
2、用求 最短路径的 Dijkstra 方法。 3. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不 仅与表中元素个数有关，而且与每块中元素个数有关。 4. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的 增大而增大。 5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把 两个栈的栈底分别设在这片内存空间的两端。 6. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。 7. 数制转换过程中经常用到栈来存储数据。 8. Hash 表的平均查找长度与处理冲突的方法无关。 9. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。
3、 10. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列 下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。 11. 图的遍历要求从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅 被访问一次。 12. 排序算法中的比较次数与初始元素序列的排列无关。 13. 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树 的过程即为对无序序列进行排序的过程。 14. 邻接多重表的建立及其各种基本操作的实现和邻接表相似 15. 用链表(llink-rlink)存储包含 n 个结点的二叉树，结点的 2n 个指针区域 中有 n-1 个空指针。
4、16. 表达式求值问题中经常用到顺序表来存储数据。 17. 迷宫求解问题结束时，若栈空，则表明没有路径存在。 18. 从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。 19. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后 出型结构。 20. 括号匹配的检验中经常用到单链表来存储数据。答案：答案：一、单项选择题（一、单项选择题（6060 分，共分，共 2020 题，每小题题，每小题 3 3 分）分） 1. A 2. B 3. B 4. D 5. A 6. C 7. D 8. B 9. A 10. B 11. C 12. D 13. C 14. C 15. A 16. D 17. B 18. A 19. B 20. A 二、判断题（二、判断题（4040 分，共分，共 2020 题，每小题题，每小题 2 2 分）分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
