《数据结构基础教程》习题及解答

《数据结构基础教程》习题解答

（新）1章习题解答一、填空意义，只是反映数据元素某一方面的属性。数据是以数据元素为单位存放在内存的，分配给它的内存区域称为存储结点。每个数据元素都具有完整、确定的实际意义，是数据加工处理的对象。如果两个数据结点之间有着逻辑上的某种关系，那么就称这两个结点是邻接的。在一个存储结点里，除了要有数据本身的内容外，还要有体现数据间邻接关系的内容。二、选择在常见的数据处理中，B 是最基本的处理。A．删除 B．查找 C．读取 D．插2．下面给出的名称中，A不是数据元素的同义词。A．字段 B．结点 C．顶点 D．记录D是图状关系的特例。只有线性关系 B．只有树型关系C．线性关系和树型关系都不 D．线性关系和树型关系D据间的逻辑关系。只能有1个 B．只能有2个 C．只能有3个 D．可以有多5．本书将采用C来描述算法。A．自然语言 B．流程图（即框图） C．类C语言 D．C语言6．有下面的算法段：for(i=0;i<n;i++)k++;其时间复杂度为B。2A．O(1) B．O(n) C．O(logn) D．O(n2)2-1-习题解答三、问答么样的邻接关系，为什么？答：是一种线性关系，因为这些姓氏之间符合关系的“有头有尾，顺序排列”的特点。什么是数据结点？什么是存储结点？它们间有什么关系？答：数据结点即是数据集合中的一个数据元素，存储结点是存放数据结点的内存单位。在存储结点里，不仅要存放数据结点的内容，还要（显式或隐式地）存放数据结点间的逻辑关系。为什么说链式存储既提高了存储的利用率，又降低了存储的利用率？列举几个数据之间具有树型结构的实际例子。答：学校各级管理之间，是一种分支层次结构；一本书的书目，是一种分支层次结构。判断如下除法过程是否是一个算法，为什么：开始；给变量m5，给变量n0；m=m/n；输出结束。0不能为除数，本题第步不具有有效性，所以它不是一个算法。但如果n的初值不为0，则是一个正确的算法。四、应用用类C语言中的do-while、2、9、10答：算法编写如下。voidnum(){i=1;do{printf(“i=%d\n”,i);i=i+1;}while(i<=10);}用类C语言中的if-else语句，编写算法，描述当输入的数据大于等于00答：算法编写如下。voidjudge(){scanf(“%d\n”,&x);if(x>=0)-2-习题解答printf(“输入的是正数”);elseprintf(“输入的是负数”);}1 #”和“#1 for(i=0;i<n;i++)for(j=0;j<n;j++){#1y=1;for(k=0;k<n;k++)#2y=y+1;}1 答：标有记号“#”的基本操作的执行次数是：n2；标有记号“#”的基本操作的执行次数是：n31 3个算法段的时间复杂度：（1）x++；（2）for(j=1;j<n;j++)x++;（3）for(j=1;j<=n;j++){printf(“j=%”,j);for(k=j;k<=n;k++)x++;}（）的时间复杂度为(1；O(n)；printf”执行次数的数量级为nx++”执行次数是：n+(n-1)+(n-2)+……+2+1n(n+1)/2其数量级为O(n2)，因此整个算法段的时间复杂度应该是O(n2)。2章习题解答一、填空n称为线性表的长度。以顺序存储结构实现的线性表，被称为顺序表。在一个双链表中，已经由指针ptr指向需要删除的存储结点，则删除该结点所要行的两条操作是①ptr->Prior->Next=ptr->Next; ②ptr->Next->Prior=ptr->Prior; 。设tailtail->Next->Next。在一个不带表头结点的非空单链表中，若要在指针qtr所指结点的后面插入一个值-3-习题解答为x的结点，则需要执行下列操作：ptr=malloc(size);ptr->Data=x;ptr->Next=qtr->Next;qtr->Next=ptr;顺序表Sq=(a

w个存储单元。1 2 3 n若m为元素a1的起始地址，那么元素an的存储地址是m+(n-1)*w。二、选择下面，对非空线性表特点的论述，C是正确的。A．所有结点有且只有一个直接前驱B．所有结点有且只有一个直接后继C．每个D．结点1对多的邻接关系来维系其逻辑关系的一般单链表Lk_hA。A．Lk_h==NULL B．Lk_h->Next==C．Lk_h->Next==Lk_h D．Lk_h!=NULLB带表头结点的单链表Lk_h为空的判定条件是B。A．Lk_h==NULL B．Lk_h->Next==C．Lk_h->Next==Lk_h D．BA．n B．n/2 C．n+1 D．(n+1)/2在一个单链表中，已知qtrptr所指结点的直接前驱。现要在qtrptr所指结点之间插入一个rtrC。C．qtr->Next=rtr;rtr->Next=ptr;A．rtr->Next=ptr->Next; ptr->Next=B．C．qtr->Next=rtr;rtr->Next=ptr;D．ptr->Next=rtr; rtr->Next=qtr->Next;在一个单链表中，若现在要删除ptrA。A．ptr->Next=ptr->Next->Next;B．ptr=ptr->Next; ptr->Next=ptr->Next->Next;C．ptr=ptr->Next->Next;D．ptr->Nextptr;ni个元素（1≤i≤n）B个元素。A．n-i B．n-i+1 C．n-i-1 D．ini个元素时，需要往前移动A个元素。A．n-i B．n-i+1 C．n-i-1 D．i99．设tail是指向一个非空带表头结点的循环单链表的尾指针。那么，删除链表起始结点的操作应该是D。A．ptr=tail; B．tail=tail->Next;-4-习题解答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->Nextptr->Next=qtr; ptr->Next=qtr;C．qtr->Next=ptr->Next; D．ptr->Next=qtrptr=qtr; qtr->Next=ptr;三、问答试问，如下的线性表：L=(29，25，21，17，13，11，7，5，3，1)是有序线性表还是无序线性表？答：L是一个有序线性表。线性表Li个存储结点ai的起始地址LOC（ai）可以通过下面的公式计算得到：LOC（ai）=LOC（ai）+k-1其中k表示存储结点的长度。这个公式对吗？为什么？-1答：这个公式是对的，因为第i个存储结点ai的起始地址LOi-1个存储结点ai-1的起始地址LOC（ai）k得到。-1试说明创建顺序表算法Create_Sq()中，Sq_maxSq_num的不同之处。4．如何判断一个顺序表是否为空？答：Sq_max顺序表创建后，Sq_max代表的是顺序表内当前拥有的数4．如何判断一个顺序表是否为空？答：只需判定Sq_num的当前值是多少，如果Sq_num0，则表示顺序表Sq则表示该顺序表里有数据元素存在。2-3里，操作“Sq_num=Sq_num-Sq_num删除了一个元素，Sq_num必须减1，这样才能正确反映出删除后表中元素的个数。所以，没有这个操作是不行的。在算法2-9述，能够保证插入后最后一个结点的Next答：能够。因为原来ptr->NextΛ1qtr->Next=ptr->Next;后，就是把插入结点的NextΛ在一个单链表中，为了删除指针ptr懂并加以理解。试问，编写者能够达到目的吗？其思想是什么？x=ptr->Data;qtr=ptr->Next;ptr->Data=ptr->Next->Data;-5-习题解答ptr->Next=ptr->Next->Next;free(qtr);ptr所指结点的目的。编写者的思想是不去直接删除ptr所指的ptr直接后继的Data域内容写入ptr所指结点的Data的设计是有其可取之处的。在一个单链表中，为了在指针ptr所指结点之前插入一个由指针qtr所指的结点，有人编写了下面的操作序列，其中temp者能够达到目的吗？其思想是什么？qtr->Next=ptr->Next;ptr->Next=qtr;temp=ptr->Data;p->Data=qtr->Dataqtr->Data=temp;ptrqtr所指结点的目的。编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难，因此在这里先把qtr插入到ptr所指结点的后面，暂时成为它的直接后继。然后通过临时工作单元temp，将qtr所指结点的Data域内容进行交换，从而达到插入的目的。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域指向其直接前驱的目的。四、应用设计一个计算表头指针为Lk_h的单链表长度（即结点个数）答：算法设计如下：Length_Lk(Lk_h){n=0;ptr=Lk_h; /*ptr指向起始结点while(ptr!=NULL)-6-习题解答{ptr=ptr->Next;n=n+1;}

/*n为结点计数单元*/return(n);}用总是在表的头部插入整数结点的方法建立一个单链表，当输入为0结束。答：算法设计如下：Clink(){Lk_h=NULL;scanf(%d,while(x!=“0”){ptr=malloc(size);ptr->Data=x;ptr->Next=Lk_h;Lk_h=ptr;scanf(%d,&x);}returnLk_h;}一个不带表头结点的循环双链表CkCk_hptr入一个rtr2-214个操作步骤：①rtr->Next=ptr;②rtr->Prior=ptr->Prior;③ptr->Prior->Next=rtr;④ptr->Prior=rtr;答：4个操作步骤的具体功能体现如下图所示。试设计一个算法copy(Ck_h1,，将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1Ck_h2为表头指针的单链表Ck2答：算法具体如下。Copy(Ck_h1,Ck_h2){ptr=Ck_h1->Next;-7-习题解答qtr=Ck_h2;while(ptr!=NULL){rtr=malloc(size);rtr->Data=ptr->Data;qtr->Next=rtr;qtr=rtr;ptr=ptr->Next;}qtr->Next=NULL;}、且值小于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->Data<max))p=p->Next;

/*若结点值<max，则去除*/qtr->Next=ptr;}

/*qtr指出第1个大于max的结点位置，完成链接*/、且值小于max的数据元素。ptr结点的直接前驱。Del_Lk(Lk_h,min,max){ptr=Lk_h->Next;while(ptr!=NULL){

/*ptr指向单链表的起始结点*//*扫视直到链尾结点*/if((ptr->Data<=min)||(ptr->Data>=max){

/*不满足删除条件*/qtr=ptr;ptr=ptr->Next;}

/*qtrptr*/else{

/*ptrptr*/qtr->Next=ptr->Next;free(ptr);-8-习题解答ptr=qtr->Next;}}}一个单链表Lk的表头指针为Lk_h，不同结点的Data法，功能是计算出Data域值为x的结点的个数。答：算法应该遍历链表的每一个结点，遇到一个结点的Dataxn1。最后返回计数器。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章习题解答一、填空如果在顺序栈满时仍打算进行进栈操作，就称为发生了“上溢”出错。如果在顺序栈空时仍打算进行出栈操作，就称为发生了“下溢”出错。nn-1个数据元素。如果操作顺序是先让字母ABC进栈，做两次出栈；再让字母、、F进栈，做一次出栈；最后让字母GDA。(a+b)-(c/(d+e))ab+cde+/-。函数的递归调用有两种形式：如果一个函数是直接调用自己，就称其为直接递归、23、、5，想得到、35、1的输出顺序。那pushpop的操作序列应该是pushpushpushpushpoppushpoppop。设链栈的栈顶指针为Ls_topLs_top!=NULL。二、选择一个栈的元素进栈序列是ab、、de，那么下面的C不能做为一个出栈序列。、、cb、a B．d、、c、、aC．d、、e、、b D．a、、cd、-9-习题解答判定一个顺序队列Qs（最多有n个元素）为空的条件是C。A．Qs_rear-Qs_front==n*size B．Qs_rear-Qs_front+1==C．Qs_front==Qs_rear D．Qs_front==Qs_rear+size判定一个顺序队列Qs（最多有n个元素）真满的条件是A。A．Qs_rear-Qs_front==n*size B．Qs_rear-Qs_front+1==C．Qs_front==Qs_rear D．Qs_front==Qs_rear+size在一个链式队列LqLq_rear分别为队首、队尾指针。现在由指针ptr所指结点要进队，则插入操作应该是B。A．Lq_front->Next=ptr; Lq_front=B．Lq_rear->Next=ptr; Lq_rear=ptr;C．ptr->Next=Lq_rear; Lq_rear=ptr;D．ptr->Next=Lq_front; Lq_front=链栈与顺序栈相比，一个较为明显的优点是D。A．通常不会出现栈空的情形 B．插入操作更加便利C．删除操作更加便利 D．通常不会出现栈满的情向链栈插入一个结点时，操作顺序应该是C。A．先修改栈顶指针，再插入结点 B．无须修改栈顶指针C．先插入结点，再修改栈顶指针 D．谁先谁后没有关从链栈中删除一个结点时，操作顺序应该是AA．先保存被删结点的值，再修改栈顶指针B．先修改栈顶指针，再保存被删结点的值C．无须修改栈顶指针的值D．谁先谁后没有关系一个循环队列的最大容量为m+1，frontD。A．Cq_front=(Cq_front+1)%m B．Cq_front=(Cq_front+1)%(m+1)C．Cq_rear=(Cq_rear+1)%m D．Cq_rear=(Cq_rear+1)%(m+1)在一个循环顺序队列里，队首指针Cq_front总是指向BA．队首元素 B．队首元素的前一个队位C．任意位置 D．队首元素的后一个队位若一个栈的进栈序列是44时，进、出栈操作的顺序应该是A（表示出栈操作）IOOOIO B．IOIOIOIO C．IIOOIOIO D．IOIIIOOO三、问答11．若元素进栈的序列是1、2、3、…、n，有一个出栈序列的第1个元素是n。那么，这个出栈序列的第i个元素是什么？答：由于栈具有“先进后出”的特性，因此只有将1、23、…、n依次都进栈后，出栈序列的第1个元素才能是n。所以，在这个出栈序列里，第个i元素应该是n-i+1。设元素进栈的次序是a，b，c，d，e。试问，在下面所列的6可以是这个栈的出栈序列？A．c，e，a，b，d B．c，b，a，d，e D．a，c，b，e，d E．a，b，c，d，e F．e，a，b，c，d答：对A进行分析。由于是c1个出栈，因此b必须先于a-10-习题解答却先于b出栈，故A不能是该栈的出栈序列。C进行分析。由于是d1个出栈，因此、bc三者出栈的顺序必须是、b、却先于b出栈，故C不能是该栈的出栈序列。F进行分析。由于是e1个出栈，因此、b、d四者出栈的顺序必须是dc、b、a。但所给序列里，它们的出栈顺序全乱了，故F不能是该栈的出栈序列。因此，所列的6种元素序列里，只有B、D、E可以是这个栈的出栈序列。有一个顺序栈Ss，其栈顶指针为Ss_top，栈底指针为Ss_bottom算法，其中的两条prinf算法中的Push_Ss(Ss_top,ch)表示将ch里的元素进栈，Pop_Ss(Ss_top,表示将栈顶元素出栈，存入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条printf13个英文大写字母ABCDEFGHIJKLM2printf出的是前面输出的倒置，即MLKJIHGFEDCBA。1 2 3 4 5 4 3 2 6 5 6a、aa、a、aa栈顺序是a、a、a、aa、a，那么应该如何安排pushpop1 2 3 4 5 4 3 2 6 5 答：所需的push和pop操作序列如下：push，push，push，push，pop，pop，pop，push，push，pop，pop，popa/(b/(c/(d/e)))abcde////。这一转化结果对吗？答：转化结果是对的。试述栈与队列各自具有什么样的逻辑特点？它们之间又有什么共同点？（即往栈里插入元素）的顺序与数据元素离开栈（即从栈里删除元素）堆栈的逻辑特点是后进先出LIF，或先进后出FIL。而对队列来说，插入在一端进行，删除在另一端进行，这就使得数据元素到达队列（即往队列里插入元素）元素离开队列（即从队列里删除元素）先出FIF）或后进后出LIL。它们之间的共同之处是插入和删除只能在表的端点处进行（要知道，对于线性表，可以在表的任何位置处插入和删除。有一个顺序队列，最大容量为5。初始时有Qs_front=Qs_rear=时队列及其首、尾指针的变化情况。若不能进队时就停止，并简述原因。（1）d、、b进队 （2）d、e出队 （3）i、j进队（4）b出队 （5）n、、p进队答：队列及其首、尾指针的变化情况如下图所示。-11-习题解答在做5）时，由于队满（假溢出，故操作停止。有一个递归函数Write(x){if(x!=0){Write(x-1);for(j=1;j<=x;j++)printf(“%3d”,x);printf(“/n”);}}试问，Write(5)的输出结果是什么？答：输出结果为：12 23 3 34 4 4 45 5 5 5 5四、应用编写一个判顺序栈空的算法。要求是如果栈空，返回1，否则返回答：算法设计如下：Empty_Ss(Ss,Ss_top){if(Ss_top==0) /*return(1);else /*栈不空*/return(0);}编写一个算法，它能够输出顺序队列Qs答：算法编写如下：Print_Qs(Qs_front,Qs_rear){if(Qs_front==Qs_rear) /*printf(“queueisempty!”);-12-习题解答else{

/*队列非空！*/qtr=Qs_front;while(qtr<=Qs_rear){printf(“%d”,*qtr);qtr++;}}}编写一个算法，它能够取得链式队列首元素的值。答：取得链式队列首元素的值，只有在队列非空的前途下才有意义。算法编写如下。Getf_Lq(Lq_front,Lq_rear){if(Lq_front==Lq_rear)printf(“Thelinkedqueueiselse{

/*队列空！*//*队列非空！*/ptr=Lq_front->Next;x=ptr->Data;return(x);}}5424个人多少岁，回答说比第32岁；问第3个人多少岁，回答说比第22212110岁。试给出该递归的公式、结束条件，并编写出相应的递归算法。答：递归公式为：age(n)=age(n-1)+2 2<=n<=5递归的结束条件是：age(1)=10相应算法为：Age(n){if(n==1)return(10);else{x=age(n-1)+2;return(x);}}将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值。具体地，要开辟一个运算符栈op和一个数组st-13-习题解答st；遇到运算符时就与op栈顶元素比较，高则进栈，不高则让栈顶元素出栈，存入st，然后该运算符再次去与新的op栈顶元素比较。最后，在数组st试用这种方法，用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式。答：相应的后缀表达式是583*+2-，其图示如下。ob，当从左往右扫描后缀表达式时，每遇到操作数就让其进入ob栈，每遇到运算符就从obobob栈的栈顶值就是最终结果。试用图示计算后缀表达式583*+2-的值。答：计算结果为27，其图示如下。4章习题解答一、填空一个概念。字符串中任意多个连续字符所组成的子序列，被称作是这个串的“子串符串本身则称为“主串我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符ASCII码-14-习题解答的比较而得到的结论。设有三个串：s1=“Good”，s2=“Ф”，s3=“bye!”。则s1、、s3设有三个串：s1=“Good”，s2=“Ф”，s3=“bye!”。则s1、、s3连接后的结果串应该是“Goodbye!”。（n>1个具有相同类型的数据的有序集合。所谓“特殊矩阵ij=aji在一个n阶方阵A中若所有元素都有性质就称其为对称矩ij=aji阵。二、选择设有两个串s1。求s2s1B。A．连接 B．模式匹配 C．求子串 D．求串2．有串那么它的长度是B。A．0 B．1 C．2 D．33．设有串s1=“ABCDEFG”s2=“PQRST”。已知：算法con(x,x和y的连接串；subs(s,i,返回串s的第i个字符开始往后j返回串s的长度。那么，con(subs(s1,2,len(s2)),subs(s1,len(s2),D。A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF8阶的对称矩阵Aa1111，每个元素占一个地址空间。试问元素a85的地址是A。A．33 B．30 C．13 D．23m*mC。C．m*(m+1)/2A．m*(m-1)/2B．m*m/2 D．C．m*(m+1)/2二维数组M的每个元素含4个字符（每个字符占用一个存储单元，行下标i从15j16。那么按行顺序存储时元素M[4][6]MB的起始地址相同。A．M[3][5] B．M[4][5] C．M[4][6] D．M[5][5]M3i18j110SA的存储区开始存放AA[8][5]C。A．SA+141 B．SA+180 C．SA+222 D．SA+22588．设有一个5阶上三角矩阵A，将其元素按列优先顺序存放在一维数组B中。已知每2100。那么A[3][4]的地址是A。A．116 B．118 C．120 D．122（分析：把一个上三角矩阵按列优先顺序存放在一个一维数组B中，元素的顺序是：a11a12a22a13……A[3,4]的地址=100+a34前面的元素个数*2=100+（前3列的个数+本列a34前面的个数）*2=100+（1+2+3）+2）*2=116）-15-习题解答三、问答为什么可以把二维数组视为是一种线性结构？视为是线性表的一种推广（因为一维数组即是线性表，因此可以说它的数据元素间的逻辑关系呈现出的是一种线性结构。55图4-3（）所示为一个特殊矩阵A ，这种形式的矩阵被称作是“带状矩阵，为它的非零元素都分布在以主对角线为中心的一个带状区域里，其他位置上的元素全部为0。可以以行优先的方式，将其压缩存储到一个一维数组里，如图4-34（b）所示。试找元素下标i、j与存储序号k间的对应关系。55图4-34 带状矩阵答：压缩存储元素下标i、j与存储序号k间的对应关系是：k=2*i+j–24-35所示。试问，它对应的三元组表是什么？图4-35 稀疏矩阵示例答：它所对应的三元组表如下。四、应用-16-习题解答4-1改为用while4-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]=“\0”;return(St3);}}算法4-24-2。答：按照这样的设计，算法4-2的描述如下。Equal_St(St1,St2){i=1;while(St1[i]!={

/*两串进行比较*/if(St1[i]==St2[i]) /*相等，继续比较i++;elseblack;}

/*不等，强制退出*/-17-习题解答if(St1[i]!=St2[i])return(0);else{

/*比较是由于相应位置上的字符不同而结束*/if(St1[i]\0||St2[i]\0”)/*比较是由于长度不同而结束*/return(0);elsereturn(1);}}算法：Trans_St(St，ch1，ch2){i=1；While(St[i]！="\0"){if(St[i]==ch1)St[i]==ch2；i++；}}是通过while循环来实现将顺序串St中所有的字符ch1改为字符ch2循环来实现相同的功能。答：用for循环改写的算法如下。Trans_St(St,ch1,ch2){for(i=1;i<=St_len;i++)if(St[i]==ch1)St[i]=ch2;}编写一个算法，将顺序串St文字母A~Z对应的ASCII65~90，小写英文字母a~z对应的ASCII97~122写字母的ASCII32，就是对应小写字母的ASCII码)答：算法编写如下。Catosm_St(St){for(i=1;i<=St_len;i++)if((A<=St[i])&&(St[i]<=Z))St[i]=St[i]+32;}ij个字符删除（i+jj个位置，完成删除的功能）答：算法编写如下。-18-习题解答Moveij(St,i,j){if(i+j<=St_len){for(k=i+j;k<=St_len;k++) /*i+jj个位置St[k-j]=St[k];St_len=St_len-j;St[St_len]=“\0”;}

/*St的长度*//*安放新的串结束符*/elseprintf(“参数不合理，无法进行删除！”);}在算法4-12ptr->Next=NULL;把由指针ptr指向的最后一个要释放空间的结点的Next域设置为NULL，然后通过while循环完成释放。其实，由于知道要释放空间的结点共有mform来控制释放空间的结点个数。请试着按照这一思路改写那一小段算法。答：改写一小段算法如下。for(j=1;j<=m;j++){ptr=rtr;rtr=rtr->Next;free(ptr);}编写一个算法，功能是复制一个链串。答：复制一个完整的链串，是一件比较容易的事情。其算法起名为Copy_Lt()，参数为Lt1。具体编写如下。Copy_Lt(Lt1){ptr=Lt1_h;rtr=malloc(size);rtr->Data=ptr->Data;Lt2_h=rtr;ptr=ptr->Next;while(ptr!={qtr=malloc(size);qtr->Data=ptr->Data;rtr->Next=qtr;ptr=ptr->Next;}rtr->Next=NULL;return(Lt2_h);}-19-习题解答while循环，不断修改指针ptr，以便指向链串Lt1rtr总是指向当前已形成的新链串Lt2的最后一个结点；用指针qtr并把它链入到rtr所指结点的后面。mⅹn的矩阵A。编写一个算法，求C=A+B。即Cmⅹn矩阵，其元素满足条件：ijcij=aij+b（1≤i≤m，1≤j≤n）答：算法名为Add_Mt()，参数为A，B，C。ijAdd_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章习题解答（此处树的高度不计算根节点）一、填空72，最高是6。给定二叉树的结点数，要使树高为最矮，那么该树应该是完全二叉树形状。6，那么它共有127个结点，有64个叶结点。1518个叶结点。n2n-1个结点。将一棵完全二叉树按层次进行编号。那么，对编号为i2i2i+1。若二叉树共有n有2nn+1个指针域是空的。531个结点。二、选择4C不是完全二叉树。3D个空结点。A．10 B．8 C．6 D．4设有一棵5B-A-D-C-E，那么它的后序遍历序列为B。A．A-B-D-E-C B．B-D-E-C-AC．D-E-C-A-B D．A-B-C-D-E-20-习题解答将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是BA．无左、右孩子 B．有左孩子，无右孩子C．有右孩子，无左孩子 D．有左、有孩子6的二叉树，最多可以有A个结点。A．63 B．64 C．127 D．128在一棵非空二叉树的中序遍历序列里，根结点的右边D结点A．只有左子树上的部分 B．只有左子树上的所有C．只有右子树上的部分 D．只有右子树上的所有A。A．不发生变化 B．发生变化C．不能确定 D．以上都不对1、、、8D。A．18 B．28 C．19 D．29271。那么它的叶结点数是C。A．6 B．7 C．8 D．9105层上的结点数最多是CA．8 B．15 C．16 D．32三、问答试问满二叉树与完全二叉树之间有何关系？满二叉树。这就是满二叉树与完全二叉树之间的关系。335种，如下图所示。其中，4棵树的高度为2，1棵树的高度为1。3的满二叉树有多少个叶结点？有多少个度为2结点？答：有23=8个叶结点，有度为2的结点23-1=7个，总共有23+1-1=24-1=15个结点。有人说，任何一棵非空满二叉树，它的叶结点数等于其分支结点数加1个结论正确吗？请说明理由（5-3）答：在我们介绍的二叉树性质中，只有性质5-3是涉及叶结点数与（度为2的）分支结25-3得出所需要的结论。所以，此人说的结论是完全正确的。有人说，有一棵结点数为n>1能的话，这样一棵二叉树应该是个什么样子呢？叉树，如图所示。-21-习题解答试问，什么样的二叉树其先序遍历序列与中序遍历序列相同？左孩子的非空二叉树。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。四、应用对一个二叉树进行顺序存储，各结点的编号及数据如表所示：编号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答案图所示。。试画出这棵-22-习题解答二叉树。答：这棵二叉树如应用题3答案图所示。若一棵二叉树的左、右子树均有3列相同，右子树的中序遍历序列与后序遍历序列相同。请画出这棵二叉树。答：这棵二叉树如应用题4答案图所示。理解算法5-105-25(b)的基础上，进行下一次组合。试给出第2的情形，以及那时二叉树的样子。答：第2次组合后数组的情形如下图(a)所示，那时二叉树的样子如下图(b)所示。16203024答：构造这棵哈夫曼树的全过程如下所示。-23-习题解答113（。序号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章习题解答一、填空结点。结点。n（n≥0）在如图6-21H的祖先是G。图6-21 树示例 图6-22 树示例6-22所示。它的根结点是A，叶结点是G、、J、、-24-习题解答NOPQ、R，这棵树的度是3，这棵树的深度是4，结点F的孩子结点是J、K，结点G的父结点是C，结点HD、A是结点R的祖先。二、选择D。B． C． D．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的先序遍历是对Bt的A。先序遍历 B．中序遍历 C．后序遍历 D．无法确定3．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的BA．先序遍历 B．中序遍历 C．后序遍历 D．无法确定4 F 3．设森林中有棵树，依次有结点nnn个。把该森林转换成对应的二叉树后，4 F 31 2 3该二叉树的右子树上的结点个数是D。A B + C D ．n ．n n ．n ．A B + C D 1 1 2 3 2 35 T T ．设有由三棵树、、组成的森林，其结点个数分别为n、n、n5 T T 1 2 3 1 2 3应的二叉树为BtA个。1 1 1 1 A．n-1 B．n C．n+1 D．n+1 1 1 1 33210C。A．5 B．8 C．6 D．9注意：有n个结点的树，树中所有结点的度之和为n-1。现在这棵树应该满足条件：n-1=2*3+1*2+2*1=1011个结点（加上一个根结点1132、1506个。一棵有nB个结点。A．n-2 B．n-1 C．n+1 D．n+2一棵有nA个结点。A．0 B．n C．n+1 9A。A．树的先序遍历序列与其对应的二叉树的先序遍历序列相同B．树的先序遍历序列与其对应的二叉树的后序遍历序列相同C．树的后序遍历序列与其对应的二叉树的先序遍历序列相同D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同三、问答6-23所示的两棵树是一样的吗？为什么？答：从图6-23(a)知，该树的根结点为A，下面有两棵子树，其中的一棵子树是最小树，只有根结点为B；另一棵子树的根结点为C，下面又有一棵最小子树，它的根结点为D。从图6-23(b)知，该树的根结点也是A与图6-23(a)里的相同。因此如果把树的子树视为是无序的，那么该图所展示的两棵树是一-25-习题解答样的，否则是不一样的。

图6-23 树示例树，但树的每个结点可以有多棵子树；第二，二叉树的子树有左、右之分（即是有序的，但树的子树通常是不分顺序的。为什么对于二叉树有中序遍历，而对一般树却没有中序遍历？其结点可以有任意数目的子树，因此，无法规定怎样的访问顺序才算是“中序最右边的结点最后访问？1）层次遍历和先序遍历总是首先访问树的根结点（）于树最左边的结点（）后序遍历总是最后访问树的根结点（）的最右边的结点。2的树与一棵二叉树有什么区别？22的树结点的子不能随意换位。四、应用已知一棵树的孩子链表表示法如图6-24所示，试画出该树。图6-24 一棵树的孩子链表表示法 图6-25 树示例答：该树形状如下图所示。已知一棵树如图6-25所示。请画出该树的以下存储结构）双亲表示法（2）带-26-习题解答（子链表表示法。望能够把两者结合起来（）兄弟链表表示法。（）(a）(b孩子/(c)所示。6-26所示的二叉树转换成相应的森林。图6-26 二叉树示例 图6-27 树示例答：转换成的森林如下图所示。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。-27-习题解答6-28所示的森林转换成对应的二叉树。图6-28 森林示例 图6-29 树示例答：对应的二叉树如下图所示。6-29答：对应的二叉树如下图所示7章习题解答一、填空46条。在一个具有4个顶点的无向图中，要连通全部顶点3条边。vv之间有一条边，v）vv互i j i j i j为邻接点。图中顶点v相邻接的顶点的个数，并记为D(v。i i-28-习题解答ivivj的弧记为<v，vj>vjviij 的弧记为<v，v>，这是两条不同的弧。j i行（或第i列）i个顶点vi的度。ii个顶点vi的出度；其邻接矩阵中第i列里非零或非∞元素的个数，正好是第i个顶点vi的入度。在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vivj是连通的。GG连通图。在无向图G中，尽可能多地从集合V及E个极大的连通子图，这个子图就被称为是无向图G的一个连通分量。包含无向连通图Gn个顶点在内的极小连通子图，是这个图的生成树。15．已知无向图的顶点个数为n，边数为e。那么，在其邻接表表示法中，链表结点数与单链表表头结点数之和是15．已知无向图的顶点个数为n，边数为e。那么，在其邻接表表示法中，链表结点数与单链表表头结点数之和是n+2e。二、选择1．在一个有n个顶点的无向图中，要连通全部顶点，至少需要C条边。A．n B．n+1 C．n-1 D．n/22n个顶点的无向完全图包含有C条边。A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/23nA条边。A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/24．在一个无向图中，所有顶点的度数之和，是其所有边数之和的CA．1/2 B．1 C．2 D．45．在一个有向图中，所有顶点的入度之和BA．二分之一于 B．等于 C．两倍于 D．四倍6．一个无向连通网图的最小生成树A。A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存7．一个无向图有n个顶点，那么该图拥有的边数至少是D。A．2n B．n C．n/2 D．0nC条边。A．4n-1 B．2n-1 C．n-1 9C。A．用邻接表存储图，所用存储空间大小只与图中顶点个数有关，与边数无关B．用邻接表存储图，所用存储空间大小只与图中边数有关，与顶点个数无关CD．用邻接矩阵存储图，所用存储空间大小只与图中边数有关，与顶点个数无关10．对如图7-21所示的无向图实施深度优先搜索遍历，可能的遍历序列是B。-29-习题解答图7-21 无向图示例三、问答7-22所示的无向连通网图的。一个无向连通网图的MST唯一吗？图7-22 无向连通网图示例 图7-23 无向图示例答：其MST如图7-15(g所示。如果使用边4,6）代替边3,6MST。所以，MST不是唯一的。试述简单回路、回路两者间的联系与不同。重复出现，那么这条路径称为简单回路后一个顶点相同，那么这条路径称为回路有如图7-23v1遍历序列。答：它的邻接矩阵如图所示。从顶点v1出发的深度优先遍历序列为：v1->v2->v4->v5->v7->v6->v3注意，该序列是不唯一的。构造最小生成树的Prim算法与求单源最短路径的Dijkstra图中的顶点分成U和V-U两个部分，都是在V-U里挑选出一个顶点，并将它从V-U移到U中。那么，它们的主要区别是什么？-30-习题解答算法是从V-U里挑选MST中某个顶点相距最近的顶点，而Dijkstra算法是从V-U源点最近的顶点。m个顶点的无向图G，如何通过它的邻接矩阵判定下列问题：图中有多少条边？任意两个顶点ij之间是否有边相连？任意一个顶点i的度是多少？（）邻接矩阵中非零元素个数的一半，是图中边的数目（）元素A{,和A[,是否不为，可知顶点i和j之间是否有边相连（3）第i行或第i列上i的度。7-24回答下列问题：（1）顶点集合V； （2）边集合E； （3）每个顶点x的度D(x)；（4）一个长度为5的路径； （5）一个长度为4的回路；（6）图的一个生成树； （7）邻接矩阵； （8）邻接表。图7-24 图示例（）顶点集合V=1,2,3,,5,6。（2）边集合E={<v1,v2>,<v2,v3>,<v2,v4>,<v3,v4>,<v3,v5>,<v4,v5>,<v3,v6>,<v4,v6>}。（3）每个顶点的度：D(v1)=1，D(v2)=3，D(v3)=D(v4)=4，D(v5)=D(v6)=2。5（4）一个长度为5的路径是：v1->v2->v3->v6->v4->v。524的回路是：v2v3v5v4v。2所示。所示。所示。问答5的（6）~（8）答案-31-习题解答四、应用利用Kruskal7-14(a)所给无向连通网图的最小生成树。MSTKruskal算法时，从图的边E里挑选边v,v，因为这两个顶点分属MST中的不同连通分量，且权6 767MSTvv(b)所示。接着，从图67的边E里挑选边vv、挑选边vv、挑选边vv）挑选边v,v）挑选边v,v，1 3 1 2 4 6 5 7 3 6最终得到如图(g)所示的最小生成树。利用Floyd7-25所示的有向网图中各顶点对的最短路径长度。图7-25 有向网图示例答：Floyd算法基于的邻接矩阵，以及推演出的各个矩阵、最终结果如下所示。1Dijkstra7-26v1v1 4度是；v41 4度是；v41

的最短路径长的最短路径长的最短路径长-32-习题解答1度是；v11

v65 6

v36 3

v的最短路径长度76 是；vv的最短路径长度是。如图所示。6 1 8图7-26 图示例 图7-27 AOV网7-27所示的AOV网的拓扑排序序列。答：该网只有顶点v3的入度为0，所以只能从它开始进行拓扑排序，其拓扑序列为：v3->v1->v4->v5->v2->v6生成树。答：无向连通网以及所对应的最小生成树如图(a)、(b)所示。8章习题解答一、填空记录的集合是实施查找的数据基础。在讨论查找问题时，常把T称为查找表。有序表和分块有序表是一种静态查找表；二叉查找树是一种动态查找表。1为根结点的子树为“最小不平衡树-33-习题解答或哈希表。二、选择在对线性表进行折半查找时，要求线性表必须BA．以顺序方式存储B．以顺序方式存储，且结点按关键字有序排列C．以链式方式存储D．以链式方式存储，且结点按关键字有序排列采用顺序查找法查找长度为nC。A．n B．n/2 C．(n+1)/2 3．有一个有序表：1，3，9，12，32，41，45，62，75，77，82，95，100采用折半查找法查找值为82的记录时，要经C次关键字比较后，查找成功。A．1 B．2 C．4 D．815、38、61、84，采用二次探测法解决冲突。那么关键字为49的记录的散列地址为D。A．1 B．3 C．5 D．95．在下列各种查找方法中，只有AnA．散列查找 B．二叉查找树 C．折半查找 D．分块查找6．在开放地址法中，由于散列到同一个地址而引起的“堆积”现象，是由B产生的A．同义词之间发生冲突B．非同义词之间发生冲突CD．散列表“溢出”在最坏的情况下，查找成功时二叉查找树的平均查找长度CA．小于线性表的平均查找长度B．大于线性表的平均查找长度C．与线性表的平均查找长度相同D．无法与线性表的平均查找长度相比较C。A．必须大于、等于原散列地址B．必须小于、等于原散列地址CD．地址大小没有具体限制三、问答（1）、if、for、while、repeat，依照创建二叉查找树算法，、loopiffor找长度又是多少？-34-习题解答（）(a所示，平均查找长度是：ASLa=(1+2*2+2*3)/5=11/5=2.2(2)的二叉查找树如图(b)所示，平均查找长度是：ASLb=(1+2+3+4+5)/5=15/5=310需要的比较次数。答：根据折半查找算法，因此首先用给定值K与区间[1，10]5的元素比较次数为1[1，4]或[6，10]中继续折半查找，因281、、、9的元素的比47、104。于是，所填结果为：四、应用3527，请一步步画出构造二叉查找树的过程。答：构造二叉查找树的过程如下：给出如图8-21所示的一棵二叉查找树，在其基础上分别做操作（）删除关键字为15）插入关键字为20的记录。画出这两个操作完成后该树的形态。-35-习题解答图8-21 二叉查找树示例答：1）删除关键字为15(a)或(b)直接前驱（或左子树根结点）取代所得，而(b)则是用待删结点的直接后继（或右子树根结点）2）插入关键字为20(c所示。设散列函数为h(key)=key%1，散列表长为1（索引地址为0~1SUN，MON，TUE，WED，THU，FRI，SAT取单词第1个字母在英语字母表中的序号为关键字值（比如S的关键字值为1址法解决散列地址冲突。请画出对应的散列表。答：对应的散列表如下。4．有关键字序列：36、27、68、33、97、40、81、24、23、90、32、14，散列表长为h(key)=key%13，使用开放地址法的线性探测解决冲突。请完成下面散列表的填写（13610以比较一次就存放在了地址为10的位置，求出其平均查找长度AS。-36-习题解答答：最终的散列表如图所示。其平均查找长度ASL为：ASL（线性探测12个关键字组成的序列：Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec在等概率下查找成功的平均查找长度。树查找成功的平均查找长度。（）最终形成的二叉查找树如下图所示，其平均查找长度为：ASL=（1+2*2+3*3+3*4+2*5+6）/12=42/12=3.5-37-习题解答（2）这时成为只有右子树的单支树，其平均查找长度为：ASL=（1+2+3+4+5+6+7+8+9+10+11+12）/12=78/12=6.512个关键字组成的序列：Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec散列表长为1（地址为0~1h(key)=i/，其中i为关键字中第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.59章习题解答一、填空置上，以便构成一个新堆。、38、96、23、18、7361、46、88，采用直接插入排序算-38-习题解答法。在进行到寻找第7个关键字61的插入位置时，需要做3次比较。（7