计算机技术基础作业答案.ppt

基本概念解释 算法：是指解题方案的准确而完整的描述。算法的时间复杂性：是指执行算法所需要的计算工作量（算法的时间耗费）。填空:(1)算法的基本特征为：能行性、确定性、有穷性、算法必须拥有足够的情报。(2)算法的常用描述方法有：自然语言表示、流程图表示、N-S图表示、伪代码表示、程序语言表示(3)算法优劣的评价标准为：正确性、可读性、健壮性、高效性、简洁性。1第第2章章 习题习题（课本（课本106页）页）作业作业：2.2 顺序表的逆转算法顺序表的逆转算法2.5 队列中有多少元素？队列中有多少元素？思考题思考题：2.8 栈栈S的容量至少为多少？的容量至少为多少？22.2 顺序表的逆转算法顺序表的逆转算法void invsl(ET a,int n)int k;ET t;for(k=0;kn/2;k+)t=ak;ak=an-1-k;an-1-k=t;return;3其他算法：其他算法：1void invsl_1(ET a,int n)int k;ET t;for(k=0;kn-1-k;k+)/减法次数多减法次数多 t=ak;ak=an-1-k;an-1-k=t;return;4其他算法：其他算法：2void invsl_2(ET a,int n)int k,j;ET t;for(k=0,j=n-1;kj;k+,j-)/减法次数多减法次数多 t=ak;ak=aj;aj=t;return;5其他算法：其他算法：3void invsl_3(ET a,int n)int k,j;ET t;for(k=0;kfront，则队列中元素个数为，则队列中元素个数为rearfront；如果如果rearnext;p-next=NULL;WHILE(qNULL)DO r=q-next;q-next=p;p=q;q=r;*HEAD=p;RETURN;15162.21 2.21 已知二叉树的前序序列和中已知二叉树的前序序列和中序序列，求后序序列。序序列，求后序序列。n 前序序列的第一个结点前序序列的第一个结点D D为二叉树的根结点为二叉树的根结点n 中序序列中，根结点中序序列中，根结点D D前面的子序列前面的子序列ABCABC一定在左子一定在左子树中，后面的子序列树中，后面的子序列EFGEFG一定在右子树中一定在右子树中n 每个子序列也符合以上两条每个子序列也符合以上两条后续遍历：后续遍历：ACBEGFDACBEGFD173.1题：题：n依次输入以下元素序列：依次输入以下元素序列：56，78，34，45，85，45，36，91，84，78n构造一棵二叉排序树构造一棵二叉排序树n在树中查找在树中查找55，需要比较，需要比较多少次？多少次？18构造构造二叉排序树二叉排序树 依次读入依次读入给定序列给定序列中的每一个中的每一个元素元素：(1)(1)若若当当前前的的二二叉叉排排序序树树为为空空，则则读读入的元素为入的元素为根结点根结点；(2)(2)若若读读入入的的元元素素值值小小于于根根结结点点值值，则将元素则将元素插入到插入到左子树左子树中；中；(3)(3)若若读读入入的的元元素素值值不不小小于于根根结结点点值值，则将元素则将元素插入到插入到右子树右子树中。中。无无论论是是插插入入到到左左子子树树还还是是右右子子树树，同样按照上述方法处理。同样按照上述方法处理。19203.6题：题：213.10 Hash表技术的目标和表技术的目标和 提高查找效率的方法？提高查找效率的方法？n目标目标：提高查找效率提高查找效率n提高查找效率的提高查找效率的方法方法：n一方面一方面要使要使Hash码的均匀码的均匀性比较好性比较好n另一方面另一方面要使要使Hash码的计码的计算比较简单算比较简单22232425262728