《浙大远程数据结构与算法离线复习资料-完整版》由会员分享，可在线阅读，更多相关《浙大远程数据结构与算法离线复习资料-完整版（50页珍藏版）》请在金锄头文库上搜索。
1、-浙江大学远程教育学院数据结构与算法课程离线作业数据结构与算法课程离线作业一、填空题：一、填空题： （【序号，章，节】 。 。 。 。 。 。）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多一对多关系，图形结构中元素之间存在多对多多对多关系。【2，1，2】为了最快地存取数据元素，物理结构宜采用序存储序存储结构。3，1，2】数据结构的三要素是逻辑结构，物理结构， 操作。【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构顺序存储结构，链式存储结构链式存储结构。【4，1，3】度量算法效率可通过时间复杂度和空间复杂度时间复杂度和空间复杂度_来进
2、行。【5，1，3】设 n 为正整数，下面程序段中前置以记号 的语句的频度是n(n+1)/2n(n+1)/2。for (i=0; in; i+)for (j=0; jn; j+)if (i+j=n-1)aij=0;【6，1，3】设 n 为正整数，试确定下列各程序段中前置以记号的语句的频度:(1) i=1;k=0;whilewhile (i=n-1)i+; k+=10 * i;/ 语句的频度是_ n-1 n-1_。(2) k=0;forfor (i=1; i=n; i+)forfor (j=i; jnext=null Head-next=null_【10，3，2】在一个单链表中 p 所指结点(p
3、所指不是最后结点)之后插入一个由指针 s 所指结点，应执行 s-next=_ p-next p-next_;和 p-next=_s_的操作。【11，3，2】在一个单链表中删除 p 所指结点时，应执行以下操作：q= p-next;p-data= p-next-data;p-next=p-next-nextp-next-next_;free(q);【12，3，2】带头结点的单循环链表 Head 的判空条件是_ Head-next=null Head-next=null _；不带头结点的单循环链表的判空条件是_ Head=null Head=null_。【13，3，2】已知 L 是带表头结点的非空单
4、链表, 且 P 结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。a. 删除 P 结点的直接前驱结点的语句序列是_10 12 8 11 4 1410 12 8 11 4 14_。b. 删除结点 P 的语句序列是_10 12 7 3 1410 12 7 3 14_。c. 删除尾元结点的语句序列是_9 11 3 149 11 3 14_。(1) P = P-next;(2) P-next = P;-(3) P-next = P-next -next;(4) P = P-next -next;(5) while while (P != NULLNULL)P = P-next
5、;(6) whilewhile (Q-next != NULLNULL)P = Q; Q = Q-next;(7) while while (P-next != Q)P = P-next;(8) while while (P-next-next != Q) P = P-next;(9) whilewhile (P-next-next != NULLNULL) P = P-next;(10) Q = P;(11) Q = P-next;(12) P = L;(13) L = L-next;(14) freefree (Q);【14，3，3】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出
6、序列有C A BC A B。【15，3，3】.在栈顶指针为 HS 的链栈中，判定栈空的条件是head-next=nullhead-next=null。【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。void conversion10_16()InitStack(&s);scanf(“%d”,&N);while(N)_ Push(s, N%16) Push(s, N%16) _;N = N/16;while(!StackEmpty(s)_ Pop(s, e) Pop(s, e);if(e=9)printf(“%d”,e);else printf(“%c”,e-10+A)
7、;/* conversion */【17，3，4】若用一个大小为 6 个元素的数组来实现循环队列，且当前 rear=0 和 front=3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别是2和4。【18， 3， 4】 堆栈和队列都是线性表, 堆栈是_后进先出后进先出_的线性表, 而队列是_-先进先出先进先出_的线性表。【19，3，4】若用一个大小为 6 个元素的数组来实现循环队列，且当前 rear=0 和 front=3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别是2 和4。【20， 4， 2】 已知一棵树边的集合是,。那么根结点
8、是e e，结点 b 的双亲是d d，结点 a 的子孙有bcdjbcdj，树的深度是4 4，树的度是3 3，结点 g 在树的第3 3层。【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题【22，4，3】满三叉树的第 i 层的结点个数为3 3i-1i-1，深度为 h 时该树中共有 3 3h h-1-1结点。【23，4，3】已知一棵完全二叉树有 56 个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为 1 号。则该完全二叉树总共结
9、点有_111_111_个；有_7_7_层；第 91 号结点的双亲结点是_45_45_号；第 63 号结点的左孩子结点是_号。【24， 4， 3】 下列表示的图中， 共有_5 5_个是树； 有_3 3_个是二叉树； 有_2 2_个是完全二叉树。-【25，4，4】n 个结点的二叉排序树的最大深度是n n，最小深度为log2log2 +1+1_【26， 4， 3】 如果某二叉树的后序遍历序列是 ABCDEFGHI， 中序遍历序列是 ACBIDFEHG，则其先序遍历序列的第一个字母是I I，最后一个字母是G G。【27，4，3】下列二叉树的中序遍历序列是_ DBNGOAEC DBNGOAEC _;后序
10、遍历序列是_ DNOGBECA DNOGBECA _。-【28，5，4】设 HASH 表的大小为 n n (n=10), HASH 函数为 h(x)=x % 7,h(x)=x % 7, 如果二次探测再散列方法 Hi=(H(key)+di) mod 10 (di = 12,22,32,)解决冲突，在 HASH 表中依次插入关键字1,14,55,20,84,27以后，关键字1、20 和 27 所在地址的下标分别是、_和。插入上述 6 个元素的平均比较次数是。答案：答案：1 1、7 7、5 5、2 2【29，6，3】设无权图 G 的邻接矩阵为 A，若（vi,vj）属于图 G 的边集合，则对应元素Ai
11、j等于1 1，22、设无向图 G 的邻接矩阵为 A，若 Aij等于 0，则 Aji等于0 0。【30，6，3】若一个图用邻接矩阵表示，则删除从第i 个顶点出发的所有边的方法是矩阵第矩阵第 i i 行全部置为零行全部置为零。【31，6，2】设一个图G=V,A,V=a,b,c,d,e,f,A=,。那么顶点 e 的入度是2 2；出度是1 1；通过顶点 f 的简单回路有2 2条；就连通性而言，该图是强连通图强连通图图；它的强连通分量有1 1个；其生成树可能的最大深度是5 5。【32，7，1】排序过程一般需经过两个基本操作，它们是比较比较和移动移动。【33，7，2】在对一组关键字是（54,38,96,4
12、5,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是 60）插入到有序表时，为寻找插入位置需比较 3 3次-分别与分别与 5454、7272、9696 比较比较【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有选择排序、快速排序、堆排序、希尔排序选择排序、快速排序、堆排序、希尔排序-二、综合题（选自教材数据结构各章习题，采用二、综合题（选自教材数据结构各章习题，采用 wordword 文件格式上传）文件格式上传）【1，1，3】试分析下面一段代码的时间复杂度：if ( A B ) for ( i=0; i
13、i; j- ) A += B;else for ( i=0; ii; j- ) A += B;if if 中的时间复杂度为：中的时间复杂度为：O(n*nO(n*n ) )即即 O(nO(n ) )elseelse 中的时间复杂度为：中的时间复杂度为：O(n*n)O(n*n)即即 O(nO(n ) )【2，1，3】测试例 1.3 中秦九韶算法与直接法的效率差别。令f (x) 1i1xi/i，计算f (1.1)的值。利用 clock()函数得到两种算法在同一机器上的运行时间。答：从运行结果可以看出秦九昭算法效率上有很大优势；#include #include #include clock_t st
14、art,stop;double duration;#define MAXN 10#define MAXK 1e7double f1(int n ,double a,double x);double f2(int n ,double a,double x);/秦九昭算法double f1(int n ,double a,double x)100-/直接算法double f2(int n ,double a,double x)int main()printf(直接算法：);printf(ticks = %fn,(double)(stop-start);duration = (double)(sto
15、p-start)/CLK_TCK/MAXK ;stop = clock();start = clock();for(i=0;iMAXK;i+)f2(MAXN-1,a,1.1);double aMAXN ;for(i=0;i0;i-)p += ai*pow(x,i);int i =0 ;double p = a0;return p;for(i=n;i0;i-)p = ai-1 + x * p;int i =0 ;double p = a0;-printf(duration = %6.2en,duration);for(i=0;iMAXN;i+)ai=(double)i;start = clock
16、();for(i=0;iMAXK;i+)f1(MAXN-1,a,1.1);stop = clock();printf(秦九昭算法：);printf(ticks = %fn,(double)(stop-start);printf(duration = %6.2en,duration);return 0;【3，1，3】 试分析最大子列和算法 1.3 的空间复杂度。答：在 1.4 中存在 4 种解决最大子列的算法，具体空间复杂度如下：1、穷举法：算法并没有开辟另外的存储空间进行存储，利用的是累加所以空间复杂度为 O(2);2、部分穷举：同上3、分而治之：利用递归解决问题，故空间复杂度为 O(N);4
17、、在线处理：为 O(2);【4，1，3】试给出判断N是否为质数的O( N )的算法。答案：#include #include -int is_prime(int n)if(n!= 2 & n % 2 = 0)return 1;void main()int num = 0 ,result =0 ;printf(Input the num:);result = is_prime(num);return 0;int i = 0;for(i=3;i=sqrt(double)n);i+=2)if(n % i = 0)return 0; scanf(%d, &num);if(result) printf(
18、%d is a primen, num);else printf(%d is not a primen, num);Input the num: 55 is a prime.【5，2，2】请编写程序，输入整数n 和 a，输出S=a+aa+aaa+aaa(n 个 a)的结果。答案：答案：-#includestdio.hint main() int a,b,n,i,s=0; scanf(%d %d,&a,&n); b=a; for(i=1;i=n;i+) s+=a; a=a*10+b; printf(%dn,s);【6，2，3】请编写递归函数，输出 123.n 的全排列（n 小于 10）,并观察
19、n 逐步增大时程序的运行时间。答案：#include #include void pailie(int* data, int n, int curr)int i = 0 ;if (curr=n-1)for (i = 0; i n; +i ) printf(%d, datai); printf(n); else -for (i = curr; i n; +i) int t; t = datacurr, datacurr = datai, datai = t; pailie(data, n, curr+1); t = datacurr, datacurr = datai, datai = t; i
20、nt main()int n = 0;int i = 0;int as10 = 0,0,0,0,0,0,0,0,0,0;/n小于等于10 scanf(%d, &n);return 0;end = clock();printf(The time was: %dn, (end - start) / CLK_TCK);asi = i+1;for (i = 0; i n; +i)clock_t end;clock_t start = clock(); pailie(as, n, 0);-N 为 7-N 为 9分析来看时间上虽然有比较大的增长，但主要用于打印；但在时间复杂度上是随着n 的变大呈直线上升趋
21、势；【7，3，2】 给定一个顺序存储的线性表 L = (a1,a2,an)，请设计一个算法-删除所有值大于 min 而且小于 max 的元素。SeqList Delete(SeqList &L, int min, int max)int i;=0,j=0for (i=0; imin & L.elemimax)for(j=i;jL.length;j+)L.elemj=L.elemj+1;-L.length; return L ;【8，3，2】给定一个顺序存储的线性表 L = (a1,a2,an)，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的
22、递增子序列为(3,4,6,8)。void main()int n, i, j, k;int A1024=;int dp1024=; scanf(%d, &n);for (i=1; i=n; i+) scanf(%d, Ai); dp1 = 1;/ 有n个阶段for (i=2; i=0; j-) if (AiAj) dpi = max(dpi, dpj+1); int maximum = dp1;for (i=2; i=n; i+)printf(%d maximum is : n, maximum); maximum = max(maximum, dpi);【9，3，3】 如果有 1、2、3、4
23、、5 按顺序入栈，不同的堆栈操作（pop, push）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？答案：按照正常情况，1,2,3,4,5 的全排列组合共有 5! = 120,即 120 种，但由于像：12435、12534 之类的无法按顺序出入栈，故按照顺序入栈的情况共有 56 种：以 1 开始排列组合为 14 种以 2 开始排列组合为 14 种以 3 开始的排列组合为 9 种以 4 开始的排列组合为 4 种以 5 开始的排列组合为 1 种-【10，3，2】请编写程序将中缀表达式转换为后缀表达式。答案：使用栈的循序存储结构实现、栈的顺序存储结构，用一维数组实现#incl
24、ude #include #define OK 1#define ERROR -1#define TRUE 1#define FALSE 0#define MAXSIZE 10typedef int Status;typedef char ElemType;typedef struct ElemType dataMAXSIZE;int top;/栈顶指针Stack;/1. 初始化Status InitStack(Stack *S)int i;-for(i=0;idatai=NULL; S-top=-1;return OK;/2. 创建一个长度为n的堆栈Status CreateStack(St
25、ack *S,int n)int i =0;if(nMAXSIZE | n1) printf(输入长度有误！n);return ERROR; for(i=0;idatai=rand()%100+1; S-top=n-1;return OK;Status push(Stack *S,ElemType e)if(MAXSIZE-1=S-top) printf(栈已满n);return ERROR; /栈顶指向的元素有值 +(S-top); S-dataS-top=e;return OK;/4. 出栈Status pop(Stack *S,ElemType *e)/将栈顶元素出栈，传给eif(-1=
26、S-top) printf(栈为空！n);return ERROR; - *e=S-dataS-top; -(S-top);return OK;/5. 中缀表达式转后缀表达式void MidToFinal(char *mid,char *final)/中缀表达式为middle，要转换成后缀表达式传给last/新建一个栈，来存储符号char e; Stack S;if(OK!=InitStack(&S) printf(初始化栈失败！n); /当带转换的字符串*mid未终止时，循环处理while(*mid)/如果是数字，则直接输出if(*mid=0 & *mid=9) *(final+)=*(mi
27、d+);continue; else if(*mid=+ | *mid=- | *mid=* | *mid=/ | *mid=(/输入的是合法运算符号,比较之前是否有更高优先级的符号if(S.top=-1 | (=*mid)/当符号栈为空或遇到左括号时，符号入栈 push(&S,*(mid+);continue; if()=*mid)/遇到右括号时，栈顶元素依次出栈；直到遇到第一个左括号时结束 pop(&S,&e); *(final+)=e;while(pop(&S,&e) & e!=() *(final+)=e; / printf(%cn,e); mid+;-) | *mid=-contin
28、ue; /后续的处理都要取出临时的栈顶元素，与当前输入的符号*mid相比较；当临时栈顶元素优先级大于等于输入符号的优先级时，出栈；否则符号入栈（已经弹出一个，记得把弹出的元素也入栈） pop(&S,&e);if(+=*mid | -=*mid)if(e=() push(&S,(); push(&S,*(mid+);continue; else *(final+)=e; push(&S,*(mid+);continue; else if(*=*mid | /=*mid)if(*=e | /=e) *(final+)=e; push(&S,*(mid+);continue; else push(&
29、S,e); push(&S,*(mid+);continue; else printf(输入的字符不合法！%cn,*mid);return; /当待转换的字符已经结束时，符号栈至少还有一个元素（中缀表达式的特点：数字结尾；后缀表达式以符号结尾）；将栈中的元素依次出栈while(S.top!=-1) pop(&S,&e); *(final+)=e; /字符串的结束符！- *final=0;int main()char data=3+(5*6-7/1*7)*9;char final=; MidToFinal(data,final); printf(%sn,final);return 0;【11，4
30、，3】设二叉树的存储结构如下：LchilddataRchild10J020H032F043D957B465A078C080E0910G0101I0其中根结点的指针值为 6，Lchild，Rchild 分别为结点的左、右孩子指针域，data 为数据域。（1） 画出二叉树的逻辑结构。（2） 写出该树的前序、中序和后序遍历的序列。答：-前序遍历：ECBHFDJIGA中序遍历：ABCEDFHGIJ后序遍历：ECHFJIGDBA【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意 5个。解：解：3030 种。任写种。任写 5 5 个序列如下：个序列如下：（5 5，4 4，7
31、7，6 6，2 2，3 3，1 1） ；（5 5，7 7，4 4，6 6，2 2，3 3，1 1） ；（5 5，4 4，7 7，2 2，3 3，1 1，6 6） ；（5 5，7 7，6 6，4 4，2 2，3 3，1 1） ；（5 5，7 7，6 6，4 4，2 2，1 1，3 3）【13，4，5】给定关键字序列（11、7、16、4、22、13、5） ，请回答：（1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6 分） ；（2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4 分） ；答： （1）-2）-（-【14，4，6】假设一个文本使用的字符集为a,b,c,d,e,f,g,
32、字符的哈夫曼编码依次为0110，10，110，111，00，0111，010。（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；（2）若这些字符在文本中出现的频率分别为：3,35,13,15,20,5,9，求该哈夫曼树的带权路径长度。答：-【15，5，3】用公式 5.6 计算一下你的身份证号码的散列值是多少。答：公式 5.6 如下 h(key)=key mod 11;身份证号码信息如下：362429198307050010，设身份证为数字类型，对 11 求余后为 4【16，5，4】设有一组关键字29，01，13，15，56，20，87，27，69，9，10，74，散列函数为：
33、H(key) = key % 17，采用平方探测方法解决冲突。试在 0 到18 的散列地址空间中对该关键字序列构造散列表。答：散列地址散列地址0 0插入插入 2929插入插入 0101插入插入 1313插入插入 1515插入插入 5656插入插入 2020插入插入 8787插入插入 2727插入插入 69691 12 23 34 54 56 67 8 97 8 91010111112121313141415151616说明说明29无冲突无冲突无冲突无冲突无冲突无冲突无冲突无冲突d2=-10113155620872769-插入插入 9 9插入插入 1010插入插入 7474749无冲突d1=1无
34、冲突10【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从 0 开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key3）mod TableSize，要求装入因子为 0.7。答：tableSize 为 7/0.7，即 10，散列函数为 h(key)=(key*3) mod 10;下面为散列表插入过程散列地址0插入 7插入 8插入 30插入 11插入 18插入 9插入 14-1723114851867989说明无冲突无冲突无冲突无冲突d1=1无冲突无冲突3014-【18，6，3】已知一个无向图的顶点集为V0
35、，V1，V7，其邻接矩阵如下所示：V001011000V110101000V201000100V310000010V411000010V500100000V600011001V700000001(1) 画出该图的图形；(2) 给出从 V0出发的深度优先遍历序和广度优先遍历序。答：深度优先：广度优先：-【19，6，3】已知有向图如右图所示，请给出该图的（1） 每个顶点的入度和出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表；（5） 各个强连通分量答案：（1） ：节点号入度出度130222312413521623（2） ：1010011210110130101014011011510010
36、16111110(3)：-（4） ：（5） ：1：无强连通分量-【20，6，3】试利用 Dijkstra 算法求下图在从顶点 A 到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。答：初始（第 0步）第一步（选C）第二步(选 F)第三步(选 E)第四步(选 G)第五步(选D)第六步(选B)终点DPDPDPD-PDPDPDP-BCDEFG1521200015212106AAACC1521210616AAACCF1521210616AAACCF1521210616AAACCF1521210615AAACCD1521210615AAACCD【21，6，3】给出如下图所示的具有 7 个结点的网
37、 G。请：（1） 画出该网的邻接矩阵；（2） 采用 Prim 算法，从 4 号结点开始，给出该网的最小生成树（画出 Prim 算法的执行过程及最小生成树的生成示意图） 。1答：（1） ：00110001110010012100010130100011400100115000110161111110-437216056251353244-【22，7，4】给定数组48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定
38、。答：简单选择排序：不稳定48 25 6 90 17 84 62 48 27 96 49 72 17第 3 与第 1 元素互换位置，值分别为 6、486 25 48 90 17 84 62 48 27 96 49 72 17第 5 与第 2 元素互换位置，值分别为 17、256 17 48 90 25 84 62 48 27 96 49 72 17第 13 与第 3 元素互换位置，值分别为 17、486 17 17 90 25 84 62 48 27 96 49 72 48第 5 与第 4 元素互换位置，值分别为 25、906 17 17 25 90 84 62 48 27 96 49 72
39、48第 9 与第 5 元素互换位置，值分别为 27、906 17 17 25 27 84 62 48 90 96 49 72 48第 8 与第 6 元素互换位置，值分别为 48、846 17 17 25 27 48 62 84 90 96 49 72 48-第 13 与第 7 元素互换位置，值分别为 48、626 17 17 25 27 48 48 84 90 96 49 72 62第 11 与第 8 元素互换位置，值分别为 49、846 17 17 25 27 48 48 49 90 96 84 72 62第 13 与第 9 元素互换位置，值分别为 62、906 17 17 25 27 48
40、 48 49 62 96 84 72 90第 12 与第 10 元素互换位置，值分别为 72、966 17 17 25 27 48 48 49 62 72 84 96 906 17 17 25 27 48 48 49 62 72 84 96 90第 13 与第 12 元素互换位置，值分别为 90、966 17 17 25 27 48 48 49 62 72 84 90 96插入排序：是稳定的过程如下：48 25 6 90 17 84 62 48 27 96 49 72 1725 48 6 90 17 84 62 48 27 96 49 72 176 25 48 90 17 84 62 48 2
41、7 96 49 72 176 25 48 90 17 84 62 48 27 96 49 72 176 17 25 48 90 84 62 48 27 96 49 72 176 17 25 48 84 90 62 48 27 96 49 72 176 17 25 48 62 84 90 48 27 96 49 72 17-6 17 25 48 48 62 84 90 27 96 49 72 176 17 25 27 48 48 62 84 90 96 49 72 176 17 25 27 48 48 62 84 90 96 49 72 176 17 25 27 48 48 49 62 84 9
42、0 96 72 176 17 25 27 48 48 49 62 72 84 90 96 176 17 17 25 27 48 48 49 62 72 84 90 966 17 17 25 27 48 48 49 62 72 84 90 96冒泡排序:是稳定的；48 25 6 90 17 84 62 48 27 96 49 72 17第 1 与第 2 元素互换位置，值分别为 48、2525 48 6 90 17 84 62 48 27 96 49 72 17第 2 与第 3 元素互换位置，值分别为 48、625 6 48 90 17 84 62 48 27 96 49 72 17第 4 与第
43、5 元素互换位置，值分别为 90、1725 6 48 17 90 84 62 48 27 96 49 72 17第 5 与第 6 元素互换位置，值分别为 90、8425 6 48 17 84 90 62 48 27 96 49 72 17第 6 与第 7 元素互换位置，值分别为 90、6225 6 48 17 84 62 90 48 27 96 49 72 17第 7 与第 8 元素互换位置，值分别为 90、48-25 6 48 17 84 62 48 90 27 96 49 72 17第 8 与第 9 元素互换位置，值分别为 90、2725 6 48 17 84 62 48 27 90 96
44、 49 72 17第 10 与第 11 元素互换位置，值分别为 96、4925 6 48 17 84 62 48 27 90 49 96 72 17第 11 与第 12 元素互换位置，值分别为 96、7225 6 48 17 84 62 48 27 90 49 72 96 17第 12 与第 13 元素互换位置，值分别为 96、1725 6 48 17 84 62 48 27 90 49 72 17 96第 1 与第 2 元素互换位置，值分别为 25、66 25 48 17 84 62 48 27 90 49 72 17 96第 3 与第 4 元素互换位置，值分别为 48、176 25 17
45、48 84 62 48 27 90 49 72 17 96第 5 与第 6 元素互换位置，值分别为 84、626 25 17 48 62 84 48 27 90 49 72 17 96第 6 与第 7 元素互换位置，值分别为 84、486 25 17 48 62 48 84 27 90 49 72 17 96第 7 与第 8 元素互换位置，值分别为 84、276 25 17 48 62 48 27 84 90 49 72 17 96第 9 与第 10 元素互换位置，值分别为 90、49-6 25 17 48 62 48 27 84 49 90 72 17 96第 10 与第 11 元素互换位置
46、，值分别为 90、726 25 17 48 62 48 27 84 49 72 90 17 96第 11 与第 12 元素互换位置，值分别为 90、176 25 17 48 62 48 27 84 49 72 17 90 96第 2 与第 3 元素互换位置，值分别为 25、176 17 25 48 62 48 27 84 49 72 17 90 96第 5 与第 6 元素互换位置，值分别为 62、486 17 25 48 48 62 27 84 49 72 17 90 96第 6 与第 7 元素互换位置，值分别为 62、276 17 25 48 48 27 62 84 49 72 17 90
47、96第 8 与第 9 元素互换位置，值分别为 84、496 17 25 48 48 27 62 49 84 72 17 90 96第 9 与第 10 元素互换位置，值分别为 84、726 17 25 48 48 27 62 49 72 84 17 90 96第 10 与第 11 元素互换位置，值分别为 84、176 17 25 48 48 27 62 49 72 17 84 90 96第 5 与第 6 元素互换位置，值分别为 48、276 17 25 48 27 48 62 49 72 17 84 90 96第 7 与第 8 元素互换位置，值分别为 62、49-6 17 25 48 27 48
48、 49 62 72 17 84 90 96第 9 与第 10 元素互换位置，值分别为 72、176 17 25 48 27 48 49 62 17 72 84 90 96第 4 与第 5 元素互换位置，值分别为 48、276 17 25 27 48 48 49 62 17 72 84 90 96第 8 与第 9 元素互换位置，值分别为 62、176 17 25 27 48 48 49 17 62 72 84 90 96第 7 与第 8 元素互换位置，值分别为 49、176 17 25 27 48 48 17 49 62 72 84 90 96第 6 与第 7 元素互换位置，值分别为 48、17
49、6 17 25 27 48 17 48 49 62 72 84 90 96第 5 与第 6 元素互换位置，值分别为 48、176 17 25 27 17 48 48 49 62 72 84 90 96第 4 与第 5 元素互换位置，值分别为 27、176 17 25 17 27 48 48 49 62 72 84 90 96第 3 与第 4 元素互换位置，值分别为 25、176 17 17 25 27 48 48 49 62 72 84 90 96【23，7，4】给定数组48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17，请分别用堆排序、快速排序
50、和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。-答：堆排序：排序过程如下,从过程中的倒数第二次交换位置来看，堆排序是不稳定的；第 9 与第 4 互换位置,值分别为 96 , 17第 5 与第 2 互换位置,值分别为 84 , 6第 11 与第 5 互换位置,值分别为 72 , 6第 4 与第 1 互换位置,值分别为 96 , 25第 10 与第 4 互换位置,值分别为 49 , 25第 1 与第 0 互换位置,值分别为 96 , 48第 3 与第 1 互换位置,值分别为 90 , 48第 0 与第 12 互换位置,值分别为 96 ,
51、1717 90 84 48 49 72 62 48 27 17 25 6 96第 1 与第 0 互换位置,值分别为 90 , 17第 4 与第 1 互换位置,值分别为 49 , 17第 10 与第 4 互换位置,值分别为 25 , 17第 0 与第 11 互换位置,值分别为 90 , 66 49 84 48 25 72 62 48 27 17 17 90 96第 2 与第 0 互换位置,值分别为 84 , 6第 5 与第 2 互换位置,值分别为 72 , 6第 0 与第 10 互换位置,值分别为 84 , 1717 49 72 48 25 6 62 48 27 17 84 90 96-第 2
52、与第 0 互换位置,值分别为 72 , 17第 6 与第 2 互换位置,值分别为 62 , 17第 0 与第 9 互换位置,值分别为 72 , 1717 49 62 48 25 6 17 48 27 72 84 90 96第 2 与第 0 互换位置,值分别为 62 , 17第 0 与第 8 互换位置,值分别为 62 , 2727 49 17 48 25 6 17 48 62 72 84 90 96第 1 与第 0 互换位置,值分别为 49 , 27第 3 与第 1 互换位置,值分别为 48 , 27第 7 与第 3 互换位置,值分别为 48 , 27第 0 与第 7 互换位置,值分别为 49
53、, 2727 48 17 48 25 6 17 49 62 72 84 90 96第 1 与第 0 互换位置,值分别为 48 , 27第 3 与第 1 互换位置,值分别为 48 , 27第 0 与第 6 互换位置,值分别为 48 , 1717 48 17 27 25 6 48 49 62 72 84 90 96第 1 与第 0 互换位置,值分别为 48 , 17第 3 与第 1 互换位置,值分别为 27 , 17第 0 与第 5 互换位置,值分别为 48 , 66 27 17 17 25 48 48 49 62 72 84 90 96-第 1 与第 0 互换位置,值分别为 27 , 6第 4
54、与第 1 互换位置,值分别为 25 , 6第 0 与第 4 互换位置,值分别为 27 , 66 25 17 17 27 48 48 49 62 72 84 90 96第 1 与第 0 互换位置,值分别为 25 , 6第 3 与第 1 互换位置,值分别为 17 , 6第 0 与第 3 互换位置,值分别为 25 , 66 17 17 25 27 48 48 49 62 72 84 90 96第 1 与第 0 互换位置,值分别为 17 , 6第 0 与第 2 互换位置,值分别为 17 , 1717 6 17 25 27 48 48 49 62 72 84 90 96第 0 与第 1 互换位置,值分别
55、为 17 , 66 17 17 25 27 48 48 49 62 72 84 90 96快速排序：排序过程如下，17 互换位置可以看出，快速排序并不稳定；48 25 6 90 17 84 62 48 27 96 49 72 1717 25 6 90 17 84 62 48 27 96 49 72 9017 25 6 27 17 84 62 48 84 96 49 72 9017 25 6 27 17 48 62 48 84 96 49 72 906 17 25 27 17 48 62 48 84 96 49 72 906 17 17 25 27 48 62 48 84 96 49 72 90
56、-6 17 17 25 27 48 49 48 84 96 84 72 906 17 17 25 27 48 49 48 62 96 84 72 906 17 17 25 27 48 48 49 62 96 84 72 906 17 17 25 27 48 48 49 62 90 84 72 966 17 17 25 27 48 48 49 62 72 84 90 966 17 17 25 27 48 48 49 62 72 84 90 96归并排序：过程如下，从过程可以看出归并排序是稳定的48 25 6 90 17 84 62 48 27 96 49 72 1725 48 6 90 17 8
57、4 62 48 27 96 49 72 1725 48 6 90 17 84 48 62 27 96 49 72 176 25 48 90 17 84 48 62 27 96 49 72 176 25 48 90 17 48 62 84 27 96 49 72 176 25 48 90 17 48 62 84 27 49 72 96 176 17 25 48 48 62 84 90 27 49 72 96 176 17 25 48 48 62 84 90 17 27 49 72 966 17 17 25 27 48 48 49 62 72 84 90 966 17 17 25 27 48 48
58、 49 62 72 84 90 96【24，7，4】给定数组48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17，请用 3 种不同的增量序列分别进行希尔排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。-#include void Show(int arr, int n) int i; for ( i=0; i 0; gap /= 2) /步长的选取 for (i = 0; i gap; i+) /直接插入排序原理 for (j = i + gap; j n; j += gap) / 每次加上步长，即按列排序。
59、 if (arrj = 0 & arrk temp) / 记录后移，查找插入位置 arrk + gap = arrk; k -= gap; arrk + gap = temp; /找到位置插入 Show(arr,n); void main() int arr =48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17; int arr1=48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17;- int arr2=48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17; printf(-增量为 3 start -n); ShellSort(arr,13,3); printf(- printf(- ShellSort(arr1,13,6); printf(- printf(- ShellSort(arr2,13,9); printf(-增量为 3 end -n);增量为 6 start -n);增量为 6 end -n);增量为 9 start -n);增量为 9 end -n);-
