数据结构阶段练习4

1、华东理工大学网络学院（专科）数据结构-ch7图、ch9排序班级 学号 姓名 成绩一、填空题（每空1分，共10分） 具有n个顶点的有向图最多有_ n（n-1）条边。 在无向图G的邻接矩阵中，求第i个结点的度的方法是求邻接矩阵第i行非零元素之和。堆排序通常采用顺序存储结构。与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。 具有8个顶点的有向完全图有条弧。在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 。在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用直接插入排序方法最好。已知有向图的邻接矩阵，要计算i号顶点的入度，计算方法

2、是：将 i列元素累加。n个顶点的强连通图至少有n 条边，至多有n（n-1） 条边。二、判断正误（对的用”T”表示，错误的用”F”表示。每小题1分，共10分）（ T）若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ F ）快速排序的速度在所有的排序方法中为最快，而且所需附加空间也最少。（ F）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。（ T）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。（ T）图的广度优先遍历类似于树的层次遍历。（ T）拓扑排序时，总是在有向图中选择入度为0的顶点输出。（ F）若要求一个稠密图G的最小生成树，最好用

3、Kruscal算法来求解。（ T）拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在回路。（ T）设有一稠密图G，则G采用邻接矩阵存储较省空间。（ F）n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O（n+e）。三、单项选择题（每小题2分，共20分）已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是_。A 0 3 2 1 B 0 1 2 3 C 0 1 3 2 D 0 3 1 2已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是_DA 0 3 2 1 B 0 1 2 3 C 0 1 3 2 D 0 3 1 2排序时扫描待排

4、序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？DA堆排序B直接插入排序C快速排序D冒泡排序 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：B 。A将邻接矩阵的第i行删除B将邻接矩阵的第i行元素全部置为0C将邻接矩阵的第i列删除D将邻接矩阵的第i列元素全部置为0 快速排序在_情况下最容易发挥其长处。A被排序的数据中含有多个相同的排序关键字B被排序的数据已基本有序C被排序的数据完全无序D被排序的数据中的最大值和最小值相差悬殊堆的形状是一棵C 。A二叉排序树 B满二叉树C完全二叉树 D平衡二叉树图的深度优先遍历类似于树的A 遍历。A先序

5、 B中序 C后序 D层次有n个顶点的无向连通图至少有 A 条边。A n-1 B nC n+1 D 2n用邻接表表示图进行广度优先遍历时，通常是采_ 来实现算法的。A栈B队列C树D图。下列几种排序方法中，要求辅助空间最大的是 C 。A插入排序 B快速排序 C归并排序 D选择排序四、简答题（每小题5分，共15分）设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基 数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？说明在图的遍历中，设置访问标志数组的作用。图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点用邻接矩阵表示图时，矩阵元素的个

6、数与顶点个数是否相关？与边的条数是否相关？用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元 素的个数与边的条数有关。五、综合题(每小题10分，共30分。)画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点 的无向完全图中，边的条数为n(n-1)/2。在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个 顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。试给出以1为起点的深度优先搜索和广度优先搜索的遍历序列，并给出一棵最小生成树。深度优先搜索序列：1 2 3 6 4 5；广度优先搜索：1 2 4 5 3 6最小生成树：18给出右图的邻接矩阵、邻接表表示。Edge010100001010000001010010000000000010(1)邻接表012345六、算法设计题(15分)设计一算法，使得在尽可能少的时间内重排数组an，将所有取负值的关键字放在所有取 非负值的关键字之前。并请分析算法的时间复杂度。void part(i