则采用的排序方法是( )。
(A) 冒泡排序 (B) 快速排序 (C) 选择排序 (D) 插入排序 C
4-6 对数据36，12，57，86，9，25进行排序，如果前三趟的排序结果如下： 第1趟：12，36，57，9，25，86 第2趟：12，36，9，25，57，86 第3趟：12，9，25，36，57，86 则采用的排序方法是( )。
(A) 希尔排序 (B) 起泡排序 (C) 归并排序 (D) 基数排序 B
4-7 根据建堆算法，将关键字序列5，7，10，8，6，4调整成一个大顶堆，最少的交换次数为( )。
(A) 1 (B) 2 (C) 3 (D) 4 B
4-8 在链式基数排序中，对关键字序列369, 367, 167, 239, 237, 138, 230, 139进行第1趟分配和收集后，得到的结果是( )。
(A) 167, 138, 139, 239, 237, 230, 369, 367 (B) 239, 237, 138, 230, 139, 369, 367, 167 (C) 230, 367, 167, 237, 138, 369, 239, 139 (D) 138, 139, 167, 230, 237, 239, 367, 369 C
4-9 设int r[7]={5，2，6，4，1，7，3}; 则执行for ( i=0; i<7; i++) r[r[i]-1]=r[i]; 命令之后，数组r[7]中的数据元素存放顺序是( )。
(A) 5，2，7，4，1，6，3 (B) 3，2，1，4，5，7，6 (C) 1，2，3，4，5，6，7 (D) A、B、C都不对 这是一个计数排序，需要去好好看ppt D
4-10 设计一种排序算法，对1000个[0, 10000]之间的各不相同的整数进行排序，要求比较次数和移动次数 尽可能少。 采用计数排序
4-11 给定序列r[11]={30，25，12，16，46，21，27，38，9，18，31}，试分别给出一趟希尔排序(增量m=3)和一趟快速排序(枢轴为r[0])之后的序列r[11]。 希尔排序：r[11]={16,25,9,18,31,12,27,38,21,30,46} 快速排序：r[11]={18,25,12,16,9,21,27,30,38,46,31}
4-12 对关键字序列503, 87, 512, 61, 908, 170, 897, 275, 653, 426分别执行下列排序算法，写出第1趟排序后的关键字序列：
(1)快速排序; {426,87,275,61,170,503,897,908,653,512} (2)堆排序; {512,87,512,61,426,170,897,275,653,908}
(3)链式基数排序。{170,61,512,503,653,275,426,87,897,908}
4-13 设顺序表的结点结构为(Type Key; int Next)，其中，Key为关键字，Next为链表指针。试设计静态链表排序算法。
4-14 假设n个部门名称的基本数据存储在字符数组name[N][31]中，其中0≤n≤N≤90。试设计一个冒泡排序算法，将n个部门名称按字典序重新排列顺序。
void NameSort(RecordType **Name,int n) {
while(n>1)//一趟没有交换记录就弹出 {
i=1;
for(j=1;j if(getNameSize(Name,j)>getNameSize(Name,j+1)) { Name[j]<->Name[j+1];//交换 i=j; } n=i; } } //计算每个部门名称的大小 int getNameSize(RecordType **Name,int j) { int sum=0; for(k=0;k<=30;k++) sum = sum + Name[j][k]; return sum; } 4-15 设计基于顺序表存储结构的树形选择排序算法。 //基于顺序表存储结构的完全二叉树的选择排序 void Sorting(int L[],int n) { for (int i=1; i<=n; i++) { printf(\ //输出根结点 //将底层结点设置成“∞” int j=1; while(L[2*j]==L[1] || L[2*j+1]==L[1]) { j*=2; if (L[j]!=L[1]) j++; } L[j]=X; //将第i+1小的数据元素调整到根结点 for (int k=j; k>0; k/=2) { if (k%2) j=L[k-1]; else j=L[k+1]; if (j 4-16 假设采用链表存储类型： typedef struct RNode { int key; //数据域(也是关键字域) struct RNode *next; //指针域 } RNode, *RList; typedef RList R[N]; //链表类型, 常变量N≥n 又设R[1..n]是[10, 999]之间的随机整数。试设计一个链表基数排序算法，将R[n]中的数从小到大排序。排序结果仍存放在R[n]中。 习题5 图 5-1 设某个非连通无向图有25条边，问该图至少有( )个顶点。 (A) 7 (B) 8 (C) 9 (D) 10 C 5-2 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为( )。 23 (A) O(n+e) (B) O(n) (C) O(ne) (D) O(n) A 5-3 带权有向图G用邻接矩阵R存储，则顶点i的入度等于R中( )。 (A) 第i行非∞(或非0)的元素之和 (B) 第i列非∞(或非0)的元素之和 (C) 第i行非∞(或非0)的元素个数 (D) 第i列非∞(或非0)的元素个数 D 邻接矩阵 横坐标 头 纵坐标 尾 5-4 在关于图的遍历描述中，不正确的是( )。 (A) 图的深度优先搜索遍历不适用于有向图 (B) 图的深度优先搜索遍历是一个递归过程 (C) 图的遍历是从给定的源点出发访问图中每一个顶点一次 (D) 遍历的基本算法有两种：深度优先搜索遍历和广度优先搜索遍历 A 5-5 设计算法，由依次输入的顶点数目、狐的数目、各个顶点元素信息和各条狐信息建立有向图的邻接表。 5-6 请给出有向图的 (1) 每个顶点的入度和出度； (2) 邻接矩阵； (3) 邻接表。 5-7 设无向图G=(V，E)，V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}。从顶点a出发对图G进行深度优先搜索遍历，得到的顶点序列是( )。 (A) a b e c d f (B) a c f e b d (C) a e b c f d (D) a e d f c b D 5-8 给出无向图的 (1)深度优先遍历的顶点序列和边序列； (2)广度优先遍历的顶点序列和边序列。 5-9 概念解释：最小生成树。 设N=(V, E)是一连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边, 其中uU，vV-U，则存在一棵包含边(u, v)的最小生成树。 5-10 设无向图G=(V, E)，V={a, b, c, d, e}，E={, , , (A) E1={，，， 5-11 判断一个有向图是否存在回路，除了可以利用深度优先遍历算法外，还可以利用( )。 (A) 广度优先遍历算法 (B) 求最短路径的方法 (C) 拓扑排序方法 (D) 求关键路径的方法 C 或者深度优先排序 5-12 试绘出无向网G的最小生成树，并简要描述所依据的算法(或遍历方法)。