数据结构课后习题部分参考答案第一章一、选择题1C 2C 3A 4D 5B二、判断题1 2 3 4 5三、简答题1 常见逻辑结构：集合结构，数据元素之间的关系仅仅是属于同一个集合。线性结构，除第一个元素只有一个直接后继、最后一个元素只有一个直接前驱，其余元素有且只有唯一一个直接前驱、有且只有唯一一个直接后继，数据元素之间存在一对一的关系。树形结构，树中只有唯一一个根元素，除根元素之外，其余元素只有一个直接前驱，但可以有多个直接后继元素，数据元素之间存在一对多的关系。图形结构，元素之间关系任意，数据元素之间存在多对多的关系。常用的存储结构：顺序存储，把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。通常用数组实现。链式存储，对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附加的指针字段来表示，由此得到的存储表示称为链式存储结构。通常用指针来实现。除上述两种方法外，有时为了查找方便还采用索引存储方法和散列存储方法。索引存储：在存 储 结 点 信 息 的 同 时 ， 还 建 立 附 加 的 索 引 表 来 标 识 结 点 的 地 址 。散列存储：根据元素的关键码确定元素存储位置的存储方式。2 算法与程序的区别：程序不一定满足有穷性(如操作系统)；程序中的指令必须是机器可执行的，算法中的指令则无此限制；算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);数据结构+算法=程序。3例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录就是一个结点，对于整个表来说，只有一个开始结点和一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。这几个关系就确定了这个表的逻辑结构线形结构。那么我们怎样把这个表中的数据存储到里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录（顺序存储）还是随机存放各结点数据再用指针进行链接（链式存储）呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。4例如栈和队列，两个数据结构的逻辑结构和存储方式完全相同，只是对于运算（如插入、删除）的定义不同，两个结构具有显著不同的特性。5语句频度（1）n-1 （2）1 （3）n(n+1)/2 （4）n/2-1 （5）100 6时间复杂度（1）O(log 3n) （2）O(n 2) （3）O(n 2)7 算法思想：P (x，n)=(a nx+an-1)x+an-2)x+a1)x+a0语句：y=0 ;for (i=n;i=0;i-)y=y*x+ ai ; 函数：void p( )float x,y;int n,i,a;scanf(%f,&x);scanf(%d,&n);y=0;for (i=n;i=0;i-)scanf(%d,&a);y=y*x+a; printf(x=%4.2f,y=%6.4f,x,y);第二章一、选择题1A 2A 3D 4C 5D6B 7C 8B 9A 10D11B 12D二、判断题1 2 3 4 5 6 7 8 9 10 11 12三、算法设计题1第一种方法（从后往前比较）：因已知顺序表 L 是递增有序表，所以只要从顺序表终端结点（设为 i 位置元素）开始向前寻找到第一个小于或等于 x 的元素位置 i 后，插入该位置后面即可。在寻找过程中，由于大于 x 的元素都应放在 x 之后，所以可边寻找，边后移元素，当找到第一个小于或等于 x 的元素位置 i 时，插入 x 的位置 i+1 也空出来了。算法如下：void InsertIncreaseList1(seqlist *L,datatype x)int i;if (L-elemnum=maxsize) printf(overflow); / L-elemnum 中存放当前顺序表中的元素个数for (i=L-elemnum-1;i=0 & L-dataix;i-) L-datai+1=L-datai; /从后往前比较并移动元素L-datai+1=x; L-elemnum+;第二种方法（从前往后比较）：void InsertIncreaseList2(seqlist *L,datatype x)int i,j;if (L-elemnum=maxsize) printf(overflow);i=0;while(ielemnum-1)&(L-dataielemnum-1;j=i;j-) L-dataj+1=L-dataj; /腾位置L-datai=x; /插入L-elemnum+;2（思路同算法 2-16）6（ 同 1类似，最好也做一下。1 是顺序存储，6 是链式存储。做完同 1比较一下）7（看算法 2-17,尾插实现）第三章一、选择题1C 2B 3D 4B 5B6C 7B 8D 9C 10C二、判断题1 2 3 4 5 三、简答题1循环队列的优点是：它可以克服顺序队列的假上溢 现象，能够使存储队列的向量空间得到充分的利用。 判别循环队列的空 或满通常有两种方法：（1）另设一个变量 num 记录当前队列中的元素个数 ,当 num=0 时队空， num=maxsize时队满。（2）少用一个存储单元(即少存一个元素 ), 队空条件为 front = rear，队满条件为(rear + 1) % maxsize = front 。2栈的特点是先进后出，队列的特点是先进先出。先进后出用栈；先进先出用队列。3一个直接调用自己或通过一系列调用间接调用自己的过程称为递归。递归程序结构清晰，可读性强，而且容易用数学归纳法来证明程序的正确性。递归程序运行效率低，不论是耗费的计算时间还是占用的存储空间都比非递归程序要多。41234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321（十四种可能）四、算法设计题1思想：将一半字符入栈) 算法为：/以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的栈空间最多为 100 个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack; int IsHuiwen( char *t)/判断 t 字符向量是否为回文，若是，返回 1，否则返回 0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量长度for ( i=0; i此树的 WPL 并非最小.那么此树就不是哈夫曼树.=假设错误.=结点数大于 1 的哈夫曼树不存在度为 1 的结点7.n0=n2+1,n=n0+n1+n2= n0+0+ n0-1=2n0-18. 用数学归纳法证明。结点数 n=1 时，成立；假定 nlchild);nodenum1(root-rchild);第二种方法（不用全局变量）：求结点数的递归定义为：若为空树，结点数为 0若只有根结点，则结点数为 1；否则，结点数为根结点的左子树结点数+右子树结点数+1int nodenum2(BiTree root) if(root=NULL) return 0;else return (1+nodenum2(root-lchild)+nodenum2(root-rchild);第六章一、选择题1B 3. B 4. C 5.(1) B (2) D 7. B 10. B二、判断题1 2 3 4 7 9. 11 12三、简答题1.(1) 每个顶点入度和出度：ID(v1)=2 OD(v1)=1ID(v2)=2 OD(v2)=2ID(v3)=1 OD(v3)=3ID(v4)=3 OD(v4)=0ID(v5)=2 OD(v5)=3ID(v6)=1 OD(v6)=2(2) 邻接矩阵：0 0 0 1 0 01 0 1 0 0 00 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0(3) 邻接表：1234 562.(1)0 1 1 0 0 0 01 0 0 1 0 0 01 0 0 1 0 0 0 0 1 1 0 1 1 00 0 0 1 0 0 1 0 0 0 1 0 0 10 0 0 0 1 1 0(2)V1V2V3V4V5V6V7(4)v1,v2,v4,v3,v5,v7,v6(5)v1,v2,v3,v4,v5,v6,v73.用邻接矩阵表示图时，矩阵元素的个数与顶点个数有关（矩阵元素的个数是顶点个数的平方） ，与边的条数无关（矩阵中非零元素的个数与边的条数有关） 。四、算法设计题4 1 1 1 3 1 4 1 5 1 6 1 1 1 2 1 4 1 2 1 5 1 3 1 2 1 2 1 4 1 1 1 4 11 1 3 1 5 1 6 1 4 1 7 1 4 1 7 1 5 1 6 1 8（1）int PATHDFS(ALGraph *G，int i,int j) /以邻接表为存储结构，判断 vi 和 vj 之间是否有路径，若有返回 1，否则返回 0EdgeNode *p；visitedi=TRUE； /标记 vi 已访问p=G-adjlisti.firstedge； /取 vi 边表的头指针while(p)/依次搜索 vi 的邻接点 vk，这里 k=p-adjvexif （!visitedp-adjvex)/若 vk 尚未被访问if (p-adjvex=j)return 1;else ruturn PATHDFS(g，p-adjvex,j);/则以 Vk 为出发点向纵深搜索p=p-next； /找 vi 的下一邻接点return 0;/PATHDFS（2）int BFS(ALGraph *G，int i,int j)/以邻接表为存储结构，判断 vi 和 vj 之间是否有路径，若有返回 1，否则返回 0int i；CirQueue Q； /须将队列定义中 DataType 改为 intEdgeNode *p