《数据结构与算法》实验大纲

1、数据结构与算法实验大纲内容提要：一、实验教学目的二、总体要求与指导三、平时实验内容与指导四、期末实验选题、报告要求与评分一、实验教学目的通过该课程的实验练习，使学生能够进一步掌握各种数据结构以及建立在此基础上的算法的基本知识；进一步理解各种基本数据结构的特点；进一步掌握数据结构与算法的关系；培养学生设计有效的算法及设计数据结构的能力。二、总体要求与指导（一）远程教育辅导教师基本条件（要求）1 .熟练掌握C语言及其调试开发环境；2 .具有用C语言编写调试中等规模以上（数千行源码）程序的经验；3 .掌握数据结构与算法课程有关的知识，具有较好的算法设计和分析的能力4 .有一定的教学经验。（二）算法实

2、验要求综述根据目前远程教育计算机专业的学生的实际情况和他们的C语言基础，严格按照本科教学要求进行算法实验上机并完成相应的实验报告，对多数学生是有一定困难的.为适应不同基础的学生循序渐进地学习，我们把实验要求分成四个层次，希望学生不断往更高层次要求自己，最终能达到本课程的实验基本要求.这四个层次的要求是：1. 以熟练使用c语言的开发环境（如TC2.0或VC6.0）为主，进行简单问题的程序设计和调试分析2 .编写主程序调用调试教材中描述并在课堂中详细讲解过的算法3 .完成习题中的算法设计题并书写实验报告4.独立完成一个小的应用系统并规范书写实验报告，以进一步提高算法描述和算法分析的能力以上1至3层

3、次作为本课程的基本要求，第4层次作为综合能力的培养与提高。实验辅导教师也可以根据当地学生的具体情况，本着能提高学生两个能力（C语言的编程和调试能力，算法设计和分析能力）的目的，循序渐进地引导学生掌握算法和程序的上机实验，并参考题集的实验报告范例和本大纲第四部分的要求书写实验报告。按教学计划，本课程实验课时为15学时，安排4次平时实验和1次期末实验。由于课时数有限，要求学生在实验前作好充分准备，否则很难在两个学时内完成相关的上机与调试。上机前的准备工作主要有两项：一是仔细阅读理解书中的相关算法，需要写解题算法的还要在纸上写好算法；二是准备好要调试算法的数据，并写好调用算法的主程序。有的实验分为A

4、B（和C）实验。A实验对应第二层次的能力培养训练，B实验对应第三层次的能力培养训练。前两个实验的一部分实验给出了整个实验过程以及参考源程序，学生只要理解并直接拷贝上机运行调试即可。前两个实验的一部分和后两个实验需要学生动手组成完整的程序，并调试运行。期末实验给出了几个可选题目，学生任意选择其中一个题目完成即可，并写出实验报告。可选题目内容和评分方法见后面“期末实验报告要求与评分”。卜面就平时实验每一层次的要求作一下说明。1. 以熟练使用c语言的开发环境（如TC2.0或VC6.0）为主，进行一般问题的程序设计和调试分析该能力实际上是预修课C语言的要求，由于有相当部分学生C语言掌握不是很好，影响了

5、数据结构算法的描述和理解.所以开始应该注意弥补C语言的能力.根据经验，C语言中函数定义与调用（形参和实参的对应等），指针，类型定义与使用、结构的定义和使用、动态内存的申请等难点却是数据结构算法描述的重点，C语言的这些障碍严重影响了学生对数据结构与算法的理解，也影响了学习数据结构的兴趣.所以实验指导教师在鼓励学生主动补习C语言知识的同时，有意识安排一些符合学生基础的程序设计练习作为本课程实验的前导补充.与本课程的相公的算法题目可以推后几周上机本实验教学计划的预备实验（即实验0。是为完成该任务而设计的。如果学生的困难比较大，尽量在教学计划时间以外鼓励学生多做上机，打好基础。2. 编写主程序调用调试

6、教材中描述并在课堂中详细讲解过的算法为加深对课堂讲解的算法的理解，选择部分（尤其是基础部分，如线性表，堆栈与队列等的顺序和链式存储的最常用的基本操作）算法进行上机调试，如第二章的InitList_SqListInsert_Sq和ListDelete_Sq一组算法和第三章的InitStack、GotTop、Push和Pop组算法等。这些算法是后面章节更复杂算法的基础（如树和图中的算法），算法的积累过程象滚雪球，所以基础必不可少。调试这些算法要注意两点。一是适当修改教材算法中的非C语言的语句和增加部分局部变量的定义。由于算法的描述是类C语言的，所以要改为完整的C语言的函数。不过需要修改（增加）的地

7、方不多。二是书写一个主程序来调用并调试描述算法的函数。主程序的设计要根据算法的功能和调试需要来编写。本实验教学计划的的A实验是为完成该任务而设计的。3. 完成习题中的算法设计题并书写实验报告我们在题集的每章的算法设计题中选择少量“小问题”的算法设计练习，以培养和提高学生自己动手写算法的能力。这些算法或者与教材中基本算法类似，或者是延伸，或者是它们的应用。做这些算法设计题时，要注意过程的完整性：题目理解、功能分析、算法思想、描述算法的C函数、调用算法的主程序、运行结果、调试过程的体会等等，都尽可能书写出来。养成书写文档的好习惯。本实验教学计划的B实验是为完成该任务而设计的。4.完成一个小的应用系

8、统并规范书写实验报告，以进一步提高算法描述和算法分析的能力本实验教学计划的期末实验是为完成该任务而设计的。学有余力的学生还可以选择一到二个题集中的实习题做。三、平时实验内容与指导实验0:C语言中函数定义与调用、指针和类型的定义与使用、结构的定义、动态内存的申请等预备知识(1)实验目的：回顾复习C语言的重点与又t点，熟悉C程序调试环境，掌握一个完整程序的构成，为以后的实验打下基础。(2)实验要求：熟练掌握C语言及其上机调试环境(如TC2.0或VC6.0)的操作使用。(3)实验内容：根据学生基础，选择若干编程题(如C语言中函数定义与调用、指针和类型的定义与使用、结构的定义、动态内存的申请等)，进行

9、编译、连接和运行调试。掌握动态跟踪调试方法。(4)实验指导：可以选择简单的问题编程，不要求算法的难度，但要能使用相关C语言成分。把注意力集中在编译和连接错误的修改，运行数据的输入输出和结果分析上。实验1:线性表的顺序表示与链式表示的插入与删除1. A实验：算法调试(1) 实验目的：加深理解线性表的顺序表示与链式表示的意义和区别，理解用它们表示时插入与删除操作的算法。(2) 实验要求：理解InitList_Sq、ListInsert_Sq、ListDelete_Sq和InitList_L、ListInsert_L、ListDelete_L等算法。(3) 实验内容：设计一组输入数据并编写主程序分别

10、调用上述算法(顺序表示的算法为InitList_Sq、ListInsert_Sq、ListDelete_Sq等，链式表示的算法为InitList_L、ListInsert_L、ListDelete_L等)，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。(4) 实验指导：顺序表示和链式表示可以分成两个程序来调试(见示例程序1和2)。教材中的算法一般要作少许修改才能运行，这些修改包括：1、算法函数中局部变量的定义，如ListInsert_Sq中的i,newbase,p,q等；2、可能出现的“类”C语言的语句，必须改为C语言语句，如数据交换语句xy;3

11、、如果采用TC作为C语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如ListInsert_Sq中的参数&L要改为*L。程序中使用L方法的修改见示例程序1。一个简单程序通常主要由三部分构成：1、常量定义(#define),类型定义(typedef)及函数原型定义(#include);2、算法函数，即InitList_Sq、ListInsert_Sq、ListDelete_Sq等；3、主函数。示例程序1,InitList_Sq、ListInsert_Sq、ListDelete_Sq在TC2.0中的调试：#includestdio.h#includemalloc.

12、h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstructElemType*elem;intlength;intlistsize;SqList;StatusInitList_Sq(SqList*L)L-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemT

13、ype);if(!L-elem)return(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;returnOK;StatusListInsert_Sq(SqList*L,inti,ElemTypee)ElemType*q,*p,*newbase;if(iL-length+1)returnERROR;if(L-length=L-listsize)newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return(OVERFLO

14、W);L-elem=newbase;L-listsize+=LISTINCREMENT;q=&(L-elemi-1);for(p=&(L-elemL-length-1);p=q;-p)*(p+1)=*p;*q=e；+L-length;returnOK;StatusListDelete_Sq(SqList*L,inti,ElemType*e)ElemType*p,*q;if(iL-length)returnERROR;p=&(L-elemi-1);*e=*p;q=(L-elem+L-length-1);for(+p;plength;returnOK;voidmain()SqListLst;int

15、i,n=15;ElemTypee;if(InitList_Sq(&Lst)=OK)for(i=1;i=n;i+)if(ListInsert_Sq(&Lst,i,i)!=OK)break;printf(n);for(i=0;iLst.length;i+)printf(i,e=%d,%dn,i,Lst.elemi);getch();if(ListDelete_Sq(&Lst,10,&e)=OK)printf(delete_elem=%dn,e);getch();for(i=0;iLst.length;i+)printf(i,e=%d,%dn,i,Lst.elemi);elseprintf(dele

16、te_elemisfailedn);在VC6.0中的调试:示例程序2,InitList_L、ListInsert_L、ListDelete_L#includemath.h#includemalloc.h#includestdio.h#defineERROR0#defineTRUE1#defineFLASE0#defineOK1#defineINFEASIBLE-1#defineOVERFLOW-2typedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;StatusListInsert_L(LinkList&L,inti,E

17、lemTypee)LinkLists,p;intj;p=L;j=0;while(p&jnext;+j;if(!p|ji-1)returnERROR;s=(Lnode*)malloc(sizeof(Lnode);if(!s)returnOVERFLOW;s-data=e;s-next=p-next;p-next=s;returnOK;StatusListDelete_L(LinkList&L,inti,ElemType&e)LinkLists,p;intj;p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)returnERROR;s=p-next;p

18、-next=s-next;e=s-data;free(s);returnOK;StatusInitList_L(LinkList&L)L=(Lnode*)malloc(sizeof(Lnode);if(L)L-next=NULL;returnOK;elsereturnERROR;intcmp(Eventa,Eventb);StatusOrderInsert_L(LinkList&L,ElemTypee,int(*cmp)(Eventa,Eventb)Lnode*p,*q;p=(Lnode*)malloc(sizeof(Lnode);if(!p)return(OVERFLOW);p-data=e

19、;q=L;while(q-next&cmp(e,q-next-data)0)q=q-next;p-next=q-next;q-next=p;returnOK;intEmptyList(LinkListL)if(!L-next)return1;return0;LinkListGetHead(LinkListL)if(!L-next)returnNULL;returnL-next;StatusDelFirst(LinkListL,LinkList&p)p=L-next;if(!p)returnERROR;L-next=p-next;returnOK;voidmain()/主程序略2.B实验：练习2

20、.11设数据表va中的数据元素递增有序，试写一个程序，将x插入到顺序表的适当位置，以保持该表的有序性。(1)实验目的：加深理解线性表的顺序表示的插入操作的算法，学会使用现有算法来解决其他问题。(2)实验要求：进一步理解InitList_Sq、ListInsert_Sq算法并在其他问题中的使用。(3)实验内容：设计一组输入数据并编写主程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。(4)实验指导：第一步，编写主程序，首先读入数据并保存在顺序表中(可以用ListInsert_Sq进行逐个插入，也可以用循环语句直接读入数组中)，然后读入一个待插入的数x;再寻找x应该插入

21、的顺序表中的位置i,然后调用ListInsert_Sq插入第i个元素即可。第二步，设计调试数据，例如一组递增有序输入数据(1,3,5,6,7,9,12)以及一个待插入的数x=8。调试程序。能够正确插入后再考验算法的“健壮性”。第三步，再取x=0或x=15或x=6进行调试，以考验算法在“边界情况”下的正确性。即插入在表头，表尾以及有重复情况的插入是否正确。还可以再考虑一组递增有序输入数据为空表时插入元素的正确性。(5)程序示例：#includestdio.h#includemalloc.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defin

22、eINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstructElemType*elem;intlength;intlistsize;SqList;StatusInitList_Sq(SqList*L)L-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L-elem)return(OVERFLOW);L-length=0;L-listsize=

23、LIST_INIT_SIZE;returnOK;StatusListInsert_Sq(SqList*L,inti,ElemTypee)ElemType*q,*p,*newbase;if(iL-length+1)returnERROR;if(L-length=L-listsize)newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return(OVERFLOW);L-elem=newbase;L-listsize+=LISTINCREMENT;q=&(L-elemi

24、-1);for(p=&(L-elemL-length-1);p=q;-p)*(p+1)=*p;*q=e;+L-length;returnOK;StatusListDelete_Sq(SqList*L,inti,ElemType*e)ElemType*p,*q;if(iL-length)returnERROR;p=&(L-elemi-1);*e=*p;q=(L-elem+L-length-1);for(+p;plength;returnOK;intFindPos_Sq(SqListLst,ElemTypee)/确定e在有序表中的位置(第i个元素之前)inti;for(i=Lst.langth-1

25、;i=0;i-)if(Lst.elemi=e)returni+2;return1;voidmain()SqListLst;inti,n=15;ElemTypee;if(InitList_Sq(&Lst)=OK)printf(输入n个有序整数n);for(i=1;i=n;i+)scanf(%d,&e);if(ListInsert_Sq(&Lst,i,e)!=OK)break;printf(n个有序整数为：n);for(i=0;iLst.length;i+)printf(i,e=%d,%dn,i,Lst.elemi);getch();printf(输入要插入的整数x:n);scanf(%d,&e)

26、;if(i=FindPos_Sq(Lst,e)/确定e在有序表中的位置if(ListInsert_Sq(&Lst,i,e)!=OK)printf(Insertingelementisfailedn);elseprintf(插入的数x以后，整数序列成为：n);for(i=0;iLst.length;i+)printf(i,e=%d,%dn,i,Lst.elemi);3.C实验：习题集P.81实习1.15一元稀疏多项式计算器(1)实验目的：加深对链表特点和使用的理解，学会灵活运用已有知识，拓广思路。(2)实验要求：对InitList_L、ListInsert_L、ListDelete_L等算法，理

27、解并分析顺序表和链表的表示多项式区别，完成程序并写出试验报告。程序的基本功能有：a)输入并建立多项式；b)输入多项式为整数序列：n,c1,e1,c2,e2,c3,e3,cn,en;其中n是多项式的项数,ci和ei是第i项的系数和指数，序列按照指数降序排列；c)计算多项式在某x处的值；以及两个多项式相加；(3) 实验内容：完成算法对InitList_L、ListInsert_L、ListDelete_L等的调试，并对用链表表示的稀疏多项式进行如下计算(多项式的输出形式尽量直观)：a) 计算多项式在x处的值：doubleValue(Polynomialp,doublex)；b) 求多项式p1(x)

28、、p2(x)的和：PolynomialP_add(Polynomialp1,Polynomialp2);(5)实验指导：第一步，定义带头结点的单链表Polynomial作为稀疏多项式的数据结构：typedefstructtermdoublecoefficient;intexponent;structterm*next;term;typedefstructPolynomialterm*t;intitems;Polynomial;第二步，写出操作算法Value、P_add。第三步，编写主程序。第四步，设计若干组数据来测试算法。比如可以用以下测试数据(习题集P.81)实验2：顺序栈的实现与插入删除操

29、作1. A实验：基本算法调试及数制的转换算法(1)实验目的：加深理解顺序栈的意义，理解用它的插入与删除操作的算法。(2)实验要求：理解InitStack、StackEmpty、Push、Pop和conversion等算法。(3)实验内容：用数制的转换算法调试顺序栈的基本操作算法。编写主程序调用数制的转换conversion算法，再由conversion调用InitStack、StackEmpty、Push、Pop算法。用不同的数转换成不同的进制调试程序并对相应的输出作出分析；修改输入数据,预期输出并验证输出的结果，加深对Push和Pop算法的理解。及函数原型定义(#include);Push

30、和 Pop conversion 等；conversion等在VC6.0中的调试:(4)实验指导：建立程序的三部分构架：1、常量定义(#define),类型定义(typedef)2、算法函数，即InitStack、StackEmpty、3、主函数。示例程序1,InitStack、StackEmpty、Push和Pop、typedef int SElemType; typedef structSElemType *base; /*SElemType *top; /* int stacksize; /*在栈构造之前和销毁之后, 栈顶指针*/base 的值为 NULL*/当前已分配的存储空间，以元素

31、为单位*/SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineOVERFLOW-1#defineERROR0typedefintStatus;#include#includeStatusInitStack(SqStack&s)s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!s.base)return(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;/*

32、InitStack*/StatusPush(SqStack&s,SElemTypee)SElemType*l_temp;if(s.top-s.base=s.stacksize)/*栈满，追加存储空间*/l_temp=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!l_temp)return(OVERFLOW);s.base=l_temp;s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*(s.top+)=e;returnOK;/*

33、Push*/StatusPop(SqStack&s,SElemType&e)if(s.top=s.base)returnERROR;e=*(-s.top);returnOK;/*Pop*/intStackEmpty(SqStacks)if(s.base=s.top)return1;elsereturn0;voidconversion。SqStacks;intN,b;SElemTypee;InitStack(s);scanf(%d%d,&N,&b);while(b=2&N)Push(s,N%b);N=N/b;while(!StackEmpty(s)Pop(s,e);printf(%d,e);/*

34、conversion*/voidmain(void)conversion。;2.B实验：练习3.15(1)实验目的：加深对堆栈理解，学会灵活运用已有知识，拓广思路。(2)实验要求：按照对InitStack、StackEmpty、Push、Pop等算法理解，理解双向栈的含义与意义，建立与调试对双向栈的基本操作算法。(3)实验内容：设计一组对双向栈的操作算法InitStackTws、StackTwsEmpty、PushTwsPopTws并编写一个主程序调试它们。设计一组输入数据并对相应的输出作出分析；着重调试空栈、满栈时的情况。(4)实验指导：第一步，理解双向栈的意义是为了节省空间，减少栈溢出(满

35、栈)机会。第二步，写出双向栈的操作算法InitStackTws、StackTwsEmpty、PushTwsPopTws第三步，编写主程序。第四步，设计若干组数据调试来算法。实验3:二叉树的二叉链表示与三种遍历实验：算法6.1,6.2,6.4的实现与调试(1)实验目的：加深对递归理解与应用，学会如何建立二叉树的一种方法，并使用递归和非递归遍历算法对二叉树进行遍历。(2)实验要求：通过调用算法6.4,建立教材中“图6.8”的二叉树结构。并调用先序遍历算法6.1和中序遍历算法6.2(也可以用递归的中序遍历算法替代)输出两个序，以验证所建立的二叉树的正确性。(3)实验内容：建立图6.8的二叉树结构，并

36、检验其先序和中序序列分别是：ABCDEGF,CBEGDFA(4)实验指导：除了需要建立书上的算法6.1,6.2,6.4(可以从课件上复制程序)，还需要做以下工作：书写主程序、建立visit()函数(可以简单到只打印节点字母)。实验4：图的邻接矩阵表示及其深度优先搜索实验：算法7.2,7.4,7.5的调试(1)实验目的：加深对图的邻接矩阵存储的理解并实现深度优先遍历图的个顶点。(2)实验要求：通过调用算法7.2,建立教材中“图7.13(a)”的无向图。并调用深度优先遍历算法7.4和7.5输出顶点序列。(3)实验内容：建立教材中“图7.13(a)”的无向图。输出从顶点1开始的深度优先遍历输出的顶点

37、序列：12485367。(4)实验指导：除了需要建立书上的算法7.2,7.4,7.5,还需要做以下工作：书写主程序、建立visit()函数(可以简单到只打印节点序号)、定义邻接矩阵的存储结构。(5)可以深入探讨的问题：最好还进行以下验证：a)深度优先遍历输出的顶点序列与起始顶点的选择有关；b)如果给定的图是非连通图，如何进行连通分量的计算？c)如果给定的图是有向图，如何进行是否为DAG1(有向无环图)的验证？以及如何输出一种拓扑序列？四、期末实验选题、报告要求与评分(一)实验选题本课程的考核实验报告可以选择以下任一实验，也可以自己选择其他实验。1、第1个可选题目设计一个模拟简单整数计算器的程序

38、。该程序可以接受整数数据，运算符可以接受包含(,),+,-,*,/,%,和A(求哥运算符,aAb=ab)的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“input.txt”.文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在Output.txt”文件的每一行中。这些结果可能是值(精确到小数点后两位)，也可能是错误信息ERRORININFIXNOTATION”输入例子：499+599+699*1(3*5*(4+8)%2)2A2A31+2(

39、2/0(2-4)人32%22%5输出例子：17970256ERRORININFIXNOTATIONERRORININFIXNOTATION-8022、计算XN算法的时间性能比较至少有两种方法计算XN,算法一是进行N-1次乘法；算法二是：如果N是偶数，XN=XN/2XN/2;如果N是奇数，XN=X(N1)/2X(N1)/2X。实际上算法二还可以分成递归和迭代两种实现方式。请选择适当的数据比较上述三种计算XN的算法的时间性能。为求得函数的运行时间，可以使用C标准库函数(time.h)如下例。注意如果一个函数运行时间太少以至于在一个CLK_TCK时钟周期内就结束，需要重复K次来求时间，最后再除以K才

40、能得到较为精确的时间值。#includeclock_tstart,stop;/*clock_t是一个关于处理器时间片(ticks)的内部类型*/doubleduration;/*记录函数function。的运行时间(秒)*/intmain()/*clock()返回从程序开始运行以来的时间片总数(ticks)*/start=clock();/*记录函数function。调用前的时间*/function。；/*这里运行你的函数*/stop=clock();/*记录函数function。调用后的时间*/duration=(double)(stop-start)/CLK_TCK;/*CLK_TCK是一

41、个内部常量=每秒的ticks数*/return1;)结果可以列出类似于如下的表格（数值的选择可以视情况自行修改）N100050001000020000400006000080000100000算法1重复次数（K）Ticks总运行时间（秒）一次时间（秒）算法2（迭代）重复次数（K）Ticks总运行时间（秒）一次时间（秒）算法2（递归）重复次数（K）Ticks总运行时间（秒）一次时间(秒)U3、第3个可选题目完成字符文章(长度可达数兆)进行Huffman编码的算法的完整程序。对给定的文本文件，进行编码和解码。具体的要求可以自主确定。4、第4个可选题目给定n个村庄之间的交通图，若村庄i和j之间有道路

42、，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？最短距离的最大值最小问题一一具体的要求可以自主确定。5、第5个可选题目设计并实现一种快速排序(quicksort)的最优化的版本，并且比较在下列组合情况下的算法的性能表现：(1) Cutoff值从020Cutoff值的作用是只有当数组的长度小于等于这个值时，才使用另一种排序方法对其排序，否则继续使用quicksort算法排序。(2)选定pivot(支点)的方法分别是“第一个元素”，“三个元素的中值”，“五个元素的中值”。对上述的测试分别要采用如下三种类型的input文件：(2) 顺序的input(3) 逆序的input(3)随机的input输入文件中测试数组的大小可以从1000个数到10000个数不等。程序输入input.txt文件,输出output文件。例如：input.txt内容如下5 /数字的个数6 4321/数字用空格分开/两组测试数据中间空一行104687513920相应的output.txt内容如下Casenumber:1Numberofelements:512345Casenumber:2Numberofelements:10012345678