数据结构 第一版 (陈雁 著) 高等教育出版社 课后答案

课后答案网： 一章 习题 1、简述下列术语： 数据元素、数据、数据对象、数据结构、存储结构和算法 解： 数据元素 ：数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。 数据 ：信息的载体。是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。 数据对象 ：性质相同的数据元素的集合，是数据的一个子集。 数据结构 ：相互之间存在着一种或多种关系的数据元素的集合，包括数据的逻辑结构和物理结构两方面的内容。 存储结构 ： 数据的逻辑结构在计算集中的表示方式，包含顺序存储方法、链接存储方法、索引存储方法、散列存储方法。 算法 ： 对特定问题求解步骤的一种描述，它是指令或语句的有限序列，并具有有穷型、确定性、可行性、输入和输出五个重要特性。 2、试写一算法，自大至小依次输出顺序读入的三个整数 x，y 和 z 的值 解： f1( x,y,z; x,y,z:); %d,%d,%d,&x,&y,&z); if(xy) if(yz) %d,%d,%d,x,y,z); if(xz) %d,%d,%d,x,z,y); %d,%d,%d,z,x,y); if(xz) %d,%d,%d,y,x,z); if(zy) %d,%d,%d,z,y,x); %d,%d,%d,y,z,x); 课后答案网： 、举出一个数据结构的例子，叙述其逻辑结构、存储结构、运算等三方面的内容 解： 4、分析下列 算法的时间复杂度： （ 1） n) i=2;0) 1; /* 表已空 */ -i=x) j=i;j+) L-j=L-j+1;/*被删除元素之后的元素左移 */ i+; ; 4、设线性表 (， 储在带表头结 点的单链表中，试设计算法，求出该线性表中值为 x 的元素的序号。如果 序号为 0。 H,x) p=H- j=1;f=0; /* P 指向第一个结点， j 为计数器， f 为标志 */ p ) if(p-x) j+; p=p- f=1; f=1 ) 课后答案网： j; 0; 5、在一个非递减有序线性表中，插入一个值为 x 的元素，使插入后的线性表仍为非递减有序。分别写出用顺序表和单链表表示时的算法。 顺序表： L ,x) L- 1; /* 表已满 */ if(x=L- L-=x; L-1; i=1; x=L-i) i+; j=L-j=i;L-j+1=L-j; L-i=x; L-1; ; 单链表： H, x) p=H; s= () ; if(s) s-x; s- ; p-if(p- s-p- p-s; /* 插入 */ ; /* p-s; ; 6、设一个线性表 L=(， a n)，编写算法将其逆置，即成为（ a n， 要求逆置后的线性表仍占用原来的存储空间，并且用顺序和单链表两种方法表示，写出不同的处理过程。 顺序表： L ） i; x; i=1;i+) x=L-i; L-i=L-; L-=x; 单链表： H） d=h-if(d!= p=d-p) t=p-p-d; d=p; p=t; h=d; 课后答案网： 7、设两个单链表 A 和 B，它们的数据元素分别为 ( ,x m)和 (， y n)。设计一个算法将它们合并为一个单链表 C，使得： 当 m n 时， C (.， x n， y n， .,x m ) 当 n m 时， C (.， y m ， x m， .,y n )。 A,B ) p=A-q=B-m=0; n=0; p) m+; p=p- q) n+; q=q- if(m=n) p=A-q=B-C=A; p=B-q=A-C=B; q) t=p-p-q; q=q-p-t; p=t; 课后答案网： ; 8、试写一算法，在无表头结点的单链表中值为 a 的结点前插入一个值为 b 的结点 , 如果 a 不存在，则把 b 插在表尾 。将该算法与第 中的算法 2 7 进行比较。 H, a, b) s=() ; s-b; s-= H=s; p=H; q=p-if(p-a)/*对首元节点处理 */ s-p; H=s; q&q-a) p=q; q=q- p-s; s-q; 9、假设有一个单向循环链表，其结点包含三个域： 中 数据域， 指针域，其值为后继结点的地址， 为指针域，其初值为空（ 试设计算法将此单向循环链表改为双向循环链表。 H) 课后答案网： q=H; p=H-p) p-q; q=p; p=p- H-q; q-; 10、已知二 维数组 A57，其每个元素占四个存储单元，且A00的存储地址为 1100，试求出元素 A35的存储地址（分别讨论以行为序和以列为序方式存储时的结论）。 行为序 1100+4*(3*7+5)=1204 列为序 1100+4*(5*5+3)=1212 11、设有一个二维数组 AMN，对以下三种情况分别编写算法： （ 1） 求数组 A 的最外围元素之和； （ 2）求从 A00开始的互不相邻的各元素之和； （ 3）当 M=N 时，分别求两条对角线上的元素之和，否则输出 M N 的信息。 1(MN)/* 求数组 A 的最外围元素之和 */ s=0; i=0;*若 A 的当前项的行号等于 B 当前项的行号，则比较其列号，将较小列号的项放入 C，如果列号也相等，相加后放入 C； */ -iB-j-ij C-k-iC-k-iC-k-ik+; i+; -i-j C-k-jC-k-jC-k-jk+; 5 4 1 1 3 2 3 3 1 2 1 4 7 课后答案网： j+; C-k-jC-k-jC-k-j-ik+; j+; i+; -ij/*若 A 当前项的行号小于 B 当前项的行号，则将 A 项放入 C*/ C-k-iC-k-iC-k-ik+; i+; /*若 A 当前项的行号大于 B 当前项的行号，则将 B 项放入 C*/ C-k-jC-k-jC-k-jk+; j+; C-m=A-m;/*C 的行数 */ C-n=A-n;/*C 的列数 */ C-t=*C 的非零元个数 */ 14、设稀疏矩阵 A 用十字链表表示，编写算法查找元素： （ 1）已知 i， j，查找 Aij； （ 2）已知 x 的值，查找它在第几行第几列。 解： （ 1） *M,i,j, if(i0) p=M-i; 课后答案网： p) if(p-j) *p-;/*找到 */ p=p- ;/*未找到 */ 1;/*行号错误 */ （ 2） *M,x, i=1;i+) p=M-i; p) if(p-x) *p-*p-; p=p- ; 上机实习题 1. 设 A=（ , B=（ ,两个线性表，其数据类型是整型。若 n=m 且 i n),则称A=B；若 1 i j），而 j n m),则称 AB；除此以外，均称 A=B。设计一个比较 A、 B 大小的程序。 # 课后答案网： 00 /*存储线性表中的元素 */ /*线性表的当前表长 */ L) L=(); L-; ; L,i,x) j; ) ; /* 不合理的插入位置 i */ L- 1; /* 表已满 */ j=L-j=i;L-j+1=L-j; /* 插入位置及之后的元素右移 */ L-i=x; /*插入 x */ +L- /*表长加 1 */ ; f(A,) i=1,j,; s); s); -i=B-i) i+; j=i;j+) s,A-j); j=i;j+) s,B-j); s-s-if(0) ; 课后答案网： if(0&|(&) 1; ; A=B=n=0,m=0,i=0,d=0; A=); B=); !=B) A!=B); A=B); n:); %d,&n); i=1;i+) %d ,A-i); n); m:); %d,&m); i=1;i+) %d ,B-i); n); n); i=1;i+) %d ,A-i); n); i=1;i+) 课后答案网： %d ,B-i); i=f(A,B); if(i=0) A=B); if(; ; 2. 设计一个程序求出约瑟夫环的出列顺序。约瑟夫（ 题的一种描述是：编号为 1， 2， n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。例如 n=7,7 个人的密码依次为： 3， 1， 7， 2， 4， 8， 4， ，则正确的出列顺序应为 6， 1， 4， 7， 2， 3， 5。要求使用单向循环链表模拟此出列过程。 # x, s; s=(); s-x; s-id=if( s; s-s; 课后答案网： s-s; s; p=q=d,m,i=1; ); %d,&d); d!=0) d,i+); ); %d,&d); p=*显示数据 */ p!= %d ,p- p=p- %d,p- m:);/*输入初始 m*/ %d,&m); p=p!=p- i=1;q=p-p-q-m=q- 课后答案网： %d ,q- q); %d ,p- p); ; 第三章 习 题 l假定有编号为 A、 B、 C 的 3 辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序 (注：每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退 )。写出每一种可能的序列。 解： 产生： 会产生： 有字符串次序为 5*y 2，试利 用栈排出将次序改变为 5y-*（可用 X 代表扫描该字符串过程中顺序取一字符进栈的操作，用 S 代表从栈中取出一字符加到新字符串尾的出栈的操作）。例如， 为 操作步骤为 解： 写出链栈的取栈顶元素和置栈空的算法。 解： （ 1） Y) if(1 y=; （ 2） 课后答案网： p=p); 4假设一个算术表达式中包含圆括弧、方括弧和花括弧，编写一个判别表达式中括弧是否正确配对的算法。 解： f() p); p,#); c=; c!=#|p)!=#) if(c=(|c=|c=) p,c); if(c=) p,o); if(o!=() 1; if(c=) p,o); if(o!=) 1; if(c=) p,o); if(o!=) 1; c=; ; 课后答案网： 写出计算表达式 5+3*4/6操作 数栈和运算符栈的变化情况。 解： 步骤 入字符 1 # 5+3*4/62 # 5 +3*4/63 #+ 5 3*4/64 #+ 5， 3 *4/65 #+* 5， 3 4/66 #+* 5， 3， 4 /67 #+ 5， 12 /68 #+/ 5， 12 69 #+/ 5， 12， 6 10 #+ 5， 2， 11 # 7 12 #- 7 7# 13 #- 7， 7 # 14 # 0 # 6对于给定的十进制正整数，打印出对应的八进制正整数。 (1)写出递归算法。 (2)写出非递归算法。 解： f(n)/* 递归算法 */ *退栈求值 */ 0; 2=0=1*2; 0); 课后答案网： 对于一个具有 m 个单元的循环队列，写出求队列中元素个数的公式。 解： (m)%m 9假设用一个数组 QM来表示队列，该队列只设一个队头指针 设队尾指针而改设计数器 以记录队列中元素的个数。试编写出相应的置空队列，入队列和出队列的算法。 解： /*队头 */ *置空队列 */ ; ; x)/* 在循环队列 尾部插入一个新的元素 x */ q-1;/*队列上溢 */ ; q-x; ; y)/*删除循环队列 队头元素，并存人 *y 中 */ q-0) 1;/*队列下溢 */ )% 课后答案网： y=q- ; 10假设以带头结点的循环链表示列队，并且只设一个指针指向队尾元素结点 (注意不设头指针 )，试编写出相应的置空队列，入队列和出队列的算法。 解： /*结点结构 */ * * /*队尾指针 */ *置 空队列 */ q-*循环队列为非空 */ q- p=p); x)/* 在循环队列 尾部插入一个新的元素 x */ p=(); if(p=1; 课后答案网： p-x; p- q-*循环队列为空 */ p; p-p; q-s; s; s- ; y)/*删除循环队列 队头元素，并存人 *y 中 */ q-*队列下溢 */ 1; q-if(*只有一个节点 */ *y= *y= ; 课后答案网： 机实习题 1设计一个算法，检验 C 源程序代码中的括弧对是否正确配对。要求在某个 C 源程序文件上对你的算法进行验正。 # * x) p; p=(); p-x; p-p; y, p; if(*; /*链栈已空 */ /*出栈 */ p=*y=p- p-*; ) ch,o; ; p=if(2) 课后答案网： to n); ); fp=,r)= n); ); ch= if(|) cn, p=p, if() p=p,&o,& ):c,%dn,o, if(0) d (); o) ( : :);); :);); if() p=p,&o,& :c,%dn,o, if(0) d ); o) ( :);); : :);); 课后答案网： if() p=p,&o,& :c,%dn,o, if(0) d ); o) ( :);); :);); : ch= p=p,&o,& if(0) ; 0)/*如果栈未空 */ o) ( :); :); :); p=p,&o,& ; 课后答案网： 设计程序，模拟手机的某些短信息功能。 功能要求： （ 1）接受短信 息，若超过存储容量（如最多可存储 20 条），自动将最早接受的信息删除。 （ 2）显示短信息数量。 （ 3）逐条显示短信息（从最新的开始）； （ 4）删除其中的任意一条短信息； （ 5）清除。 /* （ 1）接受短信息，若超过存储容量（如最多可存储 20 条），自动将最早接受的信息删除。 （ 2）显示短信息数量。 （ 3）逐条显示短信息（从最新的开始）； （ 4）删除其中的任意一条短信息； （ 5）清除。 */ #0/*存储容量 */ #00/*信息长度 */ /*结点结构 */ * * *队头指针 */ * /*队尾指针 */ /*初始化 */ p; q; p=(); 课后答案网： p-; q=(); q-p-q; p-q; p; * 获得新短信 */ t; p; t= t);/*获得时间信息，模拟短信内容 */ q- q); p=(); ; p- p; p; ; ; *删除循环队列 队头元素 */ p; q-; p= /*p 指向新的队头结点 */ p-p ) q-*尾指针指向头结点 */ p); 1; 课后答案网： Lq,i)/*删除循环队列 第 i 个元素 */ p,* q; n=1; q-; p=n+; q=p-p-q-q ) p;/*尾指针指向前结点 */ q); 1; Lq,i)/*显示第 i 条短信 */ p=n=1; if(i0& n+; d d:%sn,i, q-q); nnnn); 课后答案网： = n); = to =n); = =n); = to a =n); = to =n); = to =n); =n); = =n); = =n); = =n); = n); nnnn); ) c; p; i; p=; ; c=; c!=q&c!=Q) c) g: /*获得新消息 */ G:p);e: /*显示消息 */ E:i=1;i+) p,i);d: /*删除当前消息 */ D:i:);%d,&i);p,i);p: /*删除最先的纪录 */ P:p);r: /*清楚所有消息 */ R:p); c=; ; p); ; 课后答案网： B D J I E K H G F C 题图 4树 T 第四章 1有一棵树如题图 4示，求出树的叶子结点、非终端结点、各结点的度、树的度和树深。 解 ： （ 1）叶子结点： E、 F、 G、 H、 K、 J （ 2）非终端结点： A、 B、 C、 D、 I （ 3）各结点的度：度为 3 的结点： A、 C 度为 2 的结点： D 度为 1 的结点： B、 I 度为 0 的结点： E、 F、 G、 H、 K、 J （ 4）树的度： 3 （ 5）树深： 4 2具有三个结点的二叉树有多少种不同的形态 ?请分别画出。 解 ：具有三个结点的二叉树有 5 种不同的形态，如下所示： 3如果一棵树有 的结点， 的结点， ， n m 的结点，则该树共有多少个叶子结点 ?可参考二叉树性质 3 的证明方法来思 考 m 叉树问题。 解 : 设树中有 叶子结点，那么树中总结点数 N 为： N + （ a） 由于 树中除根结点外，其它各结点都有仅有一个分支指向它，所以树中的总结点数恰好比分支数少 1。 设 B 为 树中总分支数，即有： B 外，除度为 0 的结点没有 分支外，每个 度为 k 的结点有 k 个 分支，所以总分支数又为： B 1+m 即 总结点数为： N +m （ b） 由式 (a)和式 (b)有： + +m 即得： 1+（ （ （ 1 （ i=2 m） 4写出按层遍历二叉树的算法。 课后答案网： ：二叉链表结点结构描述为： /* 数据域 */ * /* 左、右孩子指针域 */ /* 按层次遍历二叉树 ， 类型的队列 */ ); /* 初始化队列 Q */ if( , /*根结点入队列 */ ) /*队列非空 */ Q,&p); /*队头元素存入变量 (p- /*访问根结点 */ if(p- ,p- if(p- , p- /* 5设计算法求二叉树中度为 1 的结点数。 解 ：设置一个初始值为 0 的全局变量 行计数，在对二叉树进行遍历的过程中判断当前所访问的结点是否为度为 1的结点，若是则 。因此当遍历完整个二叉树后， 的结点的数目。算法描述如下： ; & !|(!& ; /*计数 */ /* 设计递归算法，求出先根序列中第 k 个结点的值。 解 : bt,k) /*求先序序列中第 */ n; n=k; if( if(n=0) 课后答案网： n); if(n!=0) n); #); 7现有按中根遍历二叉树的结果为： 画出可以得到这一结果的全部二叉树。 解 ： 8已知遍历某二叉树后的中根遍历序列 后根遍历序列 画出该二叉树。 解 ：根据二叉树后的中根遍历和后根遍历的 特点，其中根遍历序列和后根遍历序列的形式如下所示： 显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中找