数据结构(C语言版)第三版习题参考答案.doc

不管怎样，生活还是要继续向前走去有的时候伤害和失败不见得是一件坏事，它会让你变得更好，孤单和失落亦是如此每件事到最后一定会变成一件好事，只要你能够走到最后附录 习题参考答案习题 1 参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A.1.2.填空题(1). 数据 关系(2). 逻辑结构 物理结构(3). 线性数据结构 树型结构 图结构(4). 顺序存储 链式存储 索引存储 散列表（Hash）存储(5). 变量的取值范围 操作的类别(6). 数据元素间的逻辑关系 数据元素存储方式或者数据元素的物理关系(7). 关系 网状结构 树结构(8). 空间复杂度和时间复杂度(9). 空间 时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体是计算机程序加工和处理的对象包括数值数据和非数值数据数据项：数据项指不可分割的、具有独立意义的最小数据单位数据项有时也称为字段或域数据元素：数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理一个数据元素可由若干个数据项组成数据逻辑结构：数据的逻辑结构就是指数据元素间的关系数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系数据类型：是指变量的取值范围和所能够进行的操作的总和算法：是对特定问题求解步骤的一种描述是指令的有限序列1.4 语句的时间复杂度为：(1) Ο(n2) (2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int XYZ；scanf("%d%d%d"&X&YZ)；if (X>=Y) if(X>=Z) if (Y>=Z) { printf("%d%d%d"XYZ);}else{ printf("%d%d%d"XZY);}else{ printf("%d%d%d"ZXY);}else if(Z>=X) if (Y>=Z) { printf("%d%d%d"YZX);}else{ printf("%d%d%d"ZYX);}else{ printf("%d%d%d"YXZ);}}1.6 参考程序：main(){ int in;float xa[]p;printf("\nn=");scanf("%f"&n);printf("\nx=");scanf("%f"&x);for(i=0;inext=p->next; p->next=s ;(10). s->next 2.3. 解题思路：将顺序表 A 中的元素输入数组 a若数组 a 中元素个数为 n将下标为 012...（n-1）/2 的元素依次与下标为 nn-1...（n-1）/2 的元素交换输出数组 a 的元素参考程序如下：main(){ int in;float ta[];printf("\nn=");scanf("%f"&n);for(i=0;ia[0]{ t=a[i]; a[i] =a[0]; a[0]=t;} printf("%f"a[0]);for(i=2;ia[1]{ t=a[i]; a[i] =a[1]; a[1]=t;} printf("%f"a[0]);}2.5 算法与程序：main(){ int ijkn;float xta[];printf("\nx=");scanf("%f"&x);printf("\nn=");scanf("%f"&n);for(i=0;ij) {t=a[i];a[i]=a[k];a[k]=t;}}for(i=0;ix) break;for(k=n-1;k>=i;i--) // 移动线性表中元素然后插入元素 xa[k+1]=a[k];a[i]=x;for(i=0;idata[k++]=A.data[i++]；else C->data[k++]=B.data[j++]；while (idata[k++]= A.data[i++]；while (jdata[k++]=B.data[j++]；C->last=k-1；}2.7 算法思路：依次将 A 中的元素和 B 的元素比较将值相等的元素赋给 C如此直到线性表扫描完毕线性表 C 就是所求递增有序线性表算法：void merge (SeqList ASeqList BSeqList *C){ int ijk；i=0；j=0；k=0；while ( idata[k++]=A.data[i++]；C->last=k-1；}习题 3 参考答案3.1.选择题(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C (15). C (16). D(17). D (18). C (19). C (20). C 3.2.填空题（1） FILOFIFO（2） -13 4 X * + 2 Y * 3 / -（3） stack.topstack.s[stack.top]=x（4） p>llink->rlink=p->rlinkp->rlink->llink=p->rlink（5） (R-F+M)%M（6） top1+1=top2（7） F==R（8） front==rear（9） front==(rear+1)%n（10） N-13.3 答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能性表的一端插入（称为入栈push）或者读取栈顶元素或者称为"弹出、出栈"(pop)3.4 答：相同点：栈和队列都是特殊的线性表只在端点处进行插入删除操作不同点：栈只在一端（栈顶）进行插入删除操作；队列在一端（top）删除一端(rear)插入3.5 答：可能序列有 14 种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA3.6 答：不能得到 435612最先出栈的是 4则按 321 的方式出不可能得到 1 在 2 前的序列可以得到 135426按如下方式进行 push(1)pop()push(2)push(3)pop()push(4)push(5)pop()pop()pop() push(6)pop()3.7 答：stack3.8 非递归:int vonvert (int noint a[]) //将十进制数转换为 2 进制存放在 a[]并返回位数{int r;SeStack s*p;P=&s;Init_stack(p);while(no){push(pno%2);no/=10;}r=0;while(!empty_stack(p)){pop(pa+r);r++;}return r;}递归算法:void convert(int no){if(no/2>0){Convert(no/2);Printf("%d"no%2);}elseprintf("%d"no);} 3.9 参考程序：void view(SeStack s){SeStack *p; //假设栈元素为字符型 char c;p=&s;while(!empty_stack(p)){c=pop(p);printf("%c"c);}printf("\n");}3.10 答：char3.11 参考程序：void out(linkqueue q){int e;while(q.rear !=q.front ){dequeue(qe);print(e); //打印}} 习题 4 参考答案4.1 选择题：(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D4.2 填空题：（1） 串长相等且对应位置字符相等（2） 不含任何元素的串0（3） 所含字符均是空格所含空格数（4） 10（5） "hello boy"（6） 13（7） 1066（8） 模式匹配（9） 串中所含不同字符的个数（10） 364.3 StrLength (s)=14StrLength (t)=4 SubStr( s87)=" STUDENT"SubStr(t21)="O"StrIndex(s"A")=3StrIndex (st)=0StrRep(s"STUDENT"q)=" I AM A WORKER"4.4 StrRep(s"Y""+");StrRep(s"+*""*Y");4.5 空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符4.6 int EQUAl(ST){char *p*q;p=&S;q=&T;while(*p&&*q){if(*p!=*q)return *p-*q;p++;q++;}return *p-*q;}4.7 (1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=13684.8 习题 5 参考答案5.1 选择（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C（11）B（12）C（13）C（14）C（15）C（16）B5.2 填空（1）1（2）1036；1040（3）2i（4） 1 ； n ; n-1 ; 2 （5）2k-1；2k-1（6）ACDBGJKIHFE（7）p!=NULL（8）Huffman 树（9）其第一个孩子; 下一个兄弟（10）先序遍历；中序遍历5.3 叶子结点:C、F、G、L、I、M、K；非终端结点：A、B、D、E、J；各结点的度：结点： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0树深：45.4 无序树形态如下：二叉树形态如下：5.5 二叉链表如下:三叉链表如下:5.6 先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5.7 (1) 先序序列和中序序列相同：空树或缺左子树的单支树；(2) 后序序列和中序序列相同：空树或缺右子树的单支树；(3) 先序序列和后序序列相同：空树或只有根结点的二叉树5.8 这棵二叉树为:5.9 先根遍历序列:ABFGLCDIEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5.10 证明：设树中结点总数为 n叶子结点数为 n0则n=n0 + n1 + ...... + nm （1）再设树中分支数目为 B则B=n1 + 2n2 + 3n3 + ...... + m nm （2）因为除根结点外每个结点均对应一个进入它的分支所以有n= B + 1 （3）将（1）和（2）代入（3）得n0 + n1 + ...... + nm = n1 + 2n2 + 3n3 + ...... + m nm + 1从而可得叶子结点数为：n0 = n2 + 2n3 + ...... + (m-1)nm + 1 5.11 由 5.10 结论得n0 = (。