数据结构基础-南理工泰州科技学院

《数据结构基础-南理工泰州科技学院》由会员分享，可在线阅读，更多相关《数据结构基础-南理工泰州科技学院（13页珍藏版）》请在金锄头文库上搜索。

1、1习题一 绪论1 简要回答术语：数据，数据元素，数据结构，数据类型。2 数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？3 数据结构的主要运算包括哪些？4 算法分析的目的是什么？算法分析的主要方面是什么？5 分析以下程序段的时间复杂度，请说明分析的理由或原因。 Sum1( int n ) int p=1, sum=0, m ;for (m=1; m, , , , , , , 请画出该有向图，并求各顶点的入度和出度。 分别画出有向图的正邻接链表和逆邻接链表。 对图 7-27 所示的带权无向图。 写出相应的邻接矩阵表示。 写出相应的边表表示。 求出各顶点的度。 已知有向图的逆

2、邻接链表如图 7-28 所示。 画出该有向图。 写出相应的邻接矩阵表示。 写出从顶点 a 开始的深度优先和广度优先遍历序列。 画出从顶点 a 开始的深度优先和广度优先生成树。8 一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一? 对于图 7-27 所示的带权无向图。 按照 Prime 算法给出从顶点 2 开始构造最小生成树的过程。 按照 Kruskal 算法给出最小生成树的过程。 已知带权有向图如图 7-29 所示，请利用 Dijkstra 算法从顶点 V4 出发到其余顶点的最短路径及长度，给出相应的求解步骤。 已知带权有向图如图 7-30 所示，请利用 Floyd 算法求出每对顶点

3、之间的最短路径及路径长度。 一个 AOV 网用邻接矩阵表示，如图 7-31。用拓扑排序求该 AOV 网的一个拓扑序列，给9出相应的步骤。 拓扑排序的结果不是唯一的，请给出如图 7-32 所示的有向图的所有可能的拓扑序列。 请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。 设计一个算法利用图的遍历方法输出一个无向图 G 中从顶点 Vi 到 Vj 的长度为 S 的简单路径，设图采用邻接链表作为存储结构。 假设一个工程的进度计划用 AOE 网表示，如图 7-33 所示。 求出每个事件的最早发生时间和最晚发生时间。 该工程完工至少需要多少时间? 求出所有关键路径和关键活动。10习题

4、九 查找 对于一个有 n 个元素的线性表，若采用顺序查找方法时的平均查找长度是什么？若结点是有序的，则采用折半查找法是的平均查找长度是什么? 设查找表采用单链表存储，请分别写出对该表进行顺序查找的静态查找和动态查找的算法。 设二叉排序树中的关键字互不相同：则 最小元素无左孩子，最大元素无右孩子，此命题是否正确？ 最大和最小元素一定是叶子结点吗？ 一个新结点总是插入在叶子结点上吗？ 试比较哈希表构造时几种冲突处理方法的优点和缺点。 将关键字序列(10, 2, 26, 4, 18, 24, 21, 15, 8, 23, 5, 12, 14)依次插入到初态为空的二叉排序树中，请画出所得到的树 T；

5、然后画出删除 10 之后的二叉排序树 T1 ； 若再将 10 插入到 T1 中得到的二叉排序树 T2 是否与 T1 相同? 请给出 T2 的先序、中序和后序序列。 设有关键字序列为：(Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar) ，请手工构造一棵二叉排序树。该树是平衡二叉排序树? 若不是，请为其构造一棵平衡二叉排序树。 设关键字序列是(19, 14, 23, 01, 68, 84, 27, 55, 11, 34, 79)，散列表长度是 11，散列函数是 H(key)=key MOD 11， 采用开放地址法的线性探测

6、方法解决冲突，请构造该关键字序列的哈希表。 采用开放地址法的二次探测方法解决冲突，请构造该关键字序列的哈希表。 试比较线性索引和树形索引的优点和缺点。 设关键字序列是(19, 24, 23, 17, 38, 04, 27, 51, 31, 34, 69)，散列表长度是 11，散列函11数是 H(key)=key MOD 11， 采用开放地址法的线性探测方法解决冲突，请构造该关键字序列的哈希表。 求出在等概率情况下，该方法的查找成功和不成功的平均查找长度 ASL。 下图是一棵 3 阶 B_树，请画出插入关键字 B,L,P,Q 后的树形。12习题十 内部排序 回答下列各题： 从未排序序列中挑选元素

7、，并将其依次放入到已排序序列中(初始时为空)的一端的方法是什么？ 在待排序的元素基本有序的前提下，效率最高的排序方法是什么? 从未排序序列中依次取出元素与已排序序列 (初始时为空)中的元素进行比较，将其放入已排序序列的正确位置方法是什么？ 设有 1000 个元素， 希望采用最快的速度挑选出其中前 10 个最大的元素， 最好的方法是什么? 若对关键字序列为 (54, 37, 93, 25, 17, 68, 58, 41, 76)的一组记录进行快速排序时，递归调用使用的栈所能到达的最大深度是多少?共需递归调用多少次? 其中第二次递归调用是对哪组记录进行排序? 在堆排序，快速排序和归并排序中，若只从

8、存储空间考虑，应选择哪种方法；若只从排序结果的稳定性考虑，应选择哪种方法；若只从平均情况下排序最快考虑，应选择哪种方法； 设有关键字序列为(14, 17, 53, 35, 9, 32, 68, 41, 76, 23)的一组记录，请给出用希尔排序法(增量序列是 5, 3, 1)排序时的每一躺结果。 设有关键字序列为(14, 17, 53, 35, 9, 37, 68, 21, 46)的一组记录，请给出冒泡排序法排序时的每一躺结果。 设有关键字序列为(14, 17, 53, 35, 9, 37, 68, 21, 46)的一组记录，利用快速排序法进行排序时，请给出以第一个记录为基准得到的一次划分结果。 设关键字序列为(14, 17, 53, 35, 9, 37, 68, 21)的一组记录，请给出按非递增采用堆排序时的每一躺结果。13 设关键字序列为(314, 617, 253, 335, 19, 237, 464, 121, 46, 231, 176, 344)的一组记录，请给出采用基数排序时的每一躺结果。 将哨兵放在 Rn中，被排序的记录存放在 R1n-1中，重写直接插入排序算法。 实际中常采用单链表存储数据记录，请写出排序记录的结构的定义并修改。