资源描述：
《数据结构练习4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、华东理工大学网络学院《数据结构》------ch7图、ch9排序班级学号姓名成绩一、填空题（每空1分，共10分）1.具有n个顶点的有向图最多有n（n-1）条边。2.在无向图G的邻接矩阵中，求第i个结点的度的方法是求邻接矩阵第i行非零元素之和。3.堆排序通常采用顺序存储结构。4.与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。5.具有8个顶点的有向完全图有56条弧。6.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于1。7.在一个待排序的序列中，只有很少量元素不在自
2、己最终的正确位置上，但离他们的正确位置都不远，则使用直接插入排序方法最好。8.已知有向图的邻接矩阵，要计算i号顶点的入度，计算方法是：将.i列元素累加。9.n个顶点的连通无向图至少有n-1条边，至多有n(n-1)/2条边。二、判断正误（对的用”T”表示，错误的用”F”表示。每小题1分，共10分）1.(T)若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。2.(F)快速排序的速度在所有的排序方法中为最快，而且所需附加空间也最少。3.（F）采用邻接表存储的图的深度优先遍历算法类似二叉树
3、的按层次遍历算法。4.（T）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。5.（T）图的广度优先遍历类似于树的层次遍历。6.（T）拓扑排序时，总是在有向图中选择入度为0的顶点输出。7.（F）若要求一个稠密图G的最小生成树，最好用Kruscal算法来求解。8.（T）拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在回路。9.（T）从源点到汇点的最长路径称为关键路径。10.（F）n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n+e)。三、单项选择题（每小题2分，共20分）
4、1.假设以第一个元素为分界元素，对字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）进行快速排序，则第一次划分的结果是：CA(A,C,D,F,H,M,P,Q,R,S,X,Y)B(A,F,H,C,D,P,M,Q,R,S,Y,X)C(F,H,C,D,P,A,M,Q,R,S,Y,X)D(P,A,M,F,H,C,D,Q,S,Y,R,X)2.下面是三个关于有向图运算的叙述：第4/4页（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指定结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，
5、其结果必定是唯一的其中哪个（些）是正确的？DA只有（1）B（1）和（2）C都正确D都不正确3.排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？DA堆排序B直接插入排序C快速排序D冒泡排序4.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：BA将邻接矩阵的第i行删除B将邻接矩阵的第i行元素全部置为0C将邻接矩阵的第i列删除D将邻接矩阵的第i列元素全部置为05.一组序列的关键码为：{28、19、27、49、56、12、10、25}利用快速
6、排序的方法，写出以第一个记录为基准得到的一次划分结果：AA2519271012285649B2519271210284956C2519272849561210D25192710122849566.堆的形状是一棵C。A二叉排序树B满二叉树C完全二叉树D平衡二叉树7.图的深度优先遍历类似于树的A遍历。A先序B中序C后序D层次8.有n个顶点的无向连通图至少有A条边。An-1BnCn+1D2n9.有n个顶点的有向强连通图至少有B条边。An-1BnCn+1D2n10.下列几种排序方法中，要求辅助空间最大的是C。A插入
7、排序B快速排序C归并排序D选择排序四、简答题（每小题5分，共15分）1.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？无答案2.说明在图的遍历中，设置访问标志数组的作用。答：图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。第4/4页3.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？答：用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零
8、元素的个数与边的条数有关。五、综合题（每小题10分，共30分。）1.已知序列{503、87、512、61、908、170、897、275、653、462}，写出用下列算法从小到大排序第一趟结束时的序列。（1）希尔排序（第一趟排序时的增量为3）（2）冒泡排序（3）快速排序（选第一个记录为枢轴）；答案：（1）6187170462275512503908653897（2）875036151217089727565346
