《数据结构》(c语言版)测试题答案.doc 62页

'62第一章概论自测题答案姓名班级题号一二三四五六总分题分3315982015100得分一、填空题（每空1分，共33分）1.一个计算机系统包括硬件系统和软件系统两大部分。2.一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。3.计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软件，诊断程序属于系统软件（工具）。4.一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。5.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。6.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。7.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。8.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。9.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。11.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。12.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。14.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。15.一个算法的效率可分为时间效率和空间效率。16.〖00年省统考〗任何一个C程序都由一个主函数和若干个被调用的其它函数组成。17.【00年省统考题】变量一经说明，就确定该变量的取值范围（即存储单元）及确定变量所允许的运算。二、单项选择题（每小题1分，共15分）62 62（B）1.通常所说的主机是指∶A)CPUB)CPU和内存C)CPU、内存与外存D)CPU、内存与硬盘（C）2.在计算机内部，一切信息的存取、处理和传送的形式是∶A)ACSII码B)BCD码C)二进制D)十六进制（D）3.软件与程序的区别是∶A)程序价格便宜、软件价格昂贵；B)程序是用户自己编写的，而软件是由厂家提供的；C)程序是用高级语言编写的，而软件是由机器语言编写的；D)软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。（C）4.所谓“裸机”是指∶A)单片机B)单板机C)不装备任何软件的计算机D)只装备操作系统的计算机（D）5.应用软件是指∶A)所有能够使用的软件B)能被各应用单位共同使用的某种软件C)所有微机上都应使用的基本软件D)专门为某一应用目的而编制的软件（＊A）6.〖00年省统考〗C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种。（A）符号常量（B）长整型常量（C）逻辑常量（D）二进制整数（＊C）7.编译程序的功能是∶A)发现源程序中的语法错误B)改正源程序中的语法错误C)将源程序编译成目标程序D)将某一高级语言程序翻译成另一种高级语言程序（A）8.系统软件中最重要的是∶A)操作系统B)语言处理系统C)工具软件D)数据库管理系统（C）9.可移植性最好的计算机语言是∶A)机器语言B)汇编语言C)高级语言D)自然语言（B）10.非线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（C）11.数据结构中，与所使用的计算机无关的是数据的结构；A)存储B)物理C)逻辑D)物理和存储（C）12.算法分析的目的是：A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性（A）13.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性（C）14.计算机算法指的是：A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法（B）15.计算机算法必须具备输入、输出和等5个特性。62 62A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性三、简答题（每小题3分,共9分）1．我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）。2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。3.简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。四、〖00年统考题〗阅读下列C程序段，写出相应的执行结果（每小题4分，共8分）2.longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}main(){intn;longy;n=5;y=fact(n);printf(“%d,%ldn”,n,y);}答：运行结果为：5，120此题为递归运算1.printf(“Inputx”);scanf(“%d”,&x);if(x<=30)if(x>20)y=x;elseif(x>10)y=2*x;if(x>0&&x<30)printf(“x=%d,y=%d”,x,y);elseprintf(“输入数据错！”);试写出当x分别为18，8时的执行结果。答：运行结果为：x=18，y=36x=8，y=运行前的值，且从x＝30开始为数据错62 62五、【严题集1.8④】分析下面各程序段的时间复杂度（每小题5分，共20分）2.s=0;fori=0;ia.length)returnINFEASIBLE;//参数不合法else{for(count=1;count=i+1;j--)a.elem[j-1]=a.elem[j];a.length--;}returnOK;}//DeleteK答：错误有两处：①参数不合法的判别条件不完整。例如表长为10，若从第一位置（i=1）删除10个元素（k=10）,要求合理但会被判为非法。合法的入口参数条件为（0a.length)returnINFEASIBLE改为：if(！（（0=i+1;j--)a.elem[j-1]=a.elem[j];改为for(j>=i+1;j=a.length;j++)a.elem[j-1]=a.elem[j];七、编程题（每题10分，共40分）invsl(n,a)intn;ETa[];{intk;ETt;for(k=1;k<=n/2;k++){t=a[k-1];a[k-1]=a[n-k];a[n-k]=t;}return;}1.【徐士良题集，2002年1月省统考题】写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。解：输入：长度为n的线性表数组A(1:n)输出：逆转后的长度为n的线性表数组A(1:n)。C语言描述如下（其中ET为数据元素的类型）：62 622.【严题集2.6②】已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P结点后插入S结点的核心语句序列。答：此题答案不唯一，但若从已给定序列中挑选，则限制颇多。(7)Q=P;已知P结点，则不必“顺藤摸瓜”，直接链接即可。(4)S->next=P->next;(1)P->next=S;(11)P=L;(8)while(P->next!=Q)P=P->next;(10)P=Q;(4)S->next=P->next;P->next=S;3.编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。注：统计结点个数是【省统考样题】的要求，也是教材P604-6计算链表长度的要求，编程又简单，很容易作为考题。解：编写C程序如下(已上机通过)：全局变量及函数提前说明：---------------------------------#include#includetypedefstructliuyu{intdata;structliuyu*link;}test;liuyu*p,*q,*r,*head;intm=sizeof(test);voidmain()/*第一步，从键盘输入整数，不断添加到链表*/{inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;i=0;while(i!=-9999){printf("/ninputaninteger[stopby"-9999"]:");scanf("%d",&i);p->data=i;/*inputdataissaved*/p->link=(test*)malloc(m);/*m=sizeof(test));*/q=p;p=p->link;}q->link=NULL;/*原先用p->link=NULL似乎太晚！*/p=head;i=0;/*统计链表结点的个数并打印出来*/while(p->link!=NULL){printf("%d",p->data);p=p->link;i++;}printf("nnodenumber=%dn",i-1);/*结点的个数不包括-9999*/}0301陈建武：3.程序中统计结点数应是i个,而不是i-1.假设链表表长为n,i从0开始,则在统计某一结点后i加一,此时p已指向下一个结点,第一结点统计结束,i为1,p指向第二结点即当p指向尾结点(第n个结点)时i的值为n-1,while循环条件不符(指针域为null),退出循环,即得统计的结点数,为n-1.所以i的值就是结点数,不必再减一62 624.请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。答：#include/*全局变量及函数提前说明：*/#includetypedefstructliuyu{chardata;structliuyu*link;}test;liuyu*p,*q,*r,*head;intL;/*元素的个数*/intm=sizeof(test);voidbuild();/*主函数中会被调用的函数应当预先说明*/voiddisplay();intinsert_char(char,char);/*插入一个字母，在第字母Y之前，若无字母则加到末尾*/intdelet_char(char);/*删除元素X，注意保存X的前趋元素指针！*//*---------------------------------------------------------*/voidbuild()/*字母链表的生成*/{inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;for(i=1;idata=i+"a"-1;/*"a"也可用其ASCII码97来表示*/p->link=(test*)malloc(m);/*m=sizeof(test));*/p=p->link;}p->data=i+"a"-1;p->link=NULL;}/*---------------------------------------------------------*/voiddisplay()/*字母链表的输出*/{p=head;while(p->link!=NULL){printf("%c",p->data);p=p->link;}printf("%cn",p->data);}/*---------------------------------------------------------*/intinsert_char(charX,charY)/*插入一个字母X在某个字母Y之前，若找不到Y字母则加到末尾*/{p=head;r=(test*)malloc(m);r->data=X;if(head->data==Y){head=r;r->link=p;}else{while((p->data!=Y)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==Y){q->link=r;r->link=p;}else{p->link=r;r->link=NULL;}}L++;return(0);}/*---------------------------------------------------------*/intdelet_char(charX)/*删除元素X，注意保存X的前趋元素指针！*/{p=head;if(head->data==X){head=head->link;free(p);}else{while((p->data!=X)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==X){q->link=p->link;free(p);}elsereturn(-1);}L--;return(0);}62 62/*---------------------------------------------------------*/voidmain(void)/*字母线性表的生成和输出*/{L=26;build();display();printf("insertreturnvalue=%dn",insert_char("L","W"));display();printf("deletereturnvalue=%dn",delet_char("z"));display();}附：屏幕上显示的执行结果是：abcdefghijklmnopqrstuvwxyzinsertreturnvalue=0abcd9efghijklmnopqrstuvwxyzLdeletereturnvalue=0abcdefghijklmnopqrstuvwxyL62 620301陈建武修改意见：一.display()函数代码可优化为四行voiddisplay()/*字母链表的输出*/{p=head;while(p->link!=NULL)//改为while(p),因为当p指向尾结点时,p不为null,条件成立循环,//printf(),然后p被赋值为null,此时循环条件不符退出,正好.{printf("%c",p->data);p=p->link;}printf("%cn",p->data);//用while(p),此行可删}二.对intinsert_char(charX,charY),若用带头结点的链表,代码可减为10行我的程序如下(若参数没有slistp,代码要多一行,让q指向头指针)voidInsertFind(slistp,charinsertchar,charinsertpos)//字母insertpos前插入字母insertchar{slistpprior,newnode;//newnode新结点,pprior为插入位置结点的直接前驱newnode=newliuyu;//为新结点分配内存newnode->data=insertchar;//对结点数据域初始化while(p)//当p指向尾结点时最后一次循环{pprior=p;//pprior从头指针开始,指向p的直接前驱p=p->next;//p从首元结点开始,不断前移,直至最后,p为nullif(p&&(p->data==insertpos))//当p为null或者结点p的数据域为所要插入的字母,break;//则退出循环}newnode->next=pprior->next;//在找到的位置前插入pprior->next=newnode;}对删除结点的操作,若有头结点,同样可以减少代码,由此可见创建一个头结点对简化程序有很大的帮助.上面的观点,仅供参考,不对之处,请指教!62 62第3章栈和队列自测卷答案姓名班级题号一二三四五六总分题分151020202015100得分一、填空题（每空1分，共15分）1.【李春葆】向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。3.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.在一个循环队列中，队首指针指向队首元素的前一个位置。5.在具有n个单元的循环队列中，队满时共有n-1个元素。6.向栈中压入元素的操作是先移动栈顶指针，后存入元素。7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。8.〖00年统考题〗带表头结点的空循环双向链表的长度等于0。L=head头结点R=headhead解：二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（×）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（×）2.在表结构中最常用的是线性表，栈和队列不太常用。错，不一定吧？调用子程序或函数常用，CPU中也用队列。（√）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（×）5.栈和链表是两种不同的数据结构。错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。（×）6.栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（√）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（×）9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。（×）10.一个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。三、单项选择题（每小题1分，共20分）（B）1.〖00年元月统考题〗栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（C）2.〖李春葆〗若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．iＢ．n=iＣ．n-i+1Ｄ．不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的，那么输入顺序必定是1，2，3，…62 62，n，则出栈的序列是n，…，3，2，1。（B）3.〖李春葆〗判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（B）4.〖李春葆〗判定一个队列QU（最多元素为m0）为满队列的条件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1（D）5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n6.【98初程P71】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是C，第二次出队得到的元素是D。经操作后，最后在栈中或队中的元素还有E个。供选择的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：ABCDE＝2,4,1,2,27.【94初程P75】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是A。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值B；从栈中弹出（POP）一个元素时，变量T的值C。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是D，变量T的值是E。供选择的答案：A：①先进先出②后进先出③进优于出④出优于进⑤随机进出B，C：①加1②减1③不变④清0⑤加2⑥减2D：①a,b②b,c③c,a④b,a⑤c,b⑥a,cE：①n+1②n+2③n④n-1⑤n-2答案：ABCDE=2,2,1,6,4注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为n，向地址的低端递减生成，称为向下生成堆栈。8.【91初程P77】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先判别栈是否B。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D分别设在这片内存空间的两端，这样，只有当E时，才产生上溢。供选择的答案：A，B：①空②满③上溢④下溢C：①n-1②n③n+1④n/262 62D：①长度②深度③栈顶④栈底E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答案：ABCDE＝2,1,2,4,3四、简答题（每小题4分，共20分）1.【严题集3.2①和3.11①】说明线性表、栈与队的异同点。刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2.【统考书P604-11，难于严题集3.1①】设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。刘答：至少有14种。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,33.【刘自编】假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是……）若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。4.【统考书P604-13】顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：①设置一个布尔变量以区别队满还是队空；②浪费一个元素的空间，用于区别队满还是队空。③使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear队满标志是：f=(r+1)%N5.【统考书P604-14】设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32五、阅读理解（每小题5分，共20分。至少要写出思路）1.【严题集3.7①】按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教材例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：62 62A－B×C/D+E↑F答：1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;Charx,y;InitStack(S);X=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};Printf(x);}答：输出为“stack”。2.【严题集3.12②】写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,’y’);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);62 62}答：输出为“char”。1.【严题集3.13②】简述以下算法的功能（栈和队列的元素类型均为int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。六、算法设计（每小题5分，共15分。至少要写出思路）1.【李春葆及严题集3.19④】假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。答：用堆栈st进行判定，将(、[或{入栈，当遇到}、]或)时，检查当前栈顶元素是否是对应的(、[或{，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时，若栈为空表示括号正确配对，否则不配对。编程后的整个函数如下（李书P31—32）#definem0100/*m0为算术表达式中最多字符个数*/correct(exp,tag)charexp[m0];inttag;{charst[m0];inttop=0,i=1;tag=1;while(i<=m0&&tag){if(exp[i]==‘(‘||exp[i]==’[‘||exp[i]==’{‘）/*遇到‘(‘、’[‘或’{‘，则将其入栈*/{top++;st[top]=exp[i];}if(exp[i]==’)’)/*遇到’)’，若栈顶是‘(‘，则继续处理，否则以不配对返回*/if(st[top]==‘(‘)top--;elsetag=0;if(exp[i]==’)’)/*遇到’]’，若栈顶是‘[‘，则继续处理，否则以不配对返回*/if(st[top]==‘[‘]top--;elsetag=0;if(exp[i]==’)’)/*遇到’}’，若栈顶是‘{‘，则继续处理，否则以不配对返回*/if(st[top]==‘{‘top--;elsetag=0;i++;}if(top>0)tag=0;/*若栈不空，则不配对*/}严题集对应答案：3.1962 62StatusAllBrackets_Test(char*str)//判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=="("||*p=="["||*p=="{")push(s,*p);elseif(*p==")"||*p=="]"||*p=="}"){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==")"&&c!="(")returnERROR;if(*p=="]"&&c!="[")returnERROR;if(*p=="}"&&c!="{")returnERROR;//必须与当前栈顶括号匹配}}//forif(!StackEmpty(s))returnERROR;returnOK;}//AllBrackets_Test2.【统考书P604-15】假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。解：这就是解决队满队空的三种办法之①设置一个布尔变量以区别队满还是队空（其他两种见简答题）；思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1；若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。3.【严题集3.31③】试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。答：编程如下：intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0{  InitStack(S);InitQueue(Q);  while((c=getchar())!="@")  {    Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构  }  while(!StackEmpty(S))  {    Pop(S,a);DeQueue(Q,b));    if(a!=b)returnERROR;  }  returnOK;}//Palindrome_Test62 62第4～5章串和数组自测卷答案姓名班级题号一二三四五总分题分2015201530100得分一、填空题（每空1分，共20分）1.不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。（对应严题集4.1①，简答题：简述空串和空格串的区别）2.设S=“A;/document/Mary.doc”，则strlen(s)=20,“/”的字符定位的位置为3。4.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。5.设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第6次匹配成功。6.若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。7.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288B；末尾元素A57的第一个字节地址为1282；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1192；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276。8.〖00年计算机系考研题〗设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为9188。答：考虑0行0列，（58列×61行＋32行）×2字节＋基址2048=9188？？9.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。10.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】===(a,b);//头元素不必加括号（2）GetHead【GetTail【((a,b),(c,d))】】===(c,d);（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===b;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】===（d）;二、单选题（每小题1分，共15分）（B）1.〖李〗串是一种特殊的线性表，其特殊性体现在：Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符（B）2.〖李〗设有两个串p和q，求q在p中首次出现的位置的运算称作：Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长（D）3.〖李〗设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF解：con(x,y)返回x和y串的连接串，即con(x,y)＝‘ABCDEFGPQRST’；subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，则subs(s1,2,len(s2))＝subs(s1,2,5)=’BCDEF’;subs(s1,len(s2),2)＝subs(s1,5,2)=’EF’;62 62所以con(subs(s1,2,len(s2)),subs(s1,len(s2),2))＝con(’BCDEF’,’EF’)之连接，即BCDEFEF（A）4.〖01年计算机系考研题〗假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。（无第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．答案A,B,C均不对答：（57列×60行＋31行）×2字节＋10000=16902(A)(B)5.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j解：注意B的下标要求从1开始。先用第一个元素去套用，可能有B和C；再用第二个元素去套用B和C，B=2而C＝3（不符）；所以选B6.【91初程P78】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是A。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是B和C。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是D和E。供选择的答案A～E：①28②44③76④92⑤108⑥116⑦132⑧176⑨184⑩188答案：ABCDE=8,3,5,1,67.【94程P12】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是A个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是B。若按行存储，则A[2,4]的第一个字节的地址是C。若按列存储，则A[5,7]的第一个字节的地址是D。供选择的答案A～D：①12②66③72④96⑤114⑥120⑦156⑧234⑨276⑩282（11）283（12）288答案：ABCD=12,10,3,9三、简答题（每小题5分，共15分）1.KMP算法的设计思想是什么？它有什么优点？2.（软件技术？）已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；62 62按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K按列存储的元素地址公式是：Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K3.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。四、计算题（每题5分，共20分）1.设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’,求Replace(s,’STUDENT’,q)和Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。解：①Replace(s,’STUDENT’,q)＝’IAMAWORKER’②因为SubString(s,6,2)＝‘A’；SubString(s,7,8)＝‘STUDENT’Concat(t,SubString(s,7,8))＝’GOODSTUDENT’所以Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝‘AGOODSTUDENT’2.【严题集4.8②】已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。解：（由演示程序得知）nextval函数值为0102101040在第12个字符处发现匹配！s=’ADBADABBAABADABBADADA’pat=’ADABBADADA’3.（P604-18）用三元组表表示下列稀疏矩阵：解：参见填空题4.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。所以（1）可列表为：（2）可列表为：8866416-225943565353233685467858124.（P604-19）下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。62 62解：（1）为6×4矩阵，非零元素有6个，但其中一数下标有误？（2）为4×5矩阵，非零元素有5个10000000900800600700020012000改为2,1,1230000004006016000五、算法设计题（每题10分，共30分）1.【严题集4.12③】编写一个实现串的置换操作Replace(&S,T,V)的算法。解：intReplace(Stringtype&S,StringtypeT,StringtypeV);//将串S中所有子串T替换为V,并返回置换次数{for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++)//注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T)),T))//找到了与T匹配的子串{//分别把T的前面和后面部分保存为head和tailStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail));//把head,V,tail连接为新串i+=Strlen(V);//当前指针跳到插入串以后n++;n++;}//ifreturnn;}//Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S="place",T="ace",V="face",则省掉i+=Strlen(V);运行时会出现什么结果?2.【全国专升本资格考试】写出将字符串反序的递归或递推算法，例如字符串为“abcsxw”，反序为“wxscba”(注：这也是严题集4.10③编写对串求逆的递推算法)算法思路：①假定用单链表结构存储字符串；if没有到尾部字符就不停调用自身函数，直至到达末尾，再从尾部返回并打印字符；递归算法的一般形式：（殷人凯题集P102）voidp(参数表){if（递归结束条件）可直接求解步骤；基本项elsep（较小的参数）；归纳项}DLR(x*root){if(!root)return(0);printf(“%d”,root->data);DLR(root->lchild);DLR(root->rchild);}否则就打印当前字符并返回。Invert(stringlistnode*p){if(!p)return(0);elseInvert(p->next);62 62printf(“%c”,p->data)}如果当前串长为0,则return(-1)否则开始递归：if串没有到末尾，则P=P->next;再调用invert(s);elseprintf(p->data);return4.10voidString_Reverse(Stringtypes,Stringtype&r)//求s的逆串r{StrAssign(r,"");//初始化r为空串for(i=Strlen(s);i;i--){StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c));//把s的字符从后往前添加到r中/这是递推算法？}}//String_Reverse1.【严题集5.18⑤】试设计一个算法，将数组An中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)解：5.18分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:n=15,k=6,则p=3.第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]./已“顺便”移动了A[6]、A[12]…第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.程序如下：voidRSh(intA[n],intk)//把数组A的元素循环右移k位,只用一个辅助存储空间{for(i=1;i<=k;i++)if(n%i==0&&k%i==0)p=i;//求n和k的最大公约数pfor(i=0;i0)个结点的完全二叉树的深度为。(Ａ)élog2(n)ù(Ｂ)ëlog2(n)û(Ｃ)ëlog2(n)û+1(Ｄ)élog2(n)+1ù注：éxù表示不小于x的最小整数；ëxû表示不大于x的最大整数，它们与[]含义不同！（A）4．把一棵树转换为二叉树后，这棵二叉树的形态是。（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子5.【94程P11】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。树是结点的有限集合，它A根结点，记为T。其余的结点分成为m（m≥0）个B的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的C。供选择的答案A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B:①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C：①权②维数③次数④序答案：ABC＝1，1，36.【95程P13】从供选择的答案中，选出应填入下面叙述？62 62内的最确切的解答，把相应编号写在答卷的对应栏内。二叉树A。在完全的二叉树中，若一个结点没有B，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C，而N的右子女是它在原树里对应结点的D。供选择的答案A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构B:①左子结点②右子结点③左子结点或者没有右子结点④兄弟C～D：①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：A=B=C=D＝答案：ABCDE＝2，1，1，3四、简答题（每小题4分，共20分）1.【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。C的结点类型定义如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root){printf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：1.对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；2.假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。（共8分）ABDCFGE二叉树B解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：ABCCEEBADFFDGG特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。3.〖01年计算机研题〗【严题集6.27③】给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。DACFEGBHI4.【计算机研2000】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。62 6228254055603308542825334060085455NILNIL2825334060085455解：要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：5540256028083354五、阅读分析题（每题5分，共20分）1.（P604-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA2.（P604-27）把如图所示的树转化成二叉树。答：注意全部兄弟之间都要连线（包括度＝2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。ABECKFHDLGIMJBiTreeInSucc(BiTreeq){//已知q是指向中序线索二叉树上某个结点的指针，//本函数返回指向*q的后继的指针。r=q->rchild;if(!q->rtag)//若q内装右孩子,r不一定为后继结点,需要找到中序遍历q的右子树时第一个访问的结点while(!r->rtag)r=r->rchild;returnr;//}//ISucc答：这是找结点后继的程序。共有3处错误。注：当rtag＝1时说明内装后继指针，可直接返回，第一句无错。当rtag＝0时说明内装右孩子指针，但孩子未必是后继，需要计算。中序遍历应当先左再根再右，所以应当找左子树直到叶子处。r=r->lchild;直到LTag=1；应改为：while(!r->Ltag)r=r->Lchild;3.【严题集6.17③】阅读下列算法，若有错，改正之。62 624.【严题集6.21②】画出和下列二叉树相应的森林。答案：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）1.【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。可作为实验二内容。核心部分为：DLR(liuyu*root)/*中序遍历递归函数*/{if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL)){sum++;printf("%dn",root->data);}DLR(root->lchild);DLR(root->rchild);}return(0);}法二：intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree但上机时要先建树！①打印叶子结点值（并求总数）思路：先建树，再从遍历过程中打印结点值并统计。步骤1键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。叶子结点值应该是4，9,13,21,总数应该是4.62 621271721116214913编程：生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下：说明部分为：#include#includetypedefstructliuyu{intdata;structliuyu*lchild,*rchild;}test;liuyu*root;intsum=0;intm=sizeof(test);voidinsert_data(intx)/*如何生成二叉排序树？参见教材P43C程序*/{liuyu*p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root){root=s;return;}p=root;while(p)/*如何接入二叉排序树的适当位置*/{q=p;if(p->data==x){printf("dataalreadyexist!n");return;}elseif(xdata)p=p->lchild;elsep=p->rchild;}if(xdata)q->lchild=s;elseq->rchild=s;}DLR(liuyu*root)/*中序遍历递归函数*/{if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL)){sum++;printf("%dn",root->data);}DLR(root->lchild);DLR(root->rchild);}return(0);}main()/*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/{inti,x;i=1;root=NULL;/*千万别忘了赋初值给root!*/do{printf("pleaseinputdata%d:",i);i++;scanf("%d",&x);/*从键盘采集数据，以-9999表示输入结束*/if(x==-9999){DLR(root);printf("nNowoutputcountvalue:%dn",sum);return(0);}elseinsert_data(x);}/*调用插入数据元素的函数*/while(x!=-9999);return(0);}62 62执行结果：若一开始运行就输入-9999，则无叶子输出，sum=0。2.【全国专升本统考题】写出求二叉树深度的算法，先定义二叉树的抽象数据类型。（10分）或【严题集6.44④】编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。但注意，递归时应当从叶子开始向上计数，否则不易确定层数。intdepth(liuyu*root)/*统计层数*/{intd,p;/*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root==NULL)return(p);/*找到叶子之后才开始统计*/else{d=depth(root->lchild);if(d>p)p=d;/*向上回朔时，要挑出左右子树中的相对大的那个深度值*/d=depth(root->rchild);if(d>p)p=d;}p=p+1;return(p);}法二：intGet_Sub_Depth(BitreeT,intx)//求二叉树中以值为x的结点为根的子树深度{if(T->data==x){printf("%dn",Get_Depth(T));//找到了值为x的结点,求其深度exit1;}}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子树中继续寻找}}//Get_Sub_DepthintGet_Depth(BitreeT)//求子树深度的递归算法62 62{if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth附：上机调试过程步骤1键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。层数应当为41281721116214913步骤2：执行求深度的函数，并打印统计出来的深度值。完整程序如下：#include#includetypedefstructliuyu{intdata;structliuyu*lchild,*rchild;}test;liuyu*root;intsum=0;intm=sizeof(test);voidinsert_data(intx)/*如何生成二叉排序树？参见教材P43C程序*/{liuyu*p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root){root=s;return;}p=root;while(p)/*如何接入二叉排序树的适当位置*/{q=p;if(p->data==x){printf("dataalreadyexist!n");return;}elseif(xdata)p=p->lchild;elsep=p->rchild;}if(xdata)q->lchild=s;elseq->rchild=s;}intdepth(liuyu*root)/*统计深度*/{intd,p;/*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root==NULL)return(p);/*找到叶子之后才开始统计*/else{d=depth(root->lchild);if(d>p)p=d;/*向上回朔时，要挑出左右子树中的相对大的那个深度值*/d=depth(root->rchild);62 62if(d>p)p=d;}p=p+1;return(p);}voidmain()/*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/{inti,x;i=1;root=NULL;/*千万别忘了赋初值给root!*/do{printf("pleaseinputdata%d:",i);i++;scanf("%d",&x);/*从键盘采集数据，以-9999表示输入结束*/if(x==-9999){printf("nNowoutputdepthvalue=%dn",depth(root));return;}elseinsert_data(x);}/*调用插入数据元素的函数*/while(x!=-9999);return;}执行结果：3.【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。或：按层次输出二叉树中所有结点；解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。level(liuyu*T)/*liuyu*T,*p,*q[100];假设max已知*/{intf,r;f=0;r=0;/*置空队*/r=(r+1)%max;q[r]=T;/*根结点进队*/while(f!=r)/*队列不空*/{f=(f+1%max);p=q[f];/*出队*/printf("%d",p->data);/*打印根结点*/if(p->lchild){r=(r+1)%max;q[r]=p->lchild;}/*若左子树不空，则左子树进队*/if(p->rchild){r=(r+1)%max;q[r]=p->rchild;}/*若右子树不空，则右子树进队*/}return(0);62 62}法二：voidLayerOrder(BitreeT)//层序遍历二叉树{InitQueue(Q);//建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}//LayerOrder可以用前面的函数建树，然后调用这个函数来输出。完整程序如下（已上机通过）#include#include#definemax50typedefstructliuyu{intdata;structliuyu*lchild,*rchild;}test;liuyu*root,*p,*q[max];intsum=0;intm=sizeof(test);voidinsert_data(intx)/*如何生成二叉排序树？参见教材P43C程序*/{liuyu*p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root){root=s;return;}p=root;while(p)/*如何接入二叉排序树的适当位置*/{q=p;if(p->data==x){printf("dataalreadyexist!n");return;}elseif(xdata)p=p->lchild;elsep=p->rchild;}if(xdata)q->lchild=s;elseq->rchild=s;}level(liuyu*T)/*liuyu*T,*p,*q[100];假设max已知*/{intf,r;f=0;r=0;/*置空队*/r=(r+1)%max;q[r]=T;/*根结点进队*/while(f!=r)/*队列不空*/{f=(f+1%max);p=q[f];/*出队*/62 62printf("%d",p->data);/*打印根结点*/if(p->lchild){r=(r+1)%max;q[r]=p->lchild;}/*若左子树不空，则左子树进队*/if(p->rchild){r=(r+1)%max;q[r]=p->rchild;}/*若右子树不空，则右子树进队*/}return(0);}voidmain()/*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/{inti,x;i=1;root=NULL;/*千万别忘了赋初值给root!*/do{printf("pleaseinputdata%d:",i);i++;scanf("%d",&x);/*从键盘采集数据，以-9999表示输入结束*/if(x==-9999){printf("nNowoutputdatavalue:n",level(root));return;}elseinsert_data(x);}/*调用插入数据元素的函数*/while(x!=-9999);return;}4.（P604-25）已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。答：结点i的左孩子为2i，右孩子为2i+1;用循环算法打印即可。由于是完全二叉树，不必担心中途会出现孩子为null的情况。5.【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树。答：intIsFull_Bitree(BitreeT)//判断二叉树是否完全二叉树,是则返回1,否则返回0{InitQueue(Q);flag=0;EnQueue(Q,T);//建立工作队列while(!QueueEmpty(Q)){{DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);//不管孩子是否为空,都入队列}}//whilereturn1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.62 626.【严题集6.26③】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】,……19,21,3201010119213201010171060123（100）（40）（60）192132（28）（17）（11）7106（5）23方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码62 62第7章图自测卷解答姓名班级题号一二三四五总分题分1620241030100得分一、单选题（每题1分，共16分）前两大题全部来自于全国自考参考书！（C）1.在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2B.1C.2D.4（B）2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B.1C.2D.4（B）3.有8个结点的无向图最多有条边。A．14B.28C.56D.112（C）4.有8个结点的无向连通图最少有条边。A．5B.6C.7D.8（C）5.有8个结点的有向完全图有条边。A．14B.28C.56D.112（B）6.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图（A）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图A．0243156B.0136542C.0423165D.0361542（C）8.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（D）9.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A．0243156B.0135642C.0423165D.0134256（B）10.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243651B.0136425C.0423156D.0134256（C）11.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243165B.0135642C.0123465D.012345662 62（D）12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是A．0132B.0231C.0321D.0123（A）13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A．0321B.0123C.0132D.0312（A）14.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（D）15.广度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（A）16.任何一个无向连通图的最小生成树A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1.图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。3.如果n个顶点的图是一个环，则它有n棵生成树。4.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。6.设有一稀疏图G，则G采用邻接表存储较省空间。7.设有一稠密图G，则G采用邻接矩阵存储较省空间。8.图的逆邻接表存储结构只适用于有向图。9.已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。10.图的深度优先遍历序列不是惟一的。11.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储时，该算法的时间复杂度为O(n+e)。62 6212.n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储，该算法的时间复杂度为O(n+e)。13.图的BFS生成树的树高比DFS生成树的树高小或相等。14.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。15.若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。16.若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。17.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。18.拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。三、简答题（每题6分，共24分）1.【严题集7.1①】已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。答案：62 622.【严题集7.7②】请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。最小生成树：3.【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。62 624.【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。答案暂未提供。62 62四、【2001年计考研题】给定下列网G:（10分）1试着找出网G的最小生成树，画出其逻辑结构图；2用两种不同的表示法画出网G的存储结构图；3用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。五、算法设计题（每题10分，共30分）1.【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;mnextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList2.【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)。（刘提示：删除所有从第i个顶点出发的边的方法是将邻接矩阵的第i行全部置0）解：//本题中的图G均为有向无权图,其余情况容易由此写出StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w)62 62{if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc3.【严题集7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径{{if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求elseif(k>0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一}//forvisited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中}//else62 62return0;//没找到}//exist_path_len62 62第8章查找自测卷答案姓名班级A题号一二三四五总分题分1027162423100得分一、填空题（每空1分，共10分）1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。2.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7。解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。6.散列法存储的基本思想是由关键字的值决定数据的存储地址。7.有一个表长为m的散列表，初始状态为空，现将n（nhigh)return0;//查找不到时返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive2.【严题集9.31④】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”（刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。若要采用递归算法，建议您采用如下的函数首部：boolBisortTree(BiTreeT,BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。（或者直接存储前驱的数值，随时与当前根结点比较）一个漂亮的算法设计如下：intlast=0,flag=1;//last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树，是则返回1，否则返回0{if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->datadata;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree3.【严题集9.22④】已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。解：设计哈希表的步骤为：a)根据所选择的处理冲突的方法求出装载因子a的上界；b)由a值设计哈希表的长度m；c)根据关键字的特性和表长m选定合适的哈希函数。刘注：要求ASL≤3，则m必然要尽量长，以减少冲突；4.【严题集9.44④】已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。解：注意此题给出的条件：装载因子a〈1,则哈希表未填满。由此可写出下列形式简明的算法：voidPrintWord(HashTableht){//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。for(i=1;i<=26;i++){j=i;While(ht.elem[j].key){62 62if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);j=(j+1)%m;}}}//PrintWord62 62第9章排序自测卷答案姓名班级题号一二三四五总分题分241836814100得分一、填空题（每空1分，共24分）1.大多数排序算法都有两个基本的操作：比较（两个关键字的大小）和移动（记录或改变指向记录的指针）。2.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较3次。(可约定为，从后向前比较)3.在插入和选择排序中，若初始数据基本正序，则选用插入排序（到尾部）；若初始数据基本反序，则选用选择排序。4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。5.对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2)。若对其进行快速排序，在最坏的情况下所需要的时间是O(n2)。6.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间是O(n)。7．【计研题2000】对于n个记录的表进行2路归并排序，整个归并排序需进行log2n趟（遍），共计移动nlog2n次记录。(即移动到新表中的总次数！共log2n趟，每趟都要移动n个元素)8.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是H,C,Q,P,A,M,S,R,D,F,X,Y；初始步长为4的希尔（shell）排序一趟的结果是P,A,C,S,Q,D,F,X,R,H,M,Y；二路归并排序一趟扫描的结果是H,Q,C,Y，A,P,M,S,D,R,F,X；快速排序一趟扫描的结果是F,H,C,D,P,A,M,Q,R,S,Y，X；堆排序初始建堆的结果是A,D,C,R,F,Q,M,S,Y，P,H,X。9.在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。二、单项选择题（每小题1分，共18分）（C）1．将5个不同的数据进行排序，至多需要比较次。Ａ.8Ｂ.9Ｃ.10Ｄ.25（C）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为Ａ.希尔排序Ｂ.冒泡排序Ｃ.插入排序Ｄ.选择排序（D）3．62 62排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ.希尔排序Ｂ.归并排序Ｃ.插入排序Ｄ.选择排序（C）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。Ａ.从小到大排列好的Ｂ.从大到小排列好的Ｃ.元素无序Ｄ.元素基本有序（D）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为Ａ.n+1Ｂ.nＣ.n-1Ｄ.n(n-1)/2(前3个答案都太小了)（C）6．快速排序在下列哪种情况下最易发挥其长处。Ａ.被排序的数据中含有多个相同排序码Ｂ.被排序的数据已基本有序Ｃ.被排序的数据完全无序Ｄ.被排序的数据中的最大值和最小值相差悬殊（B）7．【计研题2001】对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)（C）8．若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为Ａ.38,40,46,56,79,84Ｂ.40,38,46,79,56,84Ｃ.40,38，46,56,79,84Ｄ.40,38,46,84,56,79（A&D）9．【计研题2001】在最好情况下，下列排序算法中排序算法所需比较关键字次数最少。A．冒泡B．归并C．快速D．直接插入(仅n—1次！)（C）10．【计研题2001】置换选择排序的功能是。（置换选择排序＝简单选择排序？）A．选出最大的元素B．产生初始归并段C．产生有序文件D．置换某个记录（A）11．将5个不同的数据进行排序，至少需要比较次。Ａ.4Ｂ.5Ｃ.6Ｄ.7（D）12．下列关键字序列中，是堆。Ａ.16,72,31,23,94,53Ｂ.94,23,31,72,16,53Ｃ.16,53,23,94,31,72Ｄ.16,23,53,31,94,72（B）13．堆是一种排序。Ａ.插入Ｂ.选择Ｃ.交换Ｄ.归并（C）14．堆的形状是一棵Ａ.二叉排序树Ｂ.满二叉树Ｃ.完全二叉树Ｄ.平衡二叉树（B）15．若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为Ａ.79,46,56,38,40,84Ｂ.84,79,56,38,40,46Ｃ.84,79,56,46,40,38Ｄ.84,56,79,40,46,38（B）16．下述几种排序方法中，平均查找长度（ASL）最小的是Ａ.插入排序Ｂ.快速排序Ｃ.归并排序Ｄ.选择排序（C）17．下述几种排序方法中，要求内存最大的是Ａ.插入排序Ｂ.快速排序Ｃ.归并排序Ｄ.选择排序62 62（B）18．目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是Ａ.插入排序Ｂ.二分插入排序Ｃ.快速排序Ｄ.冒泡排序三、简答题（每小题4分，共36分）1.【全国专升本题】已知序列基本有序，问对此序列最快的排序方法是多少，此时平均复杂度是多少？答：插入排序和冒泡应该是最快的。因为只有比较动作，无需移动元素。此时平均时间复杂度为O(n)2.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用哪种排序方法？答：用堆排序或锦标赛排序最合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)；若用冒泡排序则需时n!/(n-10)!3.用某种排序方法对线性表（25,84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：25,84，21,47,15,27,68,35,20→20,15,21,25，47,27,68,35,84→15,20,21,25，35,27,47,68,84→15,20,21,25，27,35,47,68,84，问采用的是什么排序方法？答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。4.对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次快速排序则看按什么数据来分子表。如果按100来分，则很惨，也会是n(n-1)/2！若按中间数据50或51来分表，则：第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（21-1）第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（22-1）第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（23-1）第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（24-1）……第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（26-1）第7轮则能全部确定，（因为27=128），在100个子表中比较和交换了n－（100－1）个元素；比较和交换总次数为：7n－(21－1＋22－1＋23－1……＋26－1＋100－1)＝7n+7－(1＋2＋4＋……＋64+100)=7n－(8+16+32+164)=700-220=480次若从中间选择初始元素，则ASL=（n+1）log2n－(21＋22＋23+……＋2m)=nlog2n+log2n－(21＋22＋23+……＋n)≈O（nlog2n）5.【全国专升本试题】【严题集10.15④】设有n个值不同的元素存于顺序结构中，试问能否用比2n-3少的比较次数选出这n个元素中的最大值和最小值？若能请说明如何实现（不需写算法）。在最坏情况下至少需进行多少次比较。（或问：对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?）答：若用冒泡排序法，求最大值需n-1次比较；第二趟改为从n-1开始求最小值，需n-2次比较，合计2n-3次。显然本题意图是放弃冒泡排序，寻找其他方法。法1：一个简单的办法是，在一趟比较时，将头两个元素分别作为最大和最小值的暂存内容，将其余n-2个元素与其相比，具体可设计为：第1步：a1a2?YES则直接替换a2，NO则再比较a1，1～2次；62 62第3步：a4>a2?YES则直接替换a2，NO则再比较a1，1～2次；……第n-1步：an>a2?YES则直接替换a2，NO则再比较a1，1～2次；合计：（n-2）×（1～2）＋1=(n-1)~(2n-3)≤2n-3最好情况至少需要n-1次比较，最坏情况需2n-3次。法2：借用快速排序第一趟思想：以a1为支点，将序列分成两个子表。这一趟需要n-1次比较；然后，在左边的子表中求最小值，冒泡一趟需要y-1次；在右边的子表中求最大值，冒泡一趟需要z-1次；合计需要(n-1)+(y-1)+(z-1)=n+y+z-3因为y+z+1=n,所以总次数＝2n－4≤2n－3!!!!!!!!!!!但最坏情况下仍为为2n-3次，即一趟完毕后仍为单子表的情况。怎么办？有无更好的办法？法3：能否用锦标赛排序思路？求最大值等于求冠军，需要n—1次比较；但接着求最小值，等于在n/2个叶子中比较即可。编程也不复杂：可设计为，第一趟：n个数据两两比较（共n/2次），小者放偶数位，大者放奇数位；第二趟：对奇数位元素继续两两比较（n/4次）；对偶数位元素也两两比较（n/4次）；合计n/2次；第三趟：对奇数位元素继续两两比较（n/23次）；对偶数位元素也两两比较（n/23次）；合计n/22次；第四趟：对奇数位元素继续两两比较（n/24次）；对偶数位元素也两两比较（n/24次）；合计n/23次；……第log2n趟：对奇数位元素继续两两比较（n/2log2n次＝1）；对偶数位元素也两两比较（1次）；合计2次；全部比较次数为：2+4+8+……＋n/2次≤2n-3（n>1）用二进制性质即可证明？因为20+21+…2k-2+2k-1<2k，即21+…2k-2+2k-1<2k—1<2k—1+2k—2(n=2k,当k＝1，即n=2时为极端情况，1＝1;n=3时，1.5<3k=2时，即n=4时，2<56.【成教考题】将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需要比较2n-1次，请说明这两种情况发生时，两个被归并的表有何特征?答：最少的比较次数是这样一种情况：若A表所有元素都小于（或大于）B表元素，则A1比较完B1～Bn之后，直接拼接即可。最多比较次数的情况应该是A、B两表互相交错，此时需要穿插重排。则A表的每个元素都要与B表元素相比，A1与B1相比，能确定其中一个元素的位置；剩下一个还要与另一表中下一元素再比较一次，即：在表A或表B的n个元素中，除了最后一个元素外，每个元素都要比较2次！最坏情况总共为2n—1次。62 626.【严题集10.11②】试问：按锦标赛排序的思想，决出8名运动员之间的名次排列，至少需编排多少场次的比赛（应考虑最坏的情况）？刘答：不能简单地用(n-1)+(n-2)log2n来计算比赛场次。要特别注意，随着n/2的叶子结点被调整完毕之后，树的深度会逐层减少！分别n=8和n=7的情况推导并归纳，得到如下计算公式：比赛场次＝（n-1）+n/2(k-1)+(n/22)(k-2)+…+n/2(k-1)，其中k=ëlog2nû当n＝8时，k=3,比赛场次＝7＋8/2(2)＋8/4=17场(这是最坏情况，即每次都先从叶子调整起)7.【严题集10.19④】假设某大旅店共有5000个床位，每天需要根据住宿旅客的文件制造一份花名册，该名册要求按省（市）的次序排列，每一省（市）按县（区）排列，又同一县（区）的旅客按姓氏排列。请你为旅店的管理人员设计一个制作这份花名册的方法。（提示）这是一个多关键字的排序问题。请思考对这个文件进行排序用哪一种方法更合适，是MSD法还是LSD法？答：采用哪种排序方法，关键要看记录的结构是如何定义的，如果旅客填表如下：省（市）县（区）姓名床位号则按题意要求，应当采用MSD法，否则无法满足。但若“姓名”项在前，则必须用LSD才符合题意要求。9.【全国专升本题】【严题集10.6④】奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则两者交换；第三趟对奇数i,第四趟对偶数i；……依次类推直至整个序列有序为止。（1）试问这种排序方法的结束条件是什么？是否为稳定排序？（2）分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。（3）分析此种排序方法的平均复杂度及最坏复杂度。答：（1）这种算法其实是两两比较，第一趟很像锦标赛的“初赛”，将胜者（大数）置于偶数单元；第二趟对偶数单元操作，即第一组大者与第二组小者战，大者后移。结果相当于冒泡排序的一趟；所以结束条件应为偶数趟无交换。结束条件是：若n为偶数时，奇数循环时i>n-1，偶数循环时i>n，若n为奇数时，奇数循环时i>n偶数循环时i>n+162 62似乎不稳定？因为交换没有依次进行。四、【全国专升本类似题】【类严题集10.1①】以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？①直接插入排序②希尔排序③冒泡排序④快速排序⑤直接选择排序⑥堆排序⑦归并排序⑧基数排序（8分）解：先回答第2问：①⑤⑦⑧皆易于在链表上实现。①直接插入排序的中间过程如下：②希尔排序的中间过程如下：③冒泡排序的中间过程如下：④快速排序的中间过程如下：⑤直接选择排序的中间过程如下：⑥堆排序（大根堆）的中间过程如下：62 62⑦归并排序排序的中间过程如下：⑧基数排序的中间过程如下：五、算法设计题（4选2，每题7分，共14分）1.【严题集10.25③】试编写教科书10.2.2节中所述链表插入排序的算法。10.25voidSLInsert_Sort(SLList&L)//静态链表的插入排序算法{L.r[0].key=0;L.r[0].next=1;L.r[1].next=0;//建初始循环链表for(i=2;i<=L.length;i++)//逐个插入{p=0;x=L.r[i].key;while(L.r[L.r[p].next].keyL.r[i];L.r[i].next=p;}p=q;}//for}//SLInsert_Sort2.【严题集10.30④】按下述原则编写快排的非递归算法：（1）一趟排序之后，先对长度较短的子序列进行排序，且将另一子序列的上、下界入栈保存；（2）若待排记录数≤3,则不再进行分割，而是直接进行比较排序。62 6210.30typedefstruct{intlow;inthigh;}boundary;//子序列的上下界类型voidQSort_NotRecurve(intSQList&L)//快速排序的非递归算法{low=1;high=L.length;InitStack(S);//S的元素为boundary类型while(low2)//如果当前子序列长度大于3且尚未排好序{pivot=Partition(L,low,high);//进行一趟划分if(high-pivot>pivot-low){Push(S,{pivot+1,high});//把长的子序列边界入栈high=pivot-1;//短的子序列留待下次排序}else{Push(S,{low,pivot-1});low=pivot+1;}}//ifelseif(low=pivotkey)high--;L.r[low]=L.r[high];while(lowL.r[high].key)L.r[low]<->L.r[high];else//子序列含有三个元素{if(L.r[low].key>L.r[low+1].key)L.r[low]<->L.r[low+1];if(L.r[low+1].key>L.r[high].key)L.r[low+1]<->L.r[high];if(L.r[low].key>L.r[low+1].key)L.r[low]<->L.r[low+1];}}//Easy_Sort1.【严题集10.41④】假设有1000个关键字为小于10000的整数的记录序列，请设计一种排序方法，要求以尽可能少的比较次数和移动次数实现排序，并按你的设计编出算法。解：可以用基数排序来实现，关键字位数d=4，数基radix=10（从0～9）则基数排序的算法如下；voidHash_Sort(inta[])//对1000个关键字为四位整数的记录进行排序{intb[10000];for(i=0;i<1000;i++)//直接按关键字散列（即分配）{for(j=a[i];b[j];j=(j+1)%10000);b[j]=a[i];}for(i=0,j=0;i<1000;j++)//将散列收回a中if(b[j]){for(x=b[j],k=j;b[k];k=(k+1)%10000)if(b[k]==x){a[i++]=x;b[k]=0;}}//if}//Hash_Sort2.【严题集10.42④】序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。10.42typedefstruct{intgt;//大于该记录的个数intlt;//小于该记录的个数}place;//整个序列中比某个关键字大或小的记录个数intGet_Mid(inta[],intn)//求一个序列的中值记录的位置{placeb[MAXSIZE];for(i=0;ia[i])b[i].gt++;62 62elseif(a[j]