数据结构---C语言描述-(耿国华)-课后习题答案

1、第一章 习题答案 2、xxV 3 、(1 )包含改变量定义的最小范围 ( 2 )数据抽象、信息隐蔽 ( 3)数据对象、对象间的关系、一组处理数据的操作 ( 4)指针类型 ( 5 )集合结构、线性结构、树形结构、图状结构 ( 6 )顺序存储、非顺序存储 ( 7 )一对一、一对多、多对多 ( 8 )一系列的操作 ( 9)有限性、输入、可行性 4、(1)A(2)C(3)C 5、语句频度为 1+ ( 1+2 ) + (1+2+3 ) + + (1+2+3+n ) 第二章 习题答案 1 、( 1 )一半，插入、删除的位置 ( 2)顺序和链式，显示，隐式 ( 3)一定，不一定 ( 4 )头指针，头结点的指

2、针域，其前驱的指针域 2、(1) A(2) A：E、 A B： H 、 L、 I、 E、 A C： F、 M D： L、 J、 A、 G 或 J、 A、 G 3) D ( 4) D ( 5) C( 6) A、 C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据 域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4 、算法如下： int Linser(SeqList *L,int X) int i=0,k; if(L-last=MAXSIZE-

3、1) printf( “表已满无法插入 ”)； return(0); while(ilastk=I;k-) L-elemk+1=L-elemk; L-elemi=X; L-last+; return(1); 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) int j; if(i(L-last+2) printf( “输入的 i， k 值不合法 ”); return ERROR; if(i+k)=(L-last+2) L-last=i-2; ruturn OK; else for(j=i+k-1;jlas

4、t;j+) elemj-k=elem j; L-last=L-last-k; return OK; 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) Node *p,*q; p=L; while(p-next!=NULL) p=p-next; if(minknext-data=mink)|(p-datanext-datanext; while(q-datanext=q-next; free(q); q=p-next; return OK; 9、算法如下： int Dele(Node *S)

5、Node *p; P=s-next; If(p= =s) printf( “只有一个结点，不删除 ”)； return 0; else if(p-next= =s) s-next=s; free(p); return 1; Else while(p-next-next!=s) P=p-next; P-next=s; Free(p); return 1; 第三章 习题答案 2、(1) 3、栈有顺序栈和链栈两种存储结构。 在顺序栈中，栈顶指针 top=-1 时，栈为空；栈顶指针 top=Stacksize-1 时，栈为满。 在带头结点链栈中，栈顶指针 top- next=NULL ，则代表栈空；只

6、要系统有可用空间， 链栈就不会出现溢出，既没有栈满。 5、 #include #include stdio.h void main( ) char ch,temp; SeqStack s; InitStack( scanf(%c, while(ch!= scanf(%c, while(ch!= scanf(%c, if(ch!=temp) break; if(!IsEmpty( else scanf(%c, if(ch=) printf(yes!n); else printf(no!n); 12 、(1)功能：将栈中元素倒置。 ( 2)功能：删除栈中的 e 元素。 (3)功能：将队列中的元素倒

7、置。 第四章习题答案 1、StrLength(s) 操作结果为 14 ；SubString(sub1,s,1,7) 操作结果为 sub1= IAM A SubString(sub2,s,7,1) 操作结果为 sub2= ； StrIndex(s, A ,4) 操作结果为 5； StrReplace(s, STUDENT ,q) 操作结果为 IAM A WORKER ； StrCat(StrCat(sub1,t), StrCat(sub2,q) 操作结果为 IAM A GOOD WORKER int StrReplace（SString S,Sstring T,SString V） int i=

8、1; / 从串 S 的第一个字符起查找串 T if（StrEmpty（T） /T 是空串 return ERROR; do i=Index（S,T,i）; / 结果 i 为从上一个 i 之后找到的子串 T 的位置 if（i） / 串 S 中存在串 T StrDelete（S,i,StrLength（T）; / 删除该串 T StrInsert（S,i,V）; / 在原串 T 的位置插入串 V i+=StrLength（V）; / 在插入的串 V 后面继续查找串 T while（i）; return OK; 第五章习题答案 1 、（1 ）数组 A 共占用 48*6=288 个字节； （2 ）数组

9、 A 的最后一个元素的地址为 1282 ； （3 ）按行存储时 loc（A36）=1000+ （3-1 ）*8+6-1*6=1126 （4 ）按列存储时 loc（A36）=1000+ （6-1 ）*6+3-1*6=1192 9、（1）（a，b）（2）（c，d）（3）（b）（4）b（5）（d） 10、D 第六章 习题答案 1 、三个结点的树的形态有两个；三个结点的二叉树的不同形态有5 个。 2、略 3、证明：分支数 =n i+2n 2+kn k（1） n= n o+n 1+ +n k（ 2） t n=分支数+1（3） 将（ 1 ）（ 2 ）代入（ 3 ）得 n0= n 2+2n 3+3n 4+

10、+ （ k-1 ） n k+1 4、 注：C结点作为D的右孩子（画图的时候忘记了，不好意思） 5、 n0=50 ，n2=nO-仁49，所以至少有 99个结点。 6、（ 1）前序和后序相同：只有一个结点的二叉树 （2）中序和后序相同：只有左子树的二叉树 （3）前序和中序相同：只有右子树的二叉树 7、 证明：I n个结点的K叉树共有nk个链域，分支数为 n-1 （即非空域） 空域=nk- （ n-1 ） =nk-n+1 8、对应的树如下： H 丁 / 一卜 k I A / p I 9、（答案不唯一） 哈夫曼树如下图所示: 哈夫曼编码如下: 频率 编码 0.070010 0.1910 0.02000

11、00 0.06 0001 0.3201 0.0300001 0.2111 0.10 0011 11、对应的二叉树如下: 12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。 typedef int ElemType; void An cestor(ElemType A,i nt n ,i nt i,i nt j) while(i!=j) if(ij) i=i/2; else j=j/2; printf(所查结点的最近公共祖先的下标是%d,值是d,i,Ai); 15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释 放相应的空间。 void Del_Sub(BiT

12、ree T) if(T-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free(T); void Del_Sub_x(BiTree T,i nt x) if(T-data=x) Del_Sub(T); else if(T-lchild) Del_Sub_x(T-lchild,x); if(T-rchild) Del_Sub_x(T-rchild,x); 22、 int Width(BiTree bt) if (bt=NULL) return (0); else BiTree p,Q50; in t fron t=1,rea

13、r=1,last=1; int temp=0, maxw=0; Qrear=bt; while(frontlchild!=NULL) Q+rear=p-lchild; if (p-rchild!=NULL) Q+rear=p-rchild; last=rear; if(tempmaxw) maxw=temp; temp=0; return (maxw); 第七章 习题答案 1、(1)顶点 1的入度为 3，出度为 0 ； 顶点 2的入度为 2 ，出度为 2 ； 顶点 3的入度为 1 ，出度为 2 ； 顶点 4的入度为 1 ，出度为 3 ； 顶点 5的入度为 2 ，出度为 1 ； 顶点 6的入度为

14、 2 ，出度为 3 ； (2) 邻接矩阵如下： 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 (3 )邻接表 (4 )逆邻接表 2、答案不唯一 (2 )深度优先遍历该图所得顶点序列为：1 , 2 , 3 , 4 , 5, 6 L|TT3HL3-m j 50 占I3P 十还匚4匿囚 3、 边的序列为：(1，2)(2，3)( 3，4)( 4，5)( 5，6) (3 )广度优先遍历该图所得顶点序列为：1，5，6，3，2，4 边的序列为：(1，5)( 1，6)( 1，3)( 1，2)( 5，4) (1 )

15、每个事件的最早发生时间： ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16, ve(6)=16, ve=19, ve(8)=21, ve(9)=23 每个事件的最晚发生时间: vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15, vl( 3)=12, vl(2)=6, vl(1)=9, vl(0)=0 (2 )每个活动的最早开始时间: e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=1

16、2, e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21 每个活动的最迟开始时间： l(0,1)=4,l(0,2)=0,l(1,3)=9,l(2,3)=6,l(2,4)=12,l(3,4)=12,l(3,5)=12,l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15,l(7,8)=19, l(6,9)=19, l(8,9)=21 (3 )关键路径如下图所示： 4、顶点1到其余顶点的最短路经为: 1- 3最短路经为 长度为15 1- 2最短路经为 长度为19 1-

17、 5最短路经为 长度为25 1- 4最短路经为 1- 6最短路经为 4 ;长度为29 4 , 6 ;长度为44 13、A(7)B(3)C(2)D(11)E(8) 14、略 15、略 第八章查找 1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找 长度。 解： ASL=(1+2*2+4*3+3*4)/10=2.9 5、 解：(1 )插入完成后的二叉排序树如下: ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5 (2)ASL=(1+282+3*4+4*5)=37/12 12、 解：哈希表构造如下: 0 1 2 3 4 5 6 7 8 9 1 0

18、2 4 3 0 5 4 1 3 6 2 1 0 1 3 6 7 H(22)=(22*3)%11=0 H(41)=(41*3)%11=2 H(53)=(53*3)%11=5 H(46)=(46*3)%11=6 H(30)=(30*3)%11=2与(41)冲突 H1(30)=(2+1)%11=3 H(13)=(13*3)%11=6与 46 冲突 H1(13)=(6+1)%11=7 H(01)=(01*3)%11=3与 30 冲突 H1(01)=(3+1)%11=4 H(67)=(67*3)%11=3与 30 冲突 H1(67)=(3+1)%11=4与 01 冲突 H2(67)=(3+2)%11=5

19、与53 冲突 H3(67)=(3+3)%11=6与46 冲突 H4(67)=(3+4)%11=7与 13 冲突 H5(67)=(3+5)%11=8 ASLsucc=(1*4+2*3+6)/8=2 ASLu nsucc=(2+8+7+6+5+4+3+2)/8=37/8 第九章排序 426 ）为例， ）堆排序（5） ，653，908 653，908 897，908 1、以关键字序列(503 , 087 , 512 , 061 , 908 , 170 , 897 , 275 , 653 , 手工执行以下排序算法，写出每一趟派结束时的关键字状态。 (1 )直接插入排序(2 )希尔排序(增量序列为 5，

20、3，1)( 3)快速排序(z 归并排序 解：(1 )略 (2)增量为 5 的排序结果：170，087，275，061，426，503，897，512 增量为 3 的排序结果：061，087，275，170，426，503，897，512， 增量为 1 的排序结果：061，087，170，275，426，503，512，653， (3 ) 一次划分后:426 087 275 061 170503897 908 653 512 分别进行：170 087 275 061426 503 512 653 897 908 061 087170275426 503 512 653 897 908 061 0

21、87 170 275 426 503 512 653 897 908 4）略 7、已知一组关键字： （40，27，28，12 ，15 ，50 ，7），要求采用快速排序法从小到大排 序。请写出每趟排序后的划分结果。 解：初始状态： 40 27 28 12 15 50 7 一次划分： 7 27 28 12 15 40 50 依次划分： 7 27 28 12 15 40 50 7 15 12 27 28 40 50 7 12 15 27 28 40 50 16 、（ 1） A3 B1 C4 D2 E7 （2）C （3）C 17 、对，错，对 数据结构课程设计指导书 一、设计内容 1. 飞机订票系统（

22、限 1 人完成） 【问题描述】 设计一个飞机订票系统，可以模拟处理飞机订票过程中的各种操作。 【基本要求】 通过此系统可以实现如下功能： 1）录入 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 。 2）查询 可以查询某个航线的情况 （如， 输入航班号， 查询起降时间， 起飞抵达城市， 航班票价， 票价折扣，确定航班是否满仓） ； 可以输入起飞抵达城市，查询飞机航班情况。 3）订票（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班。 4）退票 可退票，退票后修改相关数据文件。 客户资料有姓名，证件号，订票数量及航班情

23、况，订单要有编号。 5）修改航班信息 当航班信息改变可以修改航班数据文件 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。 2. 文章编辑（限 1 人完成） 【问题描述】 输入一页文字，程序可以统计出文字、数字、空格的个数。 【基本要求】 静态存储一页文章，每行最多不超过 80 个字符，共 N 行； 1）分别统计出其中英文字母数和空格数及整篇文章总字数； 2）统计某一字符串在文章中出现的次数，并输出该次数； 3）删除某一子串，并将后面的字符前移； 4）用指定的字符串替换某一子串； 5）存储结构使用线性表，分别用几个子函数实现相应的功能； 6）输入数据的形式和范围：可以输入

24、大写、小写的英文字母、任何数字及标点符号。 7）输出形式：分行输出用户输入的各行字符；分 4行输出”全部字母数”、”数字个数”、” 空格个数”、”文章总字数”；输出删除某一字符串后的文章；输出替换某一字符串后的 文章。 3. 宿舍管理查询软件（限 1 人完成） 【问题描述】 为宿舍管理人员编写一个宿舍管理查询软件。 【基本要求】 1）程序设计要求： 采用交互工作方式 建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序（冒泡、选择、插入排 序等任选一种 ） 2）查询菜单 : （用二分查找实现以下操作 ） 按姓名查询 按学号查询 按房号查询 3）输出任一查询结果（可以连续操作） 4. 全国

25、交通咨询模拟 【问题描述】 处于不同目的的旅客对交通工具有不同的要求。 例如， 因公出差的旅客希望在旅途中的时间 尽可能的短， 出门旅游的游客则期望旅费尽可能省， 而老年旅客则要求中转次数最少。 编制 一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 【设计要求】 1）提供对城市信息进行编辑（如：添加或删除）的功能。 2）提供对列车时刻表进行编辑（增设或删除）的功能。 3）提供两种最优决策：最快到达和最省钱到达。 4 ）旅途中耗费的总时间应该包括中转站的等候时间。 5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则，输出 信息：最快需要多长时间才

26、能到达或者最少需要多少旅费才能到达， 并详细说明于何时乘坐 哪一趟列车到何地。 测试数据：参考教科书 7.6节图 7.33 的全国交通图，自行设计列车时刻表。 【实现提示】 1）对全国城市交通图和列车时刻表进行编辑， 应该提供文件形式输入和键盘输入两种方式。 列车时刻表则需根据交通图给出各个路段的详细信息，例如：基于教科书7.6节图7.33 的交 通图， 对从北京到上海的火车， 需给出北京至天津、 天津至徐州及徐州至上海各段的出发时 间、到达时间及票价等信息。 2）以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通 工具、路程中耗费的时间和花费以及出发和到达的时间等多

27、种属性。 5. 哈夫曼编码 / 译码器（限 1 人完成） 【问题描述】 设计一个利用哈夫曼算法的编码和译码系统， 重复地显示并处理以下项目， 直到选择退出为 止。 【基本要求】 1）将权值数据存放在数据文件 （文件名为 data.txt ，位于执行程序的当前目录中 ） 2）分别采用动态和静态存储结构 3）初始化：键盘输入字符集大小 n 、n 个字符和 n 个权值，建立哈夫曼树； 4）编码：利用建好的哈夫曼树生成哈夫曼编码； 5）输出编码； 6）设字符集及频度如下表： 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47

28、57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【进一步完成内容】 1）译码功能； 2）显示哈夫曼树； 3）界面设计的优化。 6. 走迷宫游戏 【问题描述】 以一个m xn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任 意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 1 首先用二维数组存储迷宫数据，迷宫数据由用户输入。 2一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的 通路以三元组（i, j，d ）

29、形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下 一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。 3可以用多种方法实现，但至少用两种方法，用三种以上可加分。 【实现提示】 1 计算机解迷宫问题通常用的是 “穷举求解 ”方法，即从入口出发，顺着某一个方向进行探 索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置， 求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 迷宫的入口点的下标为（ 1， 1），出口点的下标为（ m， n ） 。为处理方便起见，可在迷宫的 四周加一圈障碍。对于迷宫的任一位置，均可约定有东、

30、南、西、北四个方向可通。 2有一种简单走出迷宫的方法，把手放在右边的墙上开始前进， 始终不要把手从墙上移开。 如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。 当然这样得到的路径可能不是一个最短的路径， 但它可以最终得到结果， 换句话说， 这种方 法走不出迷宫的风险是最小的。 7. 作业评分系统 【问题描述】 设计一个可以给小学生出题并且可以给出分数的系统软件。 【基本要求】 利用栈求表达式的值，可供小学生作业，并能给出分数。 1）建立试题库文件，随机产生 n 个题目； 2）题目涉及加减乘除，带括弧的混合运算； 3) 随时可以退出； 4) 给出作业分数。 【进一

31、步完成内容】 1) 保留历史分数，能回顾历史，给出与历史分数比较后的评价。 2) 界面设计的优化。 8. 散列表的设计与实现 【问题描述】 设计散列表实现电话号码查找系统。 【基本要求】 1)设每个记录有下列数据项：电话号码、用户名、地址； 2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3) 采用一定的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 查找并显示给定用户名的记录。 【进一步完成内容】 1)系统功能的完善； 2)设计不同的散列函数，比较冲突率； 3) 在散列函数确定的前提下， 尝试各种不同类型处理冲突的方法，考察平均查找长度 的变化。 9. 停车场管

32、理 【问题描述】 设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车 场内按车辆到达时间的先后顺序， 依次由北向南排列 (大门在最南端， 最先到达的第一辆车 停放在车场的最北端) ，若车场内已停满 n 辆汽车， 则后来的汽车只能在门外的便道上等待， 一旦有车开走， 则排在便道上的第一辆车即可开入； 当停车场内某辆车要离开时， 在它之后 进入的车辆必须先退出车场为它让路， 待该辆车开出大门外， 其他车辆再按原次序进入车场， 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。 试为停车场编制 按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车

33、场， 以队列模拟车场外的便道， 按照从终端读入的输入数据序列进行模拟管理。 每一组输入数据包括三个数据项：汽车 “到达”或“离去 ”信息、汽车牌照号码以及到达或离去 的时刻。 对每一组输入数据进行操作后的输出信息为： 若是车辆到达， 则输出汽车在停车场 内或便道上的停车位置； 若是车辆离去， 则输出汽车在停车场内停留的时间和应交纳的费用 (在便道上停留的时间不收费) 。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设 n=2，输入数据为：(A,5),( A,2,10),( D ,1,15),( A,3,20),( A,4,25), (A ,5,30),( D ,2,35),( D ,4,40),( E,0,0)。其中：A 表示到达(Arrival ) ; D 表示 (Departure ); E表示输入结束(End )。 【实现提示】 需另设一个栈， 临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结 构实现。