数据结构---C语言描述-(耿国华)-高等教育出版社出版-课后习题答案

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

2、：L、J、A、G 或 J、A、G(3)D(4)D(5)C (6)A、C2、头指针：指向整个链表首地址的指针，标示着整个单链表的3、开始。头结点：为了操作方便，可以在单链表的第一个结点之前附 设一个结点，该结点的数据域可以存储一些关于线性表长度的附 加信息，也可以什么都不存。首元素结点：线性表中的第一个结点成为首元素结点。4、算法如下：int Linser(SeqList *L, int X) int i二0, k;if(L-last二MAXSIZE-1) printf (“表已满无法插入”)；return(0);while(i 1as t&L- e1emilast;k=I;k-) L-elem

3、k+1=L-elemk;L-elemi=X;L-last+;return(l);5、算法如下:#define OK 1#define ERROR 0Int LDel (Seqlist *L,int i, int k) int j;if(i(L-last+2) printf (u输入的i, k值不合法”); return ERROR;if(i+k)=(L-last+2) L-Masti2;ruturn OK;elsefor (j=i+k-l;jlast;j+) elemj-k=elemj;L-last二L-last-k;return OK;6、算法如下:#define OK 1#define E

4、RROR 0Int Delet(LInkList L,int mink, int maxk) Node *p, *q;P 二L;wh订e (p-next!=NULL) p=p-next;if (minknext一dataiinink) | | (p-da 1；8二111且乂1nextdatanext;while (q-data/maxk) p-next二q-next;free(q);q二p-next;return OK;9、算法如下：int Dele (Node *S) Node *p;P=snext;If (p= =s)printf(“只有一个结点，不删除”)；return 0;elseif

5、 (p-next二 二s)snext二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二StacksizeT时，栈为满。在带头结点链栈中，栈顶指针top-next二NULL,则代表栈空；只要系统有可用空间，链栈就不会出现溢出,5、 #include ttinclude stdio. h void main()char ch, temp;SeqStack s;In

6、itStack(&s); scanf(%c, &ch);whi.le (ch!二&ch!二&)Push (&s, ch); scanf(%c, &ch);while(ch!二 &!IsEmpty(&s) Pop (&s, &temp); scanf(%c, &ch); if(ch!二temp)break;if (!IsEmpty(&s)printf (no!n);elsescanf(%c, &ch);if (ch二二) printf (yes! n); else printf(no!n);12、(1)功能：将栈中元素倒置。(2) 功能：删除栈中的e元素。(3) 功能：将队列中的元素倒置。第四章

7、习题答案1、StrLength(s)操作结果为 14； SubString(subl, s, 1, 7)操作结 果为 subl二，I AM ASubString (sub2, s, 7, 1)操作结果为 sub2二，9 ；Strindex(s,4)操作结果为5；StrReplace(s,STUDENT, q)操作结果为I AM A WORKER9；StrCat (StrCat (subl, t), StrCat (sub2, q)操作结果为，IAM A GOOD WORKER； 2、int StrReplace(SString S,Sstring T, SString V) int i=l;/

8、从串S的第一个字符起查找串Tif (StrEmpty (T)/T 是空串return ERROR;doi二Index (S, T, i);/结果i为从上一个i之后4、找到的子串T的位置if(i) 串S中存在串TStrDelete(S, i, StrLength(T);/删除该串T的位置插入串Vi+=StrLength(V); 在插入的串V后面继续查找串T while(i); return OK;第五章习题答案1、 数组A共占用48*6=288个字节；(2) 数组A的最后一个元素的地址为1282；(3) 按行存储时 loc (A36) =1000+ (3-1) *8+6-1*6二 1126(4)

9、 按列存储时 loc (A36) =1000+ (6-1) *6+3-1*6=11929、(1) (a, b) (2) (c, d) (3) (b) (4) b (5) (d)10、D第六章习题答案1、三个结点的树的形态有两个；三个结点的二叉树的不同形态 有5个。2、略3、证明：分支数=ni+2n2+.+knk(1)n= no+ni+rik(2)分支数+1(3)将(1) (2)代入(3)得 n0= n2+2n3+3n4+.+ (k-1) nk+l4、注：C结点作为D的右孩子（画图的时候忘记了，不好意思）5、n0=50, n2=n0-l=49,所以至少有99个结点。6、（1）前序和后序相同：只有

10、一个结点的二叉树（2）中序和后序相同：只有左子树的二叉树（3）前序和中序相同：只有右子树的二叉树7、证明:Vn个结点的K叉树共有nk个链域，分支数为1 （即 非空域）。空域=nk- (nl) =nk-n+18、对应的树如下:一 1、H 丁、B /丨 u 工/ P9、（答案不唯一）哈夫曼树如下图所示:八 II o / 7/ / y 51 回哈夫曼编码如下：频率编码0. 0700100. 19100. 02000000. 0600010. 32010. 03000010.21110. 10001111、对应的二叉树如下:12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。typedef in

11、t ElemType;void Ancestor(ElemType A, int n, int i, int j)while (i!=j)if(ij) i=i/2;else j二j/2;printfC所查结点的最近公共祖先的下标是d,值 是，i,Ai);15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。void Del_Sub(BiTree T) if(T-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free (T);void Del Sub x(BiTree T, int x

12、) if (T-data=x) Del_Sub(T);elseif (Tlchild) 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);BiTree p, Q50;int fro nt二 1, rear 二 1, 1 且 st=l;int temp二0, maxw=0: Q rear=bt;while(fron且st)p二Qfront+; temp+;辻(p-1chi1d!二NULL) Q+rear=p-lchild; if (

13、p-rchild!=NULL) Q+rear=p-rchild;last二rear;if(tempmaxw) maxw=temp; temp二0;return (maxw); 第七章1、(1)习题答案顶点1的入度为3, 顶点2的入度为2, 顶点3的入度为1, 顶点4的入度为1, 顶点5的入度为2, 顶点6的入度为2, （2）邻接矩阵如下：出度为0；出度为2；出度为2；出度为3；出度为1;出度为3；000000100100010001001011100000110010（3）邻接表H4JJ11S0 SSI(4)逆邻接表200? )2 172、答案不唯一(2) 深度优先遍历该图所得顶点序列为：1,

14、 2, 3, 4,边的序列为：(1, 2) (2, 3) (3, 5) (5, 6)(3) 广度优先遍历该图所得顶点序列为：1, 5, 6, 3,边的序列为：(1, 5) (1, 6) (1,5, 64) (4,2, 43) (1,2) (5, 4) 3、(1) 每个事件的最早发生时间：ve (0)=0, ve (1) =5, ve (2) =6, ve (3) =12, ve (4) =15, ve(5)=16,ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23 每个事件的最晚发生时间：vl(9)=23, vl (8)=21, vl (7)=19, vl(6)=19

15、, vl (5)=16, vl(4)=15,vl (3)=12, vl(2)=6, vl(l)=9,e(0, 1)=0,e(0, 2)=0,e(l,3)=5,e(2, 3)=6,e (2, 4) =6,e(3, 4)=12,e (3, 5)=12,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每个活动的最迟开始时间：1(0, 1)=4,1(0, 2)=0,1(1, 3)=9,1(2, 3)=6,1(2, 4)=12,1(3, 4)=12,1(3, 5)=12,1(4, 5)=15,1(

16、3, 6)二 15,1(5, 8)=16,1(4, 7)=15,1(7, 8)=19,1(6, 9)=19,1(8, 9)=21vl(O)二 02最短路经为1,5最短路经为1,4最短路经为1,6最短路经为1,3,3,3,3,2；长度为195；长度为252, 4；长度为292, 4, 6；长度为441-1-)1-1-(2) 每个活动的最早开始时间：13、A(7)B(3)C(2)D(11)E(8)14、略15、略第八章查找1、画出对长度为10的有序表进行折半查找的判定树，并求其等 概率时查找成功的平均查找长度。解：ASL= (1+2*2+4*3+3*4)/102. 95、解：(1)插入完成后的二叉

17、排序树如下:ASL二(1+2*2+3*3+3*4+2*5+1*6)/12二3.5? ? ? ?(2) ASL二(1+2*2+3*4+4*5)=37/12(3)H (22) = (22*3) %11=0H (41) = (41*3) %11=2H (53) = (53*3) %11=5H (46) = (46*3) %11=6H (30) = (30*3) %11=2 与(41)冲突H1(3O) = (2+1)%11=3H(13) = (13*3)%11=6 与46冲突H1(13) = (6+1)%11=7H(O1) = (O1*3)%11=3 与30冲突 H1(O1) = (3+1)%11=4

18、H(67)二(67*3)%11 二3 与30冲突 H1(67) = (3+1)%11=4 与01 冲突 H2 (67) = (3+2) %11=5 与53冲突 H3 (67) = (3+3)%11=6 与46冲突 H4 (67) = (3+4)%11=7 与 13冲突 H5 (67) = (3+5) %11=8ASLsucc=(1*4+2*3+6)/8=2ASLunsucc- (2+8+7+6+5+4+3+2)/8二37/8 第九章排序1、以关键字序列(503, 087, 512, 061, 908, 170, 897, 275, 653, 426)为例，手工执行以下排序算法，写出每一趟派结束

19、时 的关键字状态。(1) 直接插入排序(2)希尔排序(增量序列为5, 3, 1)快速排序(4)堆排序(5)归并排序解：(1)略(2) 增量为5的排序结果：170, 087, 275,512, 653, 908增量为3的排序结果:061, 087, 275,512, 653, 908增量为1的排序结果：061, 087, 170,653, 897, 908(3) 一次划分后：426 087 275 061 170503897 908 653 512 分别进行：170 087 275 061 426 503 512 653 897 908061 087 170 275 426 503 512 65

20、3 897 908 061 087 170 275 426 503 512 653 897 908(3)IIII061,426,503,897,170,426,503,897,275,426,503,512,(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 507 15 12 27 28 40 507 12 15 27 28 40 5016、(1) A3

21、Bl C4 D2 E7(2) C(3) C17、对，错，对数据结构课程设计指导书一、设计内容1飞机订票系统邙艮1人完成）【问题描述】设计一个飞机订票系统，可以模拟处理飞机订票过程中的各种操 作。【基本要求】 通过此系统可以实现如下功能:1）录入可以录入航班情况（数据可以存储在一个数据文件中，数据 结构、具体数据自定）。2）查询可以查询某个航线的情况（如，输入航班号，查询起降时间, 起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况。3）订票（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票,可以提供相关可选择航班。4）退票可

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

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

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

25、时乘坐哪一趟列 车到何地。测试数据：参考教科书7. 6节图7. 33的全国交通图，自行设计列车时刻表。【实现提示】UJUJ1) 对全国城市交通图和列车时刻表进行编辑，应该提供文件形 式输入和键盘输入两种方式。列车时刻表则需根据交通图给出各 个路段的详细信息，例如：基于教科书7. 6节图733的交通图， 对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州 至上海各段的出发时间、到达时间及票价等信息。if2) 以邻接表作交通图的存储结构，表示边的结构内除含有邻接 点的信息外，还应包括交通工具、路程中耗费的时间和花费以及 出发和到达的时间等多种属性。5哈夫曼编码/译码器邙艮1人完成)【问题描述

26、】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理 以下项目，直到选择退出为止。【基本要求】1) 将权值数据存放在数据文件(文件名为data, txt,位于 执行程序的当前目录中)2) 分别釆用动态和静态存储结构in3) 初始化：键盘输入字符集大小n、n个字符和n个权值, 建立哈夫曼树；4) 编码：利用建好的哈夫曼树生成哈夫曼编码；5) 输出编码；6) 设字符集及频度如下表：字符空格 ABCDEFGHIJKLM频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 NOPQRSTUVWXYZ频度 57 63 15 1 48 51 80 23 8 1

27、8 1 16 1【进一步完成内容】1) 译码功能；2) 显示哈夫曼树；3) 界面设计的优化。6. 走迷宫游戏【问题描述】以一个mxn的长方阵表示迷宫,o和1分别表示迷宫中的通路和障 覚二警计一个程序，对任意设定的迷宫，求出_条从入口到出口 的通路，或得出没有通路的结论。【基本要求】1首先用二维数组存储迷宫数据，迷宫数据由用户输入。2. 一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i, j, d）形式输出, 其中：（i, j）指示迷宫中的一个坐标，d表示走到下一坐标的 3可以用多种方法实现，但至少用两种方法，用三种以上可加 分。方向（东、南、西、北四

28、个方向所用代表数字,自行定义）。【实现提示】1. 计算机解迷宫问题通常用的是“穷举求解,方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则 沿着原路退回，换一个方向继续探索，直至出口位置，求得一条 通路。假如所有可能的通路都探索到而未能到达出口，则所设定 的迷宫没有通路。迷宫的入口点的下标为（1, 1）,出口点的下标为（m, n）0为处 理方便起见,可在迷宫的四周加一圈障碍。对于迷宫的任一位置, 均可约定有东、南、西、北四个方向可通。2. 有一种简单走出迷宫的方法，把手放在右边的墙上开始前进, 始终不要把手从墙上移开。如果迷宫向右拐,你也顺着墙向右拐。 只要不把手从墙上移

29、开，最终就会到达迷宫的出口。当然这样得 到的路径可能不是一个最短的路径，但它可以最终得到结果，换 句话说，这种方法走不出迷宫的风险是最小的。7. 作业评分系统【问题描述】 设计一个可以给小学生出题并且可以给出分数的系统软件。【基本要求】 利用栈求表达式的值，可供小学生作业，并能给出分数。1）建立试题库文件，随机产生n个题目；2）题目涉及加减乘除，带括弧的混合运算；3）随时可以退出；4）给出作业分数。【进一步完成内容】1）保留历史分数，能回顾历史，给出与历史分数比较后的评价。2）界面设计的优化。8. 散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1）设每个记录有下列数

30、据项：电话号码、用户名、地址；2）从键盘输入各记录,分别以电话号码和用户名为关键字建立散 列表;3）采用一定的方法解决冲突；4）查找并显示给定电话号码的记录;5）查找并显示给定用户名的记录。【进一步完成内容】1）系统功能的穿善2）设计不同的散列总数，比较冲突率；3）在散列函数确定的前提下，尝试各种不同类型处理冲突 的方法，考察平均查找长度的变化。9. 停车场管理【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可 供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次 由北向南排列（大门在最南端，最先到达的第一辆车停放在车场 的最北端），若车场内已停满n辆汽车，则后来的汽车只

31、能在门 外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可 开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先 退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序 进入车场，每辆停放在车场的车在它离开停车场时必须按它停留 的时间长短交纳费用O试为停车场编制按上述要求进行管理的模 拟程序。【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的 输入数据序列进行模拟管理。每一组输入数据包括三个数据项: 汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时 刻o对每一组输入数据进行操作后的输出信息为:若是车辆到达, 则输出汽车在停车场内或便道上的停车位置；若是车辆离去，贝g输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留 的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【测试数据】 设 n=2输 入 数 据 为：(4A 1, 5),(曲,2, 10), CD 1, 15),(沖,3, 20), (W, 4, 25),(A, 5, 30), CD2,35), (,4,40), (, 0, 0)。其中:缎表示到达(Arrival)； 表示(Departure)； 6E9表示输入结束(End)。 【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出 来的汽车，也用顺序存储结