数据结构各篇课后作业.doc

数据结构各章课后作业第一章 绪论课后作业1. 简述线性结构与非线性结构的不同点。2分析下面各程序段的时间复杂度（每小题5分，共20分）（2）s=0; for（i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;答：O（n2）（1） for (i=0; in; i+)for (j=0; jm; j+)Aij=0;(4)i=1; while(i=n) i=i*3;(3) x=0;for(i=1; in; i+) for (j=1; j0)，共有 n+1 _个空指针域；采用三叉链表存储，共有 n+2 个空指针域。（3）由3个结点所构成的二叉树有 5 种形态。2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。.层序序列为ABCDEFGHIJ可得出根结点为A,由中序序列为DBGEHJACIF可得如下A/ BDGEHJ CIF2.层序序列为ABCDEFGHIJ中可知BC为A的左右孩子.A/ B C3.层序序列为ABCDEFGHIJ再合1可知DEF在第三层.又由中序序列为DBGEHJACIF可知D为B的左孩子,E为B的右孩子.G为E的 左孩子.又因为在中序中C先于F,可知F为C的右孩子.A/ B C/ D E F/G4.由中序可知HJ在E的右子树上,由层序GHI可知H和I均左第四层.而由中序IF中I先于F,则I为F左孩子A/ B C/ D E F/ /G H I5.由中序HJA可知,J为H的右孩子.A/ B C/ D E F/ /G H IJ3、编写递归算法，计算二叉树中叶子结点的数目。#include #includestruct nodechar info;struct node *llink, *rlink;typedef struct node NODE;NODE *create()/构造二叉树char x;NODE *p;scanf(%c, &x);printf(%c, x);/打印出已输入的二叉树if(x!=.)p=(NODE *)malloc(sizeof(NODE);p-info=x;p-llink=create();p-rlink=create();elsep=NULL;return p;int run(NODE *t)static int count=0;if(t)run(t-llink);/递归遍历左子树，直到叶子处run(t-rlink);/递归遍历右子树，直到叶子处if(t-llink =NULL & t-rlink = NULL) count+;return count;main() NODE *T;int left_number;printf(请输入一棵树:n );T=create();printf(n);if(!T)printf(This is a empty binary tree.);elseleft_number=run(T);printf(n这棵树共有%d个子叶. n, left_number);printf(n);第七章 图课后作业1、填空题。（1） 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先搜索遍历 、 广度优先搜索遍历 等方法。（2） 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。（3）如果n个顶点的图是一个环，则它有 n 棵生成树。（4） 图的逆邻接表存储结构只适用于 有向图 图。（5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。（6）拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。2、求解下图的最小生成树，并计算出它的权值。第九章 查找课后作业1、填空题。（1）具有11个元素的有序表进行折半查找，则平均查找长度为 。（2）在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。（3）在分块查找方法中，首先查找 ，然后再查找相应的 。（4）在散列函数H(key)=key%m中，m应取 。2、设散列表长为7，记录关键字组为：15,14,28,26,56,23，散列函数：H(key)=key MOD 7，冲突处理采用线性探测法，将它们填入表中。第十章 内部排序课后作业1、填空题。（1）大多数排序算法都有两个基本的操作： 和 。（2）对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 。若对其进行快速排序，在最坏的情况下所需要的时间是 。（3）对于n个记录的集合进行归并排序，所需要的平均时间是 ，所需要的附加空间是