数据结构习题解答(新).doc 42页

'习题解答《数据结构基础教程》习题解答（新）第1章习题解答一、填空1．数据是指所有能够输入到计算机中被计算机加工、处理的符号的集合。2．可以把计算机处理的数据，笼统地分成数值型和非数值型两大类。3．数据的逻辑结构就是指数据间的邻接关系。4．数据是由一个个数据元素集合而成的。5．数据项是数据元素中不可再分割的最小标识单位，通常不具备完整、确定的实际意义，只是反映数据元素某一方面的属性。6．数据是以数据元素为单位存放在内存的，分配给它的内存区域称为存储结点。7．每个数据元素都具有完整、确定的实际意义，是数据加工处理的对象。8．如果两个数据结点之间有着逻辑上的某种关系，那么就称这两个结点是邻接的。9．在一个存储结点里，除了要有数据本身的内容外，还要有体现数据间邻接关系的内容。10．从整体上看，数据在存储器内有两种存放的方式：一是集中存放在一个连续的内存存储区中；一是利用存储器中的零星区域，分散地存放在内存的各个地方。11．在有些书里，数据的“存储结构”也称为数据的“物理结构”。12．“基本操作”是指算法中那种所需时间与操作数的具体取值无关的操作。二、选择1．在常见的数据处理中，B是最基本的处理。A．删除B．查找C．读取D．插入2．下面给出的名称中，A不是数据元素的同义词。A．字段B．结点C．顶点D．记录3．D是图状关系的特例。A．只有线性关系B．只有树型关系C．线性关系和树型关系都不D．线性关系和树型关系都4．链式存储结构中，每个数据的存储结点里D指向邻接存储结点的指针，用以反映数据间的逻辑关系。A．只能有1个B．只能有2个C．只能有3个D．可以有多个5．本书将采用C来描述算法。A．自然语言B．流程图（即框图）C．类C语言D．C语言6．有下面的算法段：for(i=0;i=0)-42- 习题解答printf(“输入的是正数”);elseprintf(“输入的是负数”);}3．分析算法段中标有记号“#1”和“#2”的基本操作的执行次数：for(i=0;iPrior->Next=ptr->Next;②ptr->Next->Prior=ptr->Prior;。7．设tail是指向非空、带表头结点的循环单链表的表尾指针。那么，该链表起始结点的存储位置应该表示成tail->Next->Next。-42- 习题解答8．在一个不带表头结点的非空单链表中，若要在指针qtr所指结点的后面插入一个值为x的结点，则需要执行下列操作：ptr=malloc(size);ptr->Data=x;ptr->Next=qtr->Next;qtr->Next=ptr;9．顺序表Sq=(a1，a2，a3，…，an)（n≥1）中，每个数据元素需要占用w个存储单元。若m为元素a1的起始地址，那么元素an的存储地址是m+(n-1)*w。10．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用顺序存储结构。二、选择1．下面，对非空线性表特点的论述，C是正确的。A．所有结点有且只有一个直接前驱B．所有结点有且只有一个直接后继C．每个结点至多只有一个直接前驱，至多只有一个直接后继D．结点间是按照1对多的邻接关系来维系其逻辑关系的2．一般单链表Lk_h为空的判定条件是A。A．Lk_h==NULLB．Lk_h->Next==NULLC．Lk_h->Next==Lk_hD．Lk_h!=NULL3．带表头结点的单链表Lk_h为空的判定条件是B。A．Lk_h==NULLB．Lk_h->Next==NULLC．Lk_h->Next==Lk_hD．Lk_h!=NULL4．往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动B个结点。A．nB．n/2C．n+1D．(n+1)/25．在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是C。A．rtr->Next=ptr->Next;ptr->Next=rtr;B．ptr->Next=rtr->Next;C．qtr->Next=rtr;rtr->Next=ptr;D．ptr->Next=rtr;rtr->Next=qtr->Next;6．在一个单链表中，若现在要删除ptr指针所指结点的直接后继结点，则需要执行的操作是A。A．ptr->Next=ptr->Next->Next;B．ptr=ptr->Next;ptr->Next=ptr->Next->Next;C．ptr=ptr->Next->Next;D．ptr->Nextptr;7．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动B个元素。A．n-iB．n-i+1C．n-i-1D．i8．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动A个元素。A．n-iB．n-i+1C．n-i-1D．i9．设tail是指向一个非空带表头结点的循环单链表的尾指针。那么，删除链表起始结点的操作应该是D。A．ptr=tail;B．tail=tail->Next;-42- 习题解答tail=tail->Next;free(tail);free(ptr);C．tail=tail->Next->Next;D．ptr=tail->Next->Next;Free(tail);tail->Next->Next=ptr->Next;Free(ptr);free(ptr);10．在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是B。A．qtr->Next=ptr;B．qtr->Next=ptr->Next;ptr->Next=qtr;ptr->Next=qtr;C．qtr->Next=ptr->Next;D．ptr->Next=qtr;ptr=qtr;qtr->Next=ptr;三、问答1．试问，如下的线性表：L=(29，25，21，17，13，11，7，5，3，1)是有序线性表还是无序线性表？答：L是一个有序线性表。2．线性表L第i个存储结点ai的起始地址LOC（ai）可以通过下面的公式计算得到：LOC（ai）=LOC（ai-1）+k其中k表示存储结点的长度。这个公式对吗？为什么？答：这个公式是对的，因为第i个存储结点ai的起始地址LOC（ai），实际上就是等于第i-1个存储结点ai-1的起始地址LOC（ai-1）加上一个存储结点的长度k得到。3．试说明创建顺序表算法Create_Sq()中，Sq_max和Sq_num的不同之处。答：Sq_max代表的是顺序表的最大长度，也就是它最多可以容纳下多少个数据元素，顺序表创建后，Sq_max是一个保持不变的常量；Sq_num代表的是顺序表内当前拥有的数据元素个数，在顺序表创建后，随着对数据元素进行的插入、删除操作，Sq_num将会不断地发生变化。4．如何判断一个顺序表是否为空？答：只需判定Sq_num的当前值是多少，如果Sq_num为0，则表示顺序表Sq为空，否则表示该顺序表里有数据元素存在。5．在算法2-3里，操作“Sq_num=Sq_num-1”的作用是什么？没有它行吗？答：该操作是非常重要的，因为顺序表里当前拥有的元素个数是通过Sq_num来记录的，删除了一个元素，Sq_num必须减1，这样才能正确反映出删除后表中元素的个数。所以，没有这个操作是不行的。6．在算法2-9里，如果现在是把一个结点插入到单链表尾结点的后面。按照算法的描述，能够保证插入后最后一个结点的Next域为“Λ”吗？答：能够。因为原来ptr->Next里是“Λ”，做了第1步操作：qtr->Next=ptr->Next;后，就是把插入结点的Next域置为“Λ”。7．在一个单链表中，为了删除指针ptr所指的结点，有人编写了下面的操作序列。读懂并加以理解。试问，编写者能够达到目的吗？其思想是什么？x=ptr->Data;qtr=ptr->Next;ptr->Data=ptr->Next->Data;-42- 习题解答ptr->Next=ptr->Next->Next;free(qtr);答：能够达到删除指针ptr所指结点的目的。编写者的思想是不去直接删除ptr所指的结点，而是在把ptr直接后继的Data域内容写入ptr所指结点的Data域之后，把它的直接后继删除。对于单链表来说，得到一个结点的直接后继容易，得到它的直接前驱难，所以这样的设计是有其可取之处的。8．在一个单链表中，为了在指针ptr所指结点之前插入一个由指针qtr所指的结点，有人编写了下面的操作序列，其中temp是一个临时工作单元。读懂并加以理解。试问，编写者能够达到目的吗？其思想是什么？qtr->Next=ptr->Next;ptr->Next=qtr;temp=ptr->Data;p->Data=qtr->Data;qtr->Data=temp;答：能够达到在指针ptr所指结点之前插入一个由指针qtr所指结点的目的。编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难，因此在这里先把qtr所指结点插入到ptr所指结点的后面，暂时成为它的直接后继。然后通过临时工作单元temp，将ptr及qtr所指结点的Data域内容进行交换，从而达到插入的目的。9．打算形成一个有表头结点的循环双链表，初始时除了每个结点的Next域已经链接好外，它们的Prior域还都是空的。有人编写了下面的算法，试图完成Prior域的链接：Com_Cd(Cd_h){ptr=Cd_h->Next;qtr=Cd_h;while(ptr!=Cd_h){ptr->Prior=qtr;qtr=ptr;ptr=ptr->Next;}Cd_h->Prior=qtr;}读懂并理解它，解释为什么能够完成各结点的Prior域的链接？答：算法中用两个指针ptr和qtr配合，从头到尾扫描这个循环双链表，以达到让每个结点的Prior域指向其直接前驱的目的。四、应用1．设计一个计算表头指针为Lk_h的单链表长度（即结点个数）的算法。答：算法设计如下：Length_Lk(Lk_h){n=0;ptr=Lk_h;/*ptr指向起始结点*/while(ptr!=NULL)-42- 习题解答{ptr=ptr->Next;n=n+1;/*n为结点计数单元*/}return(n);}2．用总是在表的头部插入整数结点的方法建立一个单链表，当输入为0时，建表过程结束。答：算法设计如下：Clink(){Lk_h=NULL;scanf(%d,&x);while(x!=“0”){ptr=malloc(size);ptr->Data=x;ptr->Next=Lk_h;Lk_h=ptr;scanf(%d,&x);}returnLk_h;}3．一个不带表头结点的循环双链表Ck的表头指针为Ck_h，要在指针ptr指向处前插入一个rtr所指结点。模仿图2-21，对一般插入位置标示出下面4个操作步骤：①rtr->Next=ptr;②rtr->Prior=ptr->Prior;③ptr->Prior->Next=rtr;④ptr->Prior=rtr;答：4个操作步骤的具体功能体现如下图所示。4．试设计一个算法copy(Ck_h1,Ck_h2)，将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1的内容，复制到一个不带表头结点的、以Ck_h2为表头指针的单链表Ck2中。答：算法具体如下。Copy(Ck_h1,Ck_h2){ptr=Ck_h1->Next;-42- 习题解答qtr=Ck_h2;while(ptr!=NULL){rtr=malloc(size);rtr->Data=ptr->Data;qtr->Next=rtr;qtr=rtr;ptr=ptr->Next;}qtr->Next=NULL;}5．已知一个带表头结点的递增单链表。试编写一个算法，功能是从表中去除值大于min、且值小于max的数据元素。（假定表中存在这样的元素）答：所需算法编写如下。Del_Sq(Lk_h,nim,max){ptr=Lk_h->Next;/*ptr指向链表的起始结点*/while((ptr!=NULL)&&(ptr->Data<=min))/*跳过所有值<=min的结点*/{qtr=ptr;ptr=ptr->Next;}while((ptr!=NULL)&&(ptr->DataNext;qtr->Next=ptr;/*qtr指出第1个大于max的结点位置，完成链接*/}6．已知一个带表头结点的无序单链表。试编写一个算法，功能是从表中去除所有值大于min、且值小于max的数据元素。答：所需算法编写如下，其中指针ptr总是指向当前被检查的结点，qtr总是指向被检查结点的直接前驱。Del_Lk(Lk_h,min,max){ptr=Lk_h->Next;/*ptr指向单链表的起始结点*/while(ptr!=NULL)/*扫视直到链尾结点*/{if((ptr->Data<=min)||(ptr->Data>=max)/*不满足删除条件*/{qtr=ptr;/*往后移动qtr和ptr*/ptr=ptr->Next;}else/*删除ptr所指结点，往后移动ptr*/{qtr->Next=ptr->Next;free(ptr);-42- 习题解答ptr=qtr->Next;}}}7．一个单链表Lk的表头指针为Lk_h，不同结点的Data域值有可能相同。编写一个算法，功能是计算出Data域值为x的结点的个数。答：算法应该遍历链表的每一个结点，遇到一个结点的Data域值为x时，计数器n就加1。最后返回计数器n。Count_Lk(Lk_h){n=0;ptr=Lk_h;while(ptr!=NULL){if(ptr->Data==x)n=n+1;ptr=ptr->Next}return(n);}第3章习题解答一、填空1．限定插入和删除操作只能在一端进行的线性表，被称为是栈。2．如果在顺序栈满时仍打算进行进栈操作，就称为发生了“上溢”出错。3．如果在顺序栈空时仍打算进行出栈操作，就称为发生了“下溢”出错。4．在具有n个数据结点的循环队列中，队满时共有n-1个数据元素。5．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。最终这个堆栈从栈顶到栈底的余留元素应该是DA。6．中缀表达式(a+b)-(c/(d+e))对应的后缀表达式是ab+cde+/-。7．函数的递归调用有两种形式：如果一个函数是直接调用自己，就称其为直接递归调用；如果一个函数是通过另一个函数来调用自己，就称其为间接递归调用。8．设某栈的元素输入顺序是1、2、3、4、5，想得到4、3、5、2、1的输出顺序。那么push、pop的操作序列应该是push、push、push、push、pop、pop、push、pop、pop、pop。9．设链栈的栈顶指针为Ls_top，那么它非空的条件应该是Ls_top!=NULL。10．队列中，允许进行删除的一端称为队首。二、选择1．一个栈的元素进栈序列是a、b、c、d、e，那么下面的C不能做为一个出栈序列。A．e、d、c、b、aB．d、e、c、b、a-42- 习题解答C．d、c、e、a、bD．a、b、c、d、e2．判定一个顺序队列Qs（最多有n个元素）为空的条件是C。A．Qs_rear-Qs_front==n*sizeB．Qs_rear-Qs_front+1==n*sizeC．Qs_front==Qs_rearD．Qs_front==Qs_rear+size3．判定一个顺序队列Qs（最多有n个元素）真满的条件是A。A．Qs_rear-Qs_front==n*sizeB．Qs_rear-Qs_front+1==n*sizeC．Qs_front==Qs_rearD．Qs_front==Qs_rear+size4．在一个链式队列Lq中，Lq_front和Lq_rear分别为队首、队尾指针。现在由指针ptr所指结点要进队，则插入操作应该是B。A．Lq_front->Next=ptr;Lq_front=ptr;B．Lq_rear->Next=ptr;Lq_rear=ptr;C．ptr->Next=Lq_rear;Lq_rear=ptr;D．ptr->Next=Lq_front;Lq_front=ptr;5．链栈与顺序栈相比，一个较为明显的优点是D。A．通常不会出现栈空的情形B．插入操作更加便利C．删除操作更加便利D．通常不会出现栈满的情形6．向链栈插入一个结点时，操作顺序应该是C。A．先修改栈顶指针，再插入结点B．无须修改栈顶指针C．先插入结点，再修改栈顶指针D．谁先谁后没有关系7．从链栈中删除一个结点时，操作顺序应该是A。A．先保存被删结点的值，再修改栈顶指针B．先修改栈顶指针，再保存被删结点的值C．无须修改栈顶指针的值D．谁先谁后没有关系8．一个循环队列的最大容量为m+1，front为队首指针，rear为队尾指针。那么进队操作时求队位号应该使用公式D。A．Cq_front=(Cq_front+1)%mB．Cq_front=(Cq_front+1)%(m+1)C．Cq_rear=(Cq_rear+1)%mD．Cq_rear=(Cq_rear+1)%(m+1)9．在一个循环顺序队列里，队首指针Cq_front总是指向B。A．队首元素B．队首元素的前一个队位C．任意位置D．队首元素的后一个队位10．若一个栈的进栈序列是1、2、3、4，那么要求出栈序列为3、2、1、4时，进、出栈操作的顺序应该是A。（注：所给顺序中，I表示进栈操作，O表示出栈操作）A．IIIOOOIOB．IOIOIOIOC．IIOOIOIOD．IOIIIOOO三、问答1．若元素进栈的序列是1、2、3、…、n，有一个出栈序列的第1个元素是n。那么，这个出栈序列的第i个元素是什么？答：由于栈具有“先进后出”的特性，因此只有将1、2、3、…、n依次都进栈后，出栈序列的第1个元素才能是n。所以，在这个出栈序列里，第个i元素应该是n-i+1。2．设元素进栈的次序是a，b，c，d，e。试问，在下面所列的6种元素序列里，哪些可以是这个栈的出栈序列？A．c，e，a，b，dB．c，b，a，d，eC．d，c，a，b，eD．a，c，b，e，dE．a，b，c，d，eF．e，a，b，c，d-42- 习题解答答：对A进行分析。由于是c第1个出栈，因此b必须先于a出栈。但所给序列里，a却先于b出栈，故A不能是该栈的出栈序列。对C进行分析。由于是d第1个出栈，因此a、b、c三者出栈的顺序必须是c、b、a。但所给序列里，a却先于b出栈，故C不能是该栈的出栈序列。对F进行分析。由于是e第1个出栈，因此a、b、c、d四者出栈的顺序必须是d、c、b、a。但所给序列里，它们的出栈顺序全乱了，故F不能是该栈的出栈序列。因此，所列的6种元素序列里，只有B、D、E可以是这个栈的出栈序列。3．有一个顺序栈Ss，其栈顶指针为Ss_top，栈底指针为Ss_bottom。阅读下面给出的算法，其中的两条prinf函数的输出结果各是什么？(算法中的Push_Ss(Ss_top,ch)表示将ch里的元素进栈，Pop_Ss(Ss_top,ch)表示将栈顶元素出栈，存入ch中)print(){for(ch=‘A’;ch<=‘A’+12;ch++){Push_Ss(Ss_top,ch);printf(“%c”,ch);}while(Ss_top!=Ss_bottom){Pop_Ss(Ss_top,ch);printf(“%c”,ch);}}答：第1条printf的输出是前13个英文大写字母ABCDEFGHIJKLM，第2条printf输出的是前面输出的倒置，即MLKJIHGFEDCBA。4．设有6个元素a1、a2、a3、a4、a5、a6，它们以此顺序依次进栈。假定要求它们的出栈顺序是a4、a3、a2、a6、a5、a1，那么应该如何安排push和pop操作序列？答：所需的push和pop操作序列如下：push，push，push，push，pop，pop，pop，push，push，pop，pop，pop5．有中缀表达式a/(b/(c/(d/e)))。有人将其转化为相应的后缀表达式是abcde////。这一转化结果对吗？答：转化结果是对的。6．试述栈与队列各自具有什么样的逻辑特点？它们之间又有什么共同点？答：对于栈来说，由于只能在栈顶处进行插入和删除操作，这就使得数据元素到达栈（即往栈里插入元素）的顺序与数据元素离开栈（即从栈里删除元素）的顺序恰好相反。所以，堆栈的逻辑特点是后进先出（LIFO），或先进后出（FILO）。而对队列来说，插入在一端进行，删除在另一端进行，这就使得数据元素到达队列（即往队列里插入元素）的顺序与数据元素离开队列（即从队列里删除元素）的顺序是完全一致的。所以，队列的逻辑特点是先进先出（FIFO）或后进后出（LILO）。它们之间的共同之处是插入和删除只能在表的端点处进行（要知道，对于线性表，可以在表的任何位置处插入和删除）。7．有一个顺序队列，最大容量为5。初始时有Qs_front=Qs_rear=0。画出做下列操作时队列及其首、尾指针的变化情况。若不能进队时就停止，并简述原因。（1）d、e、b进队（2）d、e出队（3）i、j进队（4）b出队（5）n、o、p进队-42- 习题解答答：队列及其首、尾指针的变化情况如下图所示。在做（5）时，由于队满（假溢出），故操作停止。8．有一个递归函数Write()，定义如下：Write(x){if(x!=0){Write(x-1);for(j=1;j<=x;j++)printf(“%3d”,x);printf(“/n”);}}试问，Write(5)的输出结果是什么？答：输出结果为：122333444455555四、应用1．编写一个判顺序栈空的算法。要求是如果栈空，返回1，否则返回0。答：算法设计如下：Empty_Ss(Ss,Ss_top){if(Ss_top==0)/*栈空*/return(1);else/*栈不空*/return(0);}2．编写一个算法，它能够输出顺序队列Qs上所有元素的值。答：算法编写如下：Print_Qs(Qs_front,Qs_rear){if(Qs_front==Qs_rear)/*队列空！*/-42- 习题解答printf(“queueisempty!”);else/*队列非空！*/{qtr=Qs_front;while(qtr<=Qs_rear){printf(“%d”,*qtr);qtr++;}}}3．编写一个算法，它能够取得链式队列首元素的值。答：取得链式队列首元素的值，只有在队列非空的前途下才有意义。算法编写如下。Getf_Lq(Lq_front,Lq_rear){if(Lq_front==Lq_rear)/*队列空！*/printf(“Thelinkedqueueisempty!”);else/*队列非空！*/{ptr=Lq_front->Next;x=ptr->Data;return(x);}}4．有五个人顺序坐在一起。问第5个人多少岁，回答说比第4个人大2岁；问第4个人多少岁，回答说比第3个人大2岁；问第3个人多少岁，回答说比第2个人大2岁；问第2个人多少岁，回答说比第1个人大2岁；问第1个人多少岁，回答说是10岁。试给出该递归的公式、结束条件，并编写出相应的递归算法。答：递归公式为：age(n)=age(n-1)+22<=n<=5递归的结束条件是：age(1)=10相应算法为：Age(n){if(n==1)return(10);else{x=age(n-1)+2;return(x);}}-42- 习题解答5．将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值。具体地，要开辟一个运算符栈op和一个数组st。在自左至右扫描算术表达式时，遇到操作数就直接顺序存入st；遇到运算符时就与op栈顶元素比较，高则进栈，不高则让栈顶元素出栈，存入st，然后该运算符再次去与新的op栈顶元素比较。最后，在数组st里形成所需要的后缀表达式。试用这种方法，用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式。答：相应的后缀表达式是583*+2-，其图示如下。6．语言编译时，总是先将中缀表达式转化成为后缀表达式，然后再计算后缀表达式的值，因为后缀表达式已经去除了括号，没有了运算符的优先级。计算后缀表达式的方法是只开辟一个对象栈ob，当从左往右扫描后缀表达式时，每遇到操作数就让其进入ob栈，每遇到运算符就从ob栈里弹出两个操作数进行当前的计算，并将计算结果进ob栈。该过程直至整个表达式结束。ob栈的栈顶值就是最终结果。试用图示计算后缀表达式583*+2-的值。答：计算结果为27，其图示如下。第4章习题解答一、填空1．字符串是一种特殊的线性表，特殊在于它的数据元素只能是字符，特殊在于串可以作为一个整体参与所需要的处理。2．空格串是由空格组成的串，空串是不含任何字符的串，因此空格串和空串不是一个概念。3．字符串中任意多个连续字符所组成的子序列，被称作是这个串的“子串”，这个字符串本身则称为“主串”。-42- 习题解答4．我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符ASCII码的比较而得到的结论。5．设有串s=“Iamateacher”。该串的长度是14。6．设有三个串：s1=“Good”，s2=“Ф”，s3=“bye!”。则s1、s2、s3连接后的结果串应该是“Goodbye!”。7．所谓“数组”，是指n（n>1)个具有相同类型的数据的有序集合。8．矩阵与通常所说的二维数组有关。9．所谓“特殊矩阵”，是指那些元素在矩阵中的分布具有一定规律性的矩阵；而矩阵中的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“稀疏矩阵”。10．在一个n阶方阵A中，若所有元素都有性质：aij=aji(1≤i,j≤n)，就称其为对称矩阵。二、选择1．设有两个串s1和s2。求s2在s1中首次出现的位置的操作称为B。A．连接B．模式匹配C．求子串D．求串长2．有串：“Ф”，那么它的长度是B。A．0B．1C．2D．33．设有串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))的操作结果是串D。A．BCDEFB．BCDEFGC．BCPQRSTD．BCDEFEF4．设有一个8阶的对称矩阵A，采用以行优先的方式压缩存储。a11为第1个元素，其存储地址为1，每个元素占一个地址空间。试问元素a85的地址是A。A．33B．30C．13D．235．一个m*m的对称矩阵，如果以行优先的方式压缩存入内存。那么所需存储区的容量应该是C。A．m*(m-1)/2B．m*m/2C．m*(m+1)/2D．(m+1)*(m+1)/26．二维数组M的每个元素含4个字符（每个字符占用一个存储单元），行下标i从1变到5，列下标j从1变到6。那么按行顺序存储时元素M[4][6]的起始地址与M按列顺序存储时元素B的起始地址相同。A．M[3][5]B．M[4][5]C．M[4][6]D．M[5][5]7．二维数组M中的每个元素占用3个存储单元，行下标i从1变到8，列下标j从1变到10。现从首地址为SA的存储区开始存放A。那么该数组以行优先存放时，元素A[8][5]的起始地址应该是C。A．SA+141B．SA+180C．SA+222D．SA+2258．设有一个5阶上三角矩阵A，将其元素按列优先顺序存放在一维数组B中。已知每个元素占用2个存储单元，B[1]的地址是100。那么A[3][4]的地址是A。A．116B．118C．120D．122（分析：把一个上三角矩阵按列优先顺序存放在一个一维数组B中，元素的顺序是：a11a12a22a13……A[3,4]的地址=100+a34前面的元素个数*2=100+（前3列的个数+本列a34前面的个数）*2=100+（（1+2+3）+2）*2=116-42- 习题解答）三、问答1．为什么可以把二维数组视为是一种线性结构？答：实际上，二维数组是一种较为复杂的数据结构，数据元素之间的关系并不是线性的。不过，如果我们把它看作是其每个元素为一维数组的一个一维数组，那么就可以把二维数组视为是线性表的一种推广（因为一维数组即是线性表），因此可以说它的数据元素间的逻辑关系呈现出的是一种线性结构。2．图4-34（a）所示为一个特殊矩阵A5´5，这种形式的矩阵被称作是“带状矩阵”，因为它的非零元素都分布在以主对角线为中心的一个带状区域里，其他位置上的元素全部为0。可以以行优先的方式，将其压缩存储到一个一维数组里，如图4-34（b）所示。试找出元素下标i、j与存储序号k间的对应关系。图4-34带状矩阵答：压缩存储元素下标i、j与存储序号k间的对应关系是：k=2*i+j–23．一个稀疏矩阵如图4-35所示。试问，它对应的三元组表是什么？图4-35稀疏矩阵示例答：它所对应的三元组表如下。-42- 习题解答四、应用1．请将算法4-1改为用while循环来实现。答：改写的算法4-1可以是如下所示。Concat_St(St1,St2){charSt3[maxsize];/*创建一个新的顺序串为空*/St3_len=0;if(St1_len+St2_len>maxsize+1)/*新串放不下两个串*/{printf(“两串长度之和超长！”);return(NULL);}else{i=1；while(i<=St1_len){St3[i]=St1[i];i++;}j=1;while(j<=St2_len){St3[j+St1_len]=St2[j];j++;}St3_Len=St1_len+St2_len;St3[St3_len+1]=“”;return(St3);}}2．算法4-2也可以这样来描述，直接核对相应位置上的字符是否相同，然后再分别情况做出判断：一是有不相同的字符出现，一是有一个字符串比另一个字符串长，最后则是两个串完全相等。按照这样的设计，改写算法4-2。答：按照这样的设计，算法4-2的描述如下。Equal_St(St1,St2){i=1;while(St1[i]!=“”)/*两串进行比较*/{if(St1[i]==St2[i])/*相等，继续比较*/i++;else/*不等，强制退出*/black;-42- 习题解答}if(St1[i]!=St2[i])/*比较是由于相应位置上的字符不同而结束*/return(0);else{if(St1[i]!=“”||St2[i]!=“”)/*比较是由于长度不同而结束*/return(0);elsereturn(1);}}3．算法：Trans_St(St，ch1，ch2){i=1；While(St[i]！=""){if(St[i]==ch1)St[i]==ch2；i++；}}是通过while循环来实现将顺序串St中所有的字符ch1改为字符ch2的。请改写成用for循环来实现相同的功能。答：用for循环改写的算法如下。Trans_St(St,ch1,ch2){for(i=1;i<=St_len;i++)if(St[i]==ch1)St[i]=ch2;}4．编写一个算法，将顺序串St中所有的大写字母全部换成小写字母。(提示：大写英文字母A~Z对应的ASCII码为65~90，小写英文字母a~z对应的ASCII码为97~122，在大写字母的ASCII码上加32，就是对应小写字母的ASCII码)答：算法编写如下。Catosm_St(St){for(i=1;i<=St_len;i++)if((A<=St[i])&&(St[i]<=Z))St[i]=St[i]+32;}5．已知顺序串St，编写一个算法，将其中第i个字符开始连续的j个字符删除。（提示：先要判断所给参数是否合理，然后通过将第i+j开始往后的字符全部移动j个位置，完成删除的功能）-42- 习题解答答：算法编写如下。Moveij(St,i,j){if(i+j<=St_len){for(k=i+j;k<=St_len;k++)/*将i+j开始往后的所有字符前移j个位置*/St[k-j]=St[k];St_len=St_len-j;/*修改St的长度*/St[St_len]=“”;/*安放新的串结束符*/}elseprintf(“参数不合理，无法进行删除！”);}6．在算法4-12的最后，为了释放被删结点使用的存储空间，先做了操作：ptr->Next=NULL;把由指针ptr指向的最后一个要释放空间的结点的Next域设置为NULL，然后通过while循环完成释放。其实，由于知道要释放空间的结点共有m个，因此可以取消这一操作，改用for循环通过m来控制释放空间的结点个数。请试着按照这一思路改写那一小段算法。答：改写一小段算法如下。for(j=1;j<=m;j++){ptr=rtr;rtr=rtr->Next;free(ptr);}7．编写一个算法，功能是复制一个链串。答：复制一个完整的链串，是一件比较容易的事情。其算法起名为Copy_Lt()，参数为Lt1。具体编写如下。Copy_Lt(Lt1){ptr=Lt1_h;rtr=malloc(size);rtr->Data=ptr->Data;Lt2_h=rtr;ptr=ptr->Next;while(ptr!=NULL){qtr=malloc(size);qtr->Data=ptr->Data;rtr->Next=qtr;ptr=ptr->Next;}rtr->Next=NULL;return(Lt2_h);-42- 习题解答}算法是通过while循环，不断修改指针ptr，以便指向链串Lt1的各个结点；指针rtr总是指向当前已形成的新链串Lt2的最后一个结点；用指针qtr指向刚申请到的新存储结点，并把它链入到rtr所指结点的后面。8．已知两个mⅹn的矩阵A和B。编写一个算法，求C=A+B。即C也是一个mⅹn的矩阵，其元素满足条件：cij=aij+bij（1≤i≤m，1≤j≤n）答：算法名为Add_Mt()，参数为A，B，C。Add_Mt(A,B,C){for(i=1;i<=m;i++)for(j=1;j<=n;j++)C[i][j]=A[i][j]+B[i][j];}第5章习题解答一、填空1．结点数为7的二叉树的高度最矮是2，最高是6。2．给定二叉树的结点数，要使树高为最大，那么该树应该是单枝形状。3．给定二叉树的结点数，要使树高为最矮，那么该树应该是完全二叉树形状。4．如果一棵满二叉树的深度为6，那么它共有127个结点，有64个叶结点。5．有15个结点的二叉树，最少有1个叶结点，最多有8个叶结点。6．由n个带权值的叶结点生成的哈夫曼树，最终共有2n-1个结点。7．将一棵完全二叉树按层次进行编号。那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是2i；如果有右孩子，则右孩子的编号应该是2i+1。8．若二叉树共有n个结点，采用二叉链表存储结构。那么在所有存储结点里，一共会有2n个指针域，其中有n+1个指针域是空的。9．深度为5的二叉树，至多有31个结点。10．在二叉树中，有一个结点具有左、右两个孩子。那么在中序遍历序列里，它的右孩子一定排在它的右边。二、选择1．在所给的4棵二叉树中，C不是完全二叉树。2．把一棵深度为3的左单支二叉树改造成完全二叉树时，要增添D个空结点。A．10B．8C．6D．43．设有一棵5个结点的二叉树，其先序遍历序列为：A-B-C-D-E，中序遍历序列为：B-A-D-C-E，那么它的后序遍历序列为B。A．A-B-D-E-CB．B-D-E-C-A-42- 习题解答C．D-E-C-A-BD．A-B-C-D-E4．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是B。A．无左、右孩子B．有左孩子，无右孩子C．有右孩子，无左孩子D．有左、有孩子5．深度为6的二叉树，最多可以有A个结点。A．63B．64C．127D．1286．在一棵非空二叉树的中序遍历序列里，根结点的右边D结点。A．只有左子树上的部分B．只有左子树上的所有C．只有右子树上的部分D．只有右子树上的所有7．在任何一棵二叉树的各种遍历序列中，叶结点的相对次序是A。A．不发生变化B．发生变化C．不能确定D．以上都不对8．权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是D。A．18B．28C．19D．299．一棵二叉树度2的结点数为7，度1的结点数为6。那么它的叶结点数是C。A．6B．7C．8D．910．在一棵二叉树中，第5层上的结点数最多是C个。A．8B．15C．16D．32三、问答1．试问满二叉树与完全二叉树之间有何关系？答：由满二叉树与完全二叉树的定义可知，满二叉树一定是一棵完全二叉树，但完全二叉树却不一定是一棵满二叉树。如果一棵二叉树不是完全二叉树，那么它绝对不可能是一棵满二叉树。这就是满二叉树与完全二叉树之间的关系。2．请画出由3个结点构成的所有二叉树，它们的高度分别是多少？答：大小为3的不同的二叉树共有5种，如下图所示。其中，4棵树的高度为2，1棵树的高度为1。3．一棵高度为3的满二叉树有多少个叶结点？有多少个度为2的结点？总共有多少个结点？答：有23=8个叶结点，有度为2的结点23-1=7个，总共有23+1-1=24-1=15个结点。4．有人说，任何一棵非空满二叉树，它的叶结点数等于其分支结点数加1。这样的一个结论正确吗？请说明理由。（提示：利用性质5-3）答：在我们介绍的二叉树性质中，只有性质5-3是涉及叶结点数与（度为2的）分支结点数的关系的。对于满二叉树来说，所有的分支结点都是度为2的结点。因此，正好可以直接利用性质5-3得出所需要的结论。所以，此人说的结论是完全正确的。5．有人说，有一棵结点数为n>1的二叉树，只包含有一个叶结点。这可能吗？如果可能的话，这样一棵二叉树应该是个什么样子呢？答：这是完全可能的，这种二叉树是从根结点开始只有左子树，或只有右子树的单支二叉树，如图所示。-42- 习题解答6．试问，什么样的二叉树其先序遍历序列与中序遍历序列相同？答：先序遍历序列与中序遍历序列相同的二叉树，或是空二叉树，或是任一结点都没有左孩子的非空二叉树。7．分别写出如图5-32所示二叉树的先序、中序、后序遍历序列。图5-32二叉树示例答：先序遍历序列为：A-B-C-D-F-G-H-E，中序遍历序列为：B-A-D-G-F-H-C-E，后序遍历序列为：B-G-H-F-D-E-C-A。四、应用1．对一个二叉树进行顺序存储，各结点的编号及数据如表所示：编号i1234571011数据xABCDEFGH试画出对应的二叉树，并给出先序、中序、后序遍历该二叉树后，所得到的各种结点序列。答：对应的二叉树如图所示。其先序遍历序列是：A-B-D-E-G-H-C-F；中序遍历序列是：D-B-G-E-H-A-C-F；后许遍历序列是：D-G-H-E-B-F-C-A。2．已知中序遍历序列为：A-B-C-E-F-G-H-D，后序遍历序列为：A-B-F-H-G-E-D-C。试画出这棵二叉树。答：这棵二叉树如应用题2答案图所示。-42- 习题解答3．已知前序遍历序列为：A-B-C-D-E-F，中序遍历序列为：C-B-A-E-D-F。试画出这棵二叉树。答：这棵二叉树如应用题3答案图所示。4．若一棵二叉树的左、右子树均有3个结点，其左子树的先序遍历序列与中序遍历序列相同，右子树的中序遍历序列与后序遍历序列相同。请画出这棵二叉树。答：这棵二叉树如应用题4答案图所示。5．理解算法5-10。在图5-25(b)的基础上，进行下一次组合。试给出第2次组合后数组的情形，以及那时二叉树的样子。答：第2次组合后数组的情形如下图(a)所示，那时二叉树的样子如下图(b)所示。6．权值序列为：10、16、20、6、30、24，请用图示来表达构造一棵哈夫曼树的全过程。答：构造这棵哈夫曼树的全过程如下所示。-42- 习题解答7．一棵有11个结点的二叉树的顺序存储情况如表所示，序号3的结点是根结点。画出该二叉树，并给出它的先序、中序、后序遍历序列（其中“^”表示空）。序号1234567891011Lchild6^7^8^5^2^^DataMFAKBLCRDSERchild^^^9^10411^^^答：二叉树如图所示，先序遍历序列为：A-C-B-R-S-E-D-F-M-L-K，中序遍历序列为：R-B-S-C-E-A-F-D-L-K-M，后序遍历序列为：R-S-B-E-C-F-K-L-M-D-A。第6章习题解答一、填空1．树中结点的度，是指结点拥有子树的个数。2．树中除根结点外，其他结点有且只有一个前驱结点，但可以有零个或多个后继结点。3．树中一个结点的直接后继，或一个结点子树的根结点，被称作是该结点的孩子结点。4．树中一个结点的子树中的任何结点，都被称作是该结点的子孙结点。5．树中有同一双亲的结点，被互称为兄弟结点。6．所谓结点的深度，即是指该结点位于树的层次数。7．双亲位于树中相同层次上的结点，互称为堂兄弟结点。8．在数据结构中，把n（n≥0）棵互不相交的树的集合称为森林。9．在如图6-21所示的树中，，结点H的祖先是A、D、G。图6-21树示例图6-22树示例10．在树中，一个结点的孩子个数，称为该结点的度。11．一棵树的形状如图6-22所示。它的根结点是A，叶结点是-42- 习题解答E、G、I、J、K、L、N、O、P、Q、R，这棵树的度是3，这棵树的深度是4，结点F的孩子结点是J、K，结点G的父结点是C，结点M、H、D、A是结点R的祖先。二、选择1．已知一棵单右支的二叉树，如下左图所示。把它还原成森林，应该是D。A．B．C．D．2．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的先序遍历是对Bt的A。A．先序遍历B．中序遍历C．后序遍历D．无法确定3．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的B。A．先序遍历B．中序遍历C．后序遍历D．无法确定4．设森林F中有3棵树，依次有结点n1、n2、n3个。把该森林转换成对应的二叉树后，该二叉树的右子树上的结点个数是D。A．n1B．n1+n2C．n3D．n2+n35．设有由三棵树T1、T2、T3组成的森林，其结点个数分别为n1、n2、n3。与该森林相应的二叉树为Bt。则该二叉树根结点的左子树中应该有结点A个。A．n1-1B．n1C．n1+1D．n1+n26．现有一棵度为3的树，它有两个度为3的结点，一个度为2的结点，两个度为1的结点。那么其度为0的结点的个数应该是C。A．5B．8C．6D．9注意：有n个结点的树，树中所有结点的度之和为n-1。现在这棵树应该满足条件：n-1=2*3+1*2+2*1=10这表示该树共有11个结点（加上一个根结点）。在11个结点里，减去度为3、2、1的结点数5，剩下的就是度为0的结点。所以，该树有叶结点6个。7．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有B个结点。A．n-2B．n-1C．n+1D．n+28．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的右子树上共有A个结点。A．0B．nC．n+1D．n+29．下列说法中，正确的是A。A．树的先序遍历序列与其对应的二叉树的先序遍历序列相同B．树的先序遍历序列与其对应的二叉树的后序遍历序列相同C．树的后序遍历序列与其对应的二叉树的先序遍历序列相同D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同三、问答1．如图6-23所示的两棵树是一样的吗？为什么？答：从图6-23(a)知，该树的根结点为A，下面有两棵子树，其中的一棵子树是最小树，只有根结点为B；另一棵子树的根结点为C，下面又有一棵最小子树，它的根结点为D。-42- 习题解答从图6-23(b)知，该树的根结点也是A，它的下面也有两棵子树，这两棵子树的构成也与图6-23(a)里的相同。因此如果把树的子树视为是无序的，那么该图所展示的两棵树是一样的，否则是不一样的。图6-23树示例2．二叉树与树有什么不同？答：二叉树是一种树，但是一种特殊的树。第一，二叉树的每个结点至多可以有两棵子树，但树的每个结点可以有多棵子树；第二，二叉树的子树有左、右之分（即是有序的），但树的子树通常是不分顺序的。3．为什么对于二叉树有中序遍历，而对一般树却没有中序遍历？答：二叉树有中序遍历，是因为二叉树的每个结点最多只有两个子树，且子树有左、右之分，因此可以规定在访问左子树和右子树的中间去访问子树的根结点。但对于一般的树，其结点可以有任意数目的子树，因此，无法规定怎样的访问顺序才算是“中序”。所以，对一般的树没有中序遍历。4．对于树的各种遍历，哪一种遍历是（1）首先访问树的根结点？（2）位于最左边的结点最先访问？（3）根结点最后访问？（4）最右边的结点最后访问？答：（1）层次遍历和先序遍历总是首先访问树的根结点；（2）后序遍历总是最先访问位于树最左边的结点；（3）后序遍历总是最后访问树的根结点；（4）前序遍历总是最后访问树的最右边的结点。5．一棵度为2的树与一棵二叉树有什么区别？答：从形状上看，一棵度为2的树与一棵二叉树没有什么区别。但度为2的树结点的子树一般是无序的，没有左、右之分；而二叉树结点的子树是有序的，它们之间有左、右之分，不能随意换位。四、应用1．已知一棵树的孩子链表表示法如图6-24所示，试画出该树。图6-24一棵树的孩子链表表示法图6-25树示例答：该树形状如下图所示。2．已知一棵树如图6-25所示。-42- 习题解答请画出该树的以下存储结构：（1）双亲表示法；（2）带双亲的孩子链表表示法（我们介绍过双亲表示法和孩子链表表示法，没有介绍过带双亲的孩子链表表示法。望能够把两者结合起来）；（3）孩子/兄弟链表表示法。答：（1）双亲表示法如下图(a)所示；（2）带双亲的孩子链表表示法如图下(b)所示；（3）孩子/兄弟链表表示法如下图(c)所示。3．将图6-26所示的二叉树转换成相应的森林。图6-26二叉树示例图6-27树示例答：转换成的森林如下图所示。4．给出如图6-27所示树的先序遍历序列和后序遍历序列。答：该树的先序遍历序列为：A-B-E-F-K-L-M-C-G-D-H-I-J；该树的后序遍历序列是：E-K-M-L-F-B-G-C-H-I-J-D-A。-42- 习题解答5．将图6-28所示的森林转换成对应的二叉树。图6-28森林示例图6-29树示例答：对应的二叉树如下图所示。6．将图6-29所示的树转换成相对应的二叉树。答：对应的二叉树如下图所示第7章习题解答一、填空1．由4个顶点组成的一个连通图，应该有边6条。2．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要3条边。3．在无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，那么则称顶点vi和vj互为邻接点。4．图中顶点vi的“度”，是指与它相邻接的顶点的个数，并记为D(vi)。-42- 习题解答5．在有向图中，把从顶点vi到顶点vj的弧记为，而把从顶点vj到顶点vi的弧记为，这是两条不同的弧。6．对于一个无向图，其邻接矩阵中第i行（或第i列）里非零或非∞元素的个数，正好是第i个顶点vi的度。7．对于一个有向图，其邻接矩阵中第i行里非零或非∞元素的个数，正好是第i个顶点vi的出度；其邻接矩阵中第i列里非零或非∞元素的个数，正好是第i个顶点vi的入度。8．在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vi与vj是连通的。9．如果无向图G中任意一对顶点之间都是连通的，则称该图G为连通图，否则是非连通图。10．在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个连通分量。11．包含无向连通图G的所有n个顶点在内的极小连通子图，是这个图的生成树。12．只要在无向连通图的生成树里减少任意一条边，它就成为了一个非连通图。13．对图的广度优先搜索，类似于对树进行按层次遍历。14．拓扑排序是得到AOV网的一个线性序列，使得网中所有顶点间的优先关系在序列中得以体现。15．已知无向图的顶点个数为n，边数为e。那么，在其邻接表表示法中，链表结点数与单链表表头结点数之和是n+2e。二、选择1．在一个有n个顶点的无向图中，要连通全部顶点，至少需要C条边。A．nB．n+1C．n-1D．n/22．对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有n个顶点的无向完全图包含有C条边。A．n(n-1)B．n(n+1)C．n(n-1)/2D．n(n+1)/23．对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有n个顶点的有向完全图包含有A条边。A．n(n-1)B．n(n+1)C．n(n-1)/2D．n(n+1)/24．在一个无向图中，所有顶点的度数之和，是其所有边数之和的C倍。A．1/2B．1C．2D．45．在一个有向图中，所有顶点的入度之和B所有顶点的出度之和。A．二分之一于B．等于C．两倍于D．四倍于6．一个无向连通网图的最小生成树A。A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在7．一个无向图有n个顶点，那么该图拥有的边数至少是D。A．2nB．nC．n/2D．08．一个有n个顶点的无向连通网图，其生成树里含有C条边。A．4n-1B．2n-1C．n-1D．n/29．下面关于图的存储的叙述中，正确的是C。A．用邻接表存储图，所用存储空间大小只与图中顶点个数有关，与边数无关B．用邻接表存储图，所用存储空间大小只与图中边数有关，与顶点个数无关C．用邻接矩阵存储图，所用存储空间大小只与图中顶点个数有关，与边数无关D．用邻接矩阵存储图，所用存储空间大小只与图中边数有关，与顶点个数无关10．对如图7-21所示的无向图实施深度优先搜索遍历，可能的遍历序列是B。-42- 习题解答图7-21无向图示例三、问答1．试求图7-22所示的无向连通网图的MST。一个无向连通网图的MST唯一吗？图7-22无向连通网图示例图7-23无向图示例答：其MST如图7-15(g)所示。如果使用边（v4,v6）代替边（v3,v6），就可以得到另一个MST。所以，MST不是唯一的。2．试述简单回路、回路两者间的联系与不同。答：简单回路的定义是“如果一条路径的第一个顶点和最后一个顶点相同，其他顶点不重复出现，那么这条路径称为简单回路”；回路的定义是“如果一条路径的第一个顶点和最后一个顶点相同，那么这条路径称为回路”。比较后可知，一条路径是简单回路，那么它一定是回路，因为回路只要求路径的起始顶点和终端顶点相同，简单路径是满足这一要求的；但一条路径是回路，则不一定是简单回路，因为回路时并不去理会路径中的其他顶点是否重复出现，可是简单路径是不允许其他顶点重复出现的。3．有如图7-23所示的一个无向图，给出它的邻接矩阵以及从顶点v1出发的深度优先遍历序列。答：它的邻接矩阵如图所示。从顶点v1出发的深度优先遍历序列为：v1->v2->v4->v5->v7->v6->v3注意，该序列是不唯一的。4．构造最小生成树的Prim算法与求单源最短路径的Dijkstra算法十分相似，它们都把图中的顶点分成U和V-U两个部分，都是在V-U里挑选出一个顶点，并将它从V-U移到U中。那么，它们的主要区别是什么？-42- 习题解答答：这两个算法的处理思路确实较为相似，主要区别在于：Prim算法是从V-U里挑选出下一个与MST中某个顶点相距最近的顶点，而Dijkstra算法是从V-U里挑选出下一个离源点最近的顶点。5．对有m个顶点的无向图G，如何通过它的邻接矩阵判定下列问题：（1）图中有多少条边？（2）任意两个顶点i和j之间是否有边相连？（3）任意一个顶点i的度是多少？答：（1）邻接矩阵中非零元素个数的一半，是图中边的数目；（2）通过判断邻接矩阵中元素A{[i,j]和A[j,i]是否不为0，可知顶点i和j之间是否有边相连；（3）第i行或第i列上非零元素的个数，就是顶点i的度。6．对图7-24回答下列问题：（1）顶点集合V；（2）边集合E；（3）每个顶点x的度D(x)；（4）一个长度为5的路径；（5）一个长度为4的回路；（6）图的一个生成树；（7）邻接矩阵；（8）邻接表。图7-24图示例答：（1）顶点集合V={v1,v2,v3,v4,v5,v6}。（2）边集合E={,,,,,,,}。（3）每个顶点的度：D(v1)=1，D(v2)=3，D(v3)=D(v4)=4，D(v5)=D(v6)=2。（4）一个长度为5的路径是：v1->v2->v3->v6->v4->v5。（5）一个长度为4的回路是：v2->v3->v5->v4->v2。（6）如下图(a)所示。（7）如下图(b)所示。（8）如下图(c)所示。问答5的（6）~（8）答案-42- 习题解答四、应用1．利用Kruskal算法，求图7-14(a)所给无向连通网图的最小生成树。答：初始时，所求MST里只有七个各自孤立的连通分量，如图(a)所示。开始执行Kruskal算法时，从图的边E里挑选边（v6,v7），因为这两个顶点分属MST中的不同连通分量，且权值为最小。这样，该边把MST里的顶点v6和v7连接在了一起，如图(b)所示。接着，从图的边E里挑选边（v1,v3）、挑选边（v1,v2）、挑选边（v4,v6）挑选边（v5,v7）挑选边（v3,v6），最终得到如图(g)所示的最小生成树。2．利用Floyd算法，求图7-25所示的有向网图中各顶点对的最短路径长度。图7-25有向网图示例答：Floyd算法基于的邻接矩阵，以及推演出的各个矩阵、最终结果如下所示。3．利用Dijkstra算法，求图7-26所示的图中顶点v1到其他各顶点间的最短路径长度。答：v1到v2的最短路径长度是4；v1到v3的最短路径长度是4；v1到v4-42- 习题解答的最短路径长度是1；v1到v5的最短路径长度是6；v1到v6的最短路径长度是3；v1到v7的最短路径长度是6；v1到v8的最短路径长度是7。如图所示。图7-26图示例图7-27AOV网4．写出图7-27所示的AOV网的拓扑排序序列。答：该网只有顶点v3的入度为0，所以只能从它开始进行拓扑排序，其拓扑序列为：v3->v1->v4->v5->v2->v65．已知无向连通网的邻接矩阵如下所示，试画出该无向连通网以及所对应的最小生成树。答：无向连通网以及所对应的最小生成树如图(a)、(b)所示。第8章习题解答一、填空1．记录的集合是实施查找的数据基础。在讨论查找问题时，常把T称为查找表。2．能够唯一确定记录的数据项，被称为关键字。3．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那么这种查找称为静态查找；如果查找过程会伴随着对数据元素的变更，那么这种查找称为动态查找。4．有序表和分块有序表是一种静态查找表；二叉查找树是一种动态查找表。5．在AVL树的平衡调整中，称离插入结点最近且其平衡因子绝对值大于1的那个结点为根结点的子树为“　最小不平衡树　”。-42- 习题解答6．在散列查找中使用的函数，称为“散列函数”。在散列法中的查找表，称为散列表或哈希表。7．散列法中，如果两个不同的关键字经过散列函数的计算后，得到了相同的索引地址，那么这种现象被称作“冲突”。8．散列法中，计算后得到相同索引地址的那些不同关键字，被称作“同义词”。二、选择1．在对线性表进行折半查找时，要求线性表必须B。A．以顺序方式存储B．以顺序方式存储，且结点按关键字有序排列C．以链式方式存储D．以链式方式存储，且结点按关键字有序排列2．采用顺序查找法查找长度为n的线性表时，其平均查找长度为C。A．nB．n/2C．(n+1)/2D．(n-1)/23．有一个有序表：1，3，9，12，32，41，45，62，75，77，82，95，100采用折半查找法查找值为82的记录时，要经C次关键字比较后，查找成功。A．1B．2C．4D．84．设散列表长m=14，散列函数h(key)=key%11。表中已有四个记录，关键字分别为15、38、61、84，采用二次探测法解决冲突。那么关键字为49的记录的散列地址为D。A．1B．3C．5D．95．在下列各种查找方法中，只有A查找法的平均查找长度与表长n无关。A．散列查找B．二叉查找树C．折半查找D．分块查找6．在开放地址法中，由于散列到同一个地址而引起的“堆积”现象，是由B产生的。A．同义词之间发生冲突B．非同义词之间发生冲突C．同义词之间或非同义词之间发生冲突D．散列表“溢出”7．在最坏的情况下，查找成功时二叉查找树的平均查找长度C。A．小于线性表的平均查找长度B．大于线性表的平均查找长度C．与线性表的平均查找长度相同D．无法与线性表的平均查找长度相比较8．在散列中采用线性探测法解决冲突时，产生的一系列后继散列地址C。A．必须大于、等于原散列地址B．必须小于、等于原散列地址C．可以大于或小于但不能等于原散列地址D．地址大小没有具体限制三、问答1．（1）给出关键字序列：loop、if、for、while、repeat，依照创建二叉查找树算法，画出所对应的二叉查找树。该树的平均查找长度是多少？（2）又给出关键字序列：while、repeat、loop、if、for，依照创建二叉查找树算法，画出所对应的二叉查找树。该树的平均查找长度又是多少？-42- 习题解答答：（1）的二叉查找树如图(a)所示，平均查找长度是：ASLa=(1+2*2+2*3)/5=11/5=2.2(2)的二叉查找树如图(b)所示，平均查找长度是：ASLb=(1+2+3+4+5)/5=15/5=32．利用折半查找法对一个长度为10的有序表进行查找，请填写查找表中每个元素时所需要的比较次数。答：根据折半查找算法，因此首先用给定值K与区间[1，10]的中点比较，因此下标为5的元素比较次数为1。若没有找到，接着应该在区间[1，4]或[6，10]中继续折半查找，因此下标为2和下标为8的元素的比较次数为2。继续下去，下标为1、3、6、9的元素的比较次数为3。最后，下标为4、7、10的元素的比较次数为4。于是，所填结果为：四、应用1．有关键字序列：20、10、30、15、25、5、35、12、27，请一步步画出构造二叉查找树的过程。答：构造二叉查找树的过程如下：2．给出如图8-21所示的一棵二叉查找树，在其基础上分别做操作：（1）删除关键字为15的记录；（2）插入关键字为20的记录。画出这两个操作完成后该树的形态。-42- 习题解答图8-21二叉查找树示例答：1）删除关键字为15的记录后，该树的形态如图(a)或(b)所示，(a)是用待删结点的直接前驱（或左子树根结点）取代所得，而(b)则是用待删结点的直接后继（或右子树根结点）取代所得；（2）插入关键字为20的记录后，该树的形态如图(c)所示。3．设散列函数为h(key)=key%11，散列表长为11（索引地址为0~10）。给定：SUN，MON，TUE，WED，THU，FRI，SAT取单词第1个字母在英语字母表中的序号为关键字值（比如S的关键字值为19），采用链地址法解决散列地址冲突。请画出对应的散列表。答：对应的散列表如下。4．有关键字序列：36、27、68、33、97、40、81、24、23、90、32、14，散列表长为13，采用的散列函数为：h(key)=key%13，使用开放地址法的线性探测解决冲突。请完成下面散列表的填写（比如，第1个插入的是36，它的散列地址为10，由于没有发生冲突，所以比较一次就存放在了地址为10的位置），求出其平均查找长度ASL。-42- 习题解答答：最终的散列表如图所示。其平均查找长度ASL为：ASL（线性探测）=（2+1+2+1+2+5+1+1+3+1+1+3）/12=1.925．已知由12个关键字组成的序列：Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec（1）按照所给顺序构造一棵初始为空的二叉查找树，画出最终形成的二叉查找树，求在等概率下查找成功的平均查找长度。（2）若对关键字序列按照字母递增的顺序排列成有序表，求在等概率下这棵二叉查找树查找成功的平均查找长度。答：（1）最终形成的二叉查找树如下图所示，其平均查找长度为：ASL=（1+2*2+3*3+3*4+2*5+6）/12=42/12=3.5-42- 习题解答（2）这时成为只有右子树的单支树，其平均查找长度为：ASL=（1+2+3+4+5+6+7+8+9+10+11+12）/12=78/12=6.56．已知由12个关键字组成的序列：Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec散列表长为13（地址为0~12），散列函数为：h(key)=i/2，其中i为关键字中第1个字母在字母表里的序号。（1）用线性探测法解决冲突，给出所构造的散列表以及查找成功的平均查找长度。（2）用链地址法解决冲突，给出所构造的散列表以及查找成功的平均查找长度。答：（1）用线性探测法解决冲突时，插入地址及比较次数如下：h(Jan)=10/2=5，比较1次插入；h(Feb)=6/2=3，比较1次插入；h(Mar)=13/2=6，比较1次插入；h(Apr)=1/2=3，比较1次插入；h(May)=13/2=6，比较2次插入；h(Jun)=10/2=5，比较4次插入；h(Jul)=10/2=5，比较5次插入；h(Aug)=1/2=0，比较2次插入；h(Sep)=19/2=9，比较2次插入；h(Oct)=15/2=7，比较5次插入；h(Nov)=14/2=7，比较6次插入；h(Dec)=4/2=2，比较1次插入。所以，构造的散列表如图所示。平均查找长度为：ASL=（1+1+1+1+2+4+5+2+2+5+6+1）/12=31/12≈2.6（2）用链地址法解决冲突时，构造的散列表如图所示。平均查找长度为：ASL=（1+2+1+1+1+2+3+1+2+1+2+1）/12=18/12=1.5第9章习题解答一、填空1．一次筛选的目的，就是将不满足堆性质的完全二叉树根结点，调整到其适当的位置上，以便构成一个新堆。2．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是稳定的。-42- 习题解答3．有待排关键字序列：54、38、96、23、18、73、61、46、88，采用直接插入排序算法。在进行到寻找第7个关键字61的插入位置时，需要做3次比较。（注意：在进行到寻找第7个关键字61的插入位置时，前面的6个关键字已经排好了序：18、23、38、54、73、96。由于比较是从后往前进行的，所以在与96、73、54比较后，就能够确定60的插入位置了）4．选择排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。5．快速排序方法是通过适当的位置交换，把序列中的元素一次性地放到了它的最终位置上。6．有待排序的关键字序列：54、38、96、23、15、72、60、45、83，对这样的一个特定的序列进行冒泡排序。整个排序过程需进行5趟扫描，才能完成排序任务。（注意：第4趟已经排好，第5趟时由于判断没有交换而结束排序）7．对关键字序列22、86、19、49、12、30、65、35、18做一趟排序后，得到的结果是18、12、19、22、49、30、65、35、86。因此，可以认为采用的排序方法是快速排序。8．一个堆中所有非叶结点的关键字值都小于或等于其左、右孩子的关键字值。二、选择1．在下面给出的各种排序算法中，只有A是稳定排序算法。A．冒泡排序B．快速排序C．直接选择排序D．堆排序2．在下面给出的各种排序算法中，只有B不是稳定排序算法。A．冒泡排序B．快速排序C．直接插入排序D．折半插入排序3．在给出的四棵二叉树中，只有C满足一个堆的条件。4．已知无序的待排关键字序列为：46、79、56、38、40、84。利用堆排序方法创建的初始堆应该是BA．38，56，40，79，46，84B．38，40，56，79，46，84C．38，40，46，56，79，84D．38，46，40，56，79，845．对关键字序列：46、79、56、38、40、84采用快速排序方法。若以46为枢轴，那么一次划分后的结果应该是D。A．38，40，46，79，56，84B．38，40，46，84，56，79C．40，38，46，79，84，56D．40，38，46，56，79，846．从待排序序列中依次取出元素与已排好序的序列里的元素进行比较，并存放到已排序序列的正确位置上，这种排序方法是A。A．直接插入排序B．交换排序C．冒泡排序D．选择排序7．当两个元素出现逆序时就交换它们的位置，这种排序方法是C。A．直接插入排序B．冒泡排序C．交换排序D．选择排序8．具有24个记录的待排序列，采用冒泡排序时，最少需要进行的比较次数是B。A．1B．23C．24D．5129．用某种排序方法对序列：24、84、21、47、16、28、66、35、20进行排序，序列的变化情况为：24，84，21，47，16，28，66，35，20-42- 习题解答20，16，21，24，47，28，66，35，8416，20，21，24，35，28，47，66，8416，20，21，24，28，35，47，66，84那么，这里采用的排序方法是C。A．直接插入排序B．冒泡排序C．快速排序D．选择排序三、问答1．在直接插入排序算法中，什么条件保证了该算法的稳定性？答：在该算法中，可能停止while循环的一个条件是“temp.key>=Ar[j].key”，正是它保证了直接插入排序算法的稳定性。比如在例9-2里，由于比较到第2个76大于、等于第1个76，所以while循环就结束了，不再往后移动比较范围内的记录。因此，第2个76肯定在第1个76的后面，不会跑到它的前面去。如果将while循环改为：while((temp.key>=Ar[j].key)&&(j>=1))那么，它就不会保证直接插入排序算法是稳定的了。2．在冒泡排序算法里，是什么条件保证它的稳定性？答：冒泡排序是一种稳定排序算法，主要是因为算法里每趟扫描时的判定条件设定为：Ar[j].key>Ar[j+1].key，它保证了原先在前面的记录，排序后仍然排在前面，不会改变它们之间的相对顺序。如果把大于号改为大于等于，那么算法就不是稳定的了。3．试问内排序与外排序有什么区别？答：内、外排序虽然都是排序，但由于排序过程中所使用存储器的不同，而被分为内排序和外排序。所谓“内排序”，是指待排记录序列全部存放在内存，整个排序过程都在内存里完成；所谓“外排序”，是指内存中容纳不下所有待排记录序列，排序过程中需要不断地与外存进行数据交换。4．有两个关键字序列：3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。试问谁是堆，谁不是堆？把不是堆的序列通过筛选将它调整为一个堆。答：依照序列的顺序，画出对应的完全二叉树如(a)和(b)所示。可以看出，(a)是一个堆，(b)则不是，因为结点7破坏了堆的性质。为此，先将7和15对换，如图(c)所示；然后再将7和8对换，如图(d)所示。这时，序列2就被调整为是一个堆了。5．有以下四个待排关键字序列：19，23，3，15，7，21，2823，21，28，15，19，3，719，7，15，28，23，21，33，7，15，19，21，23，28对它们采用快速排序方法进行排序，试问哪一种情况速度最慢？答：在最后一种情况时，序列已经排好序，因此对它的排序速度最慢。四、应用1．将冒泡排序算法修改成记录关键字由大到小递减排列。答：已知有n个记录的无序序列，存放在一个一维数组Ar里。对它进行递减的冒泡排序，并最后得到排序结果。算法名为Bub_Sort1()，参数为Ar，n。-42- 习题解答Bub_Sort1(Ar,n){for(i=1;iAr[large].key)/*如果发现更大者，随时修改large的值*/large=j;if(large!=i)/*large与比较范围首元素下标不同，则交换*/{temp=Ar[i];/*交换是利用临时变量temp进行的*/Ar[i]=Ar[large];Ar[large]=temp;}}}4．已知待排的关键字序列：70、83、99、65、10、32、7、9，请给出采用直接插入排序方法时每趟的图示过程。答：采用直接插入排序方法时每趟的图示过程如下。5．有待排序的关键字序列：18、02、22、15、56、18、88、27、68，请给出采用冒泡排序方法时每趟的图示过程（注意：这里有两个关键字都是18）。答：采用冒泡排序方法时每趟的图示过程如下。-42-'