1. 画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索遍历该图所的顶点序列和边的序列。
邻接表：深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6
边的序列：（1，2） （2，3） （3，4） （4，5） （5，6）
广度优先搜索：顶点序列：1 -2 -3 -6 -5-4
边的序列：（1，2） （1，3） （1，6） （1，5） （5，4）
2 已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
解：邻接矩阵所表示的图如下：
自顶点1出发进行遍历所得的深度优先生成树：
自顶点1出发进行遍历所得的广度优先生成树：
3 请对下图的无向带权图。
1）写出它的邻接矩阵，并按普里母算法求其最小生成树。
2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
解：（1）邻接矩阵：
普里母算法求得的最小生成树：
2）邻接表：
克鲁斯卡尔算法生成最小生成树过程：
4 试列出下图中全部可能的拓扑有序序列。
解：全部的拓扑有序序列如下：
5 试利用dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。
s是已求得最短路径的终点的集合，则下一条最短路径（设其为终点为x）或者是弧（v,x）,或者是中间只经过s中的顶点而最后达到x的路径。
第十章排序练习题。
1、以关键字序列（503,087,512,061,908,170,897,275,653,426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态：
1）直接插入排序；（2）希尔排序（增量d[1]=5）
3）快速排序； （4）堆排序；
5）归并排序； （6）基数排序。
2、判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最小）。
3、试以作为监视哨改写直接插入排序算法。其中，为待排序记录且k4、编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。
5、序列的“中值记录”指的是：如果将此序列排序后，它是第个记录。试写一个求中值记录的算法。
《数据结构》各章课后作业答案
第一章绪论课后作业答案。1.简述线性结构与非线性结构的不同点。答 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。2 分析下面各程序段的时间复杂度 每小题5分，共20分 数据结构 数据结构 各章课后作业答案 数据结构 各章课后作业答案 6 数据结构 各章课后作业答案...
数据结构课后作业
数据结构 课后作业第二课。1 课堂作业 下堂课提问问题 mallco 函数和reallco 函数的意义和基本用法。2 课后作业 准备两个本子交替使用，需要抄题 简答题。1.简述一下什么是数据结构？2.简述一下为什么算法的复杂度不是算法设计中最重要的要求？计算题。1.指出算法的功能并求出其时间复杂度。...
数据结构 王红梅 课后答案
目录。第 1 章绪论 2 第 2 章线性表 8 第 3 章特殊线性表 栈 队列和串 16 第 4 章广义线性表 多维数组和广义表 23 第 5 章树和二叉树 27 第 6 章图 37 第 7 章查找技术 45 第 8 章排序技术 53 第 9 章索引技术 61 课后习题讲解 1.填空 是数据的基本单...