西南交通大学-zhy-数据结构第三次作业-2020版.docx

5星

浏览量: 0

大小:None

文件类型：None

简介：
这是一份来自西南交通大学的数据结构课程第三次作业文档（2020年版本），包含了学生zhy完成的各项练习和问题解答。西南交大；西南交通大学；数据结构；赵宏宇 1. 写算法：（1）已知二叉树的根结点指针为bt，求该二叉树中的叶子数目。（2）已知某二叉树的根结点地址root，各节点的左、右儿子指针域已经正确填充。编写一个算法将所有节点的双亲指针域正确填充。（3）已知某二叉树的根结点指针bt。编写算法，交换该二叉树中所有节点的左右子树。（4）给定n个结点的数据值按顺序存于一维数组（元素下标范围0..n-1）。编写算法，由该数组首地址和长度n建立对应的二叉链表存储结构。 2. 上机题：（1）用先序遍历法建立一个二叉树的二叉链表存储结构。结点data域值类型为int，输入的先序序列中0表示NULL指针域，其它有效节点的数据均不等于0。定义三个算法函数分别计算并输出该二叉树中数据的最大值、所有节点数据之和以及小于零的数据个数。（2）从键盘输入n个数值建立一个n元完全二叉树的顺序存储结构，并实现先序遍历，中序遍历及后序遍历。

全部评论 (0)

还没有任何评论哟~

客服

西南交通大学-zhy-数据结构第三次作业-2020版.docx

优质

这是一份来自西南交通大学的数据结构课程第三次作业文档（2020年版本），包含了学生zhy完成的各项练习和问题解答。西南交大；西南交通大学；数据结构；赵宏宇 1. 写算法：（1）已知二叉树的根结点指针为bt，求该二叉树中的叶子数目。（2）已知某二叉树的根结点地址root，各节点的左、右儿子指针域已经正确填充。编写一个算法将所有节点的双亲指针域正确填充。（3）已知某二叉树的根结点指针bt。编写算法，交换该二叉树中所有节点的左右子树。（4）给定n个结点的数据值按顺序存于一维数组（元素下标范围0..n-1）。编写算法，由该数组首地址和长度n建立对应的二叉链表存储结构。 2. 上机题：（1）用先序遍历法建立一个二叉树的二叉链表存储结构。结点data域值类型为int，输入的先序序列中0表示NULL指针域，其它有效节点的数据均不等于0。定义三个算法函数分别计算并输出该二叉树中数据的最大值、所有节点数据之和以及小于零的数据个数。（2）从键盘输入n个数值建立一个n元完全二叉树的顺序存储结构，并实现先序遍历，中序遍历及后序遍历。

西南交通大学-zhy-数据结构第四次作业.docx

优质

这是西南交通大大学学生zhy提交的数据结构课程的第四次作业，内容涵盖了数据结构相关的理论应用和编程实践。文档包含了对各种数据结构的理解以及算法实现的具体代码。西南交大；西南交通大学；数据结构；赵宏宇一、二叉树（二） 1. 编写算法： (1) 二叉树的直径定义为从根结点至叶子的最大路径长度。编写求解该值的算法。 (2) 已知二叉树(用二叉链表表示)根节点指针bt，以及两个节点p和q。请设计一个算法找出这两个节点最近公共祖先，并返回其地址。 (3) 给定一棵以二叉链表形式存储的二叉树及其根结点指针bt，请编写程序利用叶子结点的rchild字段将所有叶子连接成单向链表，最后输出该链表头结点地址。 2. 编程题： (1) 输入一个不含重复字符的字符串。假设此串中的每个字符代表完全二叉树的一个节点值，建立对应的完全二叉树（使用二叉链表存储），然后分别进行前序、中序和后序遍历输出结果。 (2) 根据输入的先序序列(其中##表示空节点)，构建一个以char类型为数据域的二叉链表，完成该树的中序线索化，并用非递归方式实现其正逆两种顺序的中序遍历。二、图 1. 已知某无向图如下。请画出它的多重邻接表示意图并给出从顶点v0出发进行深度和广度优先搜索时访问节点序列。 2. 设计一个算法来检测给定无向图是否存在环路，提示：在执行DFS过程中，若当前结点的某个相邻结点已被标记为已访问且该相邻结点不是上一递归步骤中的父节点，则表明存在回边即形成了环。 3. 编写程序建立某无向图的邻接表结构，并输出深度和广度优先搜索时顶点被访问顺序。 4. 设计一个算法构建AOE网络并计算所有事件ve[]及vl[]值，最后按要求格式展示结果。 5. 选做题*：给定AOE网的邻接表存储以及其所有的ve[], vl[]数据，请编写程序输出该图的所有关键路径。每条路径应以源点至汇点顶点序列的形式给出（即需保持拓扑顺序）。

西南交通大学-zhy-数据结构第一次作业.docx

优质

这份文档是西南交通大学学生ZHY的数据结构课程第一次作业，包含了对基本概念的理解和算法实现等内容。西南交大;西南交通大学;数据结构;赵宏宇;《C语言版》数据结构习题集（严蔚敏，吴伟明）绪论：1.8, 1.9, 1.12, 1.20 线性表: 2.19, 2.20, 2.21 (电子教案例5) 线性表: 2.24, 2.31, 2.32

西南交通大学-zhy-数据结构第五次作业.zip

优质

此文件为西南交通大学学生zhy提交的数据结构课程第五次作业，包含代码、算法分析及相关文档。西南交通大学数据结构课程由赵宏宇教授讲授，以下是部分习题：一、查找 1. 算法设计：已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key，请编写算法使用对分查找求下标i，满足ai-1

数据结构作业（第1-10章）- 西南交通大学.zip

优质

该文件包含西南交通大学的数据结构课程前十个章节的相关习题和解答，适用于学生复习巩固及教师教学参考。数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中高效地组织和管理数据以支持快速查找、插入与删除操作。本压缩包“西南交通大学数据结构作业1-10章.zip”包含了该课程从第1次到第5次的作业内容，这将帮助我们深入了解数据结构的基本概念及其应用。首先，在初步学习阶段通常会接触到线性结构，例如数组和链表等。数组是最基本的数据结构之一，它在内存中存储一系列相同类型的元素，并通过索引进行访问。而链表则不同，其节点不连续存放而是通过指针链接起来的，这使得插入与删除操作更为灵活。实际问题中可能会遇到顺序表和链表的选择问题，需要根据具体需求来确定使用哪种结构。第2次作业可能涉及栈和队列这两种特殊的线性结构。栈是一种后进先出（LIFO）的数据结构，在函数调用、表达式求值等场景中有广泛应用；而队列则是先进先出（FIFO）的，常用于任务调度及数据缓冲等领域中。了解并掌握这些操作方法对于理解相关算法至关重要。第3次作业可能会深入到树形结构的学习，例如二叉树。二叉树每个节点最多有两个子节点，并分为左、右两个方向。不同类型的二叉树如完全二叉树和平衡二叉树（比如AVL或红黑树）在搜索与排序等领域有着广泛应用。学习过程中还需要理解和实现遍历算法，包括但不限于前序、中序以及后序遍历。第4次作业可能涵盖图结构的学习内容。由顶点和边组成的图形可以表示现实世界中的各种关系，例如社交网络及交通系统等复杂场景下应用广泛。常见的图的遍历方法有深度优先搜索（DFS）与广度优先搜索（BFS），而最小生成树算法如Prim或Kruskal以及最短路径问题求解方案如Dijkstra和Floyd-Warshall同样是重要的研究课题。第5次作业可能涉及动态规划及排序算法的学习。动态规划是一种通过将大问题分解为小问题并存储中间结果来避免重复计算的策略，适用于解决斐波那契序列、背包等问题；而各种常见的排序方法如冒泡排序、选择排序等在不同场景下的效率和适用性也是数据结构课程的重要内容。完成这五次作业后，学生可以逐步掌握数据结构的基本概念，并学会设计与分析相关算法。这对于进一步学习高级算法及解决实际问题具有重要意义。这些基础知识不仅对软件开发有帮助，在数据分析或机器学习等领域同样有着深远的影响。因此，深入理解和实践数据结构是每个计算机科学专业学生的必备技能之一。

西南交通大学算法作业第七次

优质

本作业为《西南交通大学算法课程》第七次练习，涵盖图论、动态规划等核心算法问题，旨在通过实践加深学生对复杂算法的理解与应用。 ### 知识点一：分支限界法在旅行问题中的应用 #### 1. 分支限界法概览分支限界法是一种用于搜索解空间树的方法，通常用来解决优化问题，例如寻找最小成本路径、最优调度方案等。与回溯法相比，分支限界法更加关注在搜索过程中对解空间树进行剪枝，以减少不必要的搜索，提高效率。 #### 2. 旅行问题背景本案例中考虑的是一个旅行问题：给定一系列城市及其之间的距离和汽油价格，任务是设计一条从起点到终点的路径，使得总的旅行成本最低。这是一个典型的组合优化问题，可以通过分支限界法来解决。 #### 3. 目标函数、限界函数及约束函数 - **目标函数**：总旅行成本最小化。 - **限界函数**：基于当前路径的已知成本和未来可能发生的最小成本（即后续城市中汽油价格最低的成本）的估计。 - **约束函数**：确保路径上的每一步都满足物理上的可行性（如剩余油量足够行驶至下一个城市）。 #### 4. 解空间树和搜索空间树 - **解空间树**：描述了所有可能的解路径，每个节点代表一个城市的访问顺序。 - **搜索空间树**：展示了实际搜索过程中经过的路径，包括已访问的城市和未访问的城市。 #### 5. 算法时间复杂度分析对于这个问题，在最坏情况下分支限界法的时间复杂度大约为O(n!)，因为需要考虑所有可能的路径组合。但是通过有效的限界函数和剪枝策略，实际运行的时间复杂度会显著降低。 ### 知识点二：分支限界法在贪吃蛇游戏中的应用 #### 1. 贪吃蛇游戏背景在贪吃蛇游戏中，目标是让蛇从当前位置移动到出口位置，并尽可能减少移动的步数。同时确保每一步都避开障碍物或自己的身体。 #### 2. 算法设计思路 - **目标函数**：最少移动步数。 - **限界函数**：基于当前路径的步数和剩余最短路径步数的估计。 - **约束函数**：保证蛇在每次移动时都不会碰到障碍物或自己。 #### 3. 解空间树和搜索空间树 - **解空间树**：描述了所有可能的移动路径，每个节点代表蛇的一个位置状态。 - **搜索空间树**：展示了实际搜索过程中经过的状态，包括当前位置和下一步可能的位置。 #### 4. 算法时间复杂度分析对于这个问题，在最坏情况下时间复杂度为O(4^L)，其中L是蛇的长度。每一步都有四种方向选择的可能性。通过使用分支限界法进行有效的剪枝可以大大减少搜索的时间。 ### C/C++实现框架 ```cpp #include #include #include #include using namespace std; #define MAXNNUM 1000 int head[MAXNNUM]; bool visited[MAXNNUM][MAXNNUM]; int expense[MAXNNUM][MAXNNUM]; typedef struct HeapNode { int nowplace; int res; int cost; } HeapNode; HeapNode Heap[MAXNNUM]; // 其他必要的辅助函数和主函数实现... ``` ```cpp #include #include #include #include using namespace std; #define MAXNNUM 20 int board[MAXNNUM][MAXNNUM]; bool visited[MAXNNUM][MAXNNUM]; typedef struct SnakeNode { int pos[MAXNNUM][2]; // 保存蛇的每一个位置 int step; } SnakeNode; SnakeNode Snake[MAXNNUM]; // 其他必要的辅助函数和主函数实现... ``` 以上是对给定文件中的两个问题的知识点总结，包括理论分析、算法设计思路以及部分C/C++实现框架。

数据结构第四次作业.docx

优质

本作业为《数据结构》课程第四次作业，涵盖了链表、栈和队列等基本数据结构的应用与实现，包括多项编程任务及算法设计。一、二叉树（二） 1. 写算法 (1) 定义：二叉树的直径是从根结点至叶子的最大路径长度。编写一个算法来求解给定的二叉树（以二叉链表形式存储）的直径。 (2) 已知一个由根节点指针bt表示的二叉树，以及两个节点p和q，设计并实现一个算法找出这两个结点之间的最近公共祖先，并返回该祖先结点地址。 (3) 基于给定的二叉树（以二叉链表形式存储），利用叶子结点的rchild指针域将所有叶子连接成单向链表。要求输出的是最左边第一个叶子节点地址作为单向链表头结点指针。 2. 编程题 (1) 从键盘输入一个不含重复字符的字符串，将其视为完全二叉树顺序存储结构中的元素，并建立对应的二叉链表形式的完全二叉树。输出该树的先序、中序和后序遍历结果。 (2) 使用先序遍历方法构建一棵以char类型为数据域的二叉树（用字符#表示NULL），实现其中序线索化，然后使用非递归算法输出中序遍历的结果正向序列及其逆向序列。二、图 1. 根据给定无向图绘制其多重邻接表存储结构，并根据该存储结构写出从顶点v0出发的深度优先和广度优先搜索时结点访问顺序。 2. 编写一个算法来判断无向图中是否存在环。使用深度优先遍历方法，当在某个节点处发现回边（已访问过的邻接点）且其不是当前递归调用的直接前驱顶点，则判定存在环路。 3. 编程题：构建给定无向图的邻接表存储结构，并输出该图深度和广度优先搜索时结点被访问到次序。 4. 编写程序以创建AOE网络（Activity On Edge Network）的数据结构，计算并显示每个事件的时间最早发生时间ve[]以及最晚允许开始时间vl[]值。 5. 选做题：设计算法输出所有关键路径。给定的是一个已建立邻接表存储的AOE网络G，并且已经知道了各个节点的ve和vl值。要求以源点至汇点顶点序列的形式表示每一条关键路径，确保该序列是拓扑有序的。

数据结构第五次作业.docx

优质

本作业为《数据结构》课程第五次作业，包含多项练习题和编程任务，旨在巩固学生对各种数据结构的理解与应用能力。一、查找 1. 算法设计题：已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key，编写算法用对分查找求下标i，满足ai-1

西南交通大学数据结构实验

优质

简介：西南交通大学数据结构实验课程旨在通过编程实践加深学生对抽象数据类型及算法的理解与应用，培养学生的逻辑思维和问题解决能力。西南交大数据结构实验代码采用C语言编写。