离散数学严蔚敏版课后习题答案 76页

'数据结构（C语言版）（第2版）课后习题答案李冬梅2015.373 目录第1章绪论1第2章线性表5第3章栈和队列13第4章串、数组和广义表26第5章树和二叉树33第6章图43第7章查找54第8章排序6573 第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。3．简述逻辑结构的四种基本关系并画出它们的关系图。73 答案：（1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。（2）线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。（3）树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。（4）图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。四类基本逻辑结构关系图4．存储结构由哪两种基本的存储方法实现？答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构答案：C（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A．存储结构B．存储实现C．逻辑结构D．运算实现答案：C（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致73 C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等答案：B（4）以下说法正确的是（）。A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。（5）算法的时间复杂度取决于（）。A．问题的规模B．待处理数据的初态C．计算机的配置D．A和B答案：D解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队列D．栈答案：A6．试分析下面各程序段的时间复杂度。（1）x=90;y=100; while(y>0)if(x>100){x=x-10;y--;}elsex++;答案：O(1)解释：程序的执行次数为常数阶。（2）for(i=0;i1y=0;while(x≥(y+1)*(y+1))y++;答案：O()解释：语句y++;的执行次数为 ëû。73 第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A．110B．108C．100D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。A．8B．63.5C．63D．7答案：B解释：平均要移动的元素个数为：n/2。（4）链接存储的存储结构所占存储空间（）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B73 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。（7）单链表的存储密度（）。A．大于1B．等于1C．小于1D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。A．nB．2n-1C．2nD．n-1答案：A解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。A．n-iB．n-i+1C．n-i-1D．I答案：B(10)线性表L=(a1，a2,……an)，下列说法正确的是（）。A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素C．表中诸元素的排列必须是由小到大或由大到小D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。答案：D(11)创建一个包括n个结点的有序单链表的时间复杂度是（）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)答案：C解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。(12)以下说法错误的是（）。A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构答案：D解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。(13)在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。A．s->next=p+1;p->next=s;73 B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案：D(14)在双向链表存储结构中，删除p所指的结点时须修改指针（）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;答案：A(15)在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La->next;pb=Lb->next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}//取较小者La中的元素，将pa链接在pc的后面，pa指针后移elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移else//相等时取La中的元素，删除Lb中的元素73 {pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb的头结点}（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的表头结点之后，如果两个表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素依次摘取，链接在Lc表的表头结点之后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc,){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La->next;pb=Lb->next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La;//用La的头结点作为Lc的头结点Lc->next=NULL;while(pa||pb){//只要存在一个非空表，用q指向待摘取的元素if(!pa){q=pb;pb=pb->next;}//La表为空，用q指向pb，pb指针后移elseif(!pb){q=pa;pa=pa->next;}//Lb表为空，用q指向pa，pa指针后移elseif(pa->data<=pb->data){q=pa;pa=pa->next;}//取较小者（包括相等）La中的元素，用q指向pa，pa指针后移else{q=pb;pb=pb->next;}//取较小者Lb中的元素，用q指向pb，pb指针后移q->next=Lc->next;Lc->next=q;//将q指向的结点插在Lc表的表头结点之后}deleteLb;//释放Lb的头结点}73 （3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。[题目分析]只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果两个表中相等的元素时，摘取La表中的元素，删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个到达表尾结点，为空时，依次删除另一个非空表中的所有元素。[算法描述]voidMix(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa->data==pb->data)∥交集并入结果表中。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;deleteu;}elseif(pa->datadata){u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;}}while(pa){u=pa;pa=pa->next;deleteu;}∥释放结点空间while(pb){u=pb;pb=pb->next;deleteu;}∥释放结点空间pc->next=null;∥置链表尾标记。deleteLb;//释放Lb的头结点}（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。[题目分析]求两个集合A和B的差集是指在A中删除A和B中共有的元素，即删除链表中的相应结点,所以要保存待删除结点的前驱，使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果La表中的元素小于Lb表中的元素，pre置为La表的工作指针pa删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个为空时，依次删除另一个非空表中的所有元素。[算法描述]voidDifference（LinkList&La,LinkList&Lb,int*n）73 {∥差集的结果存储于单链表La中，*n是结果集合中元素个数，调用时为0pa=La->next;pb=Lb->next;∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点pre=La;∥pre为La中pa所指结点的前驱结点的指针while（pa&&pb）{if（pa->datadata）{pre=pa;pa=pa->next;*n++;}∥A链表中当前结点指针后移elseif（pa->data>q->data）q=q->next;∥B链表中当前结点指针后移else{pre->next=pa->next;∥处理A，B中元素值相同的结点，应删除u=pa;pa=pa->next;deleteu;}∥删除结点}}（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。[题目分析]B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表。[算法描述]voidDisCompose(LinkedListA){B=A;B->next=NULL;∥B表初始化C=newLNode;∥为C申请结点空间C->next=NULL;∥C初始化为空表p=A->next;∥p为工作指针while(p!=NULL){r=p->next;∥暂存p的后继if(p->data<0){p->next=B->next;B->next=p;}∥将小于0的结点链入B表,前插法else{p->next=C->next;C->next=p;}∥将大于等于0的结点链入C表,前插法p=r;∥p指向新的待处理结点。}}（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。[题目分析]73 假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则设其下一个元素为最大值，反复进行比较，直到遍历完该链表。[算法描述]ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;//假定第一个结点中数据具有最大值p=L->next->next;while(p!=NULL){//如果下一个结点存在if(p->data>pmax->data)pmax=p;//如果p的值大于pmax的值，则重新赋值p=p->next;//遍历链表}returnpmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。[题目分析]从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部。[算法描述]voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L->next;L->next=NULL;while(p){q=p->next;//q指向*p的后继p->next=L->next;L->next=p;//*p插入在头结点之后p=q;}}（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。[题目分析]分别查找第一个值>mink的结点和第一个值≥maxk的结点，再修改指针，删除值大于mink且小于maxk的所有元素。[算法描述]voiddelete(LinkList&L,intmink,intmaxk){p=L->next;//首元结点while(p&&p->data<=mink){pre=p;p=p->next;}//查找第一个值>mink的结点if(p)73 {while(p&&p->datanext;//查找第一个值≥maxk的结点q=pre->next;pre->next=p;//修改指针while(q!=p){s=q->next;deleteq;q=s;}//释放结点空间}//if}（9）已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。[题目分析]知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。[算法描述]voidExchange（LinkedListp）∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。{q=p->llink；q->llink->rlink=p；∥p的前驱的前驱之后继为pp->llink=q->llink；∥p的前驱指向其前驱的前驱。q->rlink=p->rlink；∥p的前驱的后继为p的后继。q->llink=p；∥p与其前驱交换p->rlink->llink=q；∥p的后继的前驱指向原p的前驱p->rlink=q；∥p的后继指向其原来的前驱}∥算法exchange结束。（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。[题目分析]在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。[算法描述]voidDelete（ElemTypeA[]，intn）∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。{i=1；j=n；∥设置数组低、高端指针（下标）。while（idata;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。（5）设有一个递归算法如下      intfact(intn){ //n大于等于0           if(n<=0)return1;           elsereturnn*fact(n-1);      }则计算fact(n)需要调用该函数的次数为（）。 A． n+1     B． n-1     C．n     D．n+2答案：A73 解释：特殊值法。设n=0，易知仅调用一次fact(n)函数，故选A。（6）栈在 （）中有所应用。A．递归调用B．函数调用C．表达式求值D．前三个选项都有答案：D解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A．队列B．栈C．线性表D．有序表答案：A解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。A．2B．3C．4D．6答案：B解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。（9）若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是()。A．top++;V[top]=x;B．V[top]=x;top++;C．top--;V[top]=x;D．V[top]=x;top--;答案：C解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1..n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]。（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。A．线性表的顺序存储结构B．队列C.线性表的链式存储结构D.栈答案：D解释：利用栈的后进先出原则。（11）用链接方式存储的队列，在进行删除运算时（　）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。73 （12）循环队列存储在数组A[0..m]中，则入队时的操作为（　）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解释：数组A[0..m]中共含有m+1个元素，故在求模运算时应除以m+1。（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（　）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front答案：B解释：最大容量为n的循环队列，队满条件是(rear+1)%n==front，队空条件是rear==front。（14）栈和队列的共同点是（　）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。（15）一个递归算法必须包括（　）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分答案：B2．算法设计题（1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：Typedefstruct{inttop[2],bot[2];//栈顶和栈底指针SElemType*V;//栈数组intm;//栈最大可容纳元素个数}DblStack[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。[算法描述](1) 栈初始化73 int Init() {S.top[0]=-1;  S.top[1]=m;  return 1; //初始化成功}(2) 入栈操作：int push(stkS ,int i,int x)∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0{if(i<0||i>1){cout<<“栈号输入不对”<1){cout<<“栈号输入错误”<>x);//从键盘读入整数序列。if(x!=-1)//读入的整数不等于-1时入栈。｛if(top==maxsize-1){cout<<“栈满”<>x;//x是字符型变量。while(x!=’$’){switch{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’)//拼数if(x!=’.’)//处理整数{num=num*10+（ord(x)-ord(‘0’)）;cin>>x;}else//处理小数部分。{scale=10.0;cin>>x;while(x>=’0’&&x<=’9’){num=num+(ord(x)-ord(‘0’)/scale;scale=scale*10;cin>>x;}}//else73 push(OPND,num);num=0.0;//数压入栈，下个数初始化casex=‘’:break;//遇空格，继续读下一个字符。casex=‘+:push(OPND,pop(OPND)+pop(OPND));break;casex=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;casex=‘*:push(OPND,pop(OPND)*pop(OPND));break;casex=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default://其它符号不作处理。}//结束switchcin>>x;//读入表达式中下一个字符。}//结束while（x！=‘$’）cout<<“后缀表达式的值为”<j){cout<<“序列非法”<rear=Q->rear->next;//将队尾指针指向头结点while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队{s=Q->rear->next;Q->rear->next=s->next;deletes;　}//回收结点空间73 }(1)判队空 intEmptyQueue(LinkQueue*Q){//判队空。当头结点的next指针指向自己时为空队　returnQ->rear->next->next==Q->rear->next;}(2)入队voidEnQueue(LinkQueue*Q,Datatypex){//入队。也就是在尾结点处插入元素QueueNode*p=newQueueNode;//申请新结点p->data=x;p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p; Q->rear=p;//将尾指针移至新结点}(3)出队DatatypeDeQueue(LinkQueue*Q){//出队,把头结点之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");p=Q->rear->next->next;//p指向将要摘下的结点x=p->data;//保存结点中数据if(p==Q->rear){//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点　Q->rear=Q->rear->next;Q->rear->next=p->next;}else Q->rear->next->next=p->next;//摘下结点pdeletep;//释放被删结点returnx;}73 （7）假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。[算法描述](1)初始化SeQueueQueueInit(SeQueueQ){//初始化队列Q.front=Q.rear=0;Q.tag=0;return Q;}(2)入队SeQueueQueueIn(SeQueueQ,inte){//入队列if((Q.tag==1)&&(Q.rear==Q.front))cout<<"队列已满"<0,n<>0而得=Ack(1,Ack(1,1))//因m<>0,n=0而得73 =Ack(1,Ack(0,Ack(1,0)))//因m<>0,n<>0而得=Ack(1,Ack(0,Ack(0,1)))//因m<>0,n=0而得=Ack(1,Ack(0,2))//因m=0而得=Ack(1,3)//因m=0而得=Ack(0,Ack(1,2))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(1,1)))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(0,Ack(1,0))))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(0,Ack(0,1))))//因m<>0,n=0而得=Ack(0,Ack(0,Ack(0,2)))//因m=0而得=Ack(0,Ack(0,3))//因m=0而得=Ack(0,4)//因n=0而得=5//因n=0而得②intAckerman(intm,intn){intakm[M][N];inti,j;for(j=0;jnext)returnp->data;else{intmax=GetMax(p->next);73 returnp->data>=max?p->data:max;}}②intGetLength(LinkListp){if(!p->next)return1;else{returnGetLength(p->next)+1;}}③doubleGetAverage(LinkListp,intn){if(!p->next)returnp->data;else{doubleave=GetAverage(p->next,n-1);return(ave*(n-1)+p->data)/n;}}73 第4章串、数组和广义表1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若答案：B（2）串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。（3）串“ababaaababaa”的next数组为（）。A．012345678999B．012121111212C．011234223456D．0123012322345答案：C（4）串“ababaabab”的nextval为（）。A．010104101B．010102101C．010100011D．010101011答案：A（5）串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。A．808B．818C．1010D．1020答案：B解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。A．BA+141B．BA+180C．BA+222D．BA+225答案：B解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。73 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A．13B．32C．33D．40答案：C（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i>ch;if(ch!=".")//规定"."是字符串输入结束标志{InvertStore(A);A[i++]=ch;//字符串逆序存储}A[i]="";//字符串结尾标记}（3）编写算法，实现下面函数的功能。函数voidinsert(char*s,char*t,intpos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）[题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。[算法描述]voidinsert(char*s,char*t,intpos)//将字符串t插入字符串s的第pos个位置。{inti=1,x=0;char*p=s,*q=t;//p，q分别为字符串s和t的工作指针if(pos<1){cout<<“pos参数位置非法”<=pos;j--){*(p+x)=*p;p--;}//串s的pos后的子串右移，空出串t的位置。q--;//指针q回退到串t的最后一个字符for(j=1;j<=x;j++)*p--=*q--;//将t串插入到s的pos位置上[算法讨论]串s的结束标记("")也后移了，而串t的结尾标记不应插入到s中。（4）已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2,其多余的字符送S3。[题目分析]本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n73 且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。[算法描述]voidformat(char*s1,*s2,*s3)//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐{char*p=s1,*q=s2;inti=0;while(*p!=""&&*p=="")p++;//滤掉s1左端空格if(*p==""){cout<<"字符串s1为空串或空格串"<0)i++;while(ilchild==NULL&&T->rchild==NULL)return1;//判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回1elsereturnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);}（2）判别两棵树是否相等。73 [题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)，如果当前节点不相等，直接返回两棵树不相等;如果当前节点相等，那么就递归的判断他们的左右孩子是否相等。[算法描述]intcompareTree(TreeNode*tree1,TreeNode*tree2)//用分治的方法做，比较当前根，然后比较左子树和右子树{booltree1IsNull=(tree1==NULL);booltree2IsNull=(tree2==NULL);if(tree1IsNull!=tree2IsNull){return1;}if(tree1IsNull&&tree2IsNull){//如果两个都是NULL，则相等return0;}//如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等if(tree1->c!=tree2->c){　return1;}return(compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left));}//算法结束（3）交换二叉树每个结点的左孩子和右孩子。[题目分析]如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。[算法描述]voidChangeLR(BiTree&T){BiTreetemp;if(T->lchild==NULL&&T->rchild==NULL)return;else{temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;73 }//交换左右孩子ChangeLR(T->lchild);//递归交换左子树ChangeLR(T->rchild);//递归交换右子树}（4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。[题目分析]若树为空，返回；若某结点为叶子结点，则仅输出该结点；否则先输出该结点，递归遍历其左子树，再输出该结点，递归遍历其右子树。[算法描述]voidDoubleTraverse(BiTreeT){if(T==NULL)return;elseif(T->lchild==NULL&&T->rchild==NULL)cout<data;//叶子结点输出else{cout<data;DoubleTraverse(T->lchild);//递归遍历左子树cout<data;DoubleTraverse(T->rchild);//递归遍历右子树}}（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。[题目分析]求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。[算法描述]intWidth(BiTreebt)//求二叉树bt的最大宽度{if(bt==null)return(0);//空二叉树宽度为0else{BiTreeQ[];//Q是队列，元素为二叉树结点指针，容量足够大front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置temp=0;maxw=0;//temp记局部宽度,maxw记最大宽度Q[rear]=bt;//根结点入队列while(front<=last)73 {p=Q[front++];temp++;//同层元素数加1if(p->lchild!=null)Q[++rear]=p->lchild;//左子女入队if(p->rchild!=null)Q[++rear]=p->rchild;//右子女入队if(front>last)//一层结束，{last=rear;if(temp>maxw)maxw=temp;//last指向下层最右元素,更新当前最大宽度temp=0;}//if}//whilereturn(maxw);}//结束width（6）用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。[题目分析]若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为1的结点[算法描述]intLevel(BiTreebt)//层次遍历二叉树，并统计度为1的结点的个数{intnum=0;//num统计度为1的结点的个数if(bt){QueueInit(Q);QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列while(!QueueEmpty(Q)){p=QueueOut(Q);cout<data;//出队,访问结点if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度为1的结点if(p->lchild)QueueIn(Q,p->lchild);//非空左子女入队if(p->rchild)QueueIn(Q,p->rchild);//非空右子女入队}//while(!QueueEmpty(Q))}//if(bt)return(num);}//返回度为1的结点的个数（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。[题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。[算法描述]voidLongestPath(BiTreebt)//求二叉树中的第一条最长路径长度{BiTreep=bt,l[],s[];73 //l,s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//当前结点的右分枝已遍历{if(!s[top]->Lc&&!s[top]->Rc)//只有到叶子结点时，才查看路径长度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}elseif(top>0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while(p!=null||top>0)}//结束LongestPath（8）输出二叉树中从每个叶子结点到根结点的路径。[题目分析]采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。[算法描述]voidAllPath(BTNode*b,ElemTypepath[],intpathlen){inti;if(b!=NULL){if(b->lchild==NULL&&b->rchild==NULL)//*b为叶子结点{cout<<""<data<<"到根结点路径:"<data;for(i=pathlen-1;i>=0;i--)cout<data;//将当前结点放入路径中pathlen++;//路径长度增1AllPath(b->lchild,path,pathlen);//递归扫描左子树AllPath(b->rchild,path,pathlen);//递归扫描右子树pathlen--;//恢复环境}}//if(b!=NULL)}//算法结束73 第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。A．1/2B．1C．2D．4答案：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．1/2B．1C．2D．4答案：B解释：有向图所有顶点入度之和等于所有顶点出度之和。（3）具有n个顶点的有向图最多有（）条边。A．nB．n(n-1)C．n(n+1)D．n2答案：B解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。A．nB．2(n-1)C．n/2D．n2答案：B（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A．7B．8C．9D．10答案：C解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。A．非连通B．连通C．强连通D．有向答案：B解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。（7）下面（　）算法适合构造一个稠密图G的最小生成树。A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法答案：A解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。A．栈B.队列C.树D．图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。73 （9）用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。A．栈B.队列C.树D．图答案：A解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。（10）深度优先遍历类似于二叉树的（）。A．先序遍历B．中序遍历C．后序遍历D．层次遍历答案：A（11）广度优先遍历类似于二叉树的（）。A．先序遍历B．中序遍历C．后序遍历D．层次遍历答案：D（12）图的BFS生成树的树高比DFS生成树的树高（）。A．小B．相等C．小或相等D．大或相等答案：C解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。（13）已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（）。 图6.30邻接矩阵（14）已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。图6.31邻接表A．0132B．0231C．0321D．0123答案：D、D（15）下面（）方法可以判断出一个有向图是否有环。A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径答案：B2．应用题（1）已知图6.32所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。73  图6.32有向图图6.33无向网答案：（2）已知如图6.33所示的无向网，请给出：①邻接矩阵；②邻接表；③最小生成树答案：①③②a→b4→c3b→a4→c5→d5→e9c→a3→b5→d5→h5d→b5→c5→e7→f6→g5→h4e→b9→d7→f3f→d6→e3→g2g→d5→f2→h673 （3）已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。图6.28邻接矩阵（4）有向网如图6.35所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。 图6.34邻接矩阵图6.35有向网表6.9D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}（5）试对图6.36所示的AOE-网：①求这个工程最早可能在什么时间结束；73 ②求每个活动的最早开始时间和最迟开始时间；③确定哪些活动是关键活动图6.36AOE-网答案：按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?来确定关键活动，从而确定关键路径。1¶2¸3·4¹5º6»Ve01915293843Vl01915373843<1,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938l170152719273738-e1700801280此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6>3．算法设计题（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：①增加一个新顶点v，InsertVex(G,v)；②删除顶点v及其相关的边，DeleteVex(G,v);③增加一条边，InsertArc(G,v,w);④删除一条边，DeleteArc(G,v,w)。[算法描述]假设图G为有向无权图，以邻接矩阵作为存储结构四个算法分别如下：①增加一个新顶点vStatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G.vexnum]=v;returnOK;}//Insert_Vex②删除顶点v及其相关的边，StatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v73 {n=G.vexnum;if((m=LocateVex(G,v))<0)returnERROR;G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点for(i=0;iStatusInsert_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上插入边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(i==j)returnERROR;if(!G.arcs[j].adj){G.arcs[j].adj=1;G.arcnum++;}returnOK;}//Insert_Arc④删除一条边StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[j].adj){G.arcs[j].adj=0;73 G.arcnum--;}returnOK;}//Delete_Arc以邻接表作为存储结构，本题只给出Insert_Arc算法.其余算法类似。StatusInsert_Arc(ALGraph&G,charv,charw)//在邻接表表示的图G上插入边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;p=newArcNode;p->adjvex=j;p->nextarc=NULL;if(!G.vertices.firstarc)G.vertices.firstarc=p;else{for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc)if(q->adjvex==j)returnERROR;//边已经存在q->nextarc=p;}G.arcnum++;returnOK;}//Insert_Arc（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。[算法描述]VoidDFSn(GraphG,intv){//从第v个顶点出发非递归实现深度优先遍历图GStacks;SetEmpty(s);Push(s,v);While(!StackEmpty(s)){//栈空时第v个顶点所在的连通分量已遍历完Pop(s,k);If(!visited[k]){visited[k]=TRUE;VisitFunc(k);//访问第k个顶点//将第k个顶点的所有邻接点进栈73 for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w)){if(!visited[w]&&w!=GetTop(s))Push(s,w);//图中有环时w==GetTop(s)}}}（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。[题目分析]利用Dijkstra算法求v0到其它所有顶点的最短路径，分别保存在数组D[i]中，然后求出D[i]中值最大的数组下标m即可。[算法描述]intShortestPath_MAX(AMGraphG,intv0){//用Dijkstra算法求距离顶点v0的最短路径长度最大的一个顶点mn=G.vexnum;//n为G中顶点的个数for(v=0;vnextarc，level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//elseif(level==1)return0;}//exist_path_DFS（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。[算法描述]intvisited[MAXSIZE];73 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;//本题允许曾经被访问过的结点出现在另一条路径中}//elsereturn0;//没找到}//exist_path_len73 73 第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。（2）适用于折半查找的表的存储方式及元素排列要求为（）。A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取ë(1+10)/2û=5，与第五个元素20比较，58大于20，再取ë(6+10)/2û=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为 ëlog222û + 1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。（6）折半搜索与二叉排序树的时间性能（）。A．相同B．完全不同C．有时不相同D．数量级都是O(log2n)73 答案：C（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。A．（100，80，90，60，120，110，130）B．（100，120，110，130，80，60，90）C．（100，60，80，90，120，110，130）D．(100，80，60，90，120，130，110)答案：C解释：A、B、C、D四个选项构造二叉排序树都以100为根，易知A、B、D三个序列中第一个比100小的关键字为80，即100的左孩子为80，而C选项中100的左孩子为60，故选C。（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。A．LLB．LRC．RLD．RR答案：C（9）下列关于m阶B-树的说法错误的是（）。A．根结点至多有m棵子树B．所有叶子都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D．根结点中的数据是有序的答案：D（10）下面关于B-和B+树的叙述中，不正确的是（）。A．B-树和B+树都是平衡的多叉树B．B-树和B+树都可用于文件的索引结构C．B-树和B+树都能有效地支持顺序检索D．B-树和B+树都能有效地支持随机检索答案：C（11）m阶B-树是一棵（）。A．m叉排序树B．m叉平衡排序树C．m-1叉平衡排序树D．m+1叉平衡排序树答案：B（12）下面关于哈希查找的说法，正确的是（）。A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．哈希表的平均查找长度有时也和记录总数有关答案：C（13）下面关于哈希查找的说法，不正确的是（）。A．采用链地址法处理冲突时，查找一个元素的时间是相同的B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的C．用链地址法处理冲突，不会引起二次聚集现象73 D．用链地址法处理冲突，适合表长不确定的情况答案：A解释：在同义词构成的单链表中，查找该单链表表中不同元素，所消耗的时间不同。（14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。A．8B．3C．5D．9答案：D解释：关键字15放入位置4，关键字38放入位置5，关键字61放入位置6，关键字84放入位置7，再添加关键字49，计算得到地址为5，冲突，用二次探测法解决冲突得到新地址为6，仍冲突，再用用二次探测法解决冲突，得到新地址为4，仍冲突，再用用二次探测法解决冲突，得到新地址为9，不冲突，即将关键字49放入位置9。（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字()。A．不一定都是同义词B．一定都是同义词C．一定都不是同义词D．都相同答案：A解释：所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。2．应用题（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：①画出描述折半查找过程的判定树；②若查找元素54，需依次与哪些元素比较？③若查找元素90，需依次与哪些元素比较？④假定每个元素的查找概率相等，求查找成功时的平均查找长度。答案：①先画出判定树如下（注：mid=ë(1+12)/2û=6）：30563374287424547295②查找元素54，需依次与30,63,42,54元素比较；③查找元素90，需依次与30,63,87,95元素比较；④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，73 所以ASL＝1/12（17＋20）＝37/12≈3.08（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。答案：1271721116214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21（3）已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。答案：（4）对图7.31所示的3阶B-树，依次执行下列操作，画出各步操作的结果。①插入90②插入25③插入45④删除6073 图7.313阶B-树（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：①画出哈希表的示意图；②若查找关键字63，需要依次与哪些关键字进行比较？③若查找关键字60，需要依次与哪些关键字比较？④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。答案：①画表如下：012345678910111213141516173217634924401030314647②查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较,不匹配;然后顺移，与46,47,32,17,63相比，一共比较了6次！③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。④对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，73 所以ASL=1/11（6＋2＋3×3+6）＝23/11（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。答案：散列地址0123456789关键字14192384275520  比较次数11123412  平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5所以比较了4次。（7）设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。①线性探测法；②链地址法。答案：①散列地址012345678910关键字 4 12493813243221 比较次数 1 1121212 ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11②ASLsucc=（1*5+2*3）/8=11/873 ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/113．算法设计题（1）试写出折半查找的递归算法。[算法描述]intBinSrch（rectyper[]，intk，low，high）//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。{if（low≤high）//low和high分别是有序表的下界和上界{mid=（low+high）/2；if（r[mid].key==k）return（mid）；elseif（r[mid].key>k）return（BinSrch（r,k，mid+1，high））;elsereturn（BinSrch（r,k，low，mid-1））;}elsereturn（0）；//查找失败。}//算法结束（2）试写一个判别给定二叉树是否为二叉排序树的算法。[题目分析]根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。[算法描述]#definetrue1#definefalse0typedefstructnode{datatypedata;structnode*lchild,*rchild;}*BTree;voidJudgeBST（BTreeT,intflag）//判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{if（T!=null&&flag）{Judgebst（T->lchild,flag）；//中序遍历左子树if（pre==null）pre=T；//中序遍历的第一个结点不必判断elseif（pre->datadata）pre=T；//前驱指针指向当前结点else{flag=flase；}//不是完全二叉树Judgebst（T->rchild,flag）；//中序遍历右子树}//JudgeBST算法结束（3）已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild，rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。73 [题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有lchild）；Cout<rchild）；}}voidPrintAllx(BSTreebst，datatypex）//在二叉排序树bst中，查找值≥x的结点并输出{p=bst；if（p）{while（p&&p->datarchild；//沿右分枝找第一个值≥x的结点bst=p;//bst所指结点是值≥x的结点的树的根if（p）{f=p;p=p->lchild；//找第一个值data≥x）//沿左分枝向下，找第一个值lchild；}//f是p的双亲结点的指针，指向第一个值≥x的结点if(p)f->lchild=null;//双亲与找到的第一个值data.x=target;s->data.count=0;73 s->lchild=s->rchild=NULL;if(!T){T=s;return;}//如果该树为空则跳出该函数f=NULL;q=T;while(q){if(q->data.x==target){q->data.count++;return;}//如果找到该值则计数加一f=q;if(q->data.x>target)//如果查找值比目标值大，则为该树左孩子q=q->lchild;else//否则为右孩子q=q->rchild;}//将新结点插入树中if(f->data.x>target)f->lchild=s;elsef->rchild=s;}（5）假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。[题目分析]因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。[算法描述]intHeight（BSTreet）//求平衡二叉树t的高度{level=0；p=t；while（p）{level++；//树的高度增1if（p->bf<0）p=p->rchild；//bf=-1沿右分枝向下//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义73 elsep=p->lchild；//bf>=0沿左分枝向下}//whilereturn（level）；//平衡二叉树的高度}//算法结束（6）分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H，解决冲突的方法为链地址法。[算法描述]boolinsert(){intdata;cin>>data;intant=hash(data);LinkListp=HT[ant];//初始化散列表while(p->next){if(p->next->data==data)returnfalse;p=p->next;}//找到插入位置LinkLists;s=newLNode;s->data=data;s->next=p->next;p->next=s;//插入该结点returntrue;}booldeletes(){intdata;cin>>data;intant=hash(data);LinkListp=HT[ant];//初始化散列表while(p->next){if(p->next->data==data){LinkLists=p->next;p->next=s->next;deletes;//删除该结点returntrue;}//找到删除位置73 p=p->next；//遍历下一个结点}returnfalse;}73 第8章排序1．选择题（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。A．归并排序B．冒泡排序C．插入排序D．选择排序答案：C（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。A．归并排序B．冒泡排序C．插入排序D．选择排序答案：D（3）对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序答案：B解释：对关键字进行冒泡排序，关键字逆序时比较次数最多。（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。A．n+1B．nC．n-1D．n(n-1)/2答案：D解释：比较次数最多时，第一次比较n-1次，第二次比较n-2次……最后一次比较1次，即(n-1)+(n-2)+…+1=n(n-1)/2。（5）快速排序在下列（）情况下最易发挥其长处。A．被排序的数据中含有多个相同排序码B．被排序的数据已基本有序C．被排序的数据完全无序D．被排序的数据中的最大值和最小值相差悬殊答案：C解释：B选项是快速排序的最坏情况。（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)答案：B解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。（7）若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．38，40，46，56，79，84B．40，38，46，79，56，8473 C．40，38，46，56，79，84D．40，38，46，84，56，79答案：C（8）下列关键字序列中，（）是堆。A．16，72，31，23，94，53B．94，23，31，72，16，53C．16，53，23，94，31，72D．16，23，53，31，94，72答案：D解释：D选项为小根堆（9）堆是一种（）排序。A．插入B．选择C．交换D．归并答案：B（10）堆的形状是一棵（）。A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树答案：C（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。A．79，46，56，38，40，84B．84，79，56，38，40，46C．84，79，56，46，40，38D．84，56，79，40，46，38答案：B（12）下述几种排序方法中，要求内存最大的是（）。A．希尔排序B．快速排序C．归并排序D．堆排序答案：C解释：堆排序、希尔排序的空间复杂度为O(1)，快速排序的空间复杂度为O(log2n)，归并排序的空间复杂度为O(n)。（13）下述几种排序方法中，（）是稳定的排序方法。A．希尔排序B．快速排序C．归并排序D．堆排序答案：C解释：不稳定排序有希尔排序、简单选择排序、快速排序、堆排序；稳定排序有直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。（14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用()算法最节省时间。A．冒泡排序B．快速排序C．简单选择排序D．堆排序答案：D（15）下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。A．希尔排序B．快速排序C．冒泡排序D．堆排序答案：A解释：快速排序的每趟排序能将作为枢轴的元素放到最终位置；冒泡排序的每趟排序能将最大或最小的元素放到最终位置；堆排序的每趟排序能将最大或最小的元素放到最终位置。2．应用题73 （1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。①直接插入排序②折半插入排序③希尔排序（增量选取5，3，1）④冒泡排序⑤快速排序⑥简单选择排序⑦堆排序⑧二路归并排序答案：①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]②折半插入排序排序过程同①③希尔排序（增量选取5，3，1）102166181216*203028（增量选取5）621210181616*203028（增量选取3）2610121616*18202830（增量选取1）④冒泡排序21216281016*20618[30]212161016*20618[2830]212101616*618[202830]2101216616*[18202830]21012616[16*18202830]210612[1616*18202830]2610[121616*18202830]2610121616*18202830]73 ⑤快速排序12[6210]12[283016*201618]6[2]6[10]12[283016*201618]28261012[181616*20]28[30]18261012[16*16]18[20]283016*26101216*[16]18202830左子序列递归深度为1，右子序列递归深度为3⑥简单选择排序2[121630281016*20618]26[1630281016*201218]2610[30281616*201218]261012[281616*203018]26101216[2816*203018]2610121616*[28203018]2610121616*18[203028]2610121616*1820[2830]2610121616*182028[30]⑧二路归并排序2121630102816*2061821216301016*2028618210121616*2028306182610121616*18202830（2）给出如下关键字序列｛321，156，57，46，28，7，331，33，34，63｝，试按链式基数排序方法，列出每一趟分配和收集的过程。答案：按最低位优先法→321→156→57→46→28→7→331→33→34→63分配[0][1][2][3][4][5][6][7][8][9]3213334156572833163467收集→321→331→33→63→34→156→46→57→7→28（3）对输入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）；当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。答案：73 初始败者树  257140313161119151110111   初始归并段：R1:3,19,31,51,61,71,100,101R2:9,17,19,20,30,50,55,90R3:63．算法设计题（1）试以单链表为存储结构，实现简单选择排序算法。[算法描述]：voidLinkedListSelectSort(LinkedListhead)//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下//当前结点和最小结点的前驱指针p=head->next;while(p!=null){q=p->next;r=p;//设r是指向关键字最小的结点的指针while(q!=null){if(q->datadata)r=q;q:=q->next;}if(r!=p)r->data<-->p->data;p=p->next;}（2）有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。[算法描述]：73 typedefstructnode{ElemTypedata;structnode*prior,*next;}node，*DLinkedList;voidTwoWayBubbleSort(DLinkedListla)//对存储在带头结点的双向链表la中的元素进行双向起泡排序。{intexchange=1;//设标记DLinkedListp,temp,tail;head=la//双向链表头，算法过程中是向下起泡的开始结点tail=null;//双向链表尾，算法过程中是向上起泡的开始结点while(exchange){p=head->next;//p是工作指针，指向当前结点exchange=0;//假定本趟无交换while(p->next!=tail)//向下（右）起泡，一趟有一最大元素沉底if(p->data>p->next->data)//交换两结点指针，涉及6条链{temp=p->next;exchange=1;//有交换p->next=temp->next;temp->next->prior=p//先将结点从链表上摘下temp->next=p;p->prior->next=temp;//将temp插到p结点前temp->prior=p->prior;p->prior=temp;}elsep=p->next;//无交换，指针后移tail=p;//准备向上起泡p=tail->prior;while(exchange&&p->prior!=head)//向上（左）起泡，一趟有一最小元素冒出if(p->dataprior->data)//交换两结点指针，涉及6条链{temp=p->prior;exchange=1;//有交换p->prior=temp->prior;temp->prior->next=p；//先将temp结点从链表上摘下temp->prior=p;p->next->prior=temp;//将temp插到p结点后（右）temp->next=p->next;p->next=temp;}elsep=p->prior;//无交换，指针前移head=p;//准备向下起泡}//while(exchange)}//算法结束73 （3）设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白色砾石）和i=j){temp=r[k];r[k]=r[i];r[i]=temp;i++;}//左侧只有红色砾石，交换r[k]和r[i]else{temp=r[j];r[j]=r[i];r[i]=temp;j++;//左侧已有红色和白色砾石，先交换白色砾石到位temp=r[k];r[k]=r[i];r[i]=temp;i++;//白色砾石（i所指）和待定砾石（j所指）}//再交换r[k]和r[i]，使红色砾石入位。if(r[k].key==2)if(i<=j){temp=r[k];r[k]=r[j];r[j]=temp;j++;}//左侧已有白色砾石，交换r[k]和r[j]else{temp=r[k];r[k]=r[i];r[i]=temp;j=i+1;}//i、j分别指向红、白色砾石的后一位置}//whileif(r[k]==2)j++;/*处理最后一粒砾石elseif(r[k]==1){temp=r[j];r[j]=r[i];r[i]=temp;i++;j++;}//最后红、白、兰色砾石的个数分别为:i-1;j-i;n-j+1}//结束QkSor算法[算法讨论]若将j（上面指向白色）看作工作指针，将r[1..j-1]作为红色，r[j..k-1]为白色，r[k..n]为兰色。从j=1开始查看，若r[j]为白色，则j=j+1；若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1；若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j>k为止。73 算法片段如下：inti=1,j=1,k=n;while(j<=k)if(r[j]==1)//当前元素是红色{temp=r[i];r[i]=r[j];r[j]=temp;i++;j++;}elseif(r[j]==2)j++;//当前元素是白色else//(r[j]==3当前元素是兰色{temp=r[j];r[j]=r[k];r[k]=temp;k--;}对比两种算法，可以看出，正确选择变量（指针）的重要性。（4）编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：①采用顺序存储结构，至多使用一个记录的辅助存储空间；②算法的时间复杂度为O(n)。[算法描述]voidprocess(intA[n]){low=0;high=n-1;while(low0)high++;if(lowkey)j--;if(R[j].key==key)returnj;while(i<=j&&R[i].key